5009번 - 유치원 다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 128 MB | 152 | 96 | 77 | 61.600% |
문제
홍은 유치원에 근무하는 선생님은 총 세 명이다. 새 학기가 시작될 때, 선생님은 학생들의 반을 나눠야 한다.
선생님은 학생들의 친구 관계를 반 배정에 포함시킨다. 모든 아이들은 자신이 좋아하는 순서대로 다른 아이의 이름을 적어서 선생님께 제출했다. 좋아하는 순서는 같은 반이 되길 원하는 순서와 같다.
반의 크기가 같지 않아도 상관없다. 유치원에는 매년 새 학생이 들어오기 때문에, 그 아이들로 반을 채우면 된다. 하지만, 선생님은 작년에 맡았던 학생을 절대로 다시 맡지 않을 것이다.
뛰어난 컴퓨터 프로그래머 출신인 김상근 선생님은 모든 학생을 작년과 다른 반에 배정하면서, 각 반에 있는 모든 학생이 그 반에 속하는 학생이 제출한 순서에서 모두 상위 T위 안에 드는 방법을 찾으려고 한다. 이때, T는 가능한 작아야 한다.
입력
첫째 줄에 학생의 수 n ≤ 200 이 주어진다. 아이들의 번호는 1번부터 n번이다.
다음 n개 줄에는 각 학생들의 정보가 주어진다. 첫 번째 숫자는 작년 선생님을 나타내며 0, 1, 2중 하나이다. 다음 n-1개 숫자는 {1, 2, ..., i-1, i+1, ..., n} 이며, 주어지는 순서대로 i번 학생이 좋아하는 순서이다.
출력
가장 작은 음이 아닌 정수 T를 출력한다. T는 다음 조건을 만족해야 한다.
- 작년과 같은 선생님의 반에 속하는 학생이 없어야 한다.
- 반에 속하는 모든 학생은 학생들이 좋아하는 순서에서 상위 T위 안에 있어야 한다.
예제 입력 1
6 0 2 3 4 5 6 0 1 3 4 5 6 1 6 5 4 2 1 2 6 5 3 2 1 1 1 2 3 4 6 2 1 2 3 4 5
예제 출력 1
4
예제 입력 2
3 0 2 3 1 1 3 2 1 2
예제 출력 2
0
출처
ICPC > Regionals > Europe > Northwestern European Regional Contest > Nordic Collegiate Programming Contest > NCPC 2012 K번
- 문제를 번역한 사람: baekjoon
© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호