264  Count on Cantor
Moderator: Board moderators
264: isn't sample output wrong?
Hi,
Maybe I've misunderstood the problem!
But the sample output looks wrong to me.
Shouldn't the 14th term be 4/2 instead of 2/4 ???
Monika
Maybe I've misunderstood the problem!
But the sample output looks wrong to me.
Shouldn't the 14th term be 4/2 instead of 2/4 ???
Monika
No, the sample output is right. The order in which the terms are counted is:
for the first 15 terms. It's a zigzag!
Code: Select all
1 2 6 7 15
3 5 8 14
4 9 13
10 12
11
Hi,
I'm getting WA.
Could someone help me identify what is wrong.
Here is my code:
I'm getting WA.
Could someone help me identify what is wrong.
Here is my code:
Code: Select all
#include <stdio.h>
void main()
{
int k,N;
int z,num,den;
while(!feof(stdin))
{
scanf("%d",&N);
if( (N<1)  (N>10000000))
continue;
num=1; den=1;
z=1; k=1;
/* we are looking for kth term*/
while(k<N)
{
/*traverse along the diagonal line */
z++;
for(k+=1, num=1,den=z; (num<z) && (k<N); )
{
num++;
den;
k++;
}
if(k==N)
break;
/* traverse next diagonal line in reverse direction...*/
z++;
for(k+=1, den=1,num=z; (den<z) && (k<N); )
{
den++;
num;
k++;
}
}
printf("TERM %d IS %d/%d\n", N, num, den);
}
}
264
#include<iostream.h>
#include<stdio.h>
int main()
{
long l,r,n,i;
int sl,sr;
while(cin>>n)
{
l=r=i=sr=sl=1;
while(1)
{
if(i==n)
break;
if(l==1)
{
r++;
i++;
if(i==n)
break;
sl=1;
sr=1;
while(r!=1)
{
l=l+sl;
r=r+sr;
i++;
if(i==n)
break;
}
}
if(i==n)
break;
if(r==1)
{
l++;
i++;
if(i==n)
break;
sl=1;
sr=1;
while(l!=1)
{
l=l+sl;
r=r+sr;
i++;
if(i==n)
break;
}
}
}
printf("TREM %d IS %d/%d\n",n,l,r);
}
return 0;
}
I tried all the Sample Input and the Ouputs are correct.
But I got WA at the OlineJudge.
Can anybody help?
[/cpp]
#include<stdio.h>
int main()
{
long l,r,n,i;
int sl,sr;
while(cin>>n)
{
l=r=i=sr=sl=1;
while(1)
{
if(i==n)
break;
if(l==1)
{
r++;
i++;
if(i==n)
break;
sl=1;
sr=1;
while(r!=1)
{
l=l+sl;
r=r+sr;
i++;
if(i==n)
break;
}
}
if(i==n)
break;
if(r==1)
{
l++;
i++;
if(i==n)
break;
sl=1;
sr=1;
while(l!=1)
{
l=l+sl;
r=r+sr;
i++;
if(i==n)
break;
}
}
}
printf("TREM %d IS %d/%d\n",n,l,r);
}
return 0;
}
I tried all the Sample Input and the Ouputs are correct.
But I got WA at the OlineJudge.
Can anybody help?
[/cpp]

 Guru
 Posts: 1080
 Joined: Thu Dec 19, 2002 7:37 pm

 Learning poster
 Posts: 82
 Joined: Thu Oct 10, 2002 1:15 pm
 Location: St. Johns, Canada
 Contact:
there is a formula for solving this problem.
we can use the triangular number formula for solving this.
M H Rasel
CUET Old Sailor
http://www.acmbeginner.tk
we can use the triangular number formula for solving this.
M H Rasel
CUET Old Sailor
http://www.acmbeginner.tk
264  Count on Cantor
I am unable to solve this little problem.... can anyone who got AC try my test data?
I have tried the following:
Calculate the highest number for each diagonal, knowing that max(diag1) = 1 and max(diagN) = max(diag(N1) + N)
Then, for each number asked, i search for the first diagonal whose max number is bigger or equals to the one needed. Then I do some math based on the parity of the diagonal and finds its position in the diagonal. (whether the diagonal grows up or down)...
I dont know why but it doesnt work for 10^7..... so I hard coded it
Code follows:
[cpp]
AC, if you want the code, mail me
[/cpp]
For the following input:
10000000
999999
999998
287234
100000
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
44
45
I get the following output:
TERM 10000000 IS 1009/406
TERM 999999 IS 1008/407
TERM 999998 IS 1007/408
TERM 287234 IS 331/428
TERM 100000 IS 129/319
TERM 1 IS 1/1
TERM 2 IS 1/2
TERM 3 IS 2/1
TERM 4 IS 3/1
TERM 5 IS 2/2
TERM 6 IS 1/3
TERM 7 IS 1/4
TERM 8 IS 2/3
TERM 9 IS 3/2
TERM 10 IS 4/1
TERM 11 IS 5/1
TERM 12 IS 4/2
TERM 13 IS 3/3
TERM 14 IS 2/4
TERM 15 IS 1/5
TERM 16 IS 1/6
TERM 17 IS 2/5
TERM 18 IS 3/4
TERM 19 IS 4/3
TERM 20 IS 5/2
TERM 44 IS 2/8
TERM 45 IS 1/9
So the above output is wrong... i just got it AC.... I was calculating the numbers up to 10^6....
Oh, those 10 submissions hurts me....
I have tried the following:
Calculate the highest number for each diagonal, knowing that max(diag1) = 1 and max(diagN) = max(diag(N1) + N)
Then, for each number asked, i search for the first diagonal whose max number is bigger or equals to the one needed. Then I do some math based on the parity of the diagonal and finds its position in the diagonal. (whether the diagonal grows up or down)...
I dont know why but it doesnt work for 10^7..... so I hard coded it
Code follows:
[cpp]
AC, if you want the code, mail me
[/cpp]
For the following input:
10000000
999999
999998
287234
100000
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
44
45
I get the following output:
TERM 10000000 IS 1009/406
TERM 999999 IS 1008/407
TERM 999998 IS 1007/408
TERM 287234 IS 331/428
TERM 100000 IS 129/319
TERM 1 IS 1/1
TERM 2 IS 1/2
TERM 3 IS 2/1
TERM 4 IS 3/1
TERM 5 IS 2/2
TERM 6 IS 1/3
TERM 7 IS 1/4
TERM 8 IS 2/3
TERM 9 IS 3/2
TERM 10 IS 4/1
TERM 11 IS 5/1
TERM 12 IS 4/2
TERM 13 IS 3/3
TERM 14 IS 2/4
TERM 15 IS 1/5
TERM 16 IS 1/6
TERM 17 IS 2/5
TERM 18 IS 3/4
TERM 19 IS 4/3
TERM 20 IS 5/2
TERM 44 IS 2/8
TERM 45 IS 1/9
So the above output is wrong... i just got it AC.... I was calculating the numbers up to 10^6....
Oh, those 10 submissions hurts me....
0.000 seconds?
I just wanted to ask if there is some even faster trick to solving problem 264. I tried to go all out in terms of speed, but could only get it down to 0.006seconds, but some people on the scoreboards have 0.000.
I kept an array of size 4473 which has n*(n+1)/2 for each 0<=n<=4472. Then when given a number, i binary search through the array to find between which two spots the number lies, and from that I figure out the denom/num with a couple of additions. I can't possibly see how to make this any faster; am I missing something?
I kept an array of size 4473 which has n*(n+1)/2 for each 0<=n<=4472. Then when given a number, i binary search through the array to find between which two spots the number lies, and from that I figure out the denom/num with a couple of additions. I can't possibly see how to make this any faster; am I missing something?

 New poster
 Posts: 17
 Joined: Thu Jul 15, 2004 10:55 am
 Location: Poland, Rzeszow University of Technology

 New poster
 Posts: 8
 Joined: Fri Sep 24, 2004 8:40 am
Prob 264
Hey,
Can nbody who got any AC give me some output he got for numbers around 10^7. or may be 10 outputs from 10^7  1 to 10^7.
Well my C++ basics r also not strong in certain cases so plz could you tell me
"The input list contains a single number per line and will be terminated by endoffile." the EOF will be "EOF" itself or 1 or something else .
Can nbody who got any AC give me some output he got for numbers around 10^7. or may be 10 outputs from 10^7  1 to 10^7.
Well my C++ basics r also not strong in certain cases so plz could you tell me
"The input list contains a single number per line and will be terminated by endoffile." the EOF will be "EOF" itself or 1 or something else .
input:
output:
As for reading input, you could use one of these methods:
Code: Select all
1000000
1234567
2897534
3897346
4482323
5809231
6898729
7829873
8298733
9908727
10000000
Code: Select all
TERM 1000000 IS 1009/406
TERM 1234567 IS 240/1332
TERM 2897534 IS 495/1913
TERM 3897346 IS 1110/1683
TERM 4482323 IS 1802/1193
TERM 5809231 IS 3115/295
TERM 6898729 IS 3688/27
TERM 7829873 IS 1031/2927
TERM 8298733 IS 2032/2043
TERM 9908727 IS 801/3652
TERM 10000000 IS 2844/1629
Code: Select all
/*method 1:*/
int n;
while(cin>>n){
/*Put code here*/
}
/*method 2:*/
int n;
cin>>n;
while(!cin.fail()){
/*Put code here*/
cin>>n;
}
/*method 3:*/
char c;
cin>>c;
while(c!=1){
/*Put code here*/
cin>>c;
}

 New poster
 Posts: 33
 Joined: Tue Jun 29, 2004 1:38 pm
 Location: IITM,chennai,Tamil Nadu,India
 Contact:
problem 264  PE
Why does this code give PE?
Could anyone resolve it? It's not the blank line after last no. that gives the problem!
Could anyone resolve it? It's not the blank line after last no. that gives the problem!
Code: Select all
#include<iostream>
Last edited by Karthekeyan on Thu Dec 22, 2005 4:46 am, edited 1 time in total.
Karthe
i have a presentation error problem
the question states there shouldnt be a newline after the last input
here is my output
each line goes to a new line except the last line
what am i doing wrong?
the question states there shouldnt be a newline after the last input
here is my output
Code: Select all
[root@nehru nukem]# ./a.out <in
TERM 3 IS 2/1
TERM 7 IS 1/4
TERM 14 IS 2/4
TERM 1231 IS 6/45
TERM 52 IS 7/4[root@nehru nukem]#
what am i doing wrong?
google