Bessie와 Farmer John은 Mootreepolis를 여행하다 헤어지고 그녀가 길을 잃었습니다. 수색대를 조직했지만 유일한 단서는 도시 어디서나 들리는 울음 방향입니다.
이름처럼 교통은 트리입니다. $N$개 장소($1 \le N \le 100,000$), 번호 $0$..$N$-$1$, $N$-$1$개 양방향 길로 연결되며 두 장소 사이 경로는 유일합니다. $N$개 중 하나에 있습니다.
$N$개 장소마다 수색대원 한 명이 있습니다. 전화해 울음 방향, 즉 Bessie 쪽 길이나 그 장소에서 발견했는지 물을 수 있습니다.
전화요금이 비싸 최소 통화를 원합니다. 물을 장소를 정하고 특히 $20$회 이내에 위치를 보고하게 하세요.
참고: $50\%$ 입력에서 $N$은 최대 $1000$입니다.
먼저 표준 입력으로 지도를 읽고 표준 입출력으로 채점기와 상호작용합니다. 초기 각 줄은 장소의 길 목록이며 인덱스는 영부터, 이후 상호작용에 중요합니다.
첫 줄 $N$, 이후 장소 $0$부터 이웃을 설명합니다. 첫 정수 $K$($1 \le K \le N$)는 이웃 수, 이후 $K$개 정수 $N_{0}$, $N_{1}$, …, $N_{K-1}$는 이웃의 영 기반 번호입니다. 길로 연결되면 이웃입니다.
장소를 차례로 표준 출력합니다. 각 응답은 초기 해당 줄 목록에서 Bessie 방향 길의 인덱스입니다. 표준 입력으로 읽으세요.
그녀의 장소를 출력하면 자동 종료됩니다. QOJ는 발견 시 응답 스트림을 닫습니다. 응답을 읽다 입력 끝에 도달하면 정상 종료하세요.
채점기는 적응적으로 응답하지만 모든 응답은 적어도 한 가능한 위치와 일치합니다.
발견하면 영이 아닌 점수라고 안내합니다. 현재 포함 $20$회 이하이면 $10$, $30$회 이상이면 $0$, 나머지는 $30$에서 질문 수를 뺍니다.
아래 지도 노드 $5$에 있다고 가정하며 입력 설명은 오른쪽입니다.
Node Count Neighbors
0 1 0 1 3
| | 1 1 4
2--3---4--5(B) 2 1 3
| | 3 4 0 2 6 4
6 7 4 4 3 7 1 5
5 1 4
6 1 3
7 1 4표의 query는 표준 출력, response는 표준 입력, location은 응답이 가리키는 장소입니다. details는 전체 순서 있는 이웃 목록이고 <>로 응답 해석을 표시합니다.
Query Response Location Neighbor list details 2 0 3 <3> 6 0 3 <3> 3 3 4 0 2 6 <4> 4 3 5 3 7 1 <5> 5 Done; program will be terminated
$2$, $6$에서 가장 가깝고 유일한 이웃은 $3$입니다. $3$에서는 $4$, $4$에서는 $5$입니다. 실제 $5$에 있어 $5$ 출력 후 종료합니다.
상호작용 프로그램
프로그램 버퍼에 남지 않도록 출력을 비우세요.
C/C++에서 stdio.h 사용 시 다음을:
setbuf(stdout, 0);
프로그램 앞부분에 넣으세요.
C++ iostream은 매 출력 줄을 이렇게 비우세요.
cout << line << "\n" << flush;
Pascal은 매 writeln 후 다음을:
flush(stdout);
Java는 매 출력 후 다음을:
System.out.flush();
응답 후 시간 초과면 제대로 비우지 않았을 수 있습니다.
Java 사용자
필요한 입출력 틀은 (아마) 다음입니다.
import java.io.*; import java.util.*;
public class cowtree {
public static void main(String[] args) throws IOException {
BufferedReader in = new BufferedReader(new
InputStreamReader(System.in));
/* write ... */
System.out.println(...);
System.out.flush(); /* read a reply */
response = in.readLine();
...Node: 노드
Count: 수
Neighbors: 이웃
Query: 질문
Response: 응답
Location: 장소
Neighbor list details: 이웃 목록 상세
Done; program will be terminated: 완료, 프로그램 종료
write ...: 쓰기
read a reply: 응답 읽기
입력
$1$번 줄: 정수 $N$.
$2..N+1$번 줄: $i+2$번 줄에 장소 $i$의 이웃을 공백 구분 정수 $K$, $N_{0}$, …, $N_{K-1}$로 설명합니다.
출력
- 출력 파일 줄은 없습니다. 파일 대신 표준 출력에 쓰세요.
예제
입력 1
8 1 3 1 4 1 3 4 0 2 6 4 4 3 7 1 5 1 4 1 3 1 4
출력 1
문제 출제자: MIT, 2010