264 - Count on Cantor

[monika]

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]

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]

Ok! thanks

[monika]

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]

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

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

For one thing, you should print "TERM", not "TREM". I haven't looked at the rest...

[Master]

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]

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]

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]

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.

[vladimir manich]

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]

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]

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>

[nukeu666]

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?