Concursuri de programare

Competiția echipei de programare regională DEIK, categoria Universitate/Colegiu, 30 noiembrie 2014.

Abia te pregătești pentru o competiție de programare cu colegii tăi de echipă, Alice și Bob. După câteva ore de antrenament greu, vrei să faci o pauză și să mănânci pizza. Decizi să comanzi o pizza mare pentru toți trei. Dar trebuie să alegeți ce fel de pizza ar trebui să fie.

Ai tipul tău preferat de pizza, dar Alice și Bob au considerații diferite: Alice este la dietă, așa că vrea o pizza cu cât mai puține calorii. Și Bob votează pentru cât mai multe calorii posibil din răul pur.

Decizi să votezi pentru a alege ce pizza ai comandat. Întrucât nu ar duce nicăieri ca toată lumea să voteze o pizza, recurgeți la un vot de excludere, adică fiecare dintre voi exclude o pizza într-un sistem circular. Mai întâi Alice blochează o pizza, apoi Bob, în cele din urmă puteți bloca una. Apoi este din nou rândul lui Alice, apoi Bobon etc., până când mai rămâne o singură pizza.

Ca reamintire, Alice exclude întotdeauna pizza cu cele mai multe calorii, Bob cea mai mică cu calorii și încercați să aveți sens pentru a vă menține ultima preferată.

Specificații de intrare

Introducerea începe cu n, numărul de pizza și p, numărul de serie al pizza preferată (1 ≤ n ≤ 100.000, 1 ≤ p ≤ n, numerotarea începe de la 1). Aceasta este urmată de o descriere a n pizza, fiecare pe o linie separată. Fiecare descriere constă dintr-un număr întreg c și un cuvânt w (0 ≤ c ≤ 1.000.000), unde c este valoarea calorică și w este numele pizza (până la 100 de caractere). Pizza este sortată în ordine crescătoare a valorii calorice, iar valorile calorice sunt unice pentru fiecare pizza.

Specificații de ieșire

Ar trebui să scrieți o singură linie la ieșire cu cuvântul „DA” dacă puteți vota pentru a selecta pizza preferată sau cu cuvântul „NU” dacă nu.