아직 만들고 있는 페이지입니다.

이 페이지는 아직 만드는 중입니다. 보이는 내용은 바뀔 수 있습니다.

Surround the Cat

시간 제한1초메모리 제한512 MB

요약
한 변이 10인 육각형 집에서 매초 돌 하나를 놓고 고양이는 인접한 빈 칸으로 이동한다. 고양이가 경계에 도달하기 전에 가두어야 한다.
난이도

보통10점 중 7점

유형
그래프, 게임 이론, 시뮬레이션, 그리디
정답자
아직 제출이 없습니다

문제

This is an interactive problem.

Consider a hexagonal tiling on the plane, as shown in the picture below.

Fig. 1: What the plane looks like.

The house you built for your cat is a regular hexagon of side N=10N = 10. Its six corners are located at (9,0)(9,0), (9,9)(9,9), (0,9)(0,9), (−9,0)(-9,0), (−9,−9)(-9,-9), and (0,−9)(0,-9).

For example, for N=3N = 3 the house would look like this:

Now the cat wants to escape. Thus, you need to place some rocks in the house to surround the cat so that it can not escape.

Initially, the cat is located at (0,0)(0, 0). Every second, you can choose a location in the house and place a rock. Note that you cannot place a rock at the cat's current location. After that, the cat will choose a location that is adjacent to its current location and does not contain a rock, and move there.

Once the cat reaches the boundary of the house, it will escape and win. On the other hand, if the cat cannot choose a valid move, you win. Try to surround the cat so that it will not escape.

예제1

  1. 예제 1

    입력
    0 0
    
    1 0
    
    0 0
    
    1 0
    
    0 0
    
    1 0
    
    0 0
    
    
    예상 출력
    
    1 1
    
    0 1
    
    -1 0
    
    -1 -1
    
    0 -1
    
    9 9 
    
    1 0