Home
Problem
Status
Contest
Workbook
User
Group
Forum
Register
Login
{"managingGroups":{},"author":"Xanlar0","updateTime":1710707494000,"title":"Kepezcup Round #1 Edutorial","dislikeCnt":0,"content":"-----\n# Sualları İlk Həll Edənlər\n$~$\n### A - 00:03:51 (*TheSumuraz*)\n### B - 00:06:57 (*TheSumuraz*)\n### C - 00:02:45 (*Aliyyiakbar*)\n### D - 01:32:44 (*hasanov*)\n### E - 02:01:15 (*Zakir060*)\n### F - 00:53:37 (*Aliyyiakbar*)\n$~$\n \n#### Sıralama : https://vjudge.net/contest/616707#rank\n \n-----\n# Honorable Mentions\n$~$\n#### Aliyyiakbar -\u003e İnanılmaz performansı və birinciliyi üçün.\n#### TheSumuraz -\u003e F sualında 5 ədəd cəhd göstərib öz gücünü göstərdiyi üçün.\n#### hasanov -\u003e Speedrun eləyərək 2ciliyə yüksəldiyi üçün.\n#### Zakir060 -\u003e Yarışdan sonra E sualını izah eləməyə çalış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- 1%**\n### İzah\n##### Bizə şərtdə deyildiyi kimi hər dəfə ədədi 1% artırırıq və başlanğıc ədədimiz 100dür. Ədədi 1 faiz artırmaq onun üzərinə ədədin 100\u0027ə bölünməsini gəlmək deməkdir.\n```\n#pragma GCC optimize(\"Ofast,no-stack-protector,unroll-loops\")\n#pragma GCC target(\"sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune\u003dnative\")\n\n#include \u003cbits/stdc++.h\u003e\n#include \u003cext/pb_ds/assoc_container.hpp\u003e \n#include \u003cext/pb_ds/tree_policy.hpp\u003e \n#define run ios_base::sync_with_stdio(false);cin.tie(0);\n\n#define ll long long\n#define pll pair\u003cll, ll\u003e\n#define ull unsigned ll\n#define ld long double\n#define endl \"\\n\"\n#define pb push_back\n\n#define pi 3.14159265359\n#define N 107\n#define minimum -9223372036854775807\n#define maximum -minimum\n#define mod 1000000007\n#define INF 1e12\n\nusing namespace std;\nusing namespace __gnu_pbds;\ntemplate \u003cclass t\u003e\nusing ordered_set\u003dtree\u003ct, null_type,less\u003ct\u003e, rb_tree_tag,tree_order_statistics_node_update\u003e;\n\nint main()\n{\n run;\n ll n;\n cin\u003e\u003en;\n ll k\u003d100;\n ll cvb\u003d0;\n while(n\u003ek)\n {\n \tk+\u003dk/100;\n \tcvb++;\n\t}\n\tcout\u003c\u003ccvb;\n}\n// By Xanlar\n```\n-----\n## B- Zakirin Slimelari\n### İzah\n##### Bizə verilən stringdə ardıcıl olaraq eyni olan hərfləri 1 saysaq, Hər dəfə əvvəlki hərfə bərabər olan hərf tapdıqda bu hal ödənməyənə qədər digər hərfə baxaq və qrupların sayını tapaq.\n```\n#pragma GCC optimize(\"Ofast,no-stack-protector,unroll-loops\")\n#pragma GCC target(\"sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune\u003dnative\")\n\n#include \u003cbits/stdc++.h\u003e\n#include \u003cext/pb_ds/assoc_container.hpp\u003e \n#include \u003cext/pb_ds/tree_policy.hpp\u003e \n#define run ios_base::sync_with_stdio(false);cin.tie(0);\n\n#define ll long long\n#define pll pair\u003cll, ll\u003e\n#define ull unsigned ll\n#define ld long double\n#define endl \"\\n\"\n#define pb push_back\n\n#define pi 3.14159265359\n#define N 107\n#define minimum -9223372036854775807\n#define maximum -minimum\n#define mod 1000000007\n#define INF 1e12\n\nusing namespace std;\nusing namespace __gnu_pbds;\ntemplate \u003cclass t\u003e\nusing ordered_set\u003dtree\u003ct, null_type,less\u003ct\u003e, rb_tree_tag,tree_order_statistics_node_update\u003e;\n\nint main()\n{\n run;\n ll n;\n cin\u003e\u003en;\n\tstring s;\n cin\u003e\u003es;\n ll cvb\u003d0;\n for(ll i\u003d0; i\u003cn; i++)\n {\n \twhile(s[i]\u003d\u003ds[i+1])\n \t{\n \t\ti++;\n\t\t}\n\t\tcvb++;\n\t}\n\tcout\u003c\u003ccvb;\n}\n// By Xanlar\n```\n-----\n## C- Almalar!\n### İzah\n##### N ədədi 20dən kiçik olduğuna görə aydındır ki, bitmaskdan istifadə edəcik. Həqiqətən də, bitmaskdan istifadə edərək almaları 2 qrupa bölüb, hər qrupdakıların cəmini müqayisə edə bilərik\n```\n#pragma GCC optimize(\"Ofast,no-stack-protector,unroll-loops\")\n#pragma GCC target(\"sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune\u003dnative\")\n\n#include \u003cbits/stdc++.h\u003e\n#include \u003cext/pb_ds/assoc_container.hpp\u003e \n#include \u003cext/pb_ds/tree_policy.hpp\u003e \n#define run ios_base::sync_with_stdio(false);cin.tie(0);\n\n#define ll long long\n#define pll pair\u003cll, ll\u003e\n#define ull unsigned ll\n#define ld long double\n#define endl \"\\n\"\n#define pb push_back\n\n#define pi 3.14159265359\n#define N 200007\n#define minimum -9223372036854775807\n#define maximum -minimum\n#define mod 1000000007\n#define INF 1e12\n\nusing namespace std;\nusing namespace __gnu_pbds;\ntemplate \u003cclass t\u003e\nusing ordered_set\u003dtree\u003ct, null_type,less\u003ct\u003e, rb_tree_tag,tree_order_statistics_node_update\u003e;\n\nint main()\n{\n\trun;\n ll n;\n ll minn\u003dmaximum;\n cin\u003e\u003en;\n ll a[n];\n for(ll i\u003d0; i\u003cn; i++)\n {\n cin\u003e\u003ea[i];\n }\n for(ll i\u003d0; i\u003c(1\u003c\u003cn); i++)\n {\n ll cebrayil\u003d0;\n ll sumuraz\u003d0;\n for(ll j\u003d0; j\u003cn; j++)\n {\n if(i\u0026(1\u003c\u003cj))\n cebrayil+\u003da[j];\n else\n sumuraz+\u003da[j];\n }\n minn\u003dmin(minn, abs(cebrayil-sumuraz));\n }\n cout\u003c\u003cminn;\n}\n// By Xanlar\n```\n-----\n## D- Sadəcə bir oyun\n### İzah\n##### Alimin skip istifadə etməsi üçün Röyalın 2 ədəd hard bossu öldürməsinə baxmayaraq onun yenə də hard bossla qarşılaşması lazımdır, yəni 3 ədəd çətin boss gəlsə 1 skipdən istifadə edəcək. Ancaq başqa bir hal da var ki, əgər 1-ci boss hard boss olarsa, bizim edə biləcəyimiz heç nə yoxdur və skipdən istifadə etməyə məcburuq\n```\n#pragma GCC optimize(\"Ofast,no-stack-protector,unroll-loops\")\n#pragma GCC target(\"sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune\u003dnative\")\n\n#include \u003cbits/stdc++.h\u003e\n#include \u003cext/pb_ds/assoc_container.hpp\u003e \n#include \u003cext/pb_ds/tree_policy.hpp\u003e \n#define run ios_base::sync_with_stdio(false);cin.tie(0);\n\n#define ll long long\n#define pll pair\u003cll, ll\u003e\n#define ull unsigned ll\n#define ld long double\n#define endl \"\\n\"\n#define pb push_back\n\n#define pi 3.14159265359\n#define N 200007\n#define minimum -9223372036854775807\n#define maximum -minimum\n#define mod 1000000007\n#define INF 1e12\n\nusing namespace std;\nusing namespace __gnu_pbds;\ntemplate \u003cclass t\u003e\nusing ordered_set\u003dtree\u003ct, null_type,less\u003ct\u003e, rb_tree_tag,tree_order_statistics_node_update\u003e;\n\nint main()\n{\n\trun;\n ll t;\n\tcin\u003e\u003et;\n\twhile(t--)\n\t{\n \tll n;\n \tcin\u003e\u003en;\n \tll a[n];\n \tfor(ll i\u003d0; i\u003cn; i++)\n \t{\n \t\tcin\u003e\u003ea[i];\n\t\t}\n\t\tll cvb\u003d0;\n\t\tif(a[0]\u003d\u003d1)\n\t\t\tcvb\u003d1;\n\t\tfor(ll i\u003d1; i\u003cn-2; i++)\n\t\t{\n\t\t\tif(a[i]\u003d\u003d1 \u0026\u0026 a[i+1]\u003d\u003d1 \u0026\u0026 a[i+2]\u003d\u003d1)\n\t\t\t{\n\t\t\t\tcvb++;\n\t\t\t\ti+\u003d2;\n\t\t\t}\n\t\t}\n\t\tcout\u003c\u003ccvb\u003c\u003cendl;\n\t}\n}\n// By Xanlar\n```\n-----\n## E- Segment tree?\n### İzah\n##### Bu sualda sizdən segment tree qurmaq istəyir və updatedə bir problem yoxdur, bizdən çıxışa verilməsi istənilən cəm qeyri-adidir. Bunun üçün ilk öncə build funksiyasında heç bir qeyri-adi dəyişiklik olmayacaq, sadə cəm segment treesinin buildini yazırıq\n```\nll n, q, a[N], t[N*4];\n\nvoid build(ll node, ll l, ll r)\n{\n\tif(l\u003d\u003dr)\n\t{\n\t\tt[node]\u003da[l];\n\t\treturn;\n\t}\n\tll mid\u003d(l+r)/2;\n\tbuild(node*2, l, mid);\n\tbuild(node*2+1, mid+1, r);\n\tt[node]\u003dt[node*2]+t[node*2+1];\n}\n```\n##### Get funksiyasında da adi cəm segment treesinin get funksiyasını yazırıq.\n```\nll get(ll node, ll l, ll r, ll ql, ll qr)\n{\n\tif(qr\u003cl || r\u003cql)\n\t\treturn 0;\n\tif(ql\u003c\u003dl \u0026\u0026 r\u003c\u003dqr)\n\t\treturn t[node];\n\tll mid\u003d(l+r)/2;\n\tll res1\u003dget(node*2, l, mid, ql, qr);\n\tll res2\u003dget(node*2+1, mid+1, r, ql, qr);\n\treturn res1+res2;\n}\n```\n##### Update funksiyasına keçməzdən öncə bizim massivin elementlərini bir müsbət bir mənfi olaraq yadda saxlayağıq və başladığımız indeksə görə işarəsini dəyişəscik, məsələn 1-2 -1 edirsə işarələrin yerini dəyişdikdə -1 ədədinin -1ə vurulmasının alınacağı məlumdur, -1+2\u003d1. Buna görə də massivin elementlərini bir müsbət bir mənfi olaraq saxlayacıq və querrylərdə əgər mənfi ədədləri cütlərdən başlayırıqsa cüt halını get funksiyasını mənfi get olaraq qaytarırıq. Bunu başa düşməyənlər üçün nümunədə göstərim:\n#### 2 3 4 1 5 massivini biz 2 -3 4 -1 5 kimi saxlasaq və 2 5 aralığını çıxışa verilməsi istənilirsə -3+4-1+5 yerinə 3-4+1-5 ədədi yəni -(-3+4-1+5) ədədini çıxışa verəcik.\n```\nvoid update(ll node, ll l, ll r, ll pos, ll val)\n{\n\tif(l\u003d\u003dr)\n\t{\n\t\tif(l%2\u003d\u003d0)\n\t\t\tt[node]\u003d-val;\n\t\telse\n\t\t\tt[node]\u003dval;\n\t\treturn;\n\t}\n\tll mid\u003d(l+r)/2;\n\tif(pos\u003c\u003dmid)\n\t\tupdate(node*2, l, mid, pos, val);\n\telse\n\t\tupdate(node*2+1, mid+1, r, pos, val);\n\tt[node]\u003dt[node*2]+t[node*2+1];\n}\n\nint main()\n{\n\trun;\n cin\u003e\u003en;\n for(ll i\u003d1; i\u003c\u003dn; i++)\n {\n \tcin\u003e\u003ea[i];\n \tif(i%2\u003d\u003d0)\n \t\ta[i]\u003d-1*a[i];\n\t}\n\tbuild(1, 1, n);\n\tcin\u003e\u003eq;\n\twhile(q--)\n\t{\n\t\tchar x;\n\t\tcin\u003e\u003ex;\n\t\tll l, r;\n\t\tcin\u003e\u003el\u003e\u003er;\n\t\tif(x\u003d\u003d\u00271\u0027)\n\t\t{\n\t\t\tif(l%2\u003d\u003d0)\n\t\t\t\tcout\u003c\u003c-get(1, 1, n, l, r)\u003c\u003cendl;\n\t\t\telse\n\t\t\t\tcout\u003c\u003cget(1, 1, n, l, r)\u003c\u003cendl;\n\t\t}\n\t\telse\n\t\t\tupdate(1, 1, n, l, r);\n\t}\n}\n// By Xanlar\n```\n##### Kodun ümumi halını istəyirsinizsə:\n```\n#pragma GCC optimize(\"Ofast,no-stack-protector,unroll-loops\")\n#pragma GCC target(\"sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune\u003dnative\")\n\n#include \u003cbits/stdc++.h\u003e\n#include \u003cext/pb_ds/assoc_container.hpp\u003e \n#include \u003cext/pb_ds/tree_policy.hpp\u003e \n#define run ios_base::sync_with_stdio(false);cin.tie(0);\n\n#define ll long long\n#define pll pair\u003cll, ll\u003e\n#define ull unsigned ll\n#define ld long double\n#define endl \"\\n\"\n#define pb push_back\n\n#define pi 3.14159265359\n#define N 200007\n#define minimum -9223372036854775807\n#define maximum -minimum\n#define mod 1000000007\n#define INF 1e12\n\nusing namespace std;\nusing namespace __gnu_pbds;\ntemplate \u003cclass t\u003e\nusing ordered_set\u003dtree\u003ct, null_type,less\u003ct\u003e, rb_tree_tag,tree_order_statistics_node_update\u003e;\n\nll n, q, a[N], t[N*4];\n\nvoid build(ll node, ll l, ll r)\n{\n\tif(l\u003d\u003dr)\n\t{\n\t\tt[node]\u003da[l];\n\t\treturn;\n\t}\n\tll mid\u003d(l+r)/2;\n\tbuild(node*2, l, mid);\n\tbuild(node*2+1, mid+1, r);\n\tt[node]\u003dt[node*2]+t[node*2+1];\n}\n\nll get(ll node, ll l, ll r, ll ql, ll qr)\n{\n\tif(qr\u003cl || r\u003cql)\n\t\treturn 0;\n\tif(ql\u003c\u003dl \u0026\u0026 r\u003c\u003dqr)\n\t\treturn t[node];\n\tll mid\u003d(l+r)/2;\n\tll res1\u003dget(node*2, l, mid, ql, qr);\n\tll res2\u003dget(node*2+1, mid+1, r, ql, qr);\n\treturn res1+res2;\n}\n\nvoid update(ll node, ll l, ll r, ll pos, ll val)\n{\n\tif(l\u003d\u003dr)\n\t{\n\t\tif(l%2\u003d\u003d0)\n\t\t\tt[node]\u003d-val;\n\t\telse\n\t\t\tt[node]\u003dval;\n\t\treturn;\n\t}\n\tll mid\u003d(l+r)/2;\n\tif(pos\u003c\u003dmid)\n\t\tupdate(node*2, l, mid, pos, val);\n\telse\n\t\tupdate(node*2+1, mid+1, r, pos, val);\n\tt[node]\u003dt[node*2]+t[node*2+1];\n}\n\nint main()\n{\n\trun;\n cin\u003e\u003en;\n for(ll i\u003d1; i\u003c\u003dn; i++)\n {\n \tcin\u003e\u003ea[i];\n \tif(i%2\u003d\u003d0)\n \t\ta[i]\u003d-1*a[i];\n\t}\n\tbuild(1, 1, n);\n\tcin\u003e\u003eq;\n\twhile(q--)\n\t{\n\t\tchar x;\n\t\tcin\u003e\u003ex;\n\t\tll l, r;\n\t\tcin\u003e\u003el\u003e\u003er;\n\t\tif(x\u003d\u003d\u00271\u0027)\n\t\t{\n\t\t\tif(l%2\u003d\u003d0)\n\t\t\t\tcout\u003c\u003c-get(1, 1, n, l, r)\u003c\u003cendl;\n\t\t\telse\n\t\t\t\tcout\u003c\u003cget(1, 1, n, l, r)\u003c\u003cendl;\n\t\t}\n\t\telse\n\t\t\tupdate(1, 1, n, l, r);\n\t}\n}\n// By Xanlar\n```\n-----\n## F- Asan Qraf\n### İzah\n##### Bu sualda 1 nodeundan başlayaraq hər nodeun istiqamətini (1 və ya 0) olaraq qeyd edəcik, 1 nodeunu istiqamətini 1 olaraq qeyd edək və dfslə qrafı gəzək. Əgər 1dən gəzəcəyimiz nodelar gəzilməyibsə 1in istiqamətinin əksini verəcəyik və o nodedan dfs başladacağıq, əks halda, yəni əgər həmin node gəzilibsə, digər sözlə cycle varsa, əgər gəzilmiş nodeun istiqaməti ilə olduğumuz nodeun istiqaməti ilə eynidirsə bu qrafda səhvlik var və cavab yoxdur, əks halda problem yoxdur və davam edə bilərik. Daha sonra bunları istiqamət massivindəkiləri çıxışa verə bilərik.\n```\n#pragma GCC optimize(\"Ofast,no-stack-protector,unroll-loops\")\n#pragma GCC target(\"sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune\u003dnative\")\n\n#include \u003cbits/stdc++.h\u003e\n#include \u003cext/pb_ds/assoc_container.hpp\u003e \n#include \u003cext/pb_ds/tree_policy.hpp\u003e \n#define run ios_base::sync_with_stdio(false);cin.tie(0);\n\n#define ll long long\n#define pll pair\u003cll, ll\u003e\n#define ull unsigned ll\n#define ld long double\n#define endl \"\\n\"\n#define pb push_back\n\n#define pi 3.14159265359\n#define N 200007\n#define minimum -9223372036854775807\n#define maximum -minimum\n#define mod 1000000007\n#define INF 1e12\n\nusing namespace std;\nusing namespace __gnu_pbds;\ntemplate \u003cclass t\u003e\nusing ordered_set\u003dtree\u003ct, null_type,less\u003ct\u003e, rb_tree_tag,tree_order_statistics_node_update\u003e;\n\nll n, m, used[N], dir[N];\nvector\u003cll\u003ev[N];\nbool bul\u003d1;\n\nvoid dfs(ll node)\n{\n\tused[node]\u003d1;\n\tfor(ll i:v[node])\n\t{\n\t\tif(!used[i])\n\t\t{\n\t\t\tif(dir[node]\u003d\u003d0)\n\t\t\t\tdir[i]\u003d1;\n\t\t\telse\n\t\t\t\tdir[i]\u003d0;\n\t\t\tdfs(i);\n\t\t}\n\t\telse if(used[i])\n\t\t{\n\t\t\tif(dir[i]\u003d\u003ddir[node])\n\t\t\t{\n\t\t\t\tbul\u003d0;\n\t\t\t\tbreak;\n\t\t\t}\n\t\t}\n\t}\n}\n\nint main()\n{\n\trun;\n cin\u003e\u003en\u003e\u003em;\n vector\u003cll\u003ew;\n while(m--)\n {\n \tll x, y;\n \tcin\u003e\u003ex\u003e\u003ey;\n \tv[x].pb(y);\n \tv[y].pb(x);\n \tw.pb(x);\n\t}\n\tdir[1]\u003d1;\n\tdfs(1);\n\tif(!bul)\n\t{\n\t\tcout\u003c\u003c\"NO\\n\";\n\t\treturn 0;\n\t}\n\tcout\u003c\u003c\"YES\\n\";\n\tfor(ll i:w)\n\t{\n\t\tif(dir[i]\u003d\u003d1)\n\t\t\tcout\u003c\u003c1;\n\t\telse\n\t\t\tcout\u003c\u003c0;\n\t}\n}\n// By Xanlar\n```\n# ***Əgər bu editorial sizə yardımcı oldusa,***\n# ***Bəyənməyi unutmayın!***","threadId":186941,"likeCnt":5,"createTime":1710707494000,"isWorkbook":false,"viewCnt":65,"openness":2,"fav":false,"id":4715,"trustable":false}