Home
Problem
Status
Contest
Workbook
User
Group
Forum
Register
Login
{"managingGroups":{},"author":"Aliyyiakbar","updateTime":1709240574000,"title":"NovruzCup Round #2 Editorial","dislikeCnt":0,"content":"-----\n## **A - Funkisyanı Hesabla**\n### Həll 1\n##### əgər $n$ cütdürsə, cavab $n/2$-dir, əks halda cavab $(n - 1) / 2 - n \u003d - (n + 1) / 2$ olur.\n```\n#include \u003ciostream\u003e\n\n#define AzH_TxdmN ios_base::sync_with_stdio(0);cin.tie(nullptr);cout.tie(nullptr);\nusing namespace std;\n\nlong long n;\n\nint main()\n{\n AzH_TxdmN\n cin\u003e\u003en;\n if (n%2 \u003d\u003d 0)\n {\n cout\u003c\u003cn/2\u003c\u003c\u0027\\n\u0027;\n return 0;\n }\n else\n {\n cout\u003c\u003c-(n/2)-1\u003c\u003c\u0027\\n\u0027;\n return 0;\n }\n}\n```\n-----\n## **B - Sumuş və Coraps**\n### Həll 1\n##### Sualın şərtində yazılan prossesi simulasya etmək olar, çünki $n, m \u003c\u003d 100$\n```\n#include \u003ciostream\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 a,b,res,used;\n\nsigned main()\n{\n AzH_TxdmN\n cin\u003e\u003ea\u003e\u003eb;\n while(a \u003e 0)\n {\n a--;\n res++;\n if (res%b \u003d\u003d 0)\n a++;\n }\n cout\u003c\u003cres\u003c\u003c\u0027\\n\u0027;\n}\n```\n\n### Həll 2\n##### Sualı riyazi induksiya tətbiq edərək aşağıdakı formulaya gətirmək mümkündür:\n##### $n + \\lfloor\\frac{n-1}{m-1}\\rfloor$ Burada $\\lfloor x \\rfloor$ tam hissəni bildirir.\n```\n#include \u003ciostream\u003e\nusing namespace std;\n \nint solve(int n, int m)\n{\n int s \u003d 0;\n s \u003d n + n/(m - 1);\n if (n%(m - 1) \u003d\u003d 0)\n s -\u003d 1;\n return s;\n}\n \nint main()\n{\n int n, m;\n cin \u003e\u003e n \u003e\u003e m;\n cout \u003c\u003c solve(n,m) \u003c\u003c endl;\n return 0;\n}\n```\n-----\n## **C - Zakirs Paths**\n### Həll 1\n##### Bu sualda Dinamik proqrqamlaşdırma tətbiq etmək olar. Gəlin $dp[i][j]$ bildirsin i-ci sütunun j-ci xanasına qədərki yolların sayı, onda\n##### $dp[i][j] \u003d dp[i-1][j] + dp[i][j-1]$\n##### əvvəla bütün (indeksləmə 1-dən aparılır) $dp[1][i]$ və $dp[i][1]$ -ləri 1-lə dolduraq çünki bu xanalara həmişə bir yolla gedə bilirik. Sonra isə yuxarıdakı formula ilə cavabı hesablayaq. Məsələni həll edərkən maneələri nəzərə almalıyıq.\n```\n#include \u003ciostream\u003e\n#include \u003calgorithm\u003e\n#include \u003cstring\u003e\n \n#define AzH_TxdmN ios_base::sync_with_stdio(0); cin.tie(nullptr); cout.tie(nullptr);\nusing namespace std;\n \nconst int MOD \u003d 1e9+7;\nint n,dp[1001][1001];\nchar a[1001][1001];\n \nint main()\n{\n AzH_TxdmN\n cin\u003e\u003en;\n for (int i \u003d 1; i \u003c\u003d n; i++)\n {\n for (int j \u003d 1; j \u003c\u003d n; j++)\n {\n cin\u003e\u003ea[i][j];\n }\n }\n if (a[1][1] \u003d\u003d \u0027*\u0027)\n {\n cout\u003c\u003c\"0\\n\";\n }\n else\n {\n for (int i \u003d 1; i \u003c\u003d n; i++)\n {\n if (a[1][i] \u003d\u003d \u0027*\u0027)\n {\n break;\n }\n else\n {\n dp[1][i] \u003d 1;\n }\n }\n for (int i \u003d 1; i \u003c\u003d n; i++)\n {\n if (a[i][1] \u003d\u003d \u0027*\u0027)\n {\n break;\n }\n else\n {\n dp[i][1] \u003d 1;\n }\n }\n for (int i \u003d 2; i \u003c\u003d n; i++)\n {\n for (int j \u003d 2; j \u003c\u003d n; j++)\n {\n if (a[i][j] !\u003d \u0027*\u0027)\n {\n dp[i][j] \u003d (dp[i-1][j] + dp[i][j-1])%MOD;\n }\n }\n }\n cout\u003c\u003cdp[n][n]\u003c\u003c\u0027\\n\u0027;\n }\n}\n```\n-----\n## **D - Dairəvi**\n### Həll 1\n##### Sualın şərtinə uyğun olaraq, o halda cycle tapmış olarıq ki, qrafda gələn/çıxan təpələrin sayı 2 olsun. Bütün komponentləri DFS alqoritmi ilə yığaq və yoxlayaq.\n```\n#include \u003ciostream\u003e\n#include \u003cvector\u003e\n#include \u003calgorithm\u003e\n#include \u003cext/pb_ds/assoc_container.hpp\u003e\n#include \u003cext/pb_ds/tree_policy.hpp\u003e\n\n#define int long long\n#define AzH_TxdmN ios_base::sync_with_stdio(0);cin.tie(nullptr);cout.tie(nullptr);\n\n#define ep emplace_back\nusing namespace std;\nusing namespace __gnu_pbds;\n\ntypedef tree\u003cint,null_type,less\u003cint\u003e,rb_tree_tag,tree_order_statistics_node_update\u003e__indexed_set;\ntypedef tree\u003cint,null_type,less_equal\u003cint\u003e,rb_tree_tag,tree_order_statistics_node_update\u003e__indexed_multiset;\nconst int N \u003d 3e5+9;\nconst int MOD \u003d 1e9+7;\nconst int INF \u003d 1e18;\nint used[N];\nvector\u003cint\u003ev[N];\nvector\u003cint\u003ecmp;\n\nint n,m,k,res;\n\nvoid dfs(int node)\n{\n used[node] \u003d 1;\n cmp.ep(node);\n for (int i : v[node])\n {\n if (!used[i])\n {\n dfs(i);\n }\n }\n}\n\nvoid solve()\n{\n cin\u003e\u003en\u003e\u003em;\n while(m--)\n {\n int x,y;\n cin\u003e\u003ex\u003e\u003ey;\n v[x].ep(y);\n v[y].ep(x);\n }\n for (int i \u003d 1; i \u003c\u003d n; ++i)\n {\n if (!used[i])\n {\n cmp.clear();\n dfs(i);\n bool ok \u003d true;\n for (int \u0026i : cmp) ok \u0026\u003d ((int)v[i].size() \u003d\u003d 2);\n res +\u003d ok;\n }\n }\n cout\u003c\u003cres\u003c\u003c\u0027\\n\u0027;\n}\n\nsigned main()\n{\n AzH_TxdmN\n int t \u003d 1;\n //cin\u003e\u003et;\n while (t--)\n {\n solve();\n }\n}\n```\n-----\n## **E - İntevriyü**\n### Həll 1\n##### Gəlin bu sualı nəzərə alaq: Əgər hər hansı $[a_l, ... , a_r]$ aralığını nəzərə alsaq, orada xüsusi daşın olduğunu haradan biləcəyik?\n\n- Əgər xüsusi daş bu aralıqda deyilsə, cəm $a_l + a_{l+1} + ... + a_{r-1} + a_r$ olacaq\n- Əgər xüsusi daş bu aralıqdadırsa, cəm $a_l + a_{l+1} + ... + a_{r-1} + a_r + 1$ olacaq\n\n##### Aralıqların cəmini prefix sum istifadə edərək $o(1)$ götürə bildiyimizi hesaba qatsaq, hər hansı aralıqın cavab olub olmadığını bir sorğu ilə tapa bilirik. Gəlin binary serach istifadə edərək cavabı tapmaya çalışaq. Əvvəla $[a_1;a_{n/2}]$ aralığını yoxlayaq. Əgər bu aralıqda xüsusi daş varsa, binary searchımızı bu aralıqda edək. Əks halda $[a_{n/2};a_n]$ aralığı ilə davam edək. \n##### Bu ən çoxu $\\lceil log_2(2 \\cdot 10^5 )\\rceil \u003d 18$ sorğu çəkəcək, hansı ki 30 soruğu limitindən qat qat aşağıdır.\n```\n#include \u003ciostream\u003e\n#include \u003calgorithm\u003e\n#include \u003cext/pb_ds/assoc_container.hpp\u003e\n#include \u003cext/pb_ds/tree_policy.hpp\u003e\n\n#define int long long\n#define AzH_TxdmN ios_base::sync_with_stdio(0);cin.tie(nullptr);cout.tie(nullptr);\n\nusing namespace std;\nusing namespace __gnu_pbds;\n\ntypedef tree\u003cint,null_type,less\u003cint\u003e,rb_tree_tag,tree_order_statistics_node_update\u003e__indexed_set;\ntypedef tree\u003cint,null_type,less_equal\u003cint\u003e,rb_tree_tag,tree_order_statistics_node_update\u003e__indexed_multiset;\nconst int sz \u003d 3e5+9;\nconst int MOD \u003d 1e9+7;\nconst int INF \u003d 1e18;\nint a[sz],pref[sz];\n\nint n;\n\nint ask(int l,int m)\n{\n int res;\n cout\u003c\u003c\"? \"\u003c\u003cm-l+1\u003c\u003c\u0027 \u0027;\n for (int i \u003d l; i \u003c\u003d m; ++i) cout\u003c\u003ci\u003c\u003c\u0027 \u0027;\n cout\u003c\u003cendl;\n cin\u003e\u003eres;\n return res;\n}\n\nvoid solve()\n{\n cin\u003e\u003en;\n for (int i \u003d 1; i \u003c\u003d n; ++i)\n {\n cin\u003e\u003ea[i];\n pref[i] \u003d pref[i-1] + a[i];\n }\n int l \u003d 1,r \u003d n,mid, best \u003d 0;\n while(l \u003c\u003d r)\n {\n mid \u003d (l+r)\u003e\u003e1;\n int query \u003d ask(l,mid);\n if (query \u003d\u003d pref[mid] - pref[l-1])\n {\n l \u003d mid+1;\n }\n else\n {\n best \u003d mid;\n r \u003d mid-1;\n }\n }\n cout\u003c\u003c\"! \"\u003c\u003cbest\u003c\u003cendl;\n}\n\nsigned main()\n{\n //AzH_TxdmN\n int t \u003d 1;\n cin\u003e\u003et;\n while (t--)\n {\n solve();\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-----\n","threadId":184093,"likeCnt":7,"createTime":1709150317000,"isWorkbook":false,"viewCnt":86,"openness":2,"fav":false,"id":4641,"trustable":false}