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

Post by Eduard » Tue Jan 04, 2005 6:35 pm

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:

Post by stubbscroll » Fri Jan 07, 2005 8:54 am

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

Post by neno_uci » Tue Jan 18, 2005 8:20 am

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

:oops:

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

Post by neno_uci » Tue Jan 18, 2005 8:24 am

I got AC now, thanx anyway :D

User avatar
CodeMaker
Experienced poster
Posts: 183
Joined: Thu Nov 11, 2004 12:35 pm
Location: AIUB, Bangladesh

Post by CodeMaker » Sun Feb 06, 2005 3:23 am

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

Post by nnahas » Mon Feb 07, 2005 2:52 am

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

Post by Observer » Mon Feb 07, 2005 3:03 am

Hmm... is it so hard to figure out an O(1) solution? I suggest anyone who get TLE to spend some time on that :P

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

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

Post by Sedefcho » Thu Feb 10, 2005 2:31 pm

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.

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

Hi Sedefcho !!!

Post by dovier_antonio » Sun Mar 13, 2005 11:39 am

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

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

Hi Sedefcho !!!

Post by dovier_antonio » Mon Mar 14, 2005 8:18 am

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:

Post by sumankar » Wed Mar 16, 2005 9:27 am

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

Post by Raj Ariyan » Sat Apr 16, 2005 6:17 pm

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

Post by Majjj » Wed Nov 16, 2005 5:43 pm

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:

Post by Jan » Sat Nov 19, 2005 1:56 am

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

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

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

Post by mohiul alam prince » Tue Nov 22, 2005 2:06 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

Post Reply

Return to “Volume 8 (800-899)”