880 - Cantor Fractions

[Eduard]

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.

[stubbscroll]

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

[neno_uci]

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]

I got AC now, thanx anyway

[CodeMaker]

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));
	}
}

[nnahas]

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]

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:

I suggest that it is your responsibility to explain why your program should work than to invite others to find errors.

[Sedefcho]

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]

source code deleted...

[dovier_antonio]

source code deleted...

[sumankar]

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]

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

[Majjj]

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]

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

And better to find a formula.....

[mohiul alam prince]

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