루미 알고리즘

#1359플래티넘The Coloring Game

PO 2015 훈련 캠프코딩출제 Johan Sannemo영어 원문이 문제가 어렵다면 — 배우는 순서 보기

영어 원문입니다. 원문의 수식·표를 글자로 옮겨 모양이 다를 수 있습니다. 정확한 내용은 원문 페이지에서 확인하세요. 원문 페이지 열기 (새 창)

Problem

Slugas Fulacek has challenged Oskar to a coloring game played on a paper with lots of circle on it. Some pairs of circles are connected by line segments, and are called friends.

The players take turns coloring a circle that has not yet been colored. The player who moves first (Slugas, of course) uses red color, while the second player uses blue color. When a player colors a circle none of the circle's friends may have the same color as the circle. If a player can't make a move (either because all circles are colored, or all circles left have a friend of that color), they lose.

Slugas is very intelligent, and have so far won all games he challenged Oskar to (like Clue, Battleship and guessing the next bit from a random number generator). Oskar has therefore asked for your help in playing the coloring game against Slugas.

There are two kinds of coloring games, in which the circles on the paper are laid out either:

  1. in a circle where the N circles are numbered from 1, …, N and the pairs (1, 2), (2, 3), …, (N-1, N) and (N, 1) are friends.
  2. in a line where the N circles are numbered from 1, …, N and the pairs (1, 2), (2, 3), …, (N-1, N) are friends.

Input

The input consists of only two integers: N ≥ 1 (the number of circles) and M which is either 1 or 2. 1 means that the circles are laid out in a circle, while 2 means they are in a line. Only inputs where Oskar can win with optimal play from both players are given.

Interactivity

This is an interactive problem. After reading N and M, Slugas makes his first move. You should now read the number of the circle he colored. Afterwards, you should output one line with the number of the circle you want to color.

If Slugas is unable to make a move, he will output -1. You have then won, and your program should terminate.

If you output an invalid move or no move at all even if the game is not yet over you lose.

Remember to flush the output stream after each move. In C++ this is done with cout << endl; or cout << flush;, and in C with fflush(stdout);.

Scoring

Your solution will be tested on several groups of test cases. To get points for a group you need to pass all the tests of that group.

GroupPointsConstraints
123M=1, 1 ≤ N ≤ 13
226M=1, 1 ≤ N ≤ 1000
324M=2, 1 ≤ N ≤ 13
427M=2, 1 ≤ N ≤ 1000

출처 표기

출처: Programmeringsolympiaden 2015년 훈련 캠프 · 원문 페이지 · 이용 조건 CC BY-SA · LaTeX 원문을 화면용 글로 옮겼습니다(수식·표의 모양이 다를 수 있습니다). 내용은 고치지 않았습니다.

크리에이티브 커먼즈 저작자표시-동일조건변경허락.

문제 출처: 한국정보올림피아드(KOI) (CC BY-NC-SA 4.0) · International Olympiad in Informatics (IOI) (CC BY) · Centre for Education in Mathematics and Computing (CEMC), University of Waterloo (CC BY-NC 4.0) · Programmeringsolympiaden (CC BY-SA) · CSES Problem Set (Antti Laaksonen) (CC BY-NC-SA 4.0). 루미 알고리즘은 위 단체들과 관계없는 별도의 서비스이며, 자료는 원문 그대로 싣습니다. 문제마다 출처와 이용 조건을 따로 표기합니다.