Powerful StrongholdsProblem code: SNCK02 |
All submissions for this problem are available.
[Problem Idea : Varun Jalan and Yu Yiu Ho]
In a small world not so far away, there is an ongoing war between two nations, A and B. There are n (3 n 20) strongholds in this world, with roads between some of them. Two strongholds are neighbors if there is a road between them, all roads are bidirectional. The Chef is at war and he recently came up with a scheme that will help his country to never lose the war. He would like to select a set of powerful strongholds (defined below) of minimum size and conquer those strongholds to ensure that his country will never be defeated. A set of powerful strongholds is a set of strongholds S, such that
1.For every stronghold y which does not belong to S, there is a road leading to it from a stronghold x which belongs to S. This way, any stronghold not in S is threatened by a stronghold in S.
2.S can properly defend (defined next) any attack from strongholds outside of S.
The mechanism for attacking and defending S is defined as follows:
i.In an attack, each single stronghold y not belonging to S will select one of its neighbor z belonging to S (if any) to attack. In this case y is an attacker of z.
ii.Given the attack routes of all y not belonging to S, each stronghold x belonging to S may decide to defend one of its neighbors, say z, in which case x is a defender of z. Alternatively, x may decide to defend itself, in which case x is a defender of x.
iii.The attack can be properly defended if there exists a defend route such that at every stronghold z belonging to S, there are at least as many defenders of z as attackers of z.
The rationale is that once the Chef occupies the strongholds in S, any other stronghold is immediately within reach of S by a single road (rule 1), and S will never be overwhelmed by attacks from outside (rule 2), and thus the Chef will never lose a stronghold in S. In order to make the task of occupying S easier, it is best if S is as small as possible. The Chef has given you the task to identify the smallest set of powerful strongholds so that he can proceed with his plan.
Input:
There will be multiple test cases. Each test case is a specification of the strongholds and roads. For each test case, there will be one line containing n (3 <= n <= 20), the number of strongholds, and r (0 <= r <= 190), the number of roads. Then, the next r lines each contains two integers x and y giving a road between stronghold x and y. The strongholds are numbered from 0 to n-1. There is a blank line following each test case. The last test case is followed by a line containing two zeros (after the blank line).
Output:
For each test case, output a single line of integers. The first integer is |S|, represents size of the smallest possible set of powerful strongholds. The next |S| integers give one such possible set of strongholds. If there are multiple possible answers for S, output the lexicographically smallest one.
Sample Input:
3 2 0 1 1 2 6 6 0 1 1 2 2 3 3 4 4 5 5 0 5 10 0 1 0 2 0 3 0 4 1 2 1 3 1 4 2 3 2 4 3 4 0 0
Sample Output:
2 0 1 4 0 1 2 3 3 0 1 2
| Date: | 2009-11-13 |
| Time limit: | 5s |
| Source limit: | 50000 |
| Languages: | C C99 strict C++ 4.0.0-8 C++ 4.3.2 PAS gpc PAS fpc JAVA NICE JAR C# C#2 NEM ST ASM D FORT ADA BASH PERL PYTH RUBY LUA ICON PIKE PHP SCM guile SCM qobi LISP sbcl LISP clisp SCALA HASK ERL CAML CLPS PRLG WSPC BF ICK JS |
Comments

Fetching successful submissions

if a stronghold can only
if a stronghold can only attack its neighbour how come the ans for 2nd test case is 4,
consider case where only 0,1 is chosen, then only 5,2 can attack and hence can be defended.. what am i missing?
Can there be simultaneous
Can there be simultaneous attacks? If so, can a specific stronghold support the defence of both attacks at the same time?
Fuck all those
Fuck all those strongholds!
Believe me.....reconsider my suggestions assholes!!!!!!!!
Theres no difference in your brains and your assholes.
@sanity_eclipse : You are
@ Kushagra Udai :The answer
@ Kushagra Udai :
The answer is yes: every vertex not in S can attack a vertex in S, which in some sense vertices in S are being attacked simultaneously. This also means some vertex in S may be attacked by multiple enemy strongholds. But, any vertex noy in S can only attack one vertex of S
How many tests are there in
So what was the solution?
So what was the solution?