264 - Count on Cantor

[helloneo]

printf("TERM %ld IS %ld / %ld\n",term,a,b);

should be

printf("TERM %ld IS %ld/%ld\n",term,a,b);


If you carefully see the pattern, you can find the formula..
So, you can get the answer (almost) directly..

[jainal cse du]

Thanks helloneo
Now I have got Accepted.
But,my algorithm is very poor.
so,Can you help me giving this formula?

[Donotalo]

my output to the above input is as follows:

Code: Select all

TERM 1000000 IS 1009/406
TERM 1234567 IS 240/1332
TERM 2897534 IS 495/1913
TERM 3897346 IS 1110/1683
TERM 4482323 IS 1802/1193
TERM 5809231 IS 3115/295
TERM 6898729 IS 3688/27
TERM 7829873 IS 1031/2927
TERM 8298733 IS 2032/2043
TERM 9908727 IS 801/3652
TERM 10000000 IS 2844/1629

i'm getting wa! is there any trick?

[sapnil]

Try this case:

Code: Select all

Input:
1
10000000
1000000
100000
10000
1000
100
10
9999999
999999
99999
9999
999
99
Output:
TERM 1 IS 1/1
TERM 10000000 IS 2844/1629
TERM 1000000 IS 1009/406
TERM 100000 IS 129/319
TERM 10000 IS 12/130
TERM 1000 IS 36/10
TERM 100 IS 9/6
TERM 10 IS 4/1
TERM 9999999 IS 2843/1630
TERM 999999 IS 1008/407
TERM 99999 IS 130/318
TERM 9999 IS 13/129
TERM 999 IS 37/9
TERM 99 IS 8/7

Thanks
Keep posting
Sapnil

[Sayeef]

You can do it Like this. You generatre all the summations upto 4775.

in a array val[].

formula is n(n+1)/2. When a Number is given then Binary search it. If u

find a match then cheak wheather it is even or odd. Then choose the

nom/dnom.

If you don't find the match then use the low index that is returned by

bsearch so the number<val[index] then if index is odd then choose

nom/dnom else ..... nom/dnom

I used this algo to Get 0.000 good luck

[Rizoan toufiq]

.

[Rizoan toufiq]

.

[kissu parina]

i guess u r wrong (hope u have probably solved it by now).
u dont have to print a blank line after the last test case

[jfvs]

thanks draco... my code was getting WA because I was missing that new line... shouldnt it be PE?... just wondering about that

[@ce]

The problem says "No blank line should appear after the last number." But when I try not to have a blank line after last output it tells me Presentation Error, if I make it have a blank line after the last output, my solution gets AC

I too got AC on printing \n at the end...otherwise i was getting WA.

[richatibrewal]

The following code has been accepted with runtime of 0.016s . Can someone plz tell me how to improve it.

Code: Select all

#include<cstdio>
using namespace std;
int main()
{
    int a,b,sum,m,n;
    while(scanf("%d",&n)==1)
    {
        sum=1;
        m=2;
        while(1)
        {
            if(n<=sum)
                break;
            sum=sum+(m++);
        }
        m=m-2;
        if(m%2==0)
        {
            a=sum-n+1;
            b=n-sum+m+1;
        }
        else
        {
            a=n-sum+m+1;
            b=sum-n+1;
        }
        printf("TERM %d IS %d/%d\n",n,a,b);
    }
    return 0;
}

[lighted]

The code above is not accepted code. It doesn't match sample I/O.

[richatibrewal]

The following code has been accepted with runtime of 0.016s . Can someone plz tell me how to improve it.

Code: Select all

#include<cstdio>
using namespace std;
int main()
{
    int a,b,sum,m,n;
    while(scanf("%d",&n)==1)
    {
        sum=1;
        m=2;
        while(1)
        {
            if(n<=sum)
                break;
            sum=sum+(m++);
        }
        m=m-2;
        if(m%2==0)
        {
            a=sum-n+1;
            b=n-sum+m+1;
        }
        else
        {
            a=n-sum+m+1;
            b=sum-n+1;
        }
        printf("TERM %d IS %d/%d\n",n,a,b);
    }
    return 0;
}

[lighted]

I changed your old code. In Ansi C it is accepted in O(1) with 0.012. http://ideone.com/fbwN5P

[richatibrewal]

Thank u