Page 14 of 19
Posted: Thu Mar 31, 2005 12:50 pm
by jakabjr
I get WA, I could be having the same problem or some wacky test cases...
I tryed long long to hold the numbers, but stil WA.
Here is my code:
Code: Select all
#include <stdio.h>
#include <math.h>
#define size_t long
int getl(size_t b, size_t n){
size_t i=n*n;
int count=2;
while( (i<b)&&(i>0) ) {i=i*n; count++;}
if (i==b) return count;
else return 0;
}
int main(){
double nd;
size_t a, b, n, l, sq, idle, height;
while(scanf("%ld%ld", &a, &b)==2){
if (!a && !b) break;
if (a==1 && b==1) printf("0 1\n");
else if (a == b+1) printf("1 %ld", a+b);
else if (b==1){
l = getl(a, 2);
idle = l; height = 2*a-1;
printf("%ld %ld\n", idle, height);
}
else{
sq = (size_t) sqrt(b);
for (n=2; n<=sq; n++)
if (b%n == 0){
l = getl(b, n);
if (l && (fabs(pow(n+1,l) - a) < 0.0001)){
idle = (b-1)/(n-1);
height = b+(a-b)*(n+1);
printf("%ld %ld\n", idle, height);
break;
}
}
}
}
return 0;
}
I read a, b. a = (n+1)**l and b = n**l, where n is the N in the problem and l is the number or times cats come out of hats.
Using geometric progression sums, I've come to the formulas for idle cats and total height.
the if's are for l=0, l=1 respectively n=1, which were special cases for my algorithm.
It works on sample tests and additional tests I've used, and I'm REALLY puzzeled...
Posted: Thu Mar 31, 2005 2:16 pm
by tan_Yui
Hi, jakabjr.
Try following input.
Code: Select all
2 1
4 1
1024 1
371293 248832
11 10
1 1
0 0
Output should be :
Code: Select all
1 3
2 7
10 2047
22621 1840825
1 21
0 1
And, my AC code uses
double.
Best regards.
Posted: Fri Apr 01, 2005 11:48 pm
by yaro
In this task you have to be careful about the precision errors. Even the 1e-5 precision may not work.. There is a way to solve this task using only integer numbers - just to implement some mathematical operations using ints.
And there is no need to use big num.
Posted: Wed Apr 06, 2005 11:55 am
by jakabjr
this is really embarrasing...
I left out a '\n' at an output case, and adding it gave me AC. numbers fit into long.
Sorry for my clumsiness
107 can you help me
Posted: Thu Apr 07, 2005 3:44 pm
by Luchi
can anybody give me critical inputs to check my program
#include <iostream.h>
#include <math.h>
unsigned long i , j , k , m , n , m1 , n1 , t , a[10003] , b[10003] , min , sum , pas;
void B_NULL()
{
for(i=0;i<10003;i++)
b=0;
}
void prime ()
{unsigned long N , i , j , s ;
N=100000;
s=1;a[0]=2;
for(i=3;i<=N;i+=2)
{
for(j=0;(a[j]*a[j]<i)&&(i%a[j]!=0);j++){}
if(i%a[j]!=0) {a[s]=i;s++;}
}
return;
}
int main()
{
prime();
cin>>m>>n;
while(n||m)
{
m1=m;n1=n;B_NULL();
if(m==1) cout<<0<<' '<<1<<'\n'; else
{
for(i=0;n1!=1;i++)
{t=1;
while((n1>1)&&t)
if(!(n1/a)) t=0; else
if (n1%a) {t=0;} else {n1/=a;b++;}
}
for(i=0;(i<10003)&&!b;i++);
min=b;
for(;i<10003;i++)
if(b) if(min>b) min=b;
t=1;
for(i=1;(i<=min)&&t;i++)
{sum=1;if(!(min%i)){ for(j=0;j<10003;j++) if(b[j]) for(k=0;k<b[j]/i;k++) sum*=a[j];if(pow(sum+1,i)==m) {pas=sum;t=0;}}}
m1=0;
for(j=0;j<i;j++)
{m1+=pow(pas,j)*m;m=m/(pas+1);}
n1=0;
for(j=0;j<i-1;j++)
{n1+=pow(pas,j);}
cout<<n1<<' '<<m1<<'\n';
}
cin>>m>>n;
}
return 0;
}
Posted: Thu Apr 07, 2005 4:16 pm
by jakabjr
Try following input.
2 1
4 1
1024 1
371293 248832
11 10
1 1
0 0
Output should be :
1 3
2 7
10 2047
22621 1840825
1 21
0 1
Also see the topic just below yours, from Apr 06, and find out how to solve without tables[/code]
Tests to 107
Posted: Wed Apr 13, 2005 3:23 pm
by nebel
can somebody give me some test with answers to thу 107th problem ?
thanks in advance
some question on problem 107
Posted: Sun May 29, 2005 5:39 pm
by Grazyna
I am trying to solve 107 using long long and I am getting WA.
should I use double , since the problem clarifies that it has to do with integers?
more over I saw in the forum the sample input 11 10 ,
with the output 1 21.
Is it valid input? As far as for the input pair a b there should be integers n , m such that a=(n+1)^m and b=n^m it looks like invalid to me and anyway I don't understand how it comes this specific output.
Thanks in advance for any help.
Posted: Sun May 29, 2005 9:12 pm
by neno_uci
Yes, that input is valid, that is N = 10, a big cat with 10 cats in it's hat, thus their weights are 11 * 1 / (N + 1) == 1.
I used real type in PASCAL in my AC solution..., best regards,
Yandry.
Posted: Sun May 29, 2005 10:45 pm
by dumb dan
In my AC solution I used long long when the input fit into a long long,
otherwise I used a simple form of biginteger.
Bottom line is, you have to handle those large inputs with something else than a long long.
Posted: Sun May 29, 2005 11:46 pm
by Grazyna
Thanx for reply.
It was stupid from me that I didn't consider the powers in 1 .
I am AC now.
hints for 107. TLE
Posted: Sun Jun 12, 2005 4:24 pm
by Gaolious
I got AC. but..
at first, i got TLE ( 0:10.068 ; CPU )
only i use the log10, pow math functions.
but, when change the my code ( pow -> my function )
i got AC ( 0:05.619 ; CPU )
;; careful floating point and math functions. ;;
follow code is my pow function
Code: Select all
inline unsigned int pow2( unsigned int x, unsigned int y )
{
register unsigned int ret = 1 ;
register unsigned int loop;
for (loop=0 ; loop < y ; loop++)
ret *= x ;
return ret ;
}
Re: hints for 107. TLE
Posted: Sun Jun 12, 2005 7:26 pm
by Zuza
Gaolious wrote:I got AC. but..
but, when change the my code ( pow -> my function )
i got AC ( 0:05.619 ; CPU )
I was just wondering... Try using a pow function that runs in O( lg n ) time, but uses recursion which is sooo slow. What running time will you get ?
Code: Select all
typedef unsigned int uint;
uint power( uint b, uint e )
{
if( e == 0 ) return 1;
if( e == 1 ) return b;
if( e & 1 ) return b * power( b, e - 1 );
uint tmp = power( b, e >> 1 );
return tmp * tmp;
}
Of course e ( exponent ) will never be greater that 32 or so, but i think it will eventually have an impact on the running time ( possibly worse )...
got AC.
Posted: Mon Jun 13, 2005 6:18 am
by Gaolious
got AC when use the your power function.
time is 0:06.000(CPU).
Help 107!!!
Posted: Fri Jun 17, 2005 3:11 pm
by sk
#include<stdio.h>
main(){
unsigned int n,m,i,j,a,b,t,t2,t3;
while(1){
scanf("%u %u",&n,&m);
if(n==0&&m==0)break;
if(n==1)printf("0 1\n");
else if(m==1){
a=b=0;
do{
b+=n;
n>>=1;
a++;
}while(n);
a--;
printf("%u %u\n",a,b);
}
else{
for(i=2;i<=m;i++){
t=m;
if(t%i==0){
while(t>1){
if(t%i)break;
t/=i;
}
if(t==1&&n%(i+1)==0)break;
}
}
a=b=0;
t2=i+1;
t=m;
do{
t/=i;
a+=t;
}while(t);
t=1;
do{
b+=t*n;
n/=t2;
t*=i;
}while(n);
printf("%u %u\n",a,b);
}
}
return 0;
}
Help I don't know why it is WA
I have try all I/O that have been given in this forum,and I've passed it all
Please help me
Thx !!