No.625
1人しか残っていなければ総取りできる.
2人残っている場合は最初の人は必ず反対されるので2番目の人の総取りである.
3人残っている場合は1番目の人を引退させてしまうと次に自分も引退させられるので, 必ず賛成する. よって1番目の人の総取りである.
\(i\) 人残っているときの \(j\) 番目の人の配るプレゼント数が決まったとする.
このとき, \(i+1\) 人残っている状態で先頭のサンタクロースは \(i\) 人残っているときの数よりひとつ多いプレゼントを割り当ててあげればそのサンタクロースは賛成してくれる. この賛成を半数確保できるように, \(i\) に残っているときの数が少ない順に割り当てる. 割り当てられないなら引退である. 割り当てないサンタクロースにはプレゼントは0個をアサインすればいい.