A. Queue Game

Xotira: 10 MB, Vaqt: 300 ms

2 ta do'st, Akobir va Quvonchbek "Queue" game o'yini o'ynashmoqda. Bu o'yin shartiga ko'ra o'yinchilarga \(n\) ta sondan iborat sonlar to'plami \((a_1, a_2, a_3, ..., a_n)\) beriladi, o'yinni Akobir boshlab beradi. Akobir eng katta soni olib tashlaydi, Quvonchbek esa eng kichigini, shu tariqa o'yin davom etadi. Oxirida qolgan o'yinchi g'olib boladi. Sizning vazifangiz oxirida go'lib bo'lgan o'yinchi necha soni bilan qolganini topishdan iborat.

3
2 1 3

2

B. "Juda qo'rqinchli" ko'paytma

Xotira: 64 MB, Vaqt: 1000 ms

MAXAB va MINAB topshiriqlarini hal qilgandan so'ng, Sardor Azimjonga yanada qiyin topshiriq berish haqida o'ylab qoldi va quyidagi topshiriqni berishga qaror qildi.

\(N\) ta butun sondan iborat massiv berilgan. Bu massiv elementlarini ko'paytmasi qandaydir butun sonning kvadrati bo'la oladimi yoki yo'qligini tekshirish talab etiladi.

Azimjon bu topshiriqni hal qilishni uddalay olmadi. Sizchi buni hal qila olasizmi 😉?
 

5
1 2 3 4 6

Yes

C. Optimize

Xotira: 16 MB, Vaqt: 1000 ms

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;
}

5 
1 2 3 4 5
3
1 3
0 2 4
1 4

40
60

D. Kevin o'yinchoqlar do'konida

Xotira: 16 MB, Vaqt: 1000 ms

Kevin New Yorkda yolg'iz aylanib yurib ajoyib o'yinchoq do'koniga kirib qoldi. U yerda ko'plab o'yinchoqlar Kevinga yoqib qoldi. Ammo bu ancha ko'p pul bo'lishi aniq. Shu sababli o'yinchoq do'koni egasi unga bir imkoniyat berdi. Unga ko'ra u jammi pulning xohlagan joyiga plus amalini qo'yishi mumkin. Kevinga imkoni boricha kamroq pul to'lashida yordam bering.

10000000001

2

1234

46

1231230000001

123124

E. Qismlarga bo'lish o'yini

Xotira: 16 MB, Vaqt: 1000 ms

Mirzo Ulug’bek kitob olgani kitob do’koniga bordi. Ming afsuski uning hamyonida birorta ham kitobga yetadigan puli yo’q edi. Buni chetdan kuzatib turgan kitobxona xo’jayini Mirzo Ulug’bekning kitobga qiziqishini ko’rganidan so’ng Mirzo Ulug’bekka kitob sovg’a qilish maqsadida unga o’yin o’ynashni taklif qildi, shu o’yinda Mirzo Ulug’bek necha ball yig’sa, shuncha kitobni sovg’a qilishini aytdi. Tabiiyki Mirzo Ulug’bek bunga ko’ndi va diqqat bilan o’yin shartlarini tingladi:

• Mirzo Ulug’bekga nomanfiy butun sonlardan iborat massiv beriladi.
• Mirzo Ulug’bek massivni ketma-ket elementlardan tashkil topgan, bo’sh bo’lmagan shunday 2 massivga ajratishi kerakki chap tomon elementlaridan tashkil topgan massiv elementlari yig’indisi o’ng tomon elementlaridan tashkil topgan massiv elementlari yig’indisiga teng bo’lishi kerak. Agar Mirzo Ulug’bek bu ishni amalga oshira olsa u 1 ball ga ega bo’ladi, aks holda o’yin o’z nihoyasiga yetadi.
• Har bir muvoffaqiyatli turdan so’ng Mirzo Ulug’bek chap yoki o’ng tomon elementlaridan tashkil topgan massivni o’yindan tashqariga uloqtiradi va o’zida qolgan massiv bilan o’yinni davom ettiradi.

Masalan: dastlab Mirzo Ulug’bekda \([1,2,3,6]\) massivi mavjud bo’lsin, u bu massivni \([1,2,3]\), \([6]\) shaklida ikkiga taqsimlashi mumkin(+1 ball), shundan so’ng \([6]\) ni o’yindan chiqarib, o’yinni \([1,2,3]\) bilan davom ettiradi. U bu massivni \([1,2]\), \([3]\) shaklida ikkiga taqsimlashi mumkin(+1 ball), shundan so’ng \([3]\) ni o’yindan chiqarib, o’yinni \([1,2]\) bilan davom ettiradi. U bu massivni ikkiga taqsimlay olmaydi va o’yin nihoyasiga yetib Mirzo Ulug’bek 2 ball ga ega bo’ladi, ya’ni kitob do’konidan ixtiyoriy 2 ta kitobni tekinga olib ketishi mumkin bo’ladi.

5
4
1 2 3 6
4
1 2 6 3
3
3 3 3
4
2 2 2 2
7
4 1 0 1 1 0 1

2
0
0
2
3

F. Oraliqlar daraxti

Xotira: 32 MB, Vaqt: 2000 ms

Azimjon N ta har xil elementdan iborat(qiymatlari takrorlanmaydigan) A massiv uchun 2×N-1 ta elementdan iborat T oraliqlar daraxti orqali minimum qiymatni hisoblash uchun quyidagi tartibda tuzdi:

for i in range(0, N): T[i+N-1] = A[i]

for i in range(N-2, -1, -1): T[i] = min(T[i*2+1], T[i*2+2])

Shundan so’ng o’zining A massivini tashlab yubordi va o’ziga 2×N-1 ta elementdan iborat T massivni saqlab qoldi. Azimjon uyda yo’qligidan foydalanib uning ukasi Azimjonning T massiv elementlarini qiymatlarini tartibini almashtirib qo’ydi, va hattoki ba’zi elementlarining qiymatini o’zgartirib ham qo’ygan bo’lishi mumkin. Bundan xabar topgan Azimjon o’zining T massivini qiymatlari almashgan bo’lsada yuqoridagi qonuniyatiga mos keladigan holda qayta tiklamoqchi bo’ldi. Qayta tiklaganida ham A massivga mos keladigan elementlar unikal(yagona)ligini saqlab qolishi kerak. Sizning vazifangiz Azimjon buni eplay oladimi yoki yo’qligini aniqlashdan iborat.

4
3 1 3 1 2 4 1

YES
1 1 3 1 2 3 4 

2
1 1 1

NO