Page 1 of 4
264: isn't sample output wrong?
Posted: Tue Jul 30, 2002 11:25 am
by 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
Posted: Tue Jul 30, 2002 1:14 pm
by 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!
Posted: Tue Jul 30, 2002 1:19 pm
by monika
Ok! thanks
Posted: Fri Aug 02, 2002 8:34 am
by 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);
}
}
Posted: Sat May 03, 2003 10:33 am
by 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.
264
Posted: Wed May 21, 2003 4:21 pm
by 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]
Posted: Wed May 21, 2003 4:28 pm
by little joey
For one thing, you should print "TERM", not "TREM". I haven't looked at the rest...
Posted: Tue Sep 16, 2003 5:56 am
by 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
264 - Count on Cantor
Posted: Tue Apr 06, 2004 4:44 pm
by 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....
0.000 seconds?
Posted: Tue Aug 03, 2004 11:07 am
by 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?
Posted: Wed Aug 04, 2004 10:15 pm
by 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.
Prob 264
Posted: Wed Sep 29, 2004 8:03 pm
by 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 .
Posted: Sun Oct 03, 2004 3:52 pm
by 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;
}
problem 264 - PE
Posted: Sat May 21, 2005 5:29 pm
by Karthekeyan
Why does this code give PE?
Could anyone resolve it? It's not the blank line after last no. that gives the problem!
Posted: Mon Dec 05, 2005 3:34 am
by 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?