Courses

動的プログラミング

動的グラフプログラミング

Module: 動的グラフプログラミング

Problem

1 /7

官僚

Theory Click to read/hide

Error

Problem

ミルコは大企業のCEOになった。会社には 1 から N までの番号が付けられた N 人が雇用されており、ミルコ自身も 1 番を持っています。ミルコを除くすべての従業員には上司がいます。上司は複数の部下を持つことができますが、複数の上司を持つことは
できません。
ミルコは投資家から仕事を受け取ると、一番番号の低い部下にそれを渡す。その部下はさらに番号の若い部下にも仕事を引き継ぎ、最後には部下のいない不運な社員に仕事が引き継がれて
いきます。その従業員は 1 コインを取得し、その上司は 2 コインを取得し、その上司の上司は 3 コインを取得します。そして実際にその仕事をしていた人は、この資本主義システムがいかに不公平であるかに気づき、その仕事を
辞めてしまいます。
ミルコは、会社に残る従業員が 1 名になるまで割り当てを受け取ります。ミルコ自身。その後、彼はこのタスクを完了し、コインを 1 枚受け取り、会社を辞めます。

彼は、各元従業員が合計で何枚のコインを受け取ったのか疑問に思いました。これを手伝って
ください。
入力:
最初の行には 1 つの自然数 N (1 <N<2·10⁵) — が含まれています。会社の従業員の数。次の行には、N-1 個の数値 a₂、a₃、... a_n (1 ≤ a i i — i 番目の従業員の責任者の番号
です。
出力:
N 個の数字を出力します。i 番目の数字は、i 番目の従業員が受け取ったコインの数を示す必要があります。

例:
<本体>
説明:

以下に 2 番目の例について説明します。

ミルコは最初のタスクをワーカー 2 に与え、ワーカー 3 がそれをワーカー 3 に渡し、ワーカー 3 がタスクを完了します。したがって、ワーカー 3 は 1 枚のコインを受け取り、ワーカー 2 はコインを受け取ります。コイン 2 枚と労働者 1、ミルコ自身 -コイン3枚。その後社員３が辞め
ました。ミルコは 2 番目のタスクをワーカー 2 に渡し、ワーカー 4 はそれをワーカー 4 に渡し、ワーカー 5 はすぐにタスクをワーカー 5 に渡し、ワーカー 5 がタスクを完了します。その後、ワーカー 5 はコインを 1 枚受け取り、ワーカー 4 はコインを受け取ります。コイン 2 枚、労働者 2 - 3 つのコインとミルコ -コイン4枚。社員5が辞め
ました。 3 番目のタスクを完了すると、ワーカー 4 は 1 枚のコインを受け取り、ワーカー 2 はコインを受け取ります。コイン2枚、そしてミルコ—コインが 3 つあり、その後従業員 4 が辞めました。
4 番目のタスクを完了すると、ワーカー 2 は 1 コインを受け取り、ミルコはコインを受け取ります。コイン2枚、その後2人目の従業員が辞め
ました。最後に、5 番目のタスクはミルコ自身によって実行され、これで 1 コインを受け取り、その後プロセスは停止します。

合計で、ミルコは 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