5. naloga

Plonkanje

Zaradi pojava virusa so morali organizatorji nekega tekmovanja iz znanja izvesti le-to prek interneta, kjer pa tekmovalna komisija ni mogla nadzirati, če so si tekmovalci med seboj kaj pomagali („plonkali“).

Po natančni analizi vseh oddanih nalog več sto tekmovalcev je tekmovalni komisiji uspelo (seveda s pomočjo računalnika) natančno rekonstruirati, kdo je plonkal od koga.

Podatki o plonkanju so (zaradi varstva osebnih podatkov) anonimizirani in predstavljeni v tabeli z dvema stolpcema, kjer prva številka pomeni številko tekmovalca, ki je bil pomočnik, druga pa številko prepisovalca, torej tekmovalca, ki je prepisoval (plonkal). Tisti, ki je plonkal, je seveda lahko bil ob neki drugi priložnosti pomočnik in je pomagal novemu prepisovalcu in tako naprej. Pomočnik je lahko pomagal več prepisovalcem (v prvem stolpcu bodo lahko tudi enake številke), medtem ko je prepisovalec vedno lahko plonkal samo od enega pomočnika (v drugem stolpcu bodo same različne številke). Primer:


pomočnik prepisovalec
(plonkar)
15
 18
41 62
15 29
47 50
29 47
15 41
33 21
91 55
41 37
21
 12
12 72
12 33


Iz zgornje tabele ugotovimo na primer, da je tekmovalec 41 prepisoval od tekmovalca 15 in da je tekmovalec 41 pomagal tekmovalcu 62 in tekmovalcu 37. Tekmovalec 15 pa je pomagal tudi tekmovalcu 29 in tekmovalcu 18.

Opiši postopek, ki bo iz tako podanih podatkov ugotovil:

  1. kateri so bili tisti tekmovalci, ki niso plonkali od nikogar, ampak so bili izključno pomočniki — imenujmo jih izvirni tekmovalci;
  2. kateri so bili plonkarji prvega reda, torej tekmovalci, ki so plonkali od izvirnih tekmovalcev;
  3. kateri so bili plonkarji drugega reda, torej tekmovalci, ki so plonkali od nekoga, ki je sam plonkal od izvirnega tekmovalca.

V zgornjem primeru sta izvirna tekmovalca 15 in 91, plonkarji prvega reda so 18, 41, 29 in 55, plonkarji drugega reda pa so 37, 62 in 47.