Birokrati

Osnovne informacije

Omejitve
  • Čas: 2 s
  • Spomin: 512 MB
Avtor:
  • Jure Slak
  • UPM 2018

Pošlji rešitev



Tvoji rezultati.
Nisi poslal še nobene rešitve.
Več »

Ministrstvo za notranje zadeve po šivih poka od birokratov in eden med njimi je naredil napako. Ugotoviti želite, kdo je ta birokrat, čigar sliko boste pripeli na svoj pikado. Vsak birokrat ima enolično identifikacijsko označbo oblike npr. /mnz/a/ssrs/janez, ki pomeni, da dela na oddelku mnz, pododdelku a, podpododdelku ssrs in da mu je ime janez. Poleg tega se lahko na vsakega birokrata skličemo tudi z identifikacijsko številko (ki je še manj humana od identifikacijske označbe) npr. 1.3.4.2, ki pomeni, da je drugi birokrat, ki dela na prvem oddelku, tretjem pododdelku in četrtem podpododdelku. Vsi oddelki in birokrati so oštevilčeni po abecedi, pri čemer na vsakem nivoju ločeno številčimo oddelke in birokrate. Zagotovljeno je, da so imena oddelkov na nekem nivoju enolična, enako pa velja tudi za birokrate. Birokrati in oddelki se lahko imenujejo enako, prav tako pa tudi oddelki (ali birokrati) iz različnih nivojev. Oglejmo si spisek birokratov:

/mnz/borut/jozica
/mnz/a/vinko
/mnz/borut
/mob/lojze
/mnz/a/francelj
/mnz/a/xxx/umm/polde

Imamo dva oddelka: /mnz in /mob, po abecedi oštevilčena z 1 in 2. Znotraj /mnz imamo pododdelka a in borut. (Naj vas ne zmede, da ima /mnz tudi birokrata pa imenu borut.) Znotraj oddelka a imamo še pododdelek xxx in znotraj tega še umm. Identifikacijske številke birokratov so (v enakem vrstnem redu kot zgoraj) enake

1.2.1
1.1.2
1.1
2.1
1.1.1
1.1.1.1.1

Postopek ugotavljanja krivde začnete pri receptorju, tj. pri birokratu s čim krajšo identifikacijsko številko oblike 1.1.1.\cdots.1. V zgornjem primeru je to /mnz/borut. Razložite mu svoj problem, ta pa odvrne, da on seveda ni nič kriv, in vas pošlje k nekemu drugemu birokratu. Ta birokrat zopet zvali krivdo na nekoga drugega in postopek se ponavlja dokler se ne zgodi eno izmed dvojega:

  • birokrat vas napoti k birokratu, ki sploh ne obstaja,
  • ali pa vam poda identifikacijsko številko birokrata, ki ste ga že obiskali.

Ne glede na to, kaj izmed zgornjega se zgodi, je evidentno, da je ta birokrat tako nesposoben, da niti krivde ne zna prav preložiti, in mora gotovo biti kriv.

Vhodni podatki

Na vhodu je seznam vseh birokratov, zaposlenih na ministrstvu, zraven vsakega pa piše tudi, katerega birokrata bo obtožil.

Natančneje, vsaka vrstica je sestavljena iz dveh nizov, ločenih s presledkom, pri čemer je prvi niz označba nekega birokrata, drug niz pa (potencialno neveljavna) številka birokrata, na katerega bo prvi prevalil krivdo. Prvi znak označbe je poševnica, preostanek pa je sestavljen iz nepraznih nizov, ki vsebujejo male črke angleške abecede in so ločeni s poševnicami. Številka birokrata je sestavljena iz pozitivnih celih števil, ki so ločena s pikami.

Omejitve vhodnih podatkov

  • Število vrstic ni večje od 1000.
  • Dolžina vsake vrstice je kvečjemu 256 znakov.
  • Imena ljudi, ki so direktni sodelavci (imajo enake oddelke, pododdelke itd.), so enolična.
  • Imena oddelkov na istem nivoju so enolična.
  • Neveljavne številke birokratov so sestavljene iz pozitivnih celih števil manjših od 10^9.

Izhodni podatki

Izpišite identifikacijsko označbo birokrata, ki ga boste krivili za napako.

Primeri

Vhod

/cene 1.1
/mnz/darko 3
/gregor 4
/erika 1.2

Izhod

/gregor

Vhod

/cene 1.1
/mnz/darko 2
/gregor 4
/erika 1.1

Izhod

/erika

Komentar

V prvem primeru je receptor Cene. Ta okrivi Darka, ki okrivi Gregorja. Gregor okrivi neobstoječega birokrata, zato ga določite za krivega.

Drugi primer je podoben, le da Darko obtoži Eriko, ta pa obtoži zopet Darka, ki ste ga že obiskali, in zato okrivite Eriko.

Tip: Log in to
  • submit and test your solution
  • post or read questions and answers about this task