ACM (UVa) : 151 & 440


An inherent problem of queue.
U can use ur own method / function () or
use STL queue or STL list
brute force applicable. Tho, it deems that, STL would be bit slower in compare to our own manual function.

Serial input-output given for debugging.

Critical input:
13
14
15
16
18
19
20
97
98
99

Critical output:
1
18
10
11
17
11
15
52
113
15

/* ACM (UVa) : 151
Author: Tausiq
CTE, UIU */

#include
#include using namespace std;

int N;

int simulation (int m)
{
list l;

int i;
for (i = 1; i <= N; i++) l.push_back (i); while ( l.size () > 1 ) {

l.pop_front ();

for (i = 1; i < m; i++) { l.push_back ( l.front () ); l.pop_front (); } } return l.front (); } int main () { while (scanf ("%d", &N)) { if (N == 0) return 0; int m = 1; int region = 0; while (1) { region = simulation (m); if (region == 13) break; m++; } printf("%d\n", m); } return 0; } [/sourcecode]

// Similar problem : 440 (Eeny Meeny Moo)
same process and u can use same code to solve this 1.
but … !!!
The judge’s verdict is one of outrage. I got TLE for the same code !!
at first, I run the program and saved all possible input’s output in a file.
Then I declare an array and initialized it with the outputs value … and just print it. [not a correct procedure to solve a problem. rather it’s better to find another faster algorithm which runs in time. hmm … giving advice is easy than maintain.]

Critical input:
148
144
134
78

Critical output:
205
303
513
8

One thought on “ACM (UVa) : 151 & 440

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s