10790 - How Many Points of Intersection?

[ibrahim]

What will be the output for 20000 20000 input.

3997800100000000

Dear shamim , thanks for your output. though i got AC, but my output for 20000 20000 is not same as you.
39996000100000000 (__int64 in VC6).
But after submit using long long i got accept . Someone please tell me how it's possible.
I think the output of __int64 and long long will be same. Am I right?

[Larry]

I also got 39996000100000000..

[Destination Goa]

I would also suggest to calculate result in such way that no temporary value is bigger than result. This way we can be sure that there is no overflow if final result fits into int64.

E.g. for formula a*b/3 (divisibility presumed) it would be good idea to write:
r = a%3==0 ? a/3*b : b/3*a

Otherwise cases like a=0x7FFFFFFFFFFFFFFF, b=3 won't work.

Also make sure that best path checker does not suffer from overflowing itself. In example above we use % operator which does not suffer. But for formula a*b*c/6 one could test a*b, a*c, b*c against divisibility by 6 (after testing a, b, c themselves) which might overflow before applying % operator. Split 6 to 2*3 and reduce by 2 and 3 independently.

[QulinXao]

o:comp;function T(a:longint):longint;begin t:=a*(a-1)div 2;end;
begin n:=0;
repeat
read(a,b);
if(a=0)and(b=0)then break;
o:=t(a); o:=o*T(b);
inc(n);
writeln('Case ',n,': ',o:0:0);
until false;
end.

[thomas1016]

Can u guys tell me why it didn't be C(m,2) * C(n,2) be the answer???

PLS...

Code: Select all


#include <iostream>
using namespace std;
long long int gcd(long long int,long long int);

unsigned long long int c(int,int);
int main(void){
    int a,b,d;
    d=1;
    while(cin>>a>>b){
                     if(a==0 && b==0){
                             break;
                             }
                     cout<<"Case "<<d++<<": "<<c(a,2)*c(b,2)<<endl;
                     
                     }
    //system("pause");
    return 0;
    }

unsigned long long int c(int a,int b){
unsigned long long int k,l,m;
int i;
                 k=1;
                 l=1;
                 if(a-b<b){
                           b=a-b;
                           }
                 for(i=1;i<=b;i++,a--){
                                   k*=a;
                                   l*=i;
                                   m=gcd(k,l);
                                   
                                   l/=m;
                                   k/=m;
                                   }
                 k/=l;
     
    return k;
    }
long long int gcd(long long int a,long long int b){
int tmp;
if(a>=b){tmp=a;
         a=b;
         b=tmp;
         }
 while(b%a!=0){
         b=a%b;
         tmp=a;
         a=b;
         b=tmp;
         }
         return a;   
}




[mf]

C(a,2) * C(b,2) is a correct formula.

But why are you trying to compute C(n,2) in such a complicated way?
C(n,2) is just n*(n-1)/2.

[thomas1016]

Thanks a lot .It's already AC.

[Sedefcho]

Can someone post some more test cases (if possible) ?
10x in advance.

[Rocky]

i think this problem has no critical i/o...some sample is follows...

Code: Select all

2 5
10 2
20 10
9 9
51 51
41 41
64 34
0 0

Case 1: 10
Case 2: 45
Case 3: 8550
Case 4: 1296
Case 5: 1625625
Case 6: 672400
Case 7: 1130976


GOOD LUCK
Rocky

[Sedefcho]

Sorry, I posted in the wrong thread.
I needed test input for problem 11191 yesterday.
But I managed to find my mistake and I have it now ACC.
Thanks anyway.

[chetan]

why WA ???

Code: Select all

# include <iostream>

using namespace std;
int main()
{
    int a,b,c=0;
    while(cin>>a>>b)
    {
        ++c;
        if(a==0 && b==0)    return 0;
        unsigned long long y=((a*(a-1))/2)*((b*(b-1))/2);
        cout<<"Case "<<c<<": "<<y<<'\n';
    }
   
    return 0;
}


[mf]

Your program actually does all its computations with 32-bit integers, and as a result it gets overflows.
Type of expressions in C++ is determined by the operands; so "((a*(a-1))/2)*((b*(b-1))/2)" is a perfectly valid int to the compiler, provided that a and b are int's.

[mahi_seu.bd]

#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
int main()
{
unsigned long a,b,i,j,sum,kes=0,p,k,sum1,sum2;
while(scanf("%lu%lu",&a,&b)==2){
if(a==0 && b==0) break;
sum=0;
k=0;
p=0;
kes++;
k=a-1;
p=b-1;
sum1=k*(k+1)/2;
sum2=p*(p+1)/2;
sum=(sum1*sum2);
printf("Case %lu: %lu\n",kes,sum);

}return 0;

}
I got ac.......

[valkov]

Just got AC on this one.
The problem boils down to bijection of a choose 2 and b choose 2.
Which simplifies as stated by mf to

Code: Select all

(a(a - 1)) / 2 * (b(b - 1)) / 2

or even simpler

Code: Select all

(a*b*(a-1)*(b-1)) / 4

Be careful to use proper data types so input cases such as

Code: Select all

20000 20000


provide the proper results