루미 알고리즘

#1300실버Släktträffen

PO 2010 학교 예선코딩스웨덴어 원문이 문제가 어렵다면 — 배우는 순서 보기

스웨덴어 원문입니다. 원문의 수식·표를 글자로 옮겨 모양이 다를 수 있습니다. 정확한 내용은 원문 페이지에서 확인하세요. 원문 페이지 열기 (새 창)

Problem

(그림은 원문 저장소에서 볼 수 있습니다)

Figur 1: Släktträden för de två körningsexemplen.

Det är släktträff för ättlingar till Ida-Ottilia Isaksson. För enkelhets skull har man upprättat ett släktträd och numrerat alla ättlingarna från 1 till N, samt givit Ida-Ottilia själv numret 0. Bland de M personerna vid ditt bord uppkommer en diskussion om vem som är er närmaste gemensamma släkting (uppåt i trädet). Skriv ett program som räknar ut detta.

Programmet ska fråga efter antalet ättlingar, N, och därefter fråga efter numret på varje persons förälder, vilket naturligtvis alltid är mellan 0 och N. Därefter ska programmet fråga efter antalet personer vid bordet, M (2 ≤ M ≤ N), och läsa in numret på var och en av dem. Programmet ska skriva ut numret på den person som är närmast gemensam släkting (uppåt i trädet) till alla vid bordet. Observera att detta ibland kan vara någon vid bordet.

Indata

På första raden i indata står talen N och M (2 ≤ M ≤ N ≤ 20). På andra raden står N tal, föräldrarna för varje ättling (alla mellan 0 och N). På tredje raden står M tal, personerna runt bordet (alla mellan 1 och N, utan dubbletter).

Utdata

Programmet ska skriva ut ett enda tal: numret på personernas närmaste gemensamma släkting.

예제

예제 1

입력
8 3
6 0 0 2 0 5 6 5
1 5 8
출력
5

예제 2

입력
4 2
2 0 0 3
4 1
출력
0

출처 표기

출처: Programmeringsolympiaden 2010년 학교 예선 · 원문 페이지 · 이용 조건 CC BY-SA · LaTeX 원문을 화면용 글로 옮겼습니다(수식·표의 모양이 다를 수 있습니다). 내용은 고치지 않았습니다.

크리에이티브 커먼즈 저작자표시-동일조건변경허락.

문제 출처: 한국정보올림피아드(KOI) (CC BY-NC-SA 4.0) · International Olympiad in Informatics (IOI) (CC BY) · Centre for Education in Mathematics and Computing (CEMC), University of Waterloo (CC BY-NC 4.0) · Programmeringsolympiaden (CC BY-SA) · CSES Problem Set (Antti Laaksonen) (CC BY-NC-SA 4.0). 루미 알고리즘은 위 단체들과 관계없는 별도의 서비스이며, 자료는 원문 그대로 싣습니다. 문제마다 출처와 이용 조건을 따로 표기합니다.