Dwumiany SPOJ - błędna odpowiedź

Question

Witam. Rozwiązuje zadanie http://pl.spoj.com/problems/BINOMS/ lecz niektóre przypadki przekraczają mi długość zmiennych i robi się bałagan. Np. w przypadku 500 nad 400 już się wszystko sypie, bo program licząc 100! lub mnożąc liczby w liczniku (w tym wypadku 401*402*...*500) przekracza double i zamiast zer na końcu https://pl.wikisource.org/wiki/Silnia po przekroczeniu są różne cyfry. Nie mam zielonego pojęcia jak uprościć jeszcze to działanie. Chciałbym jeszcze wspomnieć, że zadanie dotyczy tylko przypadków, gdy wynik jest poniżej miliarda.

#include <iostream>
#include <math.h>
#include <iomanip>

using namespace std;

int n,k,t,roznica,j;
double licznik,wynik;


double silnia(int s)
{
    if(s==0) return 1;
    else return s*silnia(s-1);
}




int main()
{
    cin>>t;
    for(int i=1; i<=t; i++)
    {

        cin>>n>>k;
        if ( (k == 0) || (n == k) )
        {
            cout << "1" << endl;
        }else

        if((n-k)>(n/2)) 
        {
            k=n-k;	// zmiana, by była mniejsza silnia w mianowniku

        }
        if ( (k != 0) && (n != k) )
        {

        roznica= n-k;



        cout<<setprecision(1000000);

        licznik= k+1; 
        j=2;
        for(int i=2; i<=roznica; i++) //mnożenie tego co zostało w liczniku po skróceniu tych samych silni w liczniku i mianowniku
        {

            licznik*= k+j;
            j++;


        }

        wynik= ( licznik / silnia(roznica) ); 

        cout<<wynik<<endl;

        }

    }

    return 0;
}

 

Answer 1

Rozpisz to sobie na kartce i się zastanów w jaki sposób możesz skrócić ułamek.

Comments

Czyli tablica dwuwymierna [][], dobrze rozumiem?

---

Wystarczą dwie tablice równej długości (A w zasadzie trzy: liczby pierwsze, rozkład licznika, rozkład mianownika)

---

Witam ponownie. Męczę się z tym zadaniem, a należy do łatwych. (może to jednak nie dla mnie..) Wstawiam moje wypociny. Program liczy dobrze, lecz tylko pierwsze dane. Drugi wynik jest już błędny, bo zostają pewnie dane w tablicy i nie wiem jak ją oczyścić, żeby z każdym testem tablice dla licznika i mianownika znów były puste. 

#include <iostream>
#include <math.h>
#include <iomanip>

using namespace std;

int r;
int licznik,wynik;

int pierwsze[229]={2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83,
89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197,
199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317,
331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449,
457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593,
599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727,
733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863,
877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997};
int licz[229];
int mian[229];


int i;




int main()
{
 int t=100;
    for(int o=1; o<=t; o++)
    {




        cout<<"Podaj n i k: ";
        int n,k;
        cin>>n>>k;
        if ( (k == 0) || (n == k) )
        {
            cout << "1" << endl;
        }else

        if((n-k)>(n/2))
        {
            k=n-k;  // zmiana, by byla mniejsza silnia w mianowniku

        }
        if ( (k != 0) && (n != k) )
        {
//////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////
        int roznica= n-k;





        

        for(int j=1; j<=roznica; j++) //mno¿enie tego co zosta³o w liczniku po skróceniu tych samych silni w liczniku i mianowniku
        {
            int b=0;
            licznik=k+j;
            i=0;

            while(licznik>=pierwsze[i]) //dopoki licznik(np. 910 jest WIEKSZE od liczby pierwszej od 2.
            {
                if(licznik%pierwsze[i] == 0)
                {
                    licz[i]+=1;
                    licznik=licznik/pierwsze[i];

                    i=0;
                }else i++;


                b++;
            }


            cout<<"________________"<<endl;



        }
        for(int l=0; l<50; l++)
            {
                cout<<licz[l];
            }
                cout<<"__________________________________________________"<<endl;



        ///////////////////////// MIANOWNIK ///////////////////////////////////
        ///////////////////////// MIANOWNIK ///////////////////////////////////
        ///////////////////////// MIANOWNIK ///////////////////////////////////
        ///////////////////////// MIANOWNIK ///////////////////////////////////
        roznica= n-k;

                        r=0;
        for(int j=roznica; j>1; j--) //mnozenie tego co zostalo w liczniku po skróceniu tych samych silni w liczniku i mianowniku
        {
            cout<<"Roznica= "<<roznica<<endl;
            i=0;

            while(roznica>=pierwsze[i]) //dopoki licznik(np. 910 jest WIEKSZE od liczby pierwszej od 2.
            {

                if(roznica%pierwsze[i] == 0)
                {
                    mian[i]+=1;
                    roznica=roznica/pierwsze[i];

                    i=0;
                }else i++;

            }

             r++;   roznica=n-k-r;
            for(int l=0; l<50; l++)
            {
                cout<<mian[l]<<" ";
            }
        cout<<"__________________________________________________"<<endl;
        }











            wynik=1;
        for(int r=0; r<=229; r++)
        {
                if(licz[r] == mian[r])
                {
                    licz[r]=0;
                }else
                if(licz[r]>mian[r])
                {
                    licz[r]-=mian[r];
                }else licz[r]=mian[r]-licz[r];

                if(licz[r]>0)
                {
                    for(int z=1; z<=licz[r]; z++)
                    {
                        wynik *=pierwsze[r];
                    }
                }

        }
        cout<<"WYNIK= "<<wynik<<" =WYNIK"<<endl;

     



        }
    delete [] licz;
    delete [] mian;
    cout<<"licz[0]: "<<licz[0]<<endl;
    }



    return 0;
}

 

---

Przed każdym testem wyzeruj tablice licz i mian:
 

for (int i=0; i<229; i++) {
    licz[i]=mian[i]=0;
}

 

---

Błędna odpowiedź. Pousuwałem oczywiście wszystkie niepotrzebne cout'y, a nawet komentarze. Zrobiłem trochę testów znalezionych w różnych miejscach w temacie na jednym forum i wszystko wydaje się, że gra. Endl przy output jest, więc nie wiem o co chodzi. 

#include <iostream>
#include <math.h>
#include <iomanip>

using namespace std;

int r;
int licznik,wynik;

int pierwsze[229]={2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83,
89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197,
199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317,
331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449,
457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593,
599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727,
733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863,
877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997};
int licz[229];
int mian[229];


int i;





int main()
{
 int t;
 cin>>t;
    for(int o=1; o<=t; o++)
    {





        int n,k;
        cin>>n>>k;
        if ( (k == 0) || (n == k) )
        {
            cout << "1" << endl;
        }else

        if((n-k)>(n/2))
        {
            k=n-k;

        }
        if ( (k != 0) && (n != k) )
        {

    for (int i=0; i<229; i++)
        {
            licz[i]=mian[i]=0;
        }

        int roznica= n-k;







        for(int j=1; j<=roznica; j++)
        {
            int b=0;
            licznik=k+j;
            i=0;

            while(licznik>=pierwsze[i])
            {
                if(licznik%pierwsze[i] == 0)
                {
                    licz[i]+=1;
                    licznik=licznik/pierwsze[i];

                    i=0;
                }else i++;


                b++;
            }






        }

        roznica= n-k;

                        r=0;
        for(int j=roznica; j>1; j--)
        {

            i=0;

            while(roznica>=pierwsze[i])
            {

                if(roznica%pierwsze[i] == 0)
                {
                    mian[i]+=1;
                    roznica=roznica/pierwsze[i];

                    i=0;
                }else i++;

            }

             r++;   roznica=n-k-r;


        }











            wynik=1;
        for(int r=0; r<=229; r++)
        {
                if(licz[r] == mian[r])
                {
                    licz[r]=0;
                }else
                if(licz[r]>mian[r])
                {
                    licz[r]-=mian[r];
                }else licz[r]=mian[r]-licz[r];

                if(licz[r]>0)
                {
                    for(int z=1; z<=licz[r]; z++)
                    {
                        wynik *=pierwsze[r];
                    }
                }

        }
        cout<<wynik<<endl;





        }

    }



    return 0;
}

 

Answer 2

Zaakceptowano... Program dawno działał, tylko na stronie wybierałem język gcc 6.3 zamiast g++ 4.3.2. BARDZO dziękuję za pomoc!!!