KOI 2차 2020 초4- 사탕 돌리기 > 문제은행 : 정보올림피아드&알고리즘




4603 : 사탕 돌리기

제한시간
1000 ms   
메모리제한
256 MB   
해결횟수
0 회   
시도횟수
0 회   

문제

원기둥 형태의 뚜껑이 없는 깡통 N개가 원형으로 배열되어 있다. 각 깡통에는 시계 방향 순서대로 1번부터 N번 까지의 자연 수 번호가 붙어 있으며, 각 깡통에는 사탕이 K개씩 들어 있다. 따라서, 총 N × K개의 사탕이 있는 것이다.

 

모든 사탕은 1 이상 N 이하의 자연수로 표현되는 색깔을 가진다. 모든 색 c (1 ≤ c ≤ N)에 대해, 깡통에 들어 있는 총 N × K개의 사탕 중 색깔이 c인 사탕은 정확히 K개 있다. 각 깡통에 들어 있는 사탕의 색이 무엇인지는 입력으로 주어진다.

 

이때 사탕 돌리기라는 연산은 아래와 같이 사탕을 하나씩 옮기는 N개의 작업을, 아래에 주어진 순서대로 수행하는 것을 말한다.



  • 1번 깡통에서 임의로 사탕을 하나 꺼내 2번 깡통에 넣는다.
  • 2번 깡통에서 임의로 사탕을 하나 꺼내 3번 깡통에 넣는다.
  • 3번 깡통에서 임의로 사탕을 하나 꺼내 4번 깡통에 넣는다.
  • .......
  • (N − 1)번 깡통에서 임의로 사탕을 하나 꺼내 N번 깡통에 넣는다.
  • N번 깡통에서 임의로 사탕을 하나 꺼내 1번 깡통에 넣는다.


당신은 주어진 초기 상태에서 사탕 돌리기를 정확히 Q번 반복 수행할 것이다. 수행한 이후에 당신은 c의 색깔을 가지는 모든 사탕이 c번 깡통에 들어가도록 하고 싶다. 즉, 1번 깡통에는 1번 색깔의 사탕만이 존재하고, 2번 깡통에는 2번 색깔의 사탕만이 존재하고, ...., 마지막으로 N번 깡통에는 N번 색깔의 사탕만이 존재하도록 하고자 한다. 이러한 상태를 올바른 상태라고 하자.

 

입력으로 각 깡통에 들어 있는 사탕의 상황이 주어질 때, 초기 상태에서 사탕 돌리기를 정확히 Q번 반복 수행한 후 위에서 설명한 올바른 상태를 이룰 수 있는지 판단하는 프로그램을 작성하라.


 


제약 조건


  • 2 ≤ N ≤ 2,000
  • 1 ≤ K ≤ 2,000
  • 1 ≤ Q ≤ 1,000,000,000
  • 모든 색깔 c (1 ≤ c ≤ N)에 대해, 색깔이 c인 사탕은 정확히 K개 있다.

 

부분 문제


  1. (3점) Q = 1.
  2. (6점) N = 2.
  3. (28점) K = 1.
  4. (40점) N, K ≤ 100.
  5. (23점) 추가 제약 조건 없음.​

입력형식

첫 번째 줄에 N, K, Q가 공백 하나를 사이로 두고 주어진다.

이어지는 N개의 줄의 각 i (1 ≤ i ≤ N)번째 줄에는 1 이상 N 이하인 K개의 정수가 공백 하나씩을 사이로 두고 주어지며, 이는 초기 상태에서 i번 깡통에 들어 있는 K개의 사탕의 색깔 들을 의미한다.​ 


출력형식

입력으로 주어진 초기 상태에서 사탕 돌리기를 정확히 Q번 반복 수행하여 올바른 상태로 만들 수 있다면 숫자 1을, 아니면 숫자 0을 출력한다. 


입력 예

3 1 1
2
3
1

출력 예

1

입력 예

2 5 2
1 1 2 2 2
2 2 1 1 1

출력 예

0


경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호

TEL : 031-360-4144 FAX : 031-388-0996 E-mail : hancomc@hotmail.com, comkiwer@naver.com

Copyrightⓒ 2010 jungol. All right reserved.

TOP