A. XOR
Xotira: 16 MB, Vaqt: 1000 msButun sonlardan iborat a massiv va k soni berilgan. Quyidagi shartni qanoatlantiruvchi i va j (i < j) juftliklar sonini toping:
ai ⊕ aj = k
Bu yerda ⊕ belgisi xor(iksor) amalini bildiradi.
Birinchi qatorda massiv uzunligini ifodalovchi bitta butun N soni va k butun soni (1 ≤ N ≤ 2×105 ), 1 ≤ k ≤ 109). Keyingi qatorda esa N ta butun son, a massiv elementlari beriladi(1 ≤ ai ≤ 109).
Bitta butun son – masalaning javobi
Shartni qanoatlantiruvchi juftliklar: (1, 2), (4, 5)
a1 ⊕ a2 = 7 ⊕ 3 = 4
a4 ⊕ a5 = 5 ⊕ 1 = 4
| # | INPUT.TXT | OUTPUT.TXT |
|---|---|---|
| 1 |
5 4 7 3 2 5 1 |
2 |
B. Anagrammalar
Xotira: 16 MB, Vaqt: 1000 msS satr anagrammalari deb, S satrdagi belgilar o’rnini almashtirib hosil qilish mumkin bo’lgan satrlarga aytiladi. Misol uchun “abcd” so’zini anagrammalaridan biri “cdab”.
Sizning vazifangiz S satrdan nechta turli xil anagrammalarni hosil qilish mumkinligini topishdan iborat.
Yagona qatorda faqat kichik lotin alifbosidagi harflardan iborat bitta S satr beriladi (1 ≤ |S| ≤ 10)
Bitta butun son – masala javobi.
"non" so’zini barcha anagrammalari:
non
nno
onn
| # | INPUT.TXT | OUTPUT.TXT |
|---|---|---|
| 1 |
abc |
6 |
| 2 |
non |
3 |
C. Juftliklar
Xotira: 16 MB, Vaqt: 1000 msN ta elementdan iborat a massiv berilgan. Quyidagi shartni qanoatlantiruvchi i va j juftliklar sonini toping
(a[i] × a[j]) mod m = x (i < j)
Bu yerda a mod m ifoda, a sonni m ga bo’lgandagi qoldiqni bildiradi
Birinchi qatorda butun N, m va x sonlari(1 ≤ N ≤ 2×105 , 1 ≤ m ≤ 1000, 0 ≤ x < m). Keyingi qatorda esa N ta butun son, a massiv elementlari beriladi(1 ≤ ai ≤ 109).
Bitta butun son – masala javobi.
Shartni qanoatlantiradigan juftliklar (3, 4) va (1, 2)
(3×4) mod 10 = 12 mod 10 = 2
(1×2) mod 10 = 2 mod 10 = 2
| # | INPUT.TXT | OUTPUT.TXT |
|---|---|---|
| 1 |
4 10 2 3 1 4 2 |
2 |
D. Yana anagrammalar
Xotira: 32 MB, Vaqt: 1000 msS va T satrlari berilgan. Sizdan q ta so’rov so’raladi. Har bir so’rovda to’rtta l1, r1, l2, r2 (l1 ≤ r1, l2 ≤ r2) sonlari beriladi. Sizning vazifangiz s satrni [l1, r1] oraliqdagi qism satri va t satrni [l2, r2] oraliqdagi qism satri anagramma ekanini aniqlashdan iborat.
Aniqroq qilib aytganda, har bir so’rov uchun s[l1] + s[l1+1] + … + s[r1-1] + s[r1] satr va t[l2] + t[l2+1] + … + t[r2-1] + t[r2] satrlar anagramma ekanini aniqlang.
a va b satrlar anagramma bo’lishi uchun a satrni belgilarini o’rnini almashtirish orqali b satrni hosil qilish mumkin bo’lishi lozim.
Birinchi va ikkinchi qatorlarda mos ravishda S va T satrlari beriladi (1 ≤ |S|, |T| ≤ 105). Keyingi qatorda esa bitta butun q soni, keyingi q ta qatorda 4 tadan son beriladi l1, r1, l2, r2 (1 ≤ l1 ≤ r1 ≤ |S|, 1 ≤ l2 ≤ r2 ≤ |T|).
Har bir so’rov uchun agar berilgan qism satrlar anagramma bo’lsa “YES”, aks holda “NO” chiqaring.
s[3:5] = “cde”, t[2:4] = “dec”, ko’rinib turibdiki ushbu satrlar anagramma
| # | INPUT.TXT | OUTPUT.TXT |
|---|---|---|
| 1 |
abcde bdeca 4 3 5 2 4 1 2 4 5 4 5 2 4 2 2 1 1 |
YES NO NO YES |
E. Molxona
Xotira: 16 MB, Vaqt: 1000 msMirzakarimboyvachchani n ta molxonasi bor. Ushbu molxonalarni Ox o’qidagi nuqtalar sifatida qarash mumkin, bunda i-molxona xi koordinatada joylashgan.
Mirzakarimboyvachcha mollarini bozorga olib chiqmoqchi, shuning uchun ularni ichidan yaxshilarini tanlab olishi lozim. Bunda u barcha mollarini bir yerga to’plashi lozim. Ammo u dangasaligi tufayli, ko’p masofa yurgisi kelmayapti, shuning uchun molxonalardan tanlangan joygacha bo’lgan masofalar yig’indisi minimal bo’lishini xohlayapti. Bunda esa u sizning yordamingizga muhtoj.
Boshqacha qilib aytganda, shunaqangi k nuqtani topingki, har bir i-molxonadan k nuqtagacha bo’lgan masofalar yig’indisi minimal bo’lsin. Agar shartni qanoatlantiruvchi nuqtalar ko’p bo’lsa, ular ichida eng kichigini tanlang.
Birinchi qatorda molxonalar sonini ifodalovchi butun N soni(1 ≤ N ≤ 2×105 ). Keyingi qatorda esa N ta butun son, molxonalar koordinatalari beriladi (0 ≤ xi ≤ 109).
Bitta butun son – masala javobi.
Birinchi test masala shartidagi rasmda keltirilgan
| # | INPUT.TXT | OUTPUT.TXT |
|---|---|---|
| 1 |
4 3 1 7 2 |
2 |
F. Yo’l qurilishi
Xotira: 16 MB, Vaqt: 1000 msBaytobodda 1 dan n gacha raqamlangan n ta mahalla va ularni bog’lovchi m ta yo’l bor. Har bir yo’l ikkita mahallani bir biriga bog’laydi.
Shaharda harakatlanish oson bo’lishi uchun hukumat Baytobodga yangi yo’llarni qurmoqchi, bunda Baytoboddagi a, b va c mahallalarni oladigan bo’lsak, a mahalladan b mahallaga va a mahalladan c mahallaga yo’l bo’ladigan bo’lsa, b va c mahallalarni bog’lovchi yangi yo’l quriladi. Agar bu yo’l avvaldan mavjud bo’lsa, yangi yo’l qurilmaydi.
Shu yo’sinda qancha yo’l qurish mumkinligini toping.
Birinchi qatorda ikkita n va m sonlari beriladi, bu sonlar mos ravishda mahallalar soni va ularni bog’laydigan yo’llar sonini bildiradi (1 ≤ n, m ≤ 105).
Keyingi m ta qatorda esa, yo’llarni tavsiflovchi ikkita u va v sonlari beriladi, bu esa u va v raqamli shaharlar orasida ikki tomonli yo’l borligini bildiradi(1 ≤ u, v ≤ 105, u ≠ v). Ixtiyoriy ikkita shahar orasida ko’p bilan bitta yo’l bo’lishi mumkin.
Bitta son – yangi quriladigan yo’llar sonini chop eting.
Berilgan misolda faqat 1-va 3- mahallalarni bog’lovchi yo’l qurish mumkin
| # | INPUT.TXT | OUTPUT.TXT |
|---|---|---|
| 1 |
6 3 1 2 2 3 4 5 |
1 |
G. EKUK
Xotira: 16 MB, Vaqt: 1000 msa va k sonlari berilgan, EKUK(a, b) = k bo’lgan b sonini toping. Agar bunday sonlar ko’p bo’lsa, eng kichigini toping.
Yagona qatorda a va k sonlari beriladi(0 ≤ a, k ≤ 109)
Bitta butun son – masala javobi.
| # | INPUT.TXT | OUTPUT.TXT |
|---|---|---|
| 1 |
320 2240 |
7 |
H. Excel
Xotira: 16 MB, Vaqt: 1000 msSizga katta lotin harflaridan tashkil topgan S(1 ≤ |S| ≤ 7) satri beriladi, bu mos ravishda Excel jadvalining joriy ustunini bildiradi. Siz joriy ustun nechanchi ustun ekanligini aniqlang
INPUT.TXT kirish faylida bitta satr, S kiritiladi.
OUTPUT.TXT chiqish faylida yagona son, masala natijasini chop eting.
| # | INPUT.TXT | OUTPUT.TXT |
|---|---|---|
| 1 |
A |
1 |
| 2 |
AA |
27 |