OJ Board

Posted: **Sat Feb 19, 2005 10:50 am**

shamim wrote:
ibrahim wrote: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?

Posted: **Sun Feb 20, 2005 8:45 pm**

I also got 39996000100000000..

Posted: **Sun Feb 20, 2005 9:26 pm**

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.

Posted: **Mon Apr 25, 2005 9:42 pm**

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.

Posted: **Sat Jun 10, 2006 4:26 am**

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;    
}

Posted: **Sat Jun 10, 2006 5:18 am**

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.

Posted: **Sat Jun 10, 2006 5:24 am**

Thanks a lot .It's already AC.

Posted: **Fri Apr 27, 2007 6:35 pm**

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

Posted: **Fri Apr 27, 2007 9:39 pm**

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

Posted: **Sat Apr 28, 2007 5:58 pm**

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.

Posted: **Tue Jun 05, 2007 4:36 pm**

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; 
}

Posted: **Tue Jun 05, 2007 6:14 pm**

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.

Posted: **Wed Dec 08, 2010 2:08 pm**

#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.......

Posted: **Sun May 08, 2011 7:02 pm**

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

OJ Board

10790 - How Many Points of Intersection?

Sorry but what here wrong?

10790 WA

Thank u

wrong thread

Re: 10790 - How Many Points of Intersection?

Re: 10790 - How Many Points of Intersection?