## 880 - Cantor Fractions

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

Moderator: Board moderators

Eduard
Experienced poster
Posts: 183
Joined: Fri Sep 26, 2003 2:54 pm
Location: Armenia,Yerevan

### 880 - Cantor Fractions

I solve many such problems(for example 264),but this one I'm getting TLE(on Pascal).Somebody tell me what to do or may be I must write it on C++.
Thanks.
someone who like to solve informatic problems.
http://acm.uva.es/cgi-bin/OnlineJudge?AuthorInfo:29650

stubbscroll
Experienced poster
Posts: 151
Joined: Tue Nov 16, 2004 7:23 pm
Location: Norway
Contact:
The choice of algorithm counts more than the choice of language. What is the time complexity of your algorithm?

neno_uci
Experienced poster
Posts: 104
Joined: Sat Jan 17, 2004 12:26 pm
Location: Cuba
Hi all!!!

I used the following algorithm to solve this problem:

1. Find the maximux number n for which n(n+1)/2 is closest to the input value(x).
2. s = (n * (n + 1)) / 2;
if (x == s)
cout << 1;
else
cout << n + 2 - x + s;
cout << '/';
if (x - s)
cout << x - s << endl;
else
cout << n << endl;

I have tried a lot of test cases and all are fine..., where is my mistake???

Thanx in advance,

Yandry.

Btw i used unsigned long long to store the number...

neno_uci
Experienced poster
Posts: 104
Joined: Sat Jan 17, 2004 12:26 pm
Location: Cuba
I got AC now, thanx anyway

CodeMaker
Experienced poster
Posts: 183
Joined: Thu Nov 11, 2004 12:35 pm
Location: AIUB, Bangladesh
Hi, I got TLE, can anyone say what's wrong ?

Code: Select all

``````#include<stdio.h>

void main()
{
unsigned long long n,x,p;

while(scanf("%llu",&n)==1)
{

x=1;
while((p=x*(x+1)/2)<n)
{
if(p>=n)
break;
else
x++;
}
printf("%llu/%llu\n",1+(p-n),x-(p-n));
}
}
``````
Jalal : AIUB SPARKS

nnahas
New poster
Posts: 40
Joined: Mon Nov 01, 2004 7:56 pm
CodeMaker wrote:Hi, I got TLE, can anyone say what's wrong ?

Code: Select all

``````#include<stdio.h>

void main()
{
unsigned long long n,x,p;

while(scanf("%llu",&n)==1)
{

x=1;
while((p=x*(x+1)/2)<n)
{
if(p>=n)
break;
else
x++;
}
printf("%llu/%llu\n",1+(p-n),x-(p-n));
}
}
``````
Well, I haven't attempted the problem, but if the input value can really be up to 2^64, then it is quite normal you get TLE since you would run the while loop more than 2^32 times. Use a quicker algo to get the square root of 2n, either use sqrt and double, or use the babylonian algorithm
http://www.math.jhu.edu/courses/107/arc ... ode16.html.

Observer
Guru
Posts: 570
Joined: Sat May 10, 2003 4:20 am
Location: Hong Kong
Hmm... is it so hard to figure out an O(1) solution? I suggest anyone who get TLE to spend some time on that

--------------
A quotation:
gvcormac wrote:I suggest that it is your responsibility to explain why your program should work than to invite others to find errors.
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org

Sedefcho
A great helper
Posts: 374
Joined: Sun Jan 16, 2005 10:18 pm
Location: Bulgaria
CodeMaker,

here is your code.

Code: Select all

``````#include<stdio.h>

void main()
{
unsigned long long n,x,p;

while(scanf("%llu",&n)==1)
{

x=1;
while((p=x*(x+1)/2)<n)
{
if(p>=n)
break;
else
x++;
}
printf("%llu/%llu\n",1+(p-n),x-(p-n));
}
}
``````
Note that you set X to 1 before starting your while cycle.
x=1;

That is the problem. If we call the value 1 SEED for X then
your problem is that your SEED is too low, you can use a better
value for it , thus ensuting you have in your while just a couple
of iterations.

A better SEED is this one:
x = Math.sqrt(2*N)-1
converted to the appropriate INT type you use
( I think you said it is long long or something like that ).

This way you just avoid a huge amount of looping in your
WHILE.

Make the seed x = Math.sqrt(2*N)-3 , if you want, you won't
have TLE in both cases.

dovier_antonio
New poster
Posts: 47
Joined: Fri Feb 18, 2005 5:00 am
Location: Havana, Cuba

### Hi Sedefcho !!!

source code deleted...
Last edited by dovier_antonio on Fri Feb 03, 2012 9:23 am, edited 1 time in total.

dovier_antonio
New poster
Posts: 47
Joined: Fri Feb 18, 2005 5:00 am
Location: Havana, Cuba

### Hi Sedefcho !!!

source code deleted...
Last edited by dovier_antonio on Fri Feb 03, 2012 9:24 am, edited 1 time in total.

sumankar
A great helper
Posts: 286
Joined: Tue Mar 25, 2003 8:36 am
Location: calcutta
Contact:
Hello,

Can someone tell me the input limits for this problem?Actually I was thinking whether using long long is enough or not...

Regards,
Suman.

Raj Ariyan
Learning poster
Posts: 70
Joined: Sat Feb 05, 2005 9:38 am
Location: Gurukul

### Let Reply

Hi Sumanker,
Very late replay !!! . I dont know wheither u read or not. Well, long long is enough for this problem. Thankx.
Some Love Stories Live Forever ....

Majjj
New poster
Posts: 1
Joined: Tue Nov 15, 2005 9:15 am

### 880 Cantor Fractions...

Isnt this the same as 264.... except for the printing thing and the order of printing. I am getting TLE for the program.
The time required for :-
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

is

real 0m0.010s
user 0m0.000s
sys 0m0.010s

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:
The input limit is higher here...Think about 64 bit int....

And better to find a formula.....
Ami ekhono shopno dekhi...
HomePage

mohiul alam prince
Experienced poster
Posts: 120
Joined: Sat Nov 01, 2003 6:16 am
Location: Dhaka (EWU)
Hi

I think the input limit is not more than (2^31 - 1).
i have derive a short cut form of this problem.

this is my function.

Code: Select all

``````function(int N) {
int res;
res = ceil(((-1 + sqrt(1 + 4.0 * 2.0 * N))/(double)2.0));
int ans = ((((res * res) + res) /(double) 2.0));
printf("%d/%d\n", (ans - N) + 1,res);
}
``````
I think this will be help for you.

Regards
MAP