## 880 - Cantor Fractions

Moderator: Board moderators

nymo
Experienced poster
Posts: 149
Joined: Sun Jun 01, 2003 8:58 am
Location: :)

I have tried several test cases and get correct answers. I am using long long data type. still WAs. Can someone, please, provide some more test cases...say, for large numbers whose output is hard to check by hand? THANKS
regards,
nymo

nymo
Experienced poster
Posts: 149
Joined: Sun Jun 01, 2003 8:58 am
Location: :)

### I got ACC:)

Hi, I got ACC , ... a silly mistake

himanshu
New poster
Posts: 17
Joined: Mon May 15, 2006 12:24 pm
Contact:

### TLE

I get TLE for this.

Code: Select all

``````#include<iostream>
#include<cmath>
long long sum_n(long long n)
{
return (n*(n+1))/2;
}

int main()
{
long long i;
while(std::cin >> i)
{
long long n;
for(n = (long long)(sqrt(i)); sum_n(n) < i; n*=2)
;
n /= 2;
for(; sum_n(n) < i; n++)
;
n--;
long long x = i-sum_n(n); long long y = n-x+2;
std::cout << y << '/' << x << std::endl;
}
return 0;
}``````

Also what is the explanation for the following formula posted by dovier_antonio earlier in this thread :-

Code: Select all

``````x = (sqrt(1+8*n)-1)/2;
y = x*(x+1)/2;
``````
Thank You,
HG

Taman
New poster
Posts: 32
Joined: Sun Oct 11, 2009 8:59 pm
Location: Southeast University

### Re: 880 - Cantor Fractions

Ok, in reply to Himanshu. . .Hope that you've got acc by the mean time but it's for other guys who will ask the same question . . . .ok, the first line----- "x = (sqrt(1+8*n)-1)/2;" solves a quadratic equation for n and finds the value of x, where n is expressed as (0~x)?i.in other words we can say that it solves the equation n~x*(x+1)/2. . .I assume you all know what this equation expresses. . . And the second line ----- y = x*(x+1)/2; find the maximum position of number on the same diagonal of n. . .the rest is on you. . .

marco2509
New poster
Posts: 3
Joined: Wed Oct 28, 2009 10:59 pm

### Re: 880 - Cantor Fractions

Where is the mistake?

Code: Select all

``````#include <stdio.h>
#include <math.h>
int main() {
unsigned long int k, r, n;
while(scanf("%u",&n) != EOF) {
k = (unsigned long int)(sqrt(2 * n) + 0.5);
r = k * (k + 1)/ 2 - n;
printf("%u/%u\n",1+r,k-r);
}
return 0;
}
``````

serur
A great helper
Posts: 251
Joined: Thu Feb 23, 2006 11:30 pm

### Re: 880 - Cantor Fractions

I would like to strongly emphasize that UVa264 and UVa880 are not one and the same: for instance, for input

Code: Select all

``7``
you would have

Code: Select all

``TERM 7 IS 1/4``
and

Code: Select all

``4/1``
respectively.
If there is ever a war between men and machines, it is easy to guess who will start it (c) Arthur Clarke

New poster
Posts: 1
Joined: Wed Mar 23, 2011 10:33 pm

### 880 Cantor fractions

Hi, i made it in C:
#include <stdio.h>

void cantor(int x)
{
int i = 0;
int somme = 0;
int max;

while (somme < x){
somme = somme + i;
i++;
}

somme = somme - i +2;

i = somme;
for(max = 1; somme-max > 0; max++)
somme = somme-max;

printf("%d/%d\n",max-x+i,1+x-i);

}

int main()
{
int x;

while (scanf("%d",&x)==1)
cantor(x);

return 0;
}
i have TLE...

plamplam
Experienced poster
Posts: 150
Joined: Fri May 06, 2011 11:37 am

### Re: 880 - Cantor Fractions

My code got AC in 0.056 seconds.
Im not sure about the range of the given integers in this problem. As far as I can remember, I used long long int to get AC first, but when I tried with int, I got WA. My Accepted code gives the following outputs for the following inputs:

Code: Select all

``````1
2
3
4
5
6
7
8
9
10
191
10192
10193
1019101
101920102
5930201010
50505050505
50505050506
9192919458572
23182823482828
192102919219291
1289129195945949
89283928182828282
``````

Code: Select all

``````1/1
2/1
1/2
3/1
2/2
1/3
4/1
3/2
2/3
1/4
20/1
105/39
104/40
1206/223
3402/10876
1610611060/1610618078
1073749279/1073740425
1073749278/1073740424
1610612285/1610624842
1610631509/1610611476
1304254375/1304254373
1073756034/1073739861
1216533256/1216533254
``````
You tried your best and you failed miserably. The lesson is 'never try'. -Homer Simpson

annhy
New poster
Posts: 40
Joined: Sun May 27, 2007 1:42 am
Location: Taiwan

### Re: 880 - Cantor Fractions

plamplam wrote:My code got AC in 0.056 seconds.
Im not sure about the range of the given integers in this problem. As far as I can remember, I used long long int to get AC first, but when I tried with int, I got WA. My Accepted code gives the following outputs for the following inputs:

Code: Select all

``````1
2
3
4
5
6
7
8
9
10
191
10192
10193
1019101
101920102
5930201010
50505050505
50505050506
9192919458572
23182823482828
192102919219291
1289129195945949
89283928182828282
``````
For your input data, my accepted code outputs:

Code: Select all

``````1/1
2/1
1/2
3/1
2/2
1/3
4/1
3/2
2/3
1/4
20/1
105/39
104/40
1206/223
3402/10876
2956/105950
202427/115395
202426/115396
1541685/2746187
136701/6672532
3664575/15936595
47499787/3276768
358236070/64336832
``````

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

### Re: 880 - Cantor Fractions

plamplam's output is wrong, annhy's output is correct.
plamplam wrote:My code got AC in 0.056 seconds.
Im not sure about the range of the given integers in this problem. As far as I can remember, I used long long int to get AC first, but when I tried with int, I got WA. My Accepted code gives the following outputs for the following inputs:
I solved it with int in O(1). I used conversion to long long when multiplication exceeds int range.
A person who sees the good in things has good thoughts. And he who has good thoughts receives pleasure from life... Bediuzzaman