305 - Joseph

[Darko]

Nice

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

Darko

[AdamWG]

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?

[mf]

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

[AdamWG]

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.

[LithiumDex]

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?

[mukeshtiwari]

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

[mmonish]

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

[Suyash.Upadhyay]

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

[mmonish]

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

[Suyash.Upadhyay]

Thanx
I got AC

[Unioeste_Brazil]

accepted

[Jan]

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