A. Toq sonlar
Xotira: 32 MB, Vaqt: 1000 msRoboboy toq natural sonlarni juda yaxshi ko'radi, chunki ko'plab hodisalar toq sonlarga to'g'ri keladi. Misol uchun 1 - o'rin, 5 baho, 7(chiroyli raqam), va hokazo. U o'zining dastlabki \(N\) ta yaxshi ko'rgan sonlarining yig'indisini hisoblamoqchi. Buni aniqlashda unga yordam bering!
Kirish faylining yagona satrida bitta butun son, \(N(1 \le N \le 10^9)\) soni kiritiladi.
Dastlabki \(N\) ta natural toq sonlarning yig'indisini chop eting!
| # | INPUT.TXT | OUTPUT.TXT |
|---|---|---|
| 1 |
2 |
4 |
| 2 |
7 |
49 |
B. Binar satr
Xotira: 32 MB, Vaqt: 1000 msBinar son faqat 0 va 1 dan tashkil topadi. Sizga son berilgan. Berilgan son binar son bo'la oladimi?
Kirish faylida N soni kiritiladi. \(N \le 10^{1000}\)
Agar son binar son bo'la olsa “Yes”, aks holda “No” ni chop eting.
| # | INPUT.TXT | OUTPUT.TXT |
|---|---|---|
| 1 |
100 |
Yes |
| 2 |
102 |
No |
C. Qalamlar soni
Xotira: 32 MB, Vaqt: 1000 msRoboboyda ikki o'lchovli koordinatalar sistemasida \(N\) ta to'rtburchak bor. Har bir to'rtburchakning eni (\(W_i\)) va bo'yi (\(H_i\)) berilgan. Har bir to'rtburchakning pastki qismi \(X\) o'qida joylashgan bo'lib, dastlabki to'rtburchakning chap tomoni \(Y\) o'qiga tegib turgan holda, qolgan to'rtburchaklarning chap tomoni esa o'zidan oldingi to'rtburchakka tegib turgan holda joylashgan.
Roboboy barcha to'rtburchaklarning ichini bo'yamoqchi, qaysi rangda bo'yashi muhim emas. Ammo Roboboyning bo'yash uchun mo'ljallangan qalamlari bir martalik bo'lib, faqat to'rtburchak shakldagi 1 ta maydonni bo'yay oladi.
Barcha to'rtburchaklarni ichini bo'yash uchun Roboboyga eng kamida nechta qalam kerak bo'lishini aniqlang!
Kirish faylining dastlabki satrida bitta butun son, \(N(1 \le N \le 250 \ 000)\) soni kiritiladi. Keyingi N ta qatorda 2 tadan butun son \(W_i, H_i (1 \le W_i, H_i \le 10^9)\) to'rtburchaklarning o'lchamlari kiritiladi.
Barcha to'rtburchaklarni ichini bo'yash uchun Roboboyga kerak bo'ladigan eng kam qalamlar sonini chop eting!
1-test, ajralib turishi uchun har xil rangli qalamlardan foydalanildi:
| # | INPUT.TXT | OUTPUT.TXT |
|---|---|---|
| 1 |
5 1 4 2 5 2 2 1 3 1 2 |
4 |
D. Pullik yo'llar
Xotira: 32 MB, Vaqt: 1000 msRobolandiya - go'zal diyor. U N ta shaharni o'z ichiga oladi, va shaharlar 1 dan N gacha raqamlangan.
Robolandiya mamlakatida shaharlarni bog'laydigan yo'llarning barchasi pullik yo'l bo'lib, ularning soni M ta hamda bu yo'llar ikki tomonlama harakatlanish yo'nalishiga ega. Ikkita turli shaharlarni to'g'ridan to'g'ri birlashtiradigan yo'llar soni 1 tadan ko'p emas.
Robolandiya fuqarolari barcha shaharlararo yo'llar pullik ekanligidan norozi. Davlatning eng asosiy vazifalaridan biri o'z fuqarolarini rozi qilish, ammo barcha yo'llarni bepul qila olmaydi, bunga sabab yo'llardan tushgan daromad yo'llarni tamirlash uchun kerak bo'ladi. Shu sababli fuqarolar bilan uchrashgan holda quyidagi qarorga kelindi:
- Har bir shaharga kirish yo'llaridan aynan 1 tasi pullik yo'l bo'ladi;
- Har bir yo'l faqatgina bir tomonlama harakat uchun pullik yo'l bo'la oladi.
Yo'l mas'ullari davlatning bu qarorini amalga oshirishi kerak. Ammo ba'zi hollarda bu qarorni amalga oshirishning imkoni bo'lmasligi mumkin. Yo'l mas'ullari sizning yordamingizga muhtoj. Siz berilgan ma'lumotlardan foydalangan holda yuqorida aytilgan qarorni amalga oshirish mumkin, yoki yo'qligini aniqlashda yordam bering, hamda agar mumkin bo'lsa har bir shahar uchun qaysi shahardan kelish yo'li pullik bo'lishi kerakligini aniqlab bering.
Birinchi qatorda N va M - shaharlar va yo'llar soni kiritiladi.
Keyingi M ta qatorning har birida ikkita butun son - u va v kiritiladi \(u \neq v\). Bu u va v shaharlar orasida yo'l mavjudligini anglatadi.
\(1 \le N \le 10^5\)
\(1 \le M \le 2*10^5\)
\(1 \le u, v \le N\)
Ikki shahar to'g'ridan-to'g'ri ko'pi bilan 1 ta yo'l orqali bog'lanishi kafolatlanadi.
Agar yuqoridagi qarorni amalga oshirishning imkoni bo'lmasa “No” so'zini chop eting.
Aks holda “Yes” so'zini chop eting. Keyingi N ta qatorning har birida 1 tadan butun son - har bir shahar uchun tanlangan yo'lning qarama-qarshi tomondagi shahar raqamini chop eting.
Agar bir nechta yechim mavjud bo'lsa, istalganini chop etishingiz mumkin.
| # | INPUT.TXT | OUTPUT.TXT |
|---|---|---|
| 1 |
4 5 1 2 2 3 1 3 3 4 1 4 |
Yes 3 1 2 3 |
| 2 |
4 3 1 3 3 4 2 3 |
No |
E. Massiv bahosi
Xotira: 32 MB, Vaqt: 1000 msN ta sondan tashkil topgan A massivi berilgan. Massivning - bahosi massivning ikki qo'shni elementlari farqining maksimali hisoblanadi. Massivning ko'pi bilan M ta elementi qiymatini o'zgartirgan holda, uning bahosini minimallashtiring.
Birinchi qatorda N va M butun sonlari kiritiladi.
Keyingi qatorda N ta butun son - A massiv elementlari kiritiladi.
\(1 \le N, M \le 2000\)
\(1 \le i \le N\) uchun \(-10^9 \le A_i \le 10^9\)
Yagona butun son, massivning ko'pi bilan M ta elementi qiymatini o'zgartirgan holda, uning bahosini mumkin bo'lgan minimal qiymatini chop eting.
| # | INPUT.TXT | OUTPUT.TXT |
|---|---|---|
| 1 |
4 1 4 7 7 4 |
3 |
| 2 |
6 3 9 2 6 8 1 5 |
2 |
F. Sayyohlik agentligi muammosi
Xotira: 32 MB, Vaqt: 1000 msRobolandiya - go'zal diyor. U N ta shaharni o'z ichiga oladi, va shaharlar 1 dan N gacha raqamlangan.
Robolandiya mamlakatida turli shaharlarni bog'laydigan M ta ikki tomonlama yo'l mavjud.
Robolandiya qo'riqchilari o'z prezidentini juda kuchli qo'riqlashadi. Bundan tashqari prezident xizmat safari bilan qaysi shaharga borishidan qat'iy nazar shu shaharga bog'langan barcha yo'llarni yopishadi ham.
Robolandiya fuqarolarini mamlakat bo'ylab sayohat qilishlari uchun tashkil etilgan sayyohlik agentligi o'z sayohatlarini avtobuslarda amalgan oshirganligi sababli ba'zi \(u \neq v (1 \le u, v \le n)\) juftliklar uchun u-shaharda istiqomat qiladigan fuqarolarni v-shaharga sayohatga eta olishmaydi.
Sayyohlik agentligi har bir \(i\) - shahar uchun, agar mamlakat prezidenti xizmat safari bilan \(i\)-shaharga kelgan bo'lsa jami nechta \(u \neq v (1 \le u, v \le n)\) juftliklar uchun u-shaharda istiqomat qiladigan fuqarolarni v-shaharga sayohatga eta olmasligini aniqlamoqchi.
Siz yuqori malakali dasturchi sifatida sayyohlik agentligiga yordam bering!.
Birinchi qatorda N va M, shaharlar va ularni bog'lab turuvchi ikki tomonlama yo'llar soni kiritiladi.
Keyingi M ta qatorning har birida ikkitadan butun son - har bir yo'l bog'lab turadigan ikki shaharning tartib raqami kiritiladi.
\(1 \le N \le 10^5\)
\(1 \le M \le 5*10^5\)
\(1 \le i \le N\) oralig'idagi har bir \(i\) uchun alohida qatorda, Robolandiya prezidenti xizmat safari bilan \(i\)- shaharda bo'lganida sayyohlik agentligi jami nechta \(u \neq v (1 \le u, v \le n)\) juftliklar uchun u-shaharda istiqomat qiladigan fuqarolarni v-shaharga sayohatga eta olmasligini chop eting.
| # | INPUT.TXT | OUTPUT.TXT |
|---|---|---|
| 1 |
5 4 1 2 1 3 1 4 1 5 |
20 8 8 8 8 |
| 2 |
5 5 1 2 2 3 1 3 3 4 4 5 |
8 8 16 14 8 |