OJ Board

Posted: **Fri Feb 17, 2006 9:45 am**

Nice

Note that m%(n+1) is either 0 or 1 (roughly 6 times faster?)

Darko

Posted: **Sun Jul 16, 2006 7:38 pm**

mf wrote:Actually there is a way to solve this problem without precalculation!

Here's how I've solved it, but I'm too lazy to re-derive my solution now.
The code solves the case k=13 in less than a second.
<snip>

My solution is very similar to this, although slightly more optimized (since it eliminates many m values in advance). I compiled and ran both your version and my version on my machine, and mine was about .1 second faster (0.5 seconds vs. 0.4 seconds, roughly), to compute all cases (1 through 13).

However, when I upload my code to the online judge, it exceeds the time limit. Anyone else having the same problem?

Posted: **Sun Jul 16, 2006 7:51 pm**

Input may contain repeated values of k, and if your code recomputes output every time then it'll easily time-out. (Just imagine a file with, say, a thousand of 13's).

Posted: **Mon Jul 17, 2006 1:13 am**

mf wrote:Input may contain repeated values of k, and if your code recomputes output every time then it'll easily time-out. (Just imagine a file with, say, a thousand of 13's).

Aha, I hadn't thought of that. I'll try this.

Thanks.

Posted: **Tue Apr 03, 2007 6:33 am**

The following code:

Code: Select all

#include <iostream>
using namespace std;

int main (void)
{
    int k;
    while ((cin>>k)&&k)
    {
        int p = k*2;
        int m;
        for (m=k; ; m++)
        {
            int x=p;
            int y=(m-1)%x;
            while (y>=k && x>k)
            {
                x--;
                y = (y-1+m)%x;
            }
            if (x==k)
                break;
        }
        cout << m << endl;
    }
}

Solves all possible cases in <3 seconds on my computer, and get's TLE

I used a lookup table, and got AC... But that's not why I'm posting... Is the judges computer that much slower, or is there repeating test cases in the judge's input file?

Posted: **Sat May 26, 2007 4:18 pm**

as judge input consists of many repeating test cases so you need to store the result in a table otherwise you will be definately get TLE due to repeated computation....

Posted: **Sat May 26, 2007 8:33 pm**

>>>LithiumDex
U should remove ur code from the post. Otherwise spoilers can take the chance.

Posted: **Sun Jun 03, 2007 10:03 am**

hello all,
I have solved this problem and getting correct output but still WA.
I am unable to understand, please help me.

Code: Select all

#include<iostream>

}

Thanx in advance.

Suyash

Code: Select all

Posted: **Sun Jun 03, 2007 12:26 pm**

Code: Select all

long int p[13];

This portion of ur code is not correct. If u decleare an array of size 13 u can't access index arr[13].

Posted: **Sun Jun 03, 2007 1:09 pm**

Thanx
I got AC

Posted: **Wed Oct 03, 2007 5:33 am**

accepted

Posted: **Wed Oct 03, 2007 3:43 pm**

For k = 1 the answer should be 2. And don't forget to remove your code after getting accepted.

OJ Board

305 - Joseph

305 .. Cheating judge?

305 WA

@mmonish