DAPC21-091.Entering Enemy Encampment

Medium · 1 s · 256 MB

icpc
dapc
2021

A new two-player game simulates two countries fighting over a territory. This territory contains a number of strategic positions which are suitable for setting up war camps. The players take turns setting up a camp at one of these spots.

In this territory, there are also a number of trails that connect two positions each. Whenever a player sets up a new camp, this player will send a small group of soldiers over every adjacent trail that leads to an enemy encampment. Each of these groups of soldiers will raid the enemy camp. In other words, for every trail, the second player to capture one of the incident positions can launch at most one raid over this trail. When every strategic position has been claimed, the game ends. The player that performed the most raids wins the game.

Assuming both players play optimally, who wins?

Giriş formatı

The input consists of:

• One line containing two integers $n$ ( $1 \leq n \leq 20$ ), the number of strategic positions, and $m$ ( $0 \leq m \leq \frac{n(n-1)}{2}$ ), the number of trails.

• $m$ lines, each containing two integers $a$ and $b$ ( $1 \leq a, b \leq n$ , $a\neq b$ ), indicating that there is a trail between position $a$ and position $b$ .

There is at most one trail between every pair of strategic positions.

Çıxış formatı

If the player who goes first wins, output “player 1”. If the player who goes second wins, output “player 2”. If the players tie, output “tie”.

Qeyd

Source: Delft Algorithm Programming Contest 2021 · Author: Reinier Schmiermann · License: CC BY-SA 4.0 · Original: https://dapc.wisv.ch · Statement adapted for AlgoLens and shared under the same license.

Nümunələr

Giriş #1

Çıxış #1

tie

Giriş #2

2 1
1 2

Çıxış #2

player 2

Giriş #3

Çıxış #3

player 1

Giriş formatı

The input consists of:

• One line containing two integers $n$ ( $1 \leq n \leq 20$ ), the number of strategic positions, and $m$ ( $0 \leq m \leq \frac{n(n-1)}{2}$ ), the number of trails.

• $m$ lines, each containing two integers $a$ and $b$ ( $1 \leq a, b \leq n$ , $a\neq b$ ), indicating that there is a trail between position $a$ and position $b$ .

There is at most one trail between every pair of strategic positions.