Dreissig

아직 제출이 없습니다시간 제한15초메모리 제한256 MB

문제

Two players are playing a game on the complete undirected graph with 100 vertices. Initially all its 100×992=4950\frac{100 \times 99}{2} = 4950 edges are uncolored. The players take turns in coloring the edges. The first player moves first, and at each move picks any 30 uncolored edges (or all uncolored edges if there are less than 30) and colors all of them black. The second player at each move picks any uncolored edge and colors it white. The game ends when all edges are colored.

The second player wins if they can point out a Hamiltonian cycle consisting only of white edges, otherwise the first player wins. A Hamiltonian cycle is a simple cycle that passes through each vertex exactly once.

In this problem you need to play this game as the second player. Moreover, you already know the strategy of the first player: they will pick 30 edges uniformly at random from all remaining edges. Can you win at least 95 out of 100 games as the second player?