Home
Problem
Status
Contest
Workbook
User
Group
Forum
Register
Login
{"managingGroups":{},"author":"Cebrayil09","updateTime":1710064621000,"title":"İnfo-Azerbaijan round #2 editorial","dislikeCnt":2,"content":"-----\n# Sualları İlk Həll Edənlər\n$~$\n### A - 00:50:26 (*Aliyyiakbar*)\n### B - 00:30:09 (*Zakir060*)\n### C - 00:09:32 (*Zakir060*)\n### D - 01:04:48 (*Aliyyiakbar*)\n### E - 00:52:14 (*hasanov*)\n$~$\n \n#### Sıralama : https://vjudge.net/contest/613669#rank\n \n-----\n# Honorable Mentions\n$~$\n#### Aliyyiakbar -\u003e İnanılmaz performansı və birinciliyi üçün.\n#### hasanov -\u003e E sualını yazdığı və birinciliyi çox az fərqlə əlindən verdiyi üçün üçün.\n#### ElmirHacizade -\u003e D sualını qorxudub 13 bal aldığı üçün.\n\n#### Xanlar0 -\u003e Sonradan girib speedrun etdiyi üçün.\n$~$\n### Siz olmadan contest çox mənasız olardı, iştrakınız üçün (!)təşəkkürlər.\n \n-----\n# Sualların Editorialları\n$~$\n## **A - Əliyyiəkbərin parolları**\n### Həll 1\n##### Əgər sualı diqqətlə oxusanız görərdiniz ki , Əliyyiəkbər parolları uzunluqları azalmayan(yəni artan)sıra ilə daxil edir.Biz bu məsələyə belə bir kod yaza bilərik.\n```\n#include \u003cbits/stdc++.h\u003e\nusing namespace std;\nsigned main()\n{\n ios_base::sync_with_stdio(0);\n cin.tie(0);\n cout.tie(0);\n\n int n , k;\n cin \u003e\u003e n \u003e\u003e k;\n\n map \u003c int , int \u003e m;\n string s;\n\n while(n--)\n {\n cin \u003e\u003e s;\n m[s.size()]++;\n }\n\n cin \u003e\u003e s;\n int sl \u003d s.size() , mintime \u003d 0 , maxtime \u003d 0;\n\n for(auto \u0026p : m)\n {\n if(p.first !\u003d sl)\n {\n mintime +\u003d p.second;\n maxtime +\u003d p.second;\n }\n else\n {\n mintime +\u003d 1;\n maxtime +\u003d p.second;\n break;\n }\n }\n\n mintime +\u003d ((mintime - 1) / k) * 5;\n maxtime +\u003d ((maxtime - 1) / k) * 5;\n\n cout \u003c\u003c mintime \u003c\u003c \" \" \u003c\u003c maxtime \u003c\u003c \"\\n\";\n}\n```\n-----\n## **B - Tənbəl Rəşad**\n### Həll 1\n##### Bu məsələ üçün çox sadə bir kod yaza bilərik.\n```\n#include \u003cbits/stdc++.h\u003e\n#define int long long\nusing namespace std;\n\nvoid solve()\n{\n int n;\n cin \u003e\u003e n;\n\n if(n\u003d\u003d1) cout \u003c\u003c 2 \u003c\u003c \"\\n\";\n else if(n%3\u003d\u003d0) cout \u003c\u003c n/3 \u003c\u003c \"\\n\";\n else cout \u003c\u003c n/3 + 1 \u003c\u003c \"\\n\";\n\n}\n\nsigned main()\n{\n ios_base::sync_with_stdio(0);\n cin.tie(0);\n cout.tie(0);\n\n int test;\n cin \u003e\u003e test;\n\n while(test--)\n {\n solve();\n }\n}\n```\n-----\n## **C - Zakirin bakteriyaları**\n### Həll 1\n##### Bu məsələdə lazım olan bakteriyaların sayı ədədin ikilik yazılışındaki 1-lərin sayı qədərdir. Belə bir kod yaza bilərik.\n```\n#include \u003cbits/stdc++.h\u003e\n#define int long long\nusing namespace std;\nsigned main()\n{\n ios_base::sync_with_stdio(0);\n cin.tie(0);\n cout.tie(0);\n\n int n;\n cin \u003e\u003e n;\n cout\u003c\u003c(__builtin_popcountll(n))\u003c\u003c\u0027\\n\u0027;\n}\n```\n### Həll 2\n##### Və ya ədədi 2-yə bölə-bölə gedərik və əgər ədəd tək olarsa say-ı 1 vahid artırarıq.\n```\n#include \u003cbits/stdc++.h\u003e\n#define int long long\nusing namespace std;\nsigned main()\n{\n ios_base::sync_with_stdio(0);\n cin.tie(0);\n cout.tie(0);\n\n int n , say \u003d 1;\n cin \u003e\u003e n;\n\n while (n !\u003d 1)\n {\n if (n%2 \u003d\u003d 1)\n {\n say++;\n }\n\n n /\u003d 2;\n }\n\n cout \u003c\u003c say;\n}\n```\n### Həll 3\n```\n#include \u003cbits/stdc++.h\u003e\n#define int long long\nusing namespace std;\nsigned main()\n{\n int n , say \u003d 1;\n cin \u003e\u003e n;\n while (n!\u003d1)\n {\n if (n%2 \u003d\u003d 1) say++;\n n /\u003d 2;\n }\n\n cout \u003c\u003c say;\n}\n\n```\n-----\n## **D - Elayın tapşırığı**\n### Həll 1\n##### Biz bu məsələni bfs alqoritmi ilə həll edə bilərik.İlk öncə yandıqılacaq olan təpələrin nömrələrini queue -yə əlavə edərik və daha sonra isə bfs -i çalışdırarıq.\n```\n#include \u003cbits/stdc++.h\u003e\n#define MAX (int)1e5 + 5\nusing namespace std;\nint color[MAX] , dis[MAX];\nint n , m , a , b , k;\nvector \u003c int \u003e g[MAX];\nqueue \u003c int \u003e q;\nvoid bfs()\n{\n while(!q.empty())\n {\n int u \u003d q.front();\n for(auto \u0026p : g[u])\n {\n if(color[p] \u003d\u003d 0)\n {\n q.push(p);\n color[p] \u003d 1;\n dis[p] \u003d dis[u] + 1;\n }\n }\n q.pop();\n }\n}\nsigned main()\n{\n ios_base::sync_with_stdio(0);\n cin.tie(0);\n cout.tie(0);\n\n cin \u003e\u003e n \u003e\u003e m;\n while(m--)\n {\n cin \u003e\u003e a \u003e\u003e b;\n g[a].push_back(b);\n g[b].push_back(a);\n }\n\n cin \u003e\u003e k;\n while(k--)\n {\n cin \u003e\u003e a;\n q.push(a);\n color[a] \u003d 1;\n }\n\n bfs();\n\n int maxi \u003d dis[0];\n int cord \u003d 1;\n\n for(int i \u003d 1;i \u003c\u003d n;i++)\n {\n if(dis[i] \u003e maxi)\n {\n maxi \u003d dis[i];\n cord \u003d i;\n }\n }\n\n cout \u003c\u003c maxi \u003c\u003c \"\\n\" \u003c\u003c cord;\n}\n```\n-----\n## **E - Altsətirlərin sayı**\n### Həll 1\n##### Biz bu məsələ üçün 3D dp-dən istifadə edə bilərik. \n```\n#include \u003cbits/stdc++.h\u003e\n\nusing namespace std;\n\nconst int MOD \u003d int(1e9) + 7;\nconst int N \u003d 200043;\nconst int K \u003d 4;\n\nint add(int x, int y)\n{\n \tx +\u003d y;\n \twhile(x \u003e\u003d MOD) x -\u003d MOD;\n \twhile(x \u003c 0) x +\u003d MOD;\n \treturn x;\n}\n\nint mul(int x, int y)\n{\n \treturn (x * 1ll * y) % MOD;\n}\n\nint n;\nstring s;\nint dp[N][K][K];\nchar buf[N];\nint pow3[N];\n\nint main()\n{\n\tcin \u003e\u003e n;\n\tcin \u003e\u003e buf;\n\ts \u003d buf;\n\tint cntQ \u003d 0;\n\tfor(auto c : s)\n\t\tif(c \u003d\u003d \u0027?\u0027)\n\t\t\tcntQ++;\n\tpow3[0] \u003d 1;\n\tfor(int i \u003d 1; i \u003c N; i++)\n\t\tpow3[i] \u003d mul(pow3[i - 1], 3);\n\tdp[0][0][0] \u003d 1;\n\tfor(int i \u003d 0; i \u003c n; i++)\n\t\tfor(int j \u003d 0; j \u003c\u003d 3; j++)\n\t\t\tfor(int k \u003d 0; k \u003c\u003d 3; k++)\n\t\t\t{\n\t\t\t \tif(!dp[i][j][k]) continue;\n\t\t\t \tdp[i + 1][j][k] \u003d add(dp[i + 1][j][k], dp[i][j][k]);\n\t\t\t \tif(j \u003c 3 \u0026\u0026 (s[i] \u003d\u003d \u0027?\u0027 || s[i] - \u0027a\u0027 \u003d\u003d j))\n\t\t\t \t{\n\t\t\t \t \tint nk \u003d (s[i] \u003d\u003d \u0027?\u0027 ? k + 1 : k);\n\t\t\t \t \tdp[i + 1][j + 1][nk] \u003d add(dp[i + 1][j + 1][nk], dp[i][j][k]);\n\t\t\t \t}\n\t\t \t}\n\tint ans \u003d 0;\n\tfor(int i \u003d 0; i \u003c\u003d 3; i++)\n\t\tif(cntQ \u003e\u003d i)\n\t\t\tans \u003d add(ans, mul(dp[n][3][i], pow3[cntQ - i]));\n\tcout \u003c\u003c ans;\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:#959595\"\u003eCebrayil09](https://codeforces.com/profile/Cebrayil09)\n \n-----","threadId":185534,"likeCnt":7,"createTime":1710063814000,"isWorkbook":false,"viewCnt":92,"openness":2,"fav":false,"id":4681,"trustable":false}