Home
Problem
Status
Contest
Workbook
User
Group
Forum
Register
Login
{"managingGroups":{},"author":"Aliyyiakbar","updateTime":1709405435000,"title":"Qaqa-Cell Round #1 Editorial","dislikeCnt":1,"content":"-----\n# Sualları İlk Həll Edənlər\n$~$\n### A - 00:03:39 (*Cebrayil09*)\n### B - 00:13:14 (*Zakir060*)\n### C - 00:19:15 (*Zakir060*)\n### D - 00:36:17 (*MirBala*)\n### ~~E - 99:99:99 (*Aliyyiakbar*)~~\n$~$\n\n#### Sıralama : https://vjudge.net/contest/613356#rank\n\n-----\n# Honorable Mentions\n$~$\n#### Zakir060 -\u003e İnanılmaz performansı və birinciliyi üçün.\n#### Ekber_Ekber -\u003e E sualına qorxu verib 64.29% aldığı üçün.\n#### Callmehuseyn -\u003e B sualının Eratosfen olduğunu yaydığı üçün.\n#### TheSumuraz -\u003e A sualına çox mənasız həll yazıb bəxtəbəxt tam bal adığı üçün.\n#### Mirbala -\u003e ChatGPTlike kod yazdığı üçün.\n#### Xanlar0 -\u003e Fullaya biləcəyi kontestdə cavanlara yol açdığı üçün.\n$~$\n### Sizsiz kontest çox mənasız olardı, iştrakınız üçün (!)təşəkkürlər.\n\n-----\n# Sualların Editorialları\n$~$\n## **A - Xanlar of Legend**\n### Həll 1\n##### Diqqətlə observation etdikdə görürük ki, hansı komandanın cəmi daha çoxdursa, oyunu həmin komanda qazanır. Bərabərlik halında isə oyunun qalibi həmişə göy komanda olur çünki oyuna ilk göy komanda başlayır.\n```\n#include \u003cbits/stdc++.h\u003e\nusing namespace std;\n\nint main()\n{\n int a[5],b[5];\n int sumBlue \u003d 0, sumRed \u003d 0;\n for (int i \u003d 0; i \u003c 5; ++i)\n {\n cin \u003e\u003e a[i];\n sumBlue +\u003d a[i];\n }\n for (int i \u003d 0; i \u003c 5; ++i)\n {\n cin \u003e\u003e b[i];\n sumRed +\u003d b[i];\n }\n cout \u003c\u003c (sumBlue \u003e\u003d sumRed ? \"Blue\" : \"Red\") \u003c\u003c endl;\n}\n\n```\n-----\n## **B - SAD_ə ədəd**\n### Həll 1\n##### İlk ağla gələn həllərdən biri, bütün cütlükləri yoxlamaqdır. Bunu $o(n^2 \\cdot \\sqrt{n})$ zaman səmərəliyinə etmək olar, hansı ki bütün cütlükləri gəzmək $n$ əməliyyat və hər iki cütlükün sadə olub olmadığını yoxlamaq $n \\cdot \\sqrt{n}$ əməliyyat aparır. Gəlin nəzərə alaq ki, cütlüklər $\\frac{n}{2}$ ədədindən sonra təkrarlanır və ədədin sadə olub olmadığını Eratosfen Xəlbiri alqoritmi ilə yığsaq, zaman səmərəliyimiz çox böyük bir optimizasiya ilə $o(n \\log \\log n + \\frac{n}{2})$ olur, hansı ki əgər $n \u003d 10^7$, bu $32799426 ≈ 10^8 $ əməliyyat çəkəcək.\n```\n#include \u003cbits/stdc++.h\u003e\nusing namespace std;\n\nconst int MAX_N \u003d 1e7;\nbool isprime[MAX_N+9];\n\nvoid sieve_of_eratosthenes()\n{\n memset(isprime,true,sizeof(isprime));\n for (int i \u003d 2; i*i \u003c\u003d MAX_N; ++i)\n {\n if (isprime[i])\n {\n for (int j \u003d i*i; j \u003c\u003d MAX_N; j +\u003d i)\n {\n isprime[j] \u003d false;\n }\n }\n }\n}\n\nint main()\n{\n sieve_of_eratosthenes();\n int n;\n cin \u003e\u003e n;\n for (int i \u003d 2; i \u003c\u003d (n / 2); ++i)\n {\n if (isprime[i] \u0026\u0026 isprime[n-i])\n {\n cout \u003c\u003c i \u003c\u003c \u0027 \u0027 \u003c\u003c n-i \u003c\u003c endl;\n return 0;\n }\n }\n cout \u003c\u003c -1 \u003c\u003c endl;\n}\n```\n### Həll 2\n##### $2$-dən başqa bütün sadə ədədlər təkdirlər. Hər hansı tək ədədi 2 tək ədədin cəmi şəklinə göstərmək mümkün olmadığı üçün gəlin ilk ədədimizi elə $2$ götürək. Yerdə qalan iş isə $n-2$-nin sadə olub olmadığını yoxlamaqdır. Həllimizin zaman səmərəliyi bu optimizasiya ilə $o(\\sqrt{n})$ olur.\n```\n#include \u003cbits/stdc++.h\u003e\nusing namespace std;\n\nbool isprime(const int \u0026n)\n{\n if (n \u003c\u003d 1)\n {\n return false;\n }\n for (int i \u003d 2; i*i \u003c\u003d n; ++i)\n {\n if (n%i \u003d\u003d 0)\n {\n return false;\n }\n }\n return true;\n}\n\nint main()\n{\n int n;\n cin \u003e\u003e n;\n if (isprime(n-2))\n {\n cout \u003c\u003c 2 \u003c\u003c \u0027 \u0027 \u003c\u003c n-2 \u003c\u003c endl;\n }\n else\n {\n cout \u003c\u003c -1 \u003c\u003c endl;\n }\n}\n```\n\n-----\n## **C - Uzatma Çoxda**\n### Həll 1\n##### Sualda bizdən soruşulan, $\\frac{1}{n}$ ədədinin sonsuz onluq kəsir olub olmadığını yoxlamaqdır. Riyazi üsul ilə brute-force edə bilərik çünki testlər çox azdır.\n```\n#include \u003cbits/stdc++.h\u003e\nusing namespace std;\n\nint main()\n{\n int t;\n cin \u003e\u003e t;\n while(t-- \u003e 0)\n {\n int n;\n cin \u003e\u003e n;\n int d \u003d 1, cnt \u003d 0, flag \u003d true;\n while(d)\n {\n cnt \u003d cnt + 1;\n d \u003d (d * 10) % n;\n if (cnt \u003e 10000)\n {\n flag \u003d false;\n cout \u003c\u003c \"Yes\" \u003c\u003c endl;\n break;\n }\n }\n if (flag \u003d\u003d true)\n {\n cout \u003c\u003c \"No\" \u003c\u003c endl;\n }\n }\n}\n```\n### Həll 2\n##### Eyni riyazi həlli Dinamik Proqramlaşdırmaya gətirək. $dp[i] \u003d \\frac{1}{i}$ ədədi üçün cavabımız olsun və bütün cavabları əvvəlcədən $dp[]$ massivinə yığaq.\n```\n#include \u003cbits/stdc++.h\u003e\nusing namespace std;\n\nint dp[105];\n\nvoid calc(int x)\n{\n int d \u003d 1, cnt \u003d 0, flag \u003d true;\n while(d)\n {\n cnt \u003d cnt + 1;\n d \u003d (d * 10) % x;\n if (cnt \u003e 10000)\n {\n flag \u003d false;\n break;\n }\n }\n dp[x] \u003d flag;\n}\n\nint main()\n{\n for (int i \u003d 1; i \u003c\u003d 100; ++i)\n {\n calc(i);\n }\n int t;\n cin \u003e\u003e t;\n while(t-- \u003e 0)\n {\n int n;\n cin \u003e\u003e n;\n cout \u003c\u003c (dp[n] ? \"No\" : \"Yes\") \u003c\u003c endl;\n }\n}\n```\n### Həll 3\n##### Nəzərə alsaq ki həmişə ədədi $10$-a vururq, başlanğıcdakı $d \u003d 1$ ədədinin $0$-a bərabər olması üçün n ədədi ancaq $2$ və $5$-in hasili şəklində olmalıdır. $n \u003d 2^x\\cdot5^y$ şəklində olub-olmadığını yoxlamaq üçün isə $2$-yə və $5$-ə bölə-bölə gedə bilərik.\n```\n#include \u003cbits/stdc++.h\u003e\nusing namespace std;\n\nint main()\n{\n int t;\n cin \u003e\u003e t;\n while(t-- \u003e 0)\n {\n int n;\n cin \u003e\u003e n;\n while(n % 2 \u003d\u003d 0)\n {\n n \u003d n / 2;\n }\n while(n % 5 \u003d\u003d 0)\n {\n n \u003d n / 5;\n }\n cout \u003c\u003c (n \u003d\u003d 1 ? \"No\" : \"Yes\") \u003c\u003c endl;\n }\n}\n```\n\n### Həll 4 (TheSumuraz tərəfindən)\n##### $n \u003d 2^x\\cdot5^y$ şəklində olub-olmadığını yoxlamağın daha sürətli yolu, $10^{18} ~ mod ~ n$ hesablamaqdır. Əgər qalıq 0-dırsa, ədəd $2^x\\cdot5^y$ şəklindədir. \n```\n#include \u003cbits/stdc++.h\u003e\nusing namespace std;\n\nconst long long INF \u003d 1e18;\n\nint main()\n{\n int t;\n cin \u003e\u003e t;\n while(t-- \u003e 0)\n {\n long long n;\n cin \u003e\u003e n;\n cout \u003c\u003c (INF % n !\u003d 0 ? \"Yes\" : \"No\") \u003c\u003c endl;\n }\n}\n```\n-----\n## **D - Cəbrayıl Rayonu**\n### Həll 1\n##### Qrafda axtarış alqoritmi olan DFS-i yaxşı bilirsinizsə, aydın olmalıdır ki əgər bir təpənin gedə biləcək heç bir qonşusu yoxdursa, onda bu təpə gəldiyi yer olan parenti (valideyn) ilə qonşudur. DFS alqoritmi rekursiv bir funksiyadır və stack memory ilə işləyir. Eyni prossesi stack ilə biz də təkrarlayaq və hər hansı $k$ təpəsinin qonşusu olmazsa, parenti olan ```stack.top()``` ilə cavabı cütlük olaraq saxlayaq.\n\n##### Məsələdə bir təpənin o vaxt qonşusu yoxdur ki, girişdə aldığımız string ***\"out\"***-a bərabər olsun.\n```\n#include \u003cbits/stdc++.h\u003e\nusing namespace std;\n\nint main()\n{\n vector\u003c pair\u003cint, int\u003e \u003e v;\n stack\u003cint\u003e st;\n int n;\n cin \u003e\u003e n;\n for (int i \u003d 1; i \u003c\u003d 2*n; ++i)\n {\n string s;\n int x;\n cin \u003e\u003e s \u003e\u003e x;\n if (s \u003d\u003d \"in\")\n {\n if (!st.empty())\n {\n v.push_back(make_pair(x,st.top()));\n }\n st.push(x);\n }\n else\n {\n st.pop();\n }\n }\n for (auto i : v)\n {\n cout \u003c\u003c i.first \u003c\u003c \u0027 \u0027 \u003c\u003c i.second \u003c\u003c endl;\n }\n}\n```\n-----\n## **E - Əkbərin MEX Sorğuları**\n### Həll 1\n##### STL istifadə edərək ```map``` ilə hər ədədi sayaq və ```set``` də potensial MEX cavablarını saxlayaq. ```set``` sıralı olduğundan, cavabımız həmişə ```*set.begin()``` olur. Ümumilikdə bizə $o(n \\log n)$ zaman lazımdır ki, ```set```-i cavablarla dolduraq. Bundan sonra isə cavabı çıxışa vermək $o(1)$, update querylərini yerinə yetirmək isə $o(\\log{n})$ zaman alacaq. \n```\n#include \u003ciostream\u003e\n#include \u003cmap\u003e\n#include \u003cset\u003e\n#include \u003calgorithm\u003e\n#include \u003cvector\u003e\n\n#define int long long\n#define AzH_TxdmN ios_base::sync_with_stdio(0);cin.tie(nullptr);cout.tie(nullptr);\nusing namespace std;\n\nint n,q,ql,qr;\n\nclass Mex\n{\nprivate:\n map\u003cint, int\u003e frequency;\n set\u003cint\u003e missing_numbers;\n vector\u003cint\u003e A;\n\npublic:\n Mex(vector\u003cint\u003e const\u0026 A) : A(A)\n {\n for (int i \u003d 0; i \u003c\u003d A.size(); i++)\n missing_numbers.insert(i);\n\n for (int x : A)\n {\n ++frequency[x];\n missing_numbers.erase(x);\n }\n }\n\n int mex()\n {\n return *missing_numbers.begin();\n }\n\n void update(int idx, int new_value)\n {\n if (--frequency[A[idx]] \u003d\u003d 0)\n missing_numbers.insert(A[idx]);\n A[idx] \u003d new_value;\n ++frequency[new_value];\n missing_numbers.erase(new_value);\n }\n};\n\nsigned main()\n{\n AzH_TxdmN\n cin\u003e\u003en\u003e\u003eq;\n vector\u003cint\u003ea(n);\n for (int i \u003d 0; i \u003c n; i++)\n {\n cin\u003e\u003ea[i];\n }\n Mex res(a);\n while(q--)\n {\n cin\u003e\u003eql\u003e\u003eqr;\n ql--;\n res.update(ql,qr);\n cout\u003c\u003cres.mex()\u003c\u003c\u0027\\n\u0027;\n }\n}\n```\n### Həll 2\n##### MEX-in çox önəmli qaydalarından biri, N uzunluqlu bir massivin MEX-inin həmişə $[0;N]$ aralığında olmasıdır. Bu səbəblə $N$-dən böyük elementlərə nəzər yetirməmək bizə optimizasya qazandıra bilər.\n##### Təməl məntiqi istifadə edib eyni həlli aşağıdakı kimi təkrar yazmaq olar.\n$~$\n```\n#include \u003cbits/stdc++.h\u003e\nusing namespace std;\n\nint main() {\n\tint N, Q;\n\tcin \u003e\u003e N \u003e\u003e Q;\n\tvector\u003cint\u003e A(N);\n\tfor (int i \u003d 0; i \u003c N; i++) {\n\t\tcin \u003e\u003e A[i];\n\t}\n\tvector\u003cint\u003e C(N + 1);\n\tfor (int i \u003d 0; i \u003c N; i++) {\n\t\tif (A[i] \u003c\u003d N) {\n\t\t\tC[A[i]] +\u003d 1;\n\t\t}\n\t}\n\tset\u003cint\u003e s;\n\tfor (int i \u003d 0; i \u003c\u003d N; i++) {\n\t\tif (C[i] \u003d\u003d 0) {\n\t\t\ts.insert(i);\n\t\t}\n\t}\n\tfor (int i \u003d 0; i \u003c Q; i++) {\n\t\tint p, x;\n\t\tcin \u003e\u003e p \u003e\u003e x;\n\t\tp -\u003d 1;\n\t\tif (A[p] \u003c\u003d N) {\n\t\t\tC[A[p]] -\u003d 1;\n\t\t\tif (C[A[p]] \u003d\u003d 0) {\n\t\t\t\ts.insert(A[p]);\n\t\t\t}\n\t\t}\n\t\tA[p] \u003d x;\n\t\tif (A[p] \u003c\u003d N) {\n\t\t\tif (C[A[p]] \u003d\u003d 0) {\n\t\t\t\ts.erase(A[p]);\n\t\t\t}\n\t\t\tC[A[p]] +\u003d 1;\n\t\t}\n\t\tcout \u003c\u003c *s.begin() \u003c\u003c \u0027\\n\u0027;\n\t}\n\treturn 0;\n}\n```\n\n# ***Əgər bu editorial sizə yardımcı oldusa,***\n# ***Bəyənməyi unutmayın!***\n\n## By [\u003cspan style\u003d\"color:#00A5A5\"\u003eAliyyiakbar](https://codeforces.com/profile/Aliyyiakbar)\n\t\n-----","threadId":184401,"likeCnt":8,"createTime":1709402436000,"isWorkbook":false,"viewCnt":99,"openness":2,"fav":false,"id":4652,"trustable":false}