Problem H
Röðun
Languages
en
is
Eitt af vinsælum verkefnum í tölvunarfræði er röðunarvandamálið. Gefinn er listi af raðanlegum hlutum t.d. tölum eða strengjum og markmiðið að raða þeim í annað hvort vaxandi eða minnkandi röð. Í þessu verkefni er ætlunin að raða lista af nöfnum keppenda eftir vaxandi fjölda dæma sem þau hafa leyst. Gefnar verða tvenndir af nöfnum keppenda og sagt hvor þeirra hafi leyst fleiri dæmi. Svo vill til að engir tveir keppendur hafa leyst sama fjölda dæma. Finnið röð keppendanna eða segið til ef ónægar upplýsingar eru gefnar.
Inntak
Fyrsta línan inniheldur heiltölur $n$ og $k$, þar sem $n$ er fjöldi keppenda og $k$ er fjöldi samanburða sem gefnir verða. Því næst er lína með $n$ nöfnum keppendana sem allir heita einu nafni og engir tveir keppendur heita sama nafni. Þar á eftir koma $k$ línur með samanburðunum, þ.e. lína með tveimur nöfnum keppenda og $<$ eða $>$ á milli nafnanna sem stendur fyrir hvor hefur leyst fleiri dæmi. Ed $>$ Bob þýðir að Ed hefur leyst fleiri dæmi en Bob, en Jim $<$ Cox þýðir að Jim hefur leyst færri dæmi en Cox. Sömu tveir keppendurnir eru ekki bornir saman oftar en einu sinni. Nöfn keppenda eru mesta lagi $8$ stafir á lengd.
Úttak
Nöfn keppendana í vaxandi röð eftir fjölda leystra dæma, aðgreind með bili, ef mögulegt er að ákvarða röðunina. Ef ekki er möguleg að ákvarða röðunina skal skrifa út veit ekki.
Stigagjöf
|
Hópur |
Stig |
Inntaks takmarkanir |
|
1 |
20 |
$0 < n \leq 400$, $k = \frac{n \cdot (n-1)}{2}$, allir samanburðir gefnir |
|
2 |
30 |
$0 < n \leq 100$, $0 \leq k < \frac{n \cdot (n-1)}{2}$ |
|
3 |
50 |
$100 < n \leq 100000$, $0 \leq k < \min \left(100001, \frac{n \cdot (n-1)}{2}\right)$ |
| Sample Input 1 | Sample Output 1 |
|---|---|
3 3 Arnar Benni Unnar Arnar > Benni Benni < Unnar Unnar < Arnar |
Benni Unnar Arnar |
| Sample Input 2 | Sample Output 2 |
|---|---|
6 5 Andrea Arna Freyja Hanna Sigga Unnur Freyja > Sigga Hanna < Sigga Arna > Unnur Andrea > Arna Andrea < Hanna |
Unnur Arna Andrea Hanna Sigga Freyja |
| Sample Input 3 | Sample Output 3 |
|---|---|
8 12 Bernhard Ernhardb Rnhardbe Nhardber Hardbern Ardbernh Rdbernha Dbernhar Bernhard > Ernhardb Ernhardb > Rnhardbe Rnhardbe > Nhardber Rnhardbe > Hardbern Rnhardbe > Ardbernh Rnhardbe > Rdbernha Rnhardbe > Dbernhar Nhardber > Ardbernh Hardbern > Ardbernh Ardbernh > Rdbernha Ardbernh > Dbernhar Dbernhar < Rdbernha |
veit ekki |
