사이클의 크기

번부터 번까지 개의 정점으로 이루어진 그래프가 있다. 여기서, 은 을 만족하는 소수이다.

각 에 대해, 번 정점과 번 정점은 간선으로 직접 연결되어 있다. 또한, 번 정점과 번 정점도 간선으로 직접 연결되어 있다. 즉, 그래프는 길이가 인 사이클이다.

편의상, 번 정점의 왼쪽과 오른쪽 정점을 각각 번, 번 정점이라고 하자. 번 정점에서 왼쪽과 오른쪽으로 칸 점프한다면, 각각 번과 번 정점으로 이동하게 될 것이다.

(참고사항) 정수 에 대해 은 (는 정수, 은 이상 이하의 정수)로 나타냈을 때의 의 값이다. 예를 들어 , 이다.

각 정점은 흰색 혹은 검은색의 색을 가질 수 있다. 처음에 모든 정점은 흰색이다.

어떤 정점 위에 로봇이 놓여 있다.

이제, 여러분은 아래와 같은 형식의 코드를 최대 번 실행할 수 있다. 코드를 실행하기 위해서 여러분은 코드에서 ( A | B | C )와 같이 괄호 안에 |로 구분된 곳에 주어진 선지 중 하나를 택하여 코드를 완성해야 한다. 매 실행마다 다른 코드를 완성해도 되며, 여러분은 해당 실행에서 로봇이 몇 번 점프했는지를 즉시 알 수 있다. 단, 모든 실행에 걸쳐 로봇이 점프한 횟수의 총합이 을 초과해서는 안된다.

무한 반복 {
  로봇이 ( 왼쪽 | 오른쪽 )으로 ( 1 | 10 | 100 | 1,000 )칸 점프;

  현재 정점의 색을 ( 검은색으로 변경 | 흰색으로 변경 | 변경하지 않음 );

  현재 정점의 원래 색이 ( 흰색 | 검은색 )이라면 {
    반복 중지;
  }
}

"현재 정점"은 로봇이 현재 놓여 있는 정점을 의미하고, "현재 정점의 원래 색"은 로봇이 현재 정점으로 점프한 직후 해당 정점의 색을 의미한다.

의 값을 알아내라.

아래에서 '명령어 실행' 버튼을 누르면 코드가 실행된다. 의 값을 알아냈다면, '정답 입력' 버튼을 눌러서 의 값을 입력하면 된다. 정답을 입력한 이후 "제출" 버튼을 눌러야 한다.

처음부터 다시 시작하고 싶다면, '초기화' 버튼을 누르면 된다. 예를 들어, 로봇이 점프한 횟수의 총합이 을 초과하는 경우, 더 이상 진행할 수 없으므로 초기화 버튼을 눌러 처음부터 다시 시작해야 한다.

문제 형식

인터랙티브

출처

• KOI 2024 1차대회 고등부 1교시 20번