10843  Anne's game
Moderator: Board moderators
10843  Anne's game
Is this problem really about counting Connected Labelled Graphs with n vertices and n1 edges?
I had came up with a permutation which (after factoring the numerator and denominator) ended up being wrong.
Is there any clue for this problem?
I had came up with a permutation which (after factoring the numerator and denominator) ended up being wrong.
Is there any clue for this problem?

 Experienced poster
 Posts: 162
 Joined: Thu Jul 13, 2006 7:07 am
 Location: Campus Area. Dhaka.Bangladesh
 Contact:
Re: 10843  Anne's game
why WA.
please give me some critical input output.
my code
advanced thanks
please give me some critical input output.
my code
Code: Select all
#include <cstdio>
int getMod(int a,int b,int c){
int i,n = a;
if(a == 1  a == 2)
return 1;
for(i = 1; i< b; i++){
a *= n;
a %= c;
}
return a%c;
}
int main(){
int b,i,test;
//freopen("in.txt","rt",stdin);
scanf("%d",&test);
for(i = 1;i <= test; i++){
scanf("%d",&b);
printf("Case #%d: %d\n",i,getMod(b,b2,2000000011));
}
return 0;
}
http://www.newton.0fees.net is enough!
Re: 10843  Anne's game
Integer overflow.newton wrote:why WA.
This problem has only 100 inputs which can be easily generated  "(echo 100; seq 1 100)  ./your_program". Have you even tried running your program on them and simply looking at the results? Negative numbers in the output would have surely ringed a bell.please give me some critical input output.
Re: 10843  Anne's game what is the problem??
where is the problem for this code
and what should i do to solve the problem
here is the code:
please help
and what should i do to solve the problem
here is the code:
Code: Select all
#include<stdio.h>
#include<math.h>
int main()
{
long n,num,i,m,p;
scanf("%ld",&num);
for(int it=0;it<num;it++){
scanf("%ld",&n);
p=n;
if(n==1  n==2){printf("1\n");continue;}
m=n2;
for(i=1;i<m;i++){
p=p*n;
p=p%2000000011;
}
printf("%ld\n",p);
}
return 0;
}
i love to wait... wait for better... and better will come...
http://akanoi.webs.com/
http://akanoi.webs.com/

 Learning poster
 Posts: 78
 Joined: Sun Nov 30, 2008 5:00 pm
 Location: IUTOIC, Dhaka, Bangladesh
Re: 10843  Anne's game
Hi Abid,the problem in your code is you are using too straightforward approach. In this problem your program must have the ability to calculate (100^98)%2000000011. It is not possible if you just loop from 1 to 98 and store the result of multiplication in a variable. It will be a overflow.You have to use dynamic programming. I will give you some hint: Power(X,N) can be represented by the following formula:
power(X,N) =
{ 1, if N=0;
{ X*power(X,N1), if N is odd;
{ power(X,N/2)^2, if N is even;
I have use this formula to solve the problem. It is a recursive as you can see. But it will also overflow if you do not combine it with the following idea:
That the ans will be ans%2000000011.
So.....the trick is:
"(X*Y)%M can be written as ((X%M)*(Y%M))%M ". So in the above formula you have to use this idea too if u want to get AC.
Otherwise the program will not work i think.
I hope it helps.
Good luck.
power(X,N) =
{ 1, if N=0;
{ X*power(X,N1), if N is odd;
{ power(X,N/2)^2, if N is even;
I have use this formula to solve the problem. It is a recursive as you can see. But it will also overflow if you do not combine it with the following idea:
That the ans will be ans%2000000011.
So.....the trick is:
"(X*Y)%M can be written as ((X%M)*(Y%M))%M ". So in the above formula you have to use this idea too if u want to get AC.
Otherwise the program will not work i think.
I hope it helps.
Good luck.
Last edited by Articuno on Mon Dec 01, 2008 5:27 pm, edited 2 times in total.
May be tomorrow is a better day............
Re: 10843  Anne's game
What's so impossible in a few hundreds of multiplications and divisions?Articuno wrote:In this problem your program must have the ability to calculate (100^98)%2000000011. It is not possible with traditional looping.
Modern CPUs do billions of those operations in mere seconds.

 Learning poster
 Posts: 78
 Joined: Sun Nov 30, 2008 5:00 pm
 Location: IUTOIC, Dhaka, Bangladesh
Re: 10843  Anne's game
Well mf, thank u for your comments. In my reply to abid_iut, what i meant was :
if you do this type of thing:
If i am right it will cause an overflow. In abid_iut's code, he does the similar thing and thus he is not getting the correct answer as there is an overflow. Yes, i may be wrong as i'm new in programming but in this case,i think u misunderstood me for my poor english.
I was not talking about machine's capability. I was talking about program's capability. You can not just use a loop to multiply 100 for 98 tmies and store it in a variable...it will certainly be a overflow.That's what i meant. Hope u understand and forgive me for my poor english.
Goodluck.
[I will also edit that part of my reply ]
if you do this type of thing:
Code: Select all
ans=1;
for(i=1;i<=98;i++)
{
ans=ans*100;
}
I was not talking about machine's capability. I was talking about program's capability. You can not just use a loop to multiply 100 for 98 tmies and store it in a variable...it will certainly be a overflow.That's what i meant. Hope u understand and forgive me for my poor english.
Goodluck.
[I will also edit that part of my reply ]
May be tomorrow is a better day............
Re: 10843  Anne's game
hi Articuno
thankx for ur help but still it's not giving the correct ans.
for small numbers it is OK but for big numbers.......
is this the way u told me to do or i missed something.
please help if there is any mistake and tell me where i am wrong.
here is the code:
thankx for ur help but still it's not giving the correct ans.
for small numbers it is OK but for big numbers.......
is this the way u told me to do or i missed something.
please help if there is any mistake and tell me where i am wrong.
here is the code:
Code: Select all
#include<stdio.h>
#include<math.h>
int main()
{
long N,X,i,m,p,num,ans;
scanf("%ld",&num);
for(int it=0;it<num;it++){
scanf("%ld",&X);
N=X2;
if(X==1  X==2){printf("1\n");continue;}
for(i=1;i<=N;i++){
if(i%2==0){
ans=pow(X,(N/2))*pow(X,(N/2));
ans=ans%2000000011;
}
else if(i%2!=0){
ans=X*pow(X,N1);
ans=ans%2000000011;
}
}
printf("%ld\n",ans);
}
return 0;
}
i love to wait... wait for better... and better will come...
http://akanoi.webs.com/
http://akanoi.webs.com/