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

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

Some test cases, please

Post by nymo » Mon Nov 20, 2006 9:22 pm

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

Post by nymo » Fri Mar 16, 2007 5:52 pm

Hi, I got ACC :D, ... a silly mistake :oops:

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

TLE

Post by himanshu » Fri Nov 23, 2007 9:08 am

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;
}
Please help.

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

Post by Taman » Sat Oct 17, 2009 12:00 am

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

Post by marco2509 » Thu Oct 29, 2009 7:16 am

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

Post by serur » Sun Jan 03, 2010 12:42 pm

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

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

880 Cantor fractions

Post by minipada » Wed Mar 23, 2011 10:36 pm

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

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

Re: 880 - Cantor Fractions

Post by plamplam » Fri Jun 24, 2011 1:58 pm

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

Post by annhy » Mon Apr 23, 2012 7:10 am

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: 585
Joined: Wed Jun 11, 2014 9:56 pm
Location: Kyrgyzstan, Bishkek

Re: 880 - Cantor Fractions

Post by lighted » Sun Dec 14, 2014 12:57 pm

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

Post Reply

Return to “Volume 8 (800-899)”