ACM (UVa) : 305


There r ‘k’ good guys and ‘k’ bad guys.
Total number of people = k + k = 2k
first ‘k’ r good guys and last ‘k’ bad guys.
Bad guys will be executed b4 the first good guy
So, m >= k + 1

Example:

for k = 1
Total number of people = k + k = 1 + 1 = 2
queue : 1, 2
good guy = 1
bad guy = 2
so, m = 2

for k = 2
Total number of people = k + k = 2 + 2 = 4
queue : 1, 2, 3, 4
good guy = 1, 2
bad guy = 3, 4
so, m = 7

output explanation : [ k = 2, m = 7]
1, 2, 3, 4
1, 2, 3, 4
1, 2, 4
1, 2, 4

for k = 3
Total number of people = k + k = 3 + 3 = 6
queue : 1, 2, 3, 4, 5, 6
good guy = 1, 2, 3
bad guy = 4, 5, 6
so, m = 5

output explanation : [k = 3, m = 5]
1, 2, 3, 4, 5, 6
1, 2, 3, 4, 5, 6
1, 2, 3, 4, 6
1, 2, 3, 4, 6
1, 2, 3, 6
1, 2, 3, 6

1, 2, 3

Critical input:
1
2
5
6
7
12
13

Critical output:
2
7
169
441
1872
1358657
2504881

One thought on “ACM (UVa) : 305

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