A. Optimize

Xotira: 16 MB, Vaqt: 1000 ms

Masala

Quyidagi dastur yechimini chop eting!.
#include <iostream>
using namespace std;
int main(){
    int n;
    cin >> n;
    int *a = new int[n+1];
    for(int i = 1; i <= n; i ++) cin >> a[i];
    int q, t, id, m;
    cin >> q;
    for(int i = 0; i < q; i ++){
        cin >> t >> id;
        if(t == 0)
            cin >> a[id];
        else{
            m = 1;
            for(int j = 1; j <= n; j ++)
                if(id != j)
                    m = (1LL * m * a[j]) % 1000000007;
            cout << m << endl;
        }
    }
    return 0;
}

Kiruvchi ma'lumotlar:

Kirish faylining dastlabki satrida \(n (1 \le n \le 10^5)\) ning qiymati kiritiladi. Ikkinchi satrda \(n\) ta butun son \(a (0 \le a_i \le 10^9)\) massiv elementlari bo’sh joy bilan ajratilgan holda kiritiladi. Uchunchi satrda bitta butun son, \(q (1 \le q \le 10^5)\) soni kiritiladi. to’rtinchi qatordan boshlab \(q\) ta qatorda 2 xil turdagi so’rovdan biri kiritiladi. So’rovlar quyidagicha:
0 id \(a_{id}\) - 0 bilan boshlangan satrda \(id (1 \le id \le n)\) va \(a_{id} (0 \le a_{id} \le 10^9)\) kiritiladi.
1 id - 1 bilan boshlangan satrda faqat \(id (1 \le id \le n)\) kiritiladi.

Chiquvchi ma'lumotlar:

Kiritilgan qiymatlar uchun yuqoridagi dastur kodining natijasini chop eting.

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	5 1 2 3 4 5 3 1 3 0 2 4 1 4	40 60

B. Bitwise AND

Xotira: 16 MB, Vaqt: 1000 ms

Masala

Sizga \(N (2 \le N \le 3*10^5)\) ta elementdan iborat \(A (1 \le A_i \le 10^9)\) to’plam berilgan. Siz shunday \(x\) va \(y (1 \le x, y \le N, x \neq y)\) juftlikni topingki ixtiyoriy \(i\) va \(j (1 \le i, j \le N, i \neq j)\) uchun \((A_x \& A_y) \ge (A_i \& A_j)\) shart qanoatlansin!

Kiruvchi ma'lumotlar:

Kirish faylining dastlabki satrida bitta butun son, \(N\) soni kiritiladi. Ikkinchi satrda \(N\) ta butun son, \(A\) to’plam elementlari bo’sh joy bilan ajratilgan holda kiritiladi.

Chiquvchi ma'lumotlar:

Chiqish faylida yuqoridagi shartni qanoatlantiradigan ixtiyoriy \(x\) va \(y\) ni chop eting.

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	4 3 4 2 3	1 4

C. O’chirish o’yini

Xotira: 16 MB, Vaqt: 1000 ms

Masala

Mansurbek va Saidakbar sonlar ustida o’yin o’ynashni yaxshi ko’radi. Bu o’yinlardan biri o’chirish o’yinidir. O’chirish o’yini quyidagicha bo’ladi.

Doskada 1 dan N gacha bo’lgan sonlarning ixtiyoriy permutatsiyasi yoziladi.
O’yinni Saidakbar boshlab beradi va har bir o’chirishdan so’ng navbat o’yinchilarning navbati almashadi.
Navbati kelgan o’yinchi doskadagi qolgan sonlardan ixtiyoriy birini o’chirishi kerak.
Doskadagi sonlar o’sish tartibida saralangan holga kelib qolsa o’yin tugaydi hamda navbati kelgan o’yinchi yutqazadi.

Ikkala o’yinchi ham optimal o’ynaydi. Siz o’yinda kim g’olib bo’lishini aniqlang!

Kiruvchi ma'lumotlar:

Kirish faylining dastlabki satrida bitta butun son, \(T (1 \le T \le 100)\) testlar soni kiritiladi.

Keyingi qatordan boshlab har bir test uchun ikkita satr ajratilgan. Bu satrlarning birinchisida \(N\) (doskadagi sonlar soni, \(1 ≤ N ≤ 15\)), ikkinchisida \(1, 2, \dots , N\) ketma-ketlikning ixtiyoriy permutatsiyasi kiritiladi.

Chiquvchi ma'lumotlar:

Chiqish faylida har bir test uchun alohida qatorda o’yin g’olibini chop eting!

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	2 3 1 3 2 5 5 3 2 1 4	Saidakbar Mansurbek

D. Graf ichidan to'plam

Xotira: 16 MB, Vaqt: 1000 ms

Masala

Sizga Grafning tugunlar soni \(N\) berilgan. Grafdagi tugunlar 1 dan N gacha nomerlangan. Grafda barcha \(u \% v == 0 (2 \le u, v \le n)\) shartni qanoatlantiradigan tugunlar orasida to’g’ridan to’g’ri yo’l mavjud. Siz quyidagi shartlarni qanoatlantiradigan to’plamni hosil qiling:

To’plam elementlar soni imkon qadar kam bo’lsin
Grafning barcha tuguni uchun quyidagi shartlardan biri bajarilsin:
- Tugun to’plam ichida mavjud bo’lsin
- Tugun bilan to’g’ridan to’g’ri yo’l mavjud bo’lgan boshqa bir tugun to’plam ichida mavjud bo’lsin

Kiruvchi ma'lumotlar:

Kirish faylining dastlabki satrida bitta butun son, \(T (1 \le T \le 10^5)\) testlar soni kiritiladi.

Keyingi \(T\) ta qatorda bittadan butun son, \(N (1 \le N \le 10^6)\) graf tugunlar soni kiritiladi.

Chiquvchi ma'lumotlar:

Chiqish faylida har bir test uchun alohida qatorda hosil qilingan to’plamning minimal uzunligi nechchi bo’lishini chop eting!

Izoh:

1-testda:
Grafda 2-4, 2-6, 3-6 yo’llar mavjud
To’plamni (1,4,5,6) qiymatlardan hosil qilsa bo’ladi.

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	1 6	4

E. SITA

Xotira: 16 MB, Vaqt: 1000 ms

Masala

SITA – Split into two arrays (Ikkita massivga taqsimlash)

Sizga \(N (1 \le N \le 10^5)\) ta elementdan iborat \(A (1 \le A_i \le 10^5)\) massiv berilgan. Siz ixtiyoriy natural \(X\) sonini tanlashingiz kerak va \(A\) massivning qiymati \(X\) dan kichiklaridan \(B\) massivni, \(A\) massivni qiymati \(X\) dan kattalaridan \(C\) massivni hosil qiling. Bunda \(B\) da ham \(C\) da ham kamida 1 ta element mavjud bo’lsin hamda B massiv elementlari yig’indisi \(C\) massiv elementlari yig’indisiga teng bo’lsin.

Kiruvchi ma'lumotlar:

Kirish faylining dastlabki satrida bitta butun son, \(N\) massiv elementlari soni kiritiladi. Ikkinchi satrda \(N\) ta butun son, massiv elementlari kiritiladi.

Chiquvchi ma'lumotlar:

Chiqish faylida yuqoridagi shartni qanoatlantiradigan \(X\) sonini tanlay olsangiz YES, aks holda NO so’zini chop eting.

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	5 1 1 2 3 4	YES