34597번 - Lasagna 다국어

Ovih se dana moglo naići na clickbait naslov “Znamo o čemu je Baby Lasagna razmišljao dok je čekao rezultate glasanja”. Kako nismo kliknuli na naslov, ne znamo što je odgovor. Možda je razmišljao o tome da naziv tradicionalnog talijanskog jela lazanje potječe od grčke riječi laganon, koja označava plosnatu “ploču” od tijesta izrezanu na trake? A možda je samo smišljao rješenje sljedećeg zadatka.

U zamišljenom svemiru postoji $N$ planeta označenih prirodnim brojevima od $1$ do $N$. U nultoj sekundi je na svakom planetu po jedan čovjek, označen istom oznakom. U svakoj od sljedećih $M$ sekundi će se ljudi s trenutnih teleportirati¹ na odredišne planete. Na svakom planetu je po jedan stroj za teleportiranje i prema svakom planetu je moguća teleportacija iz točno jednog planeta.

Tvoj je zadatak odrediti koliko će u sljedećih $M$ sekundi najviše ljudi istovremeno biti na svojim izvornim planetima.

¹ Teleportacija – trenutni prijenos materije s jednog na drugo mjesto uz primjenu tehnologije

U prvom retku su prirodni brojevi $N$ i $M$ ($1 ≤ N, M ≤ 1\, 000\, 000$), brojevi iz teksta zadatka.

U drugom retku je $N$ različitih prirodnih brojeva koji redom predstavljaju oznake odredišnih planeta za teleportacijske strojeve na svakom od $N$ planeta.

Ispiši traženi broj.

Opis prvog probnog primjera: Tablica za svaku sekundu i svakog čovjeka opisuje na kojem se planetu u određenoj sekundi nalazio određeni čovjek.

U prvih pet sekundi ih je najviše na svojem izvornom planetu bilo troje, i to u trećoj sekundi.

Opis drugog probnog primjera: Već u drugoj sekundi je svih petero ljudi bilo na svom izvornom planetu.