Masala #0133
Olimpiada
O’zbekistonda m ta shahar bor (m = 2k) va m ta shaharda jami n ta o’quvchi bor. Har bir o’quvchining o’zini bilim darajasi bor. (i – o’quvchining bilim darajasi ai , ya’ni i – o’quvchi ai ta algoritm biladi). Ikkita o’quvchi o’zaro bellashishsa bilim darajasi yuqoriroq o’quvchi g’olib bo’ladi. (Barcha o’quvchilarning bilim darajalari har xil ekanligi kafolatlanadi).
O’quvchilar 2 ta olimpiadada qatnashishdi. (Beruniy va Al-Xorazmiy olimpiadasi)
Beruniy olimpiadasi tartibi quyidagicha (Futbol bo’yicha Jahon Chempionati tartibiga o’xshash):
Har bir shaharda alohida olimpiada o’tqaziladi. G’olib o’quvchi keyingi turga o’tadi (o’z shahridagi bilim darajasi eng yuqori bo’lgan o’quvchi). Keyingi turda 1-shaharlik o’quvchi 2-shaharlik o’quvchi bilan, 3-shaharlik o’quvchi 4-shaharlik o’quvchi bilan va hokazo bellashishadi. G’oliblar keyingi turga o’tib 1-juftlik g’olibi 2-juftlik g’olibi bilan va hokazo bellashishadi. Yakunda finalda yutgan o’quvchi 1-o’rin, yutqazgan 2-o’rin. Yarim finalda yutqazgan o’quvchilar 3-o’rin uchun bellashishadi. Yaxshiroq tushunish uchun izohga qarang.
Al-Xorazmiy olimpiadasi tartibi quyidagicha:
Barcha n ta o’quvchilar bir joyga to’planishadi va bilim darajasi eng yuqori bo’lgan o’quvchilarga mos ravishda 1, 2 va 3-o’rinlar beriladi.
Sizning vazifangiz ikkala olimpiadaning g’oliblarini aniqlash.
Birinchi qatorda m va n kiritiladi. (4 ≤ m ≤ 215, m ≤ n ≤ 2×105)
Ikkinchi qatorda n ta natural sondan iborat a massiv - o’quvchilarning bilim darajalari kiritiladi (1 ≤ a[i] ≤ 109)
Uchinchi qatorda ham n ta natural sondan iborat c massiv kiritiladi. (c[i] – i-o’quvchining qaysi shahardanligi, 1 ≤ c[i] ≤ m)
Har bir shaharda kamida bitta o’quvchi yashashi kafolatlanadi.
Birinchi qatorda 3ta natural son. 1-olimpiadaning g’oliblarini raqamlarini chiqaring. Avval 1 - o’rin egasining raqami, keyin 2, keyin 3-o’rinning raqamini chiqaring.
Ikkinchi qatorda ham xuddi shu tartibda 2-olimpiadaning g’oliblarini chiqaring.
| # | input.txt | output.txt |
|---|---|---|
| 1 |
8 14 16 8 29 12 15 20 5 32 42 85 22 53 11 21 6 7 3 4 4 5 1 8 1 2 4 7 5 3 |
10 12 3 10 12 9 |
1 – shaharlik o’quvchilar – {7, 9}
2 – shaharlik o’quvchilar – {10}
3 – shaharlik o’quvchilar – {3, 14}
4 – shaharlik o’quvchilar – {4, 5, 11}
5 – shaharlik o’quvchilar – {6, 13}
6 – shaharlik o’quvchilar – {1}
7 – shaharlik o’quvchilar – {2, 12}
8 – shaharlik o’quvchilar – {8}
Avval Beruniy olimpiadasi g’oliblarini topamiz.
1 – shaharning olimpiadasi g’olibi 9-o’quvchi. Sababi uning bilim darajasi 42, 7-o’quvchining bilim darajasi esa 5. 9-o’quvchi keying turga o’tadi.
2 – shaharning olimpiadasi g’olibi 10-o’quvchi chunki shaharda undan boshqa o’quvchi yo’q.
Shunday qilib o’z shahrining g’olib o’quvchilari – {9, 10, 3, 11, 6, 1, 12, 8}. Keyingi turda 9-o’quvchi 10-o’quvchi bilan, 3-o’quvchi 11-o’quvchi bilan va h.k. bellashishadi. Yarim finalga kelgan o’quvchilar {10, 3, 6, 12}. Birinchi yarim finalda 10 va 3-o’quvchilar bellashishadi. Ikkinchi yarim finalda 6 va 12. Finalga chiqishdi – {10, 12}. 3-o’rin uchun bahsda bellashadi {3, 6}. Shunday qilib 1-o’rin – 10, 2-o’rin – 12 va 3-o’rin – 3-raqamli o’quvchilar.
Endi Al-Xorazmiy olimpiadasi g’oliblari:
1-o’rin – 10-raqamli o’quvchi
2-o’rin – 12-raqamli o’quvchi
3-o’rin – 9-raqamli o’quvchi
Telegram kanalimizga obuna bo'ling