Courses

동적 프로그래밍

동적 그래프 프로그래밍

Module: 동적 그래프 프로그래밍

Problem

1 /7

관료

Theory Click to read/hide

Error

Problem

Mirko는 대기업의 CEO가 되었습니다. 회사는 1에서 N까지 번호가 매겨진 N명의 직원을 고용하고 있으며 Mirko 자신이 1번입니다. Mirko를 제외한 모든 직원에게는 상사가 있습니다. 상사는 부하가 여러 명일 수 있지만 상사는 한 명을 초과할 수 없습니다.

미르코는 투자자로부터 과제를 받으면 가장 낮은 번호를 가진 부하 직원에게 넘긴다. 그 부하 직원은 또한 가장 낮은 번호의 부하 직원에게 작업을 전달하는 식으로 작업을 완료할 부하 직원이 없는 불운한 직원에게 작업이 전달될 때까지 계속됩니다.
그 일꾼은 1코인, 그의 상사는 2코인, 그 상사의 상사는 3코인을 받습니다. 그러면 실제로 그 일을 한 사람은 이 자본주의 체제가 얼마나 불공평한지 깨닫고 일을 그만둔다.

Mirko는 회사에 직원이 한 명만 남을 때까지 할당을 받습니다. — 미르코 자신. 그런 다음 그는 이 작업을 완료하고 코인 1개를 받고 회사를 떠납니다.

그는 전직 직원이 총 몇 개의 동전을 받았는지 궁금했습니다. 그를 도와주세요.

입력:
첫 번째 줄에는 하나의 자연수 N(1 ≤ N 5)이 포함됩니다. 회사 직원 수. 다음 줄에는 N-1개의 숫자 a₂, a₃, ... a_n (1 ≤ a_i <i), a_i — i번째 직원의 대표 번호.

출력:
N개의 숫자를 인쇄하십시오. i번째 숫자는 i번째 직원이 받은 동전의 수를 나타냅니다.

예:
<몸>
설명:

다음은 두 번째 예에 대한 설명입니다.

Mirko는 작업자 2에게 첫 번째 작업을 제공하고 작업을 완료한 작업자 3에게 전달합니다. 따라서 작업자 3은 동전 1개를 받고 작업자 2는 — 동전 2개, 작업자 1, Mirko 자신, — 세 개의 동전. 그 후 직원 3이 퇴사합니다.
Mirko는 두 번째 작업을 작업자 2에게 주고 작업자 4는 작업을 즉시 작업자 5에게 전달하여 작업을 완료합니다. 그 후 작업자 5는 동전 1개를 받고 작업자 4는 — 두 개의 동전, 작업자 2 — 동전 3개, Mirko — 네 개의 동전. 직원 5가 퇴사합니다.
세 번째 작업을 완료한 후 작업자 4는 동전 1개를 받고 작업자 2는 — 동전 2개, Mirko — 직원 4가 퇴사합니다.
네 번째 작업을 완료한 후 작업자 2는 동전 1개를 받고 Mirko — 두 번째 직원이 퇴사합니다.
마지막으로, 다섯 번째 작업은 Mirko가 직접 수행하며 이를 위해 코인 1개를 받은 후 프로세스가 중지됩니다.

전체적으로 Mirko는 13개의 코인, 직원 2명을 받았습니다. 동전 8개, 일꾼 4 – 동전 3개, 일꾼 3과 5 — 동전 하나.

time 1000 ms
memory 256 Mb
Rules for program design and list of errors in automatic problem checking