#!/usr/bin/env python3 # 28-Z4-6: Klučičí drby # Autor: Jenda Hadrava # Formát vstupu: # Na jediném řádku se nachází N čísel oddělených mezerami. K-té číslo nám říká, # kolikátému klukovi předává drby K-tý kluk. Číslujeme od 0. # Formát výstupu: # Na výstupu je N čísel oddělených mezerami. K-té číslo udává společenský dopad # kluka K. (Tedy počet kluků, kteří se dozvědí jím vymyšlený drb.) # Příklad vstupu: # 3 2 0 2 # Příklad výstupu: # 3 4 3 3 # Obrázek k příkladu: # # 1 -> 2 -> 0 -> 3 # ^ | # +---------+ nejlepsi_kamarad = list(map(int, input().split())) N = len(nejlepsi_kamarad) spolecensky_dopad = [0] * N navstiveni = [0] * N for drb in range(N): # Spočítáme šíření každého drbu kluk = drb K = 0 # Počítadlo kroků while navstiveni[kluk] == 0: # Všimněte si, že pole navstiveni nikdy nenulujeme. Díky tomu podmínka # výše jednak detekuje cyklus a jednak pozná to, že jsme narazili na # někoho, jehož společenský dopad již známe. navstiveni[kluk] = 1 K += 1 # Pokračujeme k nejlepšímu kamarádovi kluk = nejlepsi_kamarad[kluk] # Pokud jsme se zastavili na klukovi, jehož společenský dopad už známe, # přiceteme jej k počítadlu. Jinak jsme našli cyklus. V tom případě zde # přičítáme 0. K += spolecensky_dopad[kluk] # Zapamatujeme si, na kterém klukovi jsme se zastavili zacatek_cyklu = kluk # Vrátíme se na začátek a projdeme vše znovu kluk = drb while spolecensky_dopad[kluk] == 0: spolecensky_dopad[kluk] = K if kluk == zacatek_cyklu: # Pokud jsme narazili na začátek cyklu, nechceme již K snižovat. # Abychom K nesnížili ani příště, značku začátku cyklu si budeme # posouvat. zacatek_cyklu = nejlepsi_kamarad[zacatek_cyklu] else: K -= 1 kluk = nejlepsi_kamarad[kluk] print(*spolecensky_dopad)