10790 - How Many Points of Intersection?

All about problems in Volume 107. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

User avatar
ibrahim
Experienced poster
Posts: 149
Joined: Mon Feb 07, 2005 10:28 pm
Location: Northern University, Bangladesh
Contact:

Post by ibrahim » 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). :o
But after submit using long long i got accept :P . Someone please tell me how it's possible.
I think the output of __int64 and long long will be same. Am I right? :D

Larry
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:

Post by Larry » Sun Feb 20, 2005 8:45 pm

I also got 39996000100000000..

Destination Goa
Experienced poster
Posts: 123
Joined: Thu Feb 10, 2005 4:46 am

Post by Destination Goa » 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.
To be the best you must become the best!

QulinXao
New poster
Posts: 29
Joined: Mon Apr 05, 2004 11:12 am

Sorry but what here wrong?

Post by QulinXao » 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.

thomas1016
New poster
Posts: 19
Joined: Mon May 29, 2006 4:12 pm

10790 WA

Post by thomas1016 » 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;    
}



mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

Post by mf » 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.

thomas1016
New poster
Posts: 19
Joined: Mon May 29, 2006 4:12 pm

Thank u

Post by thomas1016 » Sat Jun 10, 2006 5:24 am

Thanks a lot .It's already AC. :lol: :lol: :lol: :lol: :lol:

User avatar
Sedefcho
A great helper
Posts: 374
Joined: Sun Jan 16, 2005 10:18 pm
Location: Bulgaria

Post by Sedefcho » Fri Apr 27, 2007 6:35 pm

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

User avatar
Rocky
Experienced poster
Posts: 124
Joined: Thu Oct 14, 2004 9:05 am
Contact:

Post by Rocky » 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

User avatar
Sedefcho
A great helper
Posts: 374
Joined: Sun Jan 16, 2005 10:18 pm
Location: Bulgaria

wrong thread

Post by Sedefcho » 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.

chetan
New poster
Posts: 43
Joined: Sun Sep 24, 2006 2:39 pm

Post by chetan » 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; 
} 

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

Post by mf » 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.

mahi_seu.bd
New poster
Posts: 4
Joined: Mon Dec 06, 2010 8:25 pm
Location: Bangladesh
Contact:

Re: 10790 - How Many Points of Intersection?

Post by mahi_seu.bd » 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.......

valkov
New poster
Posts: 20
Joined: Tue Jul 20, 2010 3:11 pm

Re: 10790 - How Many Points of Intersection?

Post by valkov » 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 :)

Post Reply

Return to “Volume 107 (10700-10799)”