## 264 - Count on Cantor

Moderator: Board moderators

monika
New poster
Posts: 13
Joined: Tue Jul 23, 2002 9:45 am

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

xenon
Learning poster
Posts: 100
Joined: Fri May 24, 2002 10:35 am
Location: Scheveningen, Holland
No, the sample output is right. The order in which the terms are counted is:

Code: Select all

`````` 1   2   6   7  15
3   5   8  14
4   9  13
10 12
11
``````
for the first 15 terms. It's a zig-zag!

monika
New poster
Posts: 13
Joined: Tue Jul 23, 2002 9:45 am
Ok! thanks monika
New poster
Posts: 13
Joined: Tue Jul 23, 2002 9:45 am
Hi,

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

Sneeze
New poster
Posts: 13
Joined: Thu Jan 30, 2003 4:04 am
[quote="xenon"]No, the sample output is right. The order in which the terms are counted is:
[code]
1 2 6 7 15
3 5 8 14
4 9 13
10 12
11
[/code]
for the first 15 terms. It's a zig-zag![/quote]

I thoutht I made the same mistake!
But I think the description should be a little clearer.

zzylhy
New poster
Posts: 6
Joined: Mon May 19, 2003 1:56 pm

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

little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm
For one thing, you should print "TERM", not "TREM". I haven't looked at the rest... Master
Learning poster
Posts: 82
Joined: Thu Oct 10, 2002 1:15 pm
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

technobug
Learning poster
Posts: 88
Joined: Sat Nov 15, 2003 6:41 pm
Location: Brasilien
Contact:

### 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(N-1) + 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....

Minilek
Learning poster
Posts: 90
Joined: Tue Jul 27, 2004 9:34 am
Location: Cambridge, MA
Contact:

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

Piotrek Mazur
New poster
Posts: 17
Joined: Thu Jul 15, 2004 10:55 am
Location: Poland, Rzeszow University of Technology
I count it this way: first I cut off as large number as I can - this is the sum of diagonals = 1+2+3+4+..... (i use sqrt, so my time is 0.006 too). Then I simply calculate the result.

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 end-of-file." the EOF will be "EOF" itself or -1 or something else .

dumb dan
Learning poster
Posts: 67
Joined: Tue Aug 05, 2003 1:02 am
input:

Code: Select all

``````1000000
1234567
2897534
3897346
4482323
5809231
6898729
7829873
8298733
9908727
10000000``````
output:

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``````
As for reading input, you could use one of these methods:

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

Karthekeyan
New poster
Posts: 33
Joined: Tue Jun 29, 2004 1:38 pm
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!

Code: Select all

``````#include<iostream>

``````
Last edited by Karthekeyan on Thu Dec 22, 2005 4:46 am, edited 1 time in total.
Karthe

nukeu666
New poster
Posts: 44
Joined: Sun Feb 13, 2005 1:13 am
Location: India
Contact:
i have a presentation error problem
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]#
``````
each line goes to a new line except the last line

what am i doing wrong?