264 - Count on Cantor

All about problems in Volume 2. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

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

264: isn't sample output wrong?

Post by monika » Tue Jul 30, 2002 11:25 am

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

Post by xenon » Tue Jul 30, 2002 1:14 pm

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

Post by monika » Tue Jul 30, 2002 1:19 pm

Ok! thanks :)

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

Post by monika » Fri Aug 02, 2002 8:34 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

Post by Sneeze » Sat May 03, 2003 10:33 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

Post by zzylhy » Wed May 21, 2003 4:21 pm

#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? :wink:
[/cpp]

User avatar
little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

Post by little joey » Wed May 21, 2003 4:28 pm

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

Master
Learning poster
Posts: 82
Joined: Thu Oct 10, 2002 1:15 pm
Location: St. Johns, Canada
Contact:

Post by Master » Tue Sep 16, 2003 5:56 am

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

Post by technobug » Tue Apr 06, 2004 4:44 pm

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?

Post by Minilek » Tue Aug 03, 2004 11:07 am

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

Post by Piotrek Mazur » Wed Aug 04, 2004 10:15 pm

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
New poster
Posts: 8
Joined: Fri Sep 24, 2004 8:40 am

Prob 264

Post by vladimir manich » Wed Sep 29, 2004 8:03 pm

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 .

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

Post by dumb dan » Sun Oct 03, 2004 3:52 pm

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
Location: IITM,chennai,Tamil Nadu,India
Contact:

problem 264 - PE

Post by Karthekeyan » Sat May 21, 2005 5:29 pm

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:

Post by nukeu666 » Mon Dec 05, 2005 3:34 am

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

Post Reply

Return to “Volume 2 (200-299)”