264 - Count on Cantor

All about problems in Volume 2. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

helloneo
Guru
Posts: 516
Joined: Mon Jul 04, 2005 6:30 am
Location: Seoul, Korea

Post by helloneo » Thu Mar 22, 2007 10:19 am

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

User avatar
jainal cse du
New poster
Posts: 23
Joined: Thu Jul 27, 2006 2:43 pm
Location: University of Dhaka,Bangladesh

Post by jainal cse du » Sat Mar 24, 2007 12:35 pm

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

User avatar
Donotalo
Learning poster
Posts: 56
Joined: Sat Aug 20, 2005 11:05 am
Location: Bangladesh

Post by Donotalo » Sun Sep 09, 2007 2:44 pm

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

sapnil
Experienced poster
Posts: 106
Joined: Thu Apr 26, 2007 2:40 pm
Location: CSE-SUST
Contact:

Post by sapnil » Mon Oct 08, 2007 12:24 pm

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
New poster
Posts: 12
Joined: Sun Jun 18, 2006 3:06 am

About Algo.....

Post by Sayeef » Sat Jan 19, 2008 2:38 pm


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 :lol: good luck



Rizoan toufiq
New poster
Posts: 4
Joined: Mon Apr 21, 2008 9:38 pm

Post by Rizoan toufiq » Mon May 24, 2010 2:05 pm

.
Last edited by Rizoan toufiq on Tue Sep 29, 2015 6:20 pm, edited 1 time in total.

Rizoan toufiq
New poster
Posts: 4
Joined: Mon Apr 21, 2008 9:38 pm

Re: 264 - Count on Cantor

Post by Rizoan toufiq » Mon May 24, 2010 2:07 pm

.
Last edited by Rizoan toufiq on Tue Sep 29, 2015 6:18 pm, edited 1 time in total.

kissu parina
New poster
Posts: 19
Joined: Thu May 20, 2010 8:58 am

Re: 264 PE?

Post by kissu parina » Thu Feb 10, 2011 3:05 pm

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 :)
one day...

jfvs
New poster
Posts: 12
Joined: Wed Feb 02, 2011 10:40 am

Re: 264

Post by jfvs » Fri Apr 01, 2011 1:43 am

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

User avatar
@ce
Learning poster
Posts: 71
Joined: Mon May 28, 2012 8:46 am
Location: Ranchi, India

Re: 264 PE?

Post by @ce » Mon Jun 25, 2012 9:59 am

Vexorian wrote: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.
-@ce

richatibrewal
New poster
Posts: 49
Joined: Mon Jun 16, 2014 7:40 pm

Re: 264 - Count on Cantor

Post by richatibrewal » Tue Oct 07, 2014 4:57 pm

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;
}
Last edited by richatibrewal on Wed Oct 08, 2014 3:02 pm, edited 3 times in total.

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

Re: 264 - Count on Cantor

Post by lighted » Wed Oct 08, 2014 9:26 am

The code above is not accepted code. It doesn't match sample I/O.
A person who sees the good in things has good thoughts. And he who has good thoughts receives pleasure from life... Bediuzzaman

richatibrewal
New poster
Posts: 49
Joined: Mon Jun 16, 2014 7:40 pm

Re: 264 - Count on Cantor

Post by richatibrewal » Wed Oct 08, 2014 3:05 pm

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

Re: 264 - Count on Cantor

Post by lighted » Wed Oct 08, 2014 4:18 pm

I changed your old code. In Ansi C it is accepted in O(1) with 0.012. http://ideone.com/fbwN5P
A person who sees the good in things has good thoughts. And he who has good thoughts receives pleasure from life... Bediuzzaman

richatibrewal
New poster
Posts: 49
Joined: Mon Jun 16, 2014 7:40 pm

Re: 264 - Count on Cantor

Post by richatibrewal » Thu Oct 09, 2014 10:22 am

Thank u

Post Reply

Return to “Volume 2 (200-299)”