## 880 - Cantor Fractions

Moderator: Board moderators

### 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
Eduard
Experienced poster

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

The choice of algorithm counts more than the choice of language. What is the time complexity of your algorithm?
stubbscroll
Experienced poster

Posts: 151
Joined: Tue Nov 16, 2004 7:23 pm
Location: Norway

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

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
neno_uci
Experienced poster

Posts: 104
Joined: Sat Jan 17, 2004 12:26 pm
Location: Cuba

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

CodeMaker
Experienced poster

Posts: 183
Joined: Thu Nov 11, 2004 12:35 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.
nnahas
New poster

Posts: 40
Joined: Mon Nov 01, 2004 7:56 pm

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
Observer
Guru

Posts: 570
Joined: Sat May 10, 2003 4:20 am
Location: Hong Kong

CodeMaker,

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.

Sedefcho
A great helper

Posts: 375
Joined: Sun Jan 16, 2005 10:18 pm
Location: Bulgaria

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

dovier_antonio
New poster

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

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.
sumankar
A great helper

Posts: 288
Joined: Tue Mar 25, 2003 8:36 am
Location: calcutta

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 ....
Raj Ariyan
Learning poster

Posts: 70
Joined: Sat Feb 05, 2005 9:38 am
Location: Gurukul

### 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
Majjj
New poster

Posts: 1
Joined: Tue Nov 15, 2005 9:15 am

The input limit is higher here...Think about 64 bit int....

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

Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm

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

mohiul alam prince
Experienced poster

Posts: 120
Joined: Sat Nov 01, 2003 6:16 am
Location: Dhaka (EWU)

Next