## 264 - Count on Cantor

Moderator: Board moderators

helloneo
Guru
Posts: 516
Joined: Mon Jul 04, 2005 6:30 am
Location: Seoul, Korea
printf("TERM %ld IS %ld / %ld\n",term,a,b);

should be

printf("TERM %ld IS %ld/%ld\n",term,a,b);

If you carefully see the pattern, you can find the formula..
So, you can get the answer (almost) directly..

jainal cse du
New poster
Posts: 23
Joined: Thu Jul 27, 2006 2:43 pm
Thanks helloneo
Now I have got Accepted.
But,my algorithm is very poor.
so,Can you help me giving this formula?

Donotalo
Learning poster
Posts: 56
Joined: Sat Aug 20, 2005 11:05 am
my output to the above input is as follows:

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``````
i'm getting wa! is there any trick?

sapnil
Experienced poster
Posts: 106
Joined: Thu Apr 26, 2007 2:40 pm
Location: CSE-SUST
Contact:
Try this case:

Code: Select all

``````Input:
1
10000000
1000000
100000
10000
1000
100
10
9999999
999999
99999
9999
999
99
Output:
TERM 1 IS 1/1
TERM 10000000 IS 2844/1629
TERM 1000000 IS 1009/406
TERM 100000 IS 129/319
TERM 10000 IS 12/130
TERM 1000 IS 36/10
TERM 100 IS 9/6
TERM 10 IS 4/1
TERM 9999999 IS 2843/1630
TERM 999999 IS 1008/407
TERM 99999 IS 130/318
TERM 9999 IS 13/129
TERM 999 IS 37/9
TERM 99 IS 8/7
``````
Thanks
Keep posting
Sapnil

Sayeef
New poster
Posts: 12
Joined: Sun Jun 18, 2006 3:06 am

You can do it Like this. You generatre all the summations upto 4775.

in a array val[].

formula is n(n+1)/2. When a Number is given then Binary search it. If u

find a match then cheak wheather it is even or odd. Then choose the

nom/dnom.

If you don't find the match then use the low index that is returned by

bsearch so the number<val[index] then if index is odd then choose

nom/dnom else ..... nom/dnom

I used this algo to Get 0.000 good luck

Rizoan toufiq
New poster
Posts: 4
Joined: Mon Apr 21, 2008 9:38 pm
.
Last edited by Rizoan toufiq on Tue Sep 29, 2015 6:20 pm, edited 1 time in total.

Rizoan toufiq
New poster
Posts: 4
Joined: Mon Apr 21, 2008 9:38 pm

### Re: 264 - Count on Cantor

.
Last edited by Rizoan toufiq on Tue Sep 29, 2015 6:18 pm, edited 1 time in total.

kissu parina
New poster
Posts: 19
Joined: Thu May 20, 2010 8:58 am

### Re: 264 PE?

i guess u r wrong (hope u have probably solved it by now).
u dont have to print a blank line after the last test case
one day...

jfvs
New poster
Posts: 12
Joined: Wed Feb 02, 2011 10:40 am

### Re: 264

thanks draco... my code was getting WA because I was missing that new line... shouldnt it be PE?... just wondering about that

@ce
Learning poster
Posts: 71
Joined: Mon May 28, 2012 8:46 am
Location: Ranchi, India

### Re: 264 PE?

Vexorian wrote:The problem says "No blank line should appear after the last number." But when I try not to have a blank line after last output it tells me Presentation Error, if I make it have a blank line after the last output, my solution gets AC
I too got AC on printing \n at the end...otherwise i was getting WA.
-@ce

richatibrewal
New poster
Posts: 49
Joined: Mon Jun 16, 2014 7:40 pm

### Re: 264 - Count on Cantor

The following code has been accepted with runtime of 0.016s . Can someone plz tell me how to improve it.

Code: Select all

``````#include<cstdio>
using namespace std;
int main()
{
int a,b,sum,m,n;
while(scanf("%d",&n)==1)
{
sum=1;
m=2;
while(1)
{
if(n<=sum)
break;
sum=sum+(m++);
}
m=m-2;
if(m%2==0)
{
a=sum-n+1;
b=n-sum+m+1;
}
else
{
a=n-sum+m+1;
b=sum-n+1;
}
printf("TERM %d IS %d/%d\n",n,a,b);
}
return 0;
}``````
Last edited by richatibrewal on Wed Oct 08, 2014 3:02 pm, edited 3 times in total.

lighted
Guru
Posts: 587
Joined: Wed Jun 11, 2014 9:56 pm
Location: Kyrgyzstan, Bishkek

### Re: 264 - Count on Cantor

The code above is not accepted code. It doesn't match sample I/O.
A person who sees the good in things has good thoughts. And he who has good thoughts receives pleasure from life... Bediuzzaman

richatibrewal
New poster
Posts: 49
Joined: Mon Jun 16, 2014 7:40 pm

### Re: 264 - Count on Cantor

The following code has been accepted with runtime of 0.016s . Can someone plz tell me how to improve it.

Code: Select all

``````#include<cstdio>
using namespace std;
int main()
{
int a,b,sum,m,n;
while(scanf("%d",&n)==1)
{
sum=1;
m=2;
while(1)
{
if(n<=sum)
break;
sum=sum+(m++);
}
m=m-2;
if(m%2==0)
{
a=sum-n+1;
b=n-sum+m+1;
}
else
{
a=n-sum+m+1;
b=sum-n+1;
}
printf("TERM %d IS %d/%d\n",n,a,b);
}
return 0;
}``````

lighted
Guru
Posts: 587
Joined: Wed Jun 11, 2014 9:56 pm
Location: Kyrgyzstan, Bishkek

### Re: 264 - Count on Cantor

I changed your old code. In Ansi C it is accepted in O(1) with 0.012. http://ideone.com/fbwN5P
A person who sees the good in things has good thoughts. And he who has good thoughts receives pleasure from life... Bediuzzaman

richatibrewal
New poster
Posts: 49
Joined: Mon Jun 16, 2014 7:40 pm

Thank u