{"id":42076,"date":"2023-01-25T21:14:06","date_gmt":"2023-01-25T17:44:06","guid":{"rendered":"https:\/\/quera.org\/blog\/?p=42076"},"modified":"2023-01-30T20:37:54","modified_gmt":"2023-01-30T17:07:54","slug":"newbies-2019-solutions","status":"publish","type":"post","link":"https:\/\/quera.org\/blog\/newbies-2019-solutions\/","title":{"rendered":"\u0631\u0627\u0647\u200c\u062d\u0644\u200c\u0647\u0627\u06cc \u0645\u0633\u0627\u0628\u0642\u0647 \u0627\u0644\u06af\u0648\u0631\u06cc\u062a\u0645\u06cc Newbies 2019"},"content":{"rendered":"\n<p class=\"has-medium-font-size wp-block-paragraph\"><strong>\u0633\u0644\u0627\u0645!<\/strong><\/p>\n\n\n\n<p class=\"wp-block-paragraph\">\u0645\u0633\u0627\u0628\u0642\u0627\u062a \u0627\u0644\u06af\u0648\u0631\u06cc\u062a\u0645\u06cc Newbies \u0632\u0645\u0633\u062a\u0648\u0646 \u0647\u0631 \u0633\u0627\u0644 \u062f\u0631 \u062f\u0627\u0646\u0634\u06af\u0627\u0647 \u0634\u0647\u06cc\u062f \u0628\u0647\u0634\u062a\u06cc \u0628\u0631\u06af\u0632\u0627\u0631 \u0645\u06cc\u0634\u0647. \u0633\u0637\u062d \u0633\u0624\u0627\u0644\u0627\u062a \u0627\u06cc\u0646 \u0645\u0633\u0627\u0628\u0642\u0647 \u0628\u0647 \u0646\u0633\u0628\u062a \u0645\u0633\u0627\u0628\u0642\u0627\u062a \u0631\u0633\u0645\u06cc ACM \u0622\u0633\u0648\u0646\u200c\u062a\u0631\u0647 \u0648\u0644\u06cc \u0633\u0628\u06a9 \u0633\u0624\u0627\u0644\u0627\u062a \u062d\u0641\u0638 \u0634\u062f\u0647 \u0648 \u0634\u0631\u06a9\u062a \u062a\u0648\u0634 \u0628\u0631\u0627\u06cc \u0639\u0644\u0627\u0642\u0647\u200c\u0645\u0646\u062f\u0627\u0646 \u0627\u0644\u06af\u0648\u0631\u06cc\u062a\u0645\u060c \u0628\u0686\u0647\u200c\u0647\u0627\u06cc \u0627\u0644\u0645\u067e\u06cc\u0627\u062f\u06cc\u060c \u062f\u0627\u0646\u0634\u062c\u0648\u0647\u0627\u06cc \u062a\u0631\u0645 \u0627\u0648\u0644 \u0648 \u062f\u0648\u0645 \u0648 \u0647\u0645\u0647 \u06a9\u0633\u0627\u0646\u06cc \u06a9\u0647 \u0645\u06cc\u200c\u062e\u0648\u0627\u0646 \u062f\u0631 \u0645\u0633\u0627\u0628\u0642\u0627\u062a ACM-ICPC \u0634\u0631\u06a9\u062a \u06a9\u0646\u0646\u062f\u060c \u0645\u06cc\u200c\u062a\u0648\u0646\u0647 \u062c\u0630\u0627\u0628 \u0648 \u0686\u0627\u0644\u0634\u06cc \u0628\u0627\u0634\u0647.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">\u0647\u0645\u0648\u0646 \u0637\u0648\u0631 \u06a9\u0647 \u0645\u06cc\u200c\u062f\u0648\u0646\u06cc\u062f \u062a\u0635\u0645\u06cc\u0645 \u06af\u0631\u0641\u062a\u06cc\u0645 \u0645\u0633\u0627\u0628\u0642\u0627\u062a \u0633\u0627\u0644\u200c\u0647\u0627\u06cc \u06af\u0630\u0634\u062a\u0647 Newbies \u0631\u0648 \u0628\u0647\u200c\u0635\u0648\u0631\u062a \u0622\u0646\u0644\u0627\u06cc\u0646 \u062f\u0631 \u06a9\u0648\u0626\u0631\u0627 \u0628\u0631\u06af\u0632\u0627\u0631 \u06a9\u0646\u06cc\u0645 \u062a\u0627 \u0641\u0631\u0635\u062a\u06cc \u0628\u0631\u0627\u06cc \u062a\u0645\u0631\u06cc\u0646 \u0648 \u0631\u0642\u0627\u0628\u062a \u0628\u0627\u0634\u0647. \u0627\u06cc\u0646 \u0647\u0641\u062a\u0647 \u0645\u0633\u0627\u0628\u0642\u0647\u200c\u06cc \u0627\u0644\u06af\u0648\u0631\u06cc\u062a\u0645\u06cc Newbies 2019 \u062f\u0631 \u06a9\u0648\u0626\u0631\u0627 \u0628\u0631\u06af\u0632\u0627\u0631 \u0634\u062f. \u0627\u06cc\u0646 \u0645\u0633\u0627\u0628\u0642\u0647 \u062f\u0631 \u0633\u0627\u0644 \u06f2\u06f0\u06f1\u06f9 \u062f\u0631 \u062f\u0627\u0646\u0634\u06af\u0627\u0647 \u0634\u0647\u06cc\u062f \u0628\u0647\u0634\u062a\u06cc \u0628\u0627 \u062a\u0644\u0627\u0634 \u00ab\u0645\u062d\u0645\u062f\u0631\u0636\u0627 \u0645\u062d\u0633\u0646\u06cc\u00bb\u060c \u00ab\u0639\u0631\u0641\u0627\u0646 \u0639\u0644\u06cc\u200c\u0645\u062d\u0645\u062f\u06cc\u00bb\u060c \u00ab\u0645\u0647\u062f\u06cc \u0622\u0647\u0646\u06af\u0631\u0627\u0646\u00bb\u060c \u00ab\u0628\u0631\u062f\u06cc\u0627 \u0627\u0628\u0647\u0631\u06cc\u00bb \u0648 \u00ab\u0639\u0644\u06cc \u0645\u06cc\u0631\u062c\u0647\u0627\u0646\u06cc\u00bb \u0637\u0631\u0627\u062d\u06cc \u0648 \u0628\u0631\u06af\u0632\u0627\u0631 \u0634\u062f\u0647 \u0628\u0648\u062f.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">\u0631\u0627\u0647\u200c\u062d\u0644\u200c\u0647\u0627\u06cc \u0633\u0624\u0627\u0644\u0627\u062a \u0627\u06cc\u0646 \u0645\u0633\u0627\u0628\u0642\u0647 \u062f\u0631 \u0627\u062f\u0627\u0645\u0647 \u062a\u0648\u0636\u06cc\u062d \u062f\u0627\u062f\u0647 \u0634\u062f\u0646\u062f. \u062f\u0631 \u0635\u0648\u0631\u062a\u06cc \u06a9\u0647 \u0645\u062a\u0648\u062c\u0647 \u0631\u0627\u0647\u200c\u062d\u0644\u06cc \u0646\u0634\u062f\u06cc\u062f\u060c \u0645\u06cc\u200c\u062a\u0648\u0646\u06cc\u062f \u062f\u0631 \u0628\u062e\u0634 \u0646\u0638\u0631\u0627\u062a\u060c \u0633\u0624\u0627\u0644\u0627\u062a \u0648 \u0627\u0628\u0647\u0627\u0645\u200c\u0647\u0627\u06cc \u062e\u0648\u062f\u062a\u0648\u0646 \u0631\u0648 \u0645\u0637\u0631\u062d \u06a9\u0646\u06cc\u062f. \u0627\u06af\u0647 \u0631\u0627\u0647\u200c\u062d\u0644 \u062f\u06cc\u06af\u0647\u200c\u0627\u06cc \u0628\u0631\u0627\u06cc \u0633\u0624\u0627\u0644\u0627\u062a \u062f\u0627\u0631\u06cc\u062f\u060c \u062e\u0648\u0634\u062d\u0627\u0644 \u0645\u06cc\u200c\u0634\u06cc\u0645 \u06a9\u0647 \u0631\u0627\u0647\u200c\u062d\u0644\u062a\u0648\u0646 \u0631\u0648 \u062f\u0631 \u0628\u062e\u0634 \u0646\u0638\u0631\u0627\u062a \u0628\u0627 \u0645\u0627 \u0648 \u062f\u0648\u0633\u062a\u0627\u0646\u062a\u0648\u0646 \u0628\u0647 \u0627\u0634\u062a\u0631\u0627\u06a9 \u0628\u0630\u0627\u0631\u06cc\u062f.<\/p>\n\n\n\n<div id=\"ez-toc-container\" class=\"ez-toc-v2_0_86 counter-hierarchy ez-toc-counter-rtl ez-toc-grey ez-toc-container-direction\">\n<div class=\"ez-toc-title-container\">\n<p class=\"ez-toc-title ez-toc-toggle\" style=\"cursor:pointer\">\u0641\u0647\u0631\u0633\u062a \u0645\u0637\u0627\u0644\u0628<\/p>\n<span class=\"ez-toc-title-toggle\"><a href=\"#\" class=\"ez-toc-pull-right ez-toc-btn ez-toc-btn-xs ez-toc-btn-default ez-toc-toggle\" aria-label=\"\u062a\u063a\u06cc\u06cc\u0631 \u0648\u0636\u0639\u06cc\u062a \u0641\u0647\u0631\u0633\u062a \u0645\u0637\u0627\u0644\u0628\"><span class=\"ez-toc-js-icon-con\"><span class=\"\"><span class=\"eztoc-hide\" style=\"display:none;\">Toggle<\/span><span class=\"ez-toc-icon-toggle-span\"><svg style=\"fill: #999;color:#999\" xmlns=\"http:\/\/www.w3.org\/2000\/svg\" class=\"list-377408\" width=\"20px\" height=\"20px\" viewBox=\"0 0 24 24\" fill=\"none\"><path d=\"M6 6H4v2h2V6zm14 0H8v2h12V6zM4 11h2v2H4v-2zm16 0H8v2h12v-2zM4 16h2v2H4v-2zm16 0H8v2h12v-2z\" fill=\"currentColor\"><\/path><\/svg><svg style=\"fill: #999;color:#999\" class=\"arrow-unsorted-368013\" xmlns=\"http:\/\/www.w3.org\/2000\/svg\" width=\"10px\" height=\"10px\" viewBox=\"0 0 24 24\" version=\"1.2\" baseProfile=\"tiny\"><path d=\"M18.2 9.3l-6.2-6.3-6.2 6.3c-.2.2-.3.4-.3.7s.1.5.3.7c.2.2.4.3.7.3h11c.3 0 .5-.1.7-.3.2-.2.3-.5.3-.7s-.1-.5-.3-.7zM5.8 14.7l6.2 6.3 6.2-6.3c.2-.2.3-.5.3-.7s-.1-.5-.3-.7c-.2-.2-.4-.3-.7-.3h-11c-.3 0-.5.1-.7.3-.2.2-.3.5-.3.7s.1.5.3.7z\"\/><\/svg><\/span><\/span><\/span><\/a><\/span><\/div>\n<nav><ul class='ez-toc-list ez-toc-list-level-1 ' ><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-1\" href=\"https:\/\/quera.org\/blog\/newbies-2019-solutions\/#A_%E2%80%93_Cosmic_Twins\" >A \u2013 Cosmic Twins<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-2\" href=\"https:\/\/quera.org\/blog\/newbies-2019-solutions\/#B_%E2%80%93_Yet_Another_Paper\" >B \u2013 Yet Another Paper<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-3\" href=\"https:\/\/quera.org\/blog\/newbies-2019-solutions\/#C_%E2%80%93_Jack-Jack_and_Matrices\" >C \u2013 Jack-Jack and Matrices<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-4\" href=\"https:\/\/quera.org\/blog\/newbies-2019-solutions\/#D_%E2%80%93_Champions_League\" >D \u2013 Champions League<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-5\" href=\"https:\/\/quera.org\/blog\/newbies-2019-solutions\/#E_%E2%80%93_Tic-Tac-Toe\" >E \u2013 Tic-Tac-Toe<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-6\" href=\"https:\/\/quera.org\/blog\/newbies-2019-solutions\/#F_%E2%80%93_Circles\" >F \u2013 Circles<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-7\" href=\"https:\/\/quera.org\/blog\/newbies-2019-solutions\/#G_%E2%80%93_Network_Connections\" >G \u2013 Network Connections<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-8\" href=\"https:\/\/quera.org\/blog\/newbies-2019-solutions\/#H_%E2%80%93_Music_Shopping\" >H \u2013 Music Shopping<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-9\" href=\"https:\/\/quera.org\/blog\/newbies-2019-solutions\/#I_%E2%80%93_Morning_Run\" >I \u2013 Morning Run<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-10\" href=\"https:\/\/quera.org\/blog\/newbies-2019-solutions\/#J_%E2%80%93_Seasons\" >J \u2013 Seasons<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-11\" href=\"https:\/\/quera.org\/blog\/newbies-2019-solutions\/#K_%E2%80%93_The_Sacred_Number\" >K \u2013 The Sacred Number<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-12\" href=\"https:\/\/quera.org\/blog\/newbies-2019-solutions\/#L_%E2%80%93_N-Bonacci_Numbers\" >L \u2013 N-Bonacci Numbers<\/a><\/li><\/ul><\/nav><\/div>\n<h2 class=\"has-medium-font-size wp-block-heading\" id=\"h-a-cosmic-twins\"><span class=\"ez-toc-section\" id=\"A_%E2%80%93_Cosmic_Twins\"><\/span><strong><a href=\"https:\/\/quera.org\/problemset\/168941\/\" target=\"_blank\" rel=\"noreferrer noopener\">A \u2013 Cosmic Twins<\/a><\/strong><span class=\"ez-toc-section-end\"><\/span><\/h2>\n\n\n\n<p class=\"wp-block-paragraph\">\u0627\u06af\u0631&nbsp;<span class=\"katex-eq\" data-katex-display=\"false\">P<\/span>&nbsp;\u0628\u06cc\u0634\u062a\u0631 \u0627\u0632&nbsp;<span class=\"katex-eq\" data-katex-display=\"false\">D<\/span>&nbsp;\u0628\u0627\u0634\u062f\u060c \u0647\u0645\u0648\u0627\u0631\u0647 \u062f\u0648 \u0646\u0641\u0631 \u0648\u062c\u0648\u062f \u062f\u0627\u0631\u0646\u062f \u06a9\u0647 \u0631\u0648\u0632\u0647\u0627\u06cc \u062a\u0648\u0644\u062f\u0634\u0627\u0646 \u062f\u0631 \u06cc\u06a9 \u0631\u0648\u0632 \u0628\u0627\u0634\u062f. \u0628\u0646\u0627\u0628\u0631\u0627\u06cc\u0646 \u062f\u0631 \u0627\u06cc\u0646 \u062d\u0627\u0644\u062a\u060c \u067e\u0627\u0633\u062e \u0645\u0633\u0626\u0644\u0647 \u0628\u0631\u0627\u0628\u0631&nbsp;<span class=\"katex-eq\" data-katex-display=\"false\">1<\/span>&nbsp;\u0627\u0633\u062a.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">\u0627\u06af\u0631&nbsp;<span class=\"katex-eq\" data-katex-display=\"false\">P<\/span>&nbsp;\u06a9\u0645\u062a\u0631 \u0645\u0633\u0627\u0648\u06cc&nbsp;<span class=\"katex-eq\" data-katex-display=\"false\">D<\/span>&nbsp;\u0628\u0627\u0634\u062f\u060c \u0627\u062d\u062a\u0645\u0627\u0644 \u0627\u06cc\u0646\u06a9\u0647 \u062f\u0648 \u0646\u0641\u0631 \u0648\u062c\u0648\u062f \u062f\u0627\u0634\u062a\u0647 \u0628\u0627\u0634\u0646\u062f \u06a9\u0647 \u0631\u0648\u0632 \u062a\u0648\u0644\u062f\u0634\u0627\u0646 \u06cc\u06a9\u06cc \u0628\u0627\u0634\u062f \u0631\u0627 \u0627\u0632 \u0637\u0631\u06cc\u0642 \u0627\u0635\u0644 \u0645\u062a\u0645\u0645 \u062d\u0633\u0627\u0628 \u0645\u06cc\u200c\u06a9\u0646\u06cc\u0645.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">\u0627\u06af\u0631 \u0633\u0627\u0644&nbsp;<span class=\"katex-eq\" data-katex-display=\"false\">D<\/span>&nbsp;\u0631\u0648\u0632 \u062f\u0627\u0634\u062a\u0647 \u0628\u0627\u0634\u062f\u060c \u0627\u062d\u062a\u0645\u0627\u0644 \u0627\u06cc\u0646\u06a9\u0647 \u0647\u06cc\u0686 \u062f\u0648\u0646\u0641\u0631\u06cc \u062a\u0648\u0644\u062f\u0634\u0627\u0646 \u062f\u0631 \u06cc\u06a9 \u0631\u0648\u0632 \u0646\u0628\u0627\u0634\u0646\u062f. \u0628\u0631\u0627\u0628\u0631 \u0627\u0633\u062a \u0628\u0627:<\/p>\n\n\n\n<div class=\"wp-block-katex-display-block katex-eq\" data-katex-display=\"true\"><pre> \\frac{D \\times (D-1) \\times  .  .  .  \\times (D-P+1)}{ D^{P} } <\/pre><\/div>\n\n\n\n<p class=\"wp-block-paragraph\">\u0628\u0646\u0627\u0628\u0631\u0627\u06cc\u0646 \u0627\u06af\u0631 \u0633\u0627\u0644&nbsp;<span class=\"katex-eq\" data-katex-display=\"false\">D<\/span>&nbsp;\u0631\u0648\u0632 \u062f\u0627\u0634\u062a\u0647 \u0628\u0627\u0634\u062f\u060c \u0627\u062d\u062a\u0645\u0627\u0644 \u0627\u06cc\u0646\u06a9\u0647 \u062f\u0648 \u0646\u0641\u0631 \u0648\u062c\u0648\u062f \u062f\u0627\u0634\u062a\u0647 \u0628\u0627\u0634\u0646\u062f \u06a9\u0647 \u062a\u0648\u0644\u062f\u0634\u0627\u0646 \u062f\u0631 \u06cc\u06a9 \u0631\u0648\u0632 \u0628\u0627\u0634\u062f \u0628\u0631\u0627\u0628\u0631 \u0627\u0633\u062a \u0628\u0627:<\/p>\n\n\n\n<div class=\"wp-block-katex-display-block katex-eq\" data-katex-display=\"true\"><pre>1- \\frac{D \\times (D-1) \\times  .  .  .  \\times (D-P+1)}{ D^{P} } <\/pre><\/div>\n\n\n\n<p class=\"wp-block-paragraph\">\u067e\u06cc\u0686\u06cc\u062f\u06af\u06cc \u0632\u0645\u0627\u0646\u06cc: <span class=\"katex-eq\" data-katex-display=\"false\">O(P) <\/span><\/p>\n\n\n\n<div style=\"height:10px\" aria-hidden=\"true\" class=\"wp-block-spacer\"><\/div>\n\n\n\n<pre class=\"wp-block-code\"><code lang=\"cpp\" class=\"language-cpp line-numbers\">#include &lt;bits\/stdc++.h&gt;\n\nusing namespace std;\n\ntypedef long double LD;\ntypedef long long int LL;\ntypedef pair &lt;int,int&gt; pii;\n\n#define L first\n#define R second\n\nint main() {\n\tios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);\n\tLD p, d;\n\tcin &gt;&gt; p &gt;&gt; d;\n\tif (d &lt; p) {\n\t\tcout &lt;&lt; \"1.000000\\n\";\n\t\treturn 0;\n\t}\n\tLD ans = 1; \n\tfor (int i = 0; i &lt; p; i++)\n\t\tans = (ans * (d - i)) \/ d;\n\tcout.precision(6);\n\tcout &lt;&lt; fixed &lt;&lt; 1 - ans &lt;&lt; endl;\n\n\treturn 0;\n}<\/code><\/pre>\n\n\n\n<div style=\"height:35px\" aria-hidden=\"true\" class=\"wp-block-spacer\"><\/div>\n\n\n\n<h2 class=\"has-medium-font-size wp-block-heading\" id=\"h-b-yet-another-paper\"><span class=\"ez-toc-section\" id=\"B_%E2%80%93_Yet_Another_Paper\"><\/span><strong><a href=\"https:\/\/quera.org\/problemset\/168942\/\" target=\"_blank\" rel=\"noreferrer noopener\">B \u2013 Yet Another Paper<\/a><\/strong><span class=\"ez-toc-section-end\"><\/span><\/h2>\n\n\n\n<p class=\"wp-block-paragraph\">\u06cc\u06a9 \u0631\u0648\u0634 \u0628\u0631\u0627\u06cc \u0645\u0631\u062a\u0628 \u06a9\u0631\u062f\u0646 \u062f\u0646\u0628\u0627\u0644\u0647\u060c \u0628\u0627 \u06a9\u0645\u062a\u0631\u06cc\u0646 \u062a\u0639\u062f\u0627\u062f \u0639\u0645\u0644\u06cc\u0627\u062a\u200c\u0647\u0627\u06cc \u062a\u0639\u0631\u06cc\u0641 \u0634\u062f\u0647 \u0627\u06cc\u0646 \u0627\u0633\u062a \u06a9\u0647\u061b \u0627\u0632 \u0686\u067e \u0628\u0647 \u0631\u0627\u0633\u062a \u062d\u0631\u06a9\u062a \u06a9\u0646\u06cc\u0645\u060c \u0647\u0631 \u0628\u0627\u0631 \u06a9\u0648\u0686\u06a9\u200c\u062a\u0631\u06cc\u0646 \u0639\u062f\u062f\u06cc \u06a9\u0647 \u062f\u0631 \u0633\u0645\u062a \u0631\u0627\u0633\u062a \u0645\u0627 \u0642\u0631\u0627\u0631 \u062f\u0627\u0634\u062a\u060c (\u0627\u06af\u0631 \u0686\u0646\u062f \u0639\u062f\u062f \u0628\u0627 \u0627\u06cc\u0646 \u062e\u0627\u0635\u06cc\u062a \u0648\u062c\u0648\u062f \u062f\u0627\u0634\u062a\u060c \u0633\u0645\u062a \u0686\u067e\u200c\u062a\u0631\u06cc\u0646 \u0631\u0627 \u062f\u0631 \u0646\u0638\u0631 \u0628\u06af\u06cc\u0631\u06cc\u062f.) \u0631\u0627 \u0628\u0647 \u062a\u0639\u062f\u0627\u062f\u06cc \u062c\u0627\u0628\u0647\u200c\u062c\u0627\u06cc\u06cc \u0628\u0647 \u0627\u06cc\u0646 \u062c\u0627\u06cc\u06af\u0627\u0647 \u0628\u06cc\u0627\u0648\u0631\u06cc\u0645.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">\u067e\u06cc\u0686\u06cc\u062f\u06af\u06cc \u0632\u0645\u0627\u0646\u06cc: <span class=\"katex-eq\" data-katex-display=\"false\">O(N^2) <\/span><\/p>\n\n\n\n<div style=\"height:10px\" aria-hidden=\"true\" class=\"wp-block-spacer\"><\/div>\n\n\n\n<pre class=\"wp-block-code\"><code lang=\"cpp\" class=\"language-cpp line-numbers\">#include &lt;bits\/stdc++.h&gt;\n\nusing namespace std;\n\nconst int maxn = 2000;\nint a[maxn];\n\nint main()\n{\n\tios_base::sync_with_stdio(false); cin.tie(0);\n\tint n;\n\tcin &gt;&gt; n;\n\tfor (int i = 0; i &lt; n; i++)\n\t\tcin &gt;&gt; a[i];\n\n\tint ans = 0;\n\tfor (int i = 0; i &lt; n; i++)\n\t{\n\t\tint min_idx = i;\n\t\tfor (int j = i + 1; j &lt; n; j++)\n\t\t\tif (a[min_idx] &gt; a[j])\n\t\t\t\tmin_idx = j;\n\n\t\tans += min_idx - i;\n\n\t\tfor (int j = min_idx - 1; j &gt;= i; j--)\n\t\t\tswap(a[j], a[j + 1]);\n\t}\n\n\tcout &lt;&lt; ans &lt;&lt; '\\n';\n\n\treturn 0;\n}<\/code><\/pre>\n\n\n\n<div style=\"height:35px\" aria-hidden=\"true\" class=\"wp-block-spacer\"><\/div>\n\n\n\n<h2 class=\"has-medium-font-size wp-block-heading\" id=\"h-c-jack-jack-and-matrices\"><span class=\"ez-toc-section\" id=\"C_%E2%80%93_Jack-Jack_and_Matrices\"><\/span><strong><a href=\"https:\/\/quera.org\/problemset\/168943\/\" target=\"_blank\" rel=\"noreferrer noopener\">C \u2013 Jack-Jack and Matrices<\/a><\/strong><span class=\"ez-toc-section-end\"><\/span><\/h2>\n\n\n\n<p class=\"wp-block-paragraph\">\u0628\u0631\u0627\u06cc \u0647\u0631 \u062e\u0627\u0646\u0647 \u0627\u0632 \u0645\u0627\u062a\u0631\u06cc\u0633 \u0647\u0645\u0647\u200c\u06cc \u062d\u0627\u0644\u062a\u200c\u0647\u0627\u06cc\u06cc \u06a9\u0647 \u0627\u0632 \u062d\u062f\u0627\u06a9\u062b\u0631&nbsp;<span class=\"katex-eq\" data-katex-display=\"false\">8<\/span>&nbsp;\u0647\u0645\u0633\u0627\u06cc\u0647\u060c&nbsp;<span class=\"katex-eq\" data-katex-display=\"false\">3<\/span>&nbsp;\u0647\u0645\u0633\u0627\u06cc\u0647 \u0631\u0627 \u0627\u0646\u062a\u062e\u0627\u0628 \u06a9\u0646\u06cc\u0645\u060c \u062f\u0631 \u0646\u0638\u0631 \u0628\u06af\u06cc\u0631\u06cc\u0645 \u0648 \u0633\u067e\u0633 \u0628\u0631\u0631\u0633\u06cc \u06a9\u0646\u06cc\u0645 \u0622\u06cc\u0627 \u062c\u0645\u0639 \u0622\u0646\u200c\u0647\u0627 \u062a\u0648\u0627\u0646\u06cc \u0627\u0632&nbsp;<span class=\"katex-eq\" data-katex-display=\"false\">2<\/span>&nbsp;\u0627\u0633\u062a \u06cc\u0627 \u062e\u06cc\u0631.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">\u067e\u06cc\u0686\u06cc\u062f\u06af\u06cc \u0632\u0645\u0627\u0646\u06cc: <span class=\"katex-eq\" data-katex-display=\"false\">O(MN) <\/span><\/p>\n\n\n\n<div style=\"height:10px\" aria-hidden=\"true\" class=\"wp-block-spacer\"><\/div>\n\n\n\n<pre class=\"wp-block-code\"><code lang=\"cpp\" class=\"language-cpp line-numbers\">#include &lt;bits\/stdc++.h&gt;\n\nusing namespace std;\n\nconst int maxn = 1000;\nint a[maxn][maxn];\n\nbool is_two_power(int n)\n{\n\tint m = n, k = 1;\n\twhile (m &gt; 1)\n\t{\n\t\tm \/= 2;\n\t\tk *= 2;\n\t}\n\n\treturn (k == n);\n}\n\nint main()\n{\n\tios_base::sync_with_stdio(false); cin.tie(0);\n\n\tint n, m;\n\tcin &gt;&gt; n &gt;&gt; m;\n\tfor (int i = 0; i &lt; n; i++)\n\t\tfor (int j = 0; j &lt; m; j++)\n\t\t\tcin &gt;&gt; a[i][j];\n\n\tint ans = 0;\n\tfor (int i = 0; i &lt; n; i++)\n\t\tfor (int j = 0; j &lt; m; j++)\n\t\t{\n\t\t\tvector &lt;int&gt; v;\n\t\t\tfor (int x = max(0, i - 1); x &lt;= min(i + 1, n - 1); x++)\n\t\t\t\tfor (int y = max(0, j - 1); y &lt;= min(j + 1, m - 1); y++)\n\t\t\t\t\tif (x != i || y != j)\n\t\t\t\t\t\tv.push_back(a[x][y]);\n\n\t\t\tbool okay = false;\n\t\t\tfor (int r = 0; r &lt; (int)v.size(); r++)\n\t\t\t\tfor (int s = r + 1; s &lt; (int)v.size(); s++)\n\t\t\t\t\tfor (int t = s + 1; t &lt; (int)v.size(); t++)\n\t\t\t\t\t\tif (is_two_power(v[r] + v[s] + v[t]))\n\t\t\t\t\t\t\tokay = true;\n\t\t\t\n\t\t\tif (okay)\n\t\t\t\tans++;\n\t\t}\n\n\tcout &lt;&lt; ans &lt;&lt; '\\n';\n\treturn 0;\n}<\/code><\/pre>\n\n\n\n<div style=\"height:35px\" aria-hidden=\"true\" class=\"wp-block-spacer\"><\/div>\n\n\n\n<h2 class=\"has-medium-font-size wp-block-heading\" id=\"h-d-champions-league\"><span class=\"ez-toc-section\" id=\"D_%E2%80%93_Champions_League\"><\/span><strong><a href=\"https:\/\/quera.org\/problemset\/168944\/\" target=\"_blank\" rel=\"noreferrer noopener\">D \u2013 Champions League<\/a><\/strong><span class=\"ez-toc-section-end\"><\/span><\/h2>\n\n\n\n<p class=\"wp-block-paragraph\">\u06a9\u0627\u0641\u06cc \u0627\u0633\u062a \u062c\u062f\u0648\u0644 \u0627\u0645\u062a\u06cc\u0627\u0632\u0627\u062a \u0631\u0627 \u0645\u062d\u0627\u0633\u0628\u0647 \u0648 \u062f\u0648 \u062a\u06cc\u0645 \u0628\u0631\u062a\u0631 \u0631\u0627 \u0637\u0628\u0642 \u062a\u0648\u0636\u06cc\u062d\u0627\u062a \u0633\u0648\u0627\u0644 \u067e\u06cc\u062f\u0627 \u0648 \u0646\u062a\u06cc\u062c\u0647 \u0631\u0627 \u0686\u0627\u067e \u06a9\u0646\u06cc\u062f.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">\u067e\u06cc\u0686\u06cc\u062f\u06af\u06cc \u0632\u0645\u0627\u0646\u06cc: <span class=\"katex-eq\" data-katex-display=\"false\">O(1) <\/span><\/p>\n\n\n\n<div style=\"height:10px\" aria-hidden=\"true\" class=\"wp-block-spacer\"><\/div>\n\n\n\n<pre class=\"wp-block-code\"><code lang=\"cpp\" class=\"language-cpp line-numbers\">#include &lt;algorithm&gt;\n#include &lt;iostream&gt;\n#include &lt;vector&gt;\n#include &lt;map&gt;\n\nusing namespace std;\n\nmap &lt;string, long long int&gt; score, goal_dif, goal_sco, goal_awa;\nvector &lt;string&gt; names;\n\nlong long int to_number(string s)\n{\n\tlong long int result = 0;\n\tfor (int i = 0; i &lt; (int)s.size(); i++)\n\t\tresult = result * 10 + s[i] - '0';\n\treturn result;\n}\n\nstring strip(string s)\n{\n\treverse(s.begin(), s.end());\n\twhile (s.back() == ' ')\n\t\ts.pop_back();\n\n\treverse(s.begin(), s.end());\n\twhile (s.back() == ' ')\n\t\ts.pop_back();\n\n\treturn s;\n}\n\nbool cmp(string teamA, string teamB)\n{\n\tif (score[teamA] != score[teamB])\n\t\treturn (score[teamA] &gt; score[teamB]);\n\n\tif (goal_dif[teamA] != goal_dif[teamB])\n\t\treturn (goal_dif[teamA] &gt; goal_dif[teamB]);\n\n\tif (goal_sco[teamA] != goal_sco[teamB])\n\t\treturn (goal_sco[teamA] &gt; goal_sco[teamB]);\n\n\treturn goal_awa[teamA] &gt; goal_awa[teamB];\n}\n\n\nvector &lt;string&gt; parse(string s)\n{\n\ts = strip(s);\n\tint mid = -1;\n\tfor (int i = 0; i &lt; (int)s.size(); i++)\n\t\tif (s[i] == '.')\n\t\t{\n\t\t\tmid = i;\n\t\t\tbreak;\n\t\t}\n\n\tstring fi = \"\";\n\tfor (int i = 0; i &lt; mid - 2; i++)\n\t\tfi += s[i];\n\tfi = strip(fi);\n\n\tstring se = \"\";\n\tfor (int i = mid + 1; i &lt; (int)s.size(); i++)\n\t\tse += s[i];\n\tse = strip(se);\n\n\tstring fi_number = \"\";\n\tfor (int i = (int)fi.size() - 1; i &gt;= 0; i--)\n\t\tif (fi[i] == ' ')\n\t\t\tbreak;\n\t\telse\n\t\t\tfi_number += fi[i];\n\treverse(fi_number.begin(), fi_number.end());\n\tfi_number = strip(fi_number);\n\n\tstring fi_name = \"\";\n\tfor (int i = 0; i &lt; (int)fi.size() - (int)fi_number.size(); i++)\n\t\tfi_name += fi[i];\n\tfi_name = strip(fi_name);\n\n\tstring se_number = \"\";\n\tfor (int i = 0; i &lt; (int)se.size(); i++)\n\t\tif (se[i] == ' ')\n\t\t\tbreak;\n\t\telse\n\t\t\tse_number += se[i];\n\tse_number = strip(se_number);\n\n\tstring se_name = \"\";\n\tfor (int i = (int)se_number.size() + 1; i &lt; (int)se.size(); i++)\n\t\tse_name += se[i];\n\tse_name = strip(se_name);\n\n\tvector &lt;string&gt; result;\n\tresult.push_back(fi_name);\n\tresult.push_back(fi_number);\n\tresult.push_back(se_name);\n\tresult.push_back(se_number);\n\treturn result;\n}\n\nint main()\n{\n\tfor (int i = 0; i &lt; 12; i++)\n\t{\n\t\tstring s;\n\t\tgetline(cin, s);\n\n\t\tvector &lt;string&gt; v = parse(s);\n\n\t\tstring HomeTeamName = v[0];\n\t\tlong long int HomeTeamGoals = to_number(v[1]);\n\n\t\tstring AwayTeamName = v[2];\n\t\tlong long int AwayTeamGoals = to_number(v[3]);\n\t\t\n\t\tnames.push_back(HomeTeamName);\n\t\tnames.push_back(AwayTeamName);\n\n\t\tgoal_dif[HomeTeamName] += HomeTeamGoals - AwayTeamGoals;\n\t\tgoal_dif[AwayTeamName] += AwayTeamGoals - HomeTeamGoals;\n\n\t\tgoal_sco[HomeTeamName] += HomeTeamGoals;\n\t\tgoal_sco[AwayTeamName] += AwayTeamGoals;\n\n\t\tgoal_awa[AwayTeamName] += AwayTeamGoals;\n\n\t\tif (HomeTeamGoals &gt; AwayTeamGoals)\n\t\t\tscore[HomeTeamName] += 3;\n\t\telse if (HomeTeamGoals &lt; AwayTeamGoals)\n\t\t\tscore[AwayTeamName] += 3;\n\t\telse\n\t\t\tscore[HomeTeamName] += 1, score[AwayTeamName] += 1;\n\t}\n\n\tsort(names.begin(), names.end());\n\tnames.resize(unique(names.begin(), names.end()) - names.begin());\n\n\tsort(names.begin(), names.end(), cmp);\n\n\tcout &lt;&lt; names[0] &lt;&lt; '\\n' &lt;&lt; names[1] &lt;&lt; '\\n';\n\n\treturn 0;\n}<\/code><\/pre>\n\n\n\n<div style=\"height:35px\" aria-hidden=\"true\" class=\"wp-block-spacer\"><\/div>\n\n\n\n<h2 class=\"has-medium-font-size wp-block-heading\" id=\"h-e-tic-tac-toe\"><span class=\"ez-toc-section\" id=\"E_%E2%80%93_Tic-Tac-Toe\"><\/span><strong><a href=\"https:\/\/quera.org\/problemset\/168945\/\" target=\"_blank\" rel=\"noreferrer noopener\">E \u2013 Tic-Tac-Toe<\/a><\/strong><span class=\"ez-toc-section-end\"><\/span><\/h2>\n\n\n\n<p class=\"wp-block-paragraph\">\u0635\u0641\u062d\u0647 \u062f\u0648\u0632&nbsp;<span class=\"katex-eq\" data-katex-display=\"false\">9<\/span>&nbsp;\u062e\u0627\u0646\u0647 \u062f\u0627\u0631\u062f \u0648 \u0647\u0631 \u062e\u0627\u0646\u0647&nbsp;<span class=\"katex-eq\" data-katex-display=\"false\">3<\/span>&nbsp;\u062d\u0627\u0644\u062a \u062f\u0627\u0631\u062f. \u06cc\u0639\u0646\u06cc \u062f\u0631 \u06a9\u0644&nbsp;<span class=\"katex-eq\" data-katex-display=\"false\">3^9<\/span>&nbsp;\u062d\u0627\u0644\u062a \u062f\u0627\u0631\u06cc\u0645. \u0645\u06cc\u200c\u062a\u0648\u0627\u0646\u06cc\u0645 \u0628\u0627 \u0627\u0633\u062a\u0641\u0627\u062f\u0647 \u0627\u0632 \u0631\u0648\u0634 \u00ab\u067e\u0633\u200c\u06af\u0631\u062f\u00bb \u0627\u0632 \u0635\u0641\u062d\u0647\u200c\u06cc \u062e\u0627\u0644\u06cc \u0634\u0631\u0648\u0639 \u06a9\u0646\u06cc\u0645 \u0648 \u0647\u0645\u0647\u200c\u06cc \u062d\u0627\u0644\u062a\u200c\u0647\u0627 \u0631\u0627 \u062a\u0648\u0644\u06cc\u062f \u06a9\u0646\u06cc\u0645. \u062f\u0631 \u0646\u0647\u0627\u06cc\u062a \u0628\u0647\u200c\u0627\u0632\u0627\u06cc \u0648\u0631\u0648\u062f\u06cc\u200c\u0647\u0627\u06cc \u0645\u062e\u062a\u0644\u0641\u060c \u0628\u0631\u0631\u0633\u06cc \u06a9\u0646\u06cc\u0645 \u0628\u0647 \u0627\u06cc\u0646 \u062a\u0631\u062a\u06cc\u0628 \u062d\u0627\u0644\u062a\u200c\u0647\u0627\u06cc \u063a\u06cc\u0631\u0645\u0645\u06a9\u0646 \u0628\u0647 \u0631\u0627\u062d\u062a\u06cc \u0628\u062f\u0633\u062a \u0645\u06cc\u200c\u0622\u06cc\u062f. (\u0628\u0631\u0631\u0633\u06cc \u0628\u0642\u06cc\u0647 \u062d\u0627\u0644\u062a\u200c\u0647\u0627 \u06a9\u0627\u0631 \u067e\u06cc\u0686\u06cc\u062f\u0647\u200c\u0627\u06cc \u0646\u06cc\u0633\u062a.)<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">\u067e\u06cc\u0686\u06cc\u062f\u06af\u06cc \u0632\u0645\u0627\u0646\u06cc: <span class=\"katex-eq\" data-katex-display=\"false\">O(1) <\/span><\/p>\n\n\n\n<div style=\"height:10px\" aria-hidden=\"true\" class=\"wp-block-spacer\"><\/div>\n\n\n\n<pre class=\"wp-block-code\"><code lang=\"cpp\" class=\"language-cpp line-numbers\">#include &lt;iostream&gt;\n#include &lt;map&gt;\n\nusing namespace std;\n\nmap &lt;string, string&gt; ans;\n\nstring finished(string state)\n{\n\tchar a[3][3];\n\tfor (int i = 0; i &lt; 3; i++)\n\t\tfor (int j = 0; j &lt; 3; j++)\n\t\t\ta[i][j] = state[i * 3 + j];\n\n\tint cnt_x = 0, cnt_o = 0;\n\tfor (int i = 0; i &lt; 3; i++)\n\t{\n\t\tcnt_x = 0, cnt_o = 0;\n\t\tfor (int j = 0; j &lt; 3; j++)\n\t\t{\n\t\t\tif (a[i][j] == 'X') cnt_x++;\n\t\t\tif (a[i][j] == 'O') cnt_o++;\n\t\t}\n\t\tif (cnt_x == 3) return \"X\";\n\t\tif (cnt_o == 3) return \"O\";\n\t}\n\n\tfor (int j = 0; j &lt; 3; j++)\n\t{\n\t\tcnt_x = 0, cnt_o = 0;\n\t\tfor (int i = 0; i &lt; 3; i++)\n\t\t{\n\t\t\tif (a[i][j] == 'X') cnt_x++;\n\t\t\tif (a[i][j] == 'O') cnt_o++;\n\t\t}\n\t\tif (cnt_x == 3) return \"X\";\n\t\tif (cnt_o == 3) return \"O\";\n\t}\n\n\tcnt_x = 0, cnt_o = 0;\n\tfor (int i = 0; i &lt; 3; i++)\n\t{\n\t\tif (a[i][i] == 'X') cnt_x++;\n\t\tif (a[i][i] == 'O') cnt_o++;\n\t}\n\tif (cnt_x == 3) return \"X\";\n\tif (cnt_o == 3) return \"O\";\n\n\tcnt_x = 0, cnt_o = 0;\n\tfor (int i = 0; i &lt; 3; i++)\n\t{\n\t\tif (a[2 - i][i] == 'X') cnt_x++;\n\t\tif (a[2 - i][i] == 'O') cnt_o++;\n\t}\n\tif (cnt_x == 3) return \"X\";\n\tif (cnt_o == 3) return \"O\";\n\n\tint cnt_q = 0;\n\tfor (int i = 0; i &lt; 3; i++)\n\t\tfor (int j = 0; j &lt; 3; j++)\n\t\t\tif (a[i][j] == '?')\n\t\t\t\tcnt_q++;\n\n\tif (cnt_q == 0)\n\t\treturn \"Draw\";\n\treturn \"Unfinished\";\n}\n\nvoid bt(string state, char turn)\n{\n\tans[state] = finished(state);\n\tif (ans[state] != \"Unfinished\")\n\t\treturn;\n\n\tfor (int i = 0; i &lt; 9; i++)\n\t\tif (state[i] == '?')\n\t\t{\n\t\t\tstate[i] = turn;\n\t\t\tbt(state, (turn == 'X' ? 'O' : 'X'));\n\t\t\tstate[i] = '?';\n\t\t}\n}\n\nint main()\n{\n\n\tbt(\"?????????\", 'X');\n\n\tstring state = \"\", s;\n\tcin &gt;&gt; s; state += s;\n\tcin &gt;&gt; s; state += s;\n\tcin &gt;&gt; s; state += s;\n\n\tif (ans.find(state) == ans.end())\n\t\tcout &lt;&lt; \"Invalid\\n\";\n\telse\n\t\tcout &lt;&lt; ans[state] &lt;&lt; '\\n';\n\n\treturn 0;\n}<\/code><\/pre>\n\n\n\n<div style=\"height:35px\" aria-hidden=\"true\" class=\"wp-block-spacer\"><\/div>\n\n\n\n<h2 class=\"has-medium-font-size wp-block-heading\" id=\"h-f-circles\"><span class=\"ez-toc-section\" id=\"F_%E2%80%93_Circles\"><\/span><strong><a href=\"https:\/\/quera.org\/problemset\/168946\/\" target=\"_blank\" rel=\"noreferrer noopener\">F \u2013 Circles<\/a><\/strong><span class=\"ez-toc-section-end\"><\/span><\/h2>\n\n\n\n<p class=\"wp-block-paragraph\">\u0635\u0641\u062d\u0647 \u0631\u0627 \u0628\u0647 \u0635\u0648\u0631\u062a \u06cc\u06a9 \u06af\u0631\u0627\u0641 \u062f\u0631 \u0646\u0638\u0631 \u0628\u06af\u06cc\u0631\u06cc\u062f. \u0631\u0627\u0633\u200c\u0647\u0627\u06cc \u06af\u0631\u0627\u0641 \u0631\u0627 \u062a\u0642\u0627\u0637\u0639\u200c\u0647\u0627 \u0648 \u06cc\u0627\u0644\u200c\u0647\u0627\u06cc \u06af\u0631\u0627\u0641 \u0631\u0627 \u06a9\u0645\u0627\u0646\u200c\u0647\u0627\u06cc \u0648\u0627\u0635\u0644 \u062f\u0648 \u062a\u0642\u0627\u0637\u0639 \u062f\u0631 \u0646\u0638\u0631 \u0628\u06af\u06cc\u0631\u06cc\u062f \u06a9\u0647 \u0647\u06cc\u0686 \u062a\u0642\u0627\u0637\u0639 \u0628\u06cc\u0646 \u0622\u0646\u200c\u0647\u0627 \u0646\u0628\u0627\u0634\u062f. \u0637\u0628\u0642 \u0642\u0636\u06cc\u0647 \u0627\u0648\u06cc\u0644\u0631 \u0628\u0631\u0627\u06cc \u06af\u0631\u0627\u0641\u200c\u0647\u0627\u06cc \u0645\u0633\u0637\u062d \u062f\u0627\u0631\u06cc\u0645:<\/p>\n\n\n\n<div class=\"wp-block-katex-display-block katex-eq\" data-katex-display=\"true\"><pre>V+F=E+2<\/pre><\/div>\n\n\n\n<p class=\"wp-block-paragraph\">\u06a9\u0647&nbsp;<span class=\"katex-eq\" data-katex-display=\"false\">F<\/span>&nbsp;\u062a\u0639\u062f\u0627\u062f \u0646\u0627\u062d\u06cc\u0647\u200c\u0647\u0627 \u0648&nbsp;<span class=\"katex-eq\" data-katex-display=\"false\">E<\/span>&nbsp;\u062a\u0639\u062f\u0627\u062f \u06cc\u0627\u0644\u200c\u0647\u0627 \u0648&nbsp;<span class=\"katex-eq\" data-katex-display=\"false\">V<\/span>&nbsp;\u062a\u0639\u062f\u0627\u062f \u0631\u0627\u0633\u200c\u0647\u0627\u06cc \u06af\u0631\u0627\u0641 \u0627\u0633\u062a. \u0645\u0633\u0626\u0644\u0647 \u067e\u06cc\u062f\u0627 \u06a9\u0631\u062f\u0646&nbsp;<span class=\"katex-eq\" data-katex-display=\"false\">F<\/span>&nbsp;\u062f\u0631 \u06af\u0631\u0627\u0641 \u0628\u0627\u0644\u0627 \u0627\u0633\u062a \u0648 \u0645\u06cc\u200c\u062a\u0648\u0627\u0646 \u0622\u0646 \u0631\u0627 \u0627\u0632 \u0631\u0648\u06cc \u062a\u0639\u062f\u0627\u062f \u0631\u0627\u0633\u200c\u0647\u0627 \u0648 \u06cc\u0627\u0644\u200c\u0647\u0627 \u0645\u0642\u0627\u06cc\u0633\u0647 \u06a9\u0631\u062f.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">\u0645\u062d\u0627\u0633\u0628\u0647\u200c\u06cc \u062a\u0639\u062f\u0627\u062f \u0631\u0627\u0633\u200c\u0647\u0627 \u0648 \u06cc\u0627\u0644\u200c\u0647\u0627\u06cc \u0627\u06cc\u0646 \u06af\u0631\u0627\u0641\u060c \u0628\u0627 \u067e\u06cc\u062f\u0627 \u06a9\u0631\u062f\u0646 \u0647\u0645\u0647\u200c\u06cc \u062a\u0642\u0627\u0637\u0639\u200c\u0647\u0627 \u0627\u0632&nbsp;<span class=\"katex-eq\" data-katex-display=\"false\">O(n^2)<\/span>&nbsp;\u0645\u0645\u06a9\u0646 \u062e\u0648\u0627\u0647\u062f \u0628\u0648\u062f.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">\u067e\u06cc\u0686\u06cc\u062f\u06af\u06cc \u0632\u0645\u0627\u0646\u06cc:&nbsp;<span class=\"katex-eq\" data-katex-display=\"false\">O(N^2)<\/span><\/p>\n\n\n\n<div style=\"height:10px\" aria-hidden=\"true\" class=\"wp-block-spacer\"><\/div>\n\n\n\n<pre class=\"wp-block-code\"><code lang=\"cpp\" class=\"language-cpp line-numbers\">#include &lt;bits\/stdc++.h&gt;\n\nusing namespace std;\n\nconst int MAXN = 1010;\nconst long double EPS = 1e-6;\n\n#define X first\n#define Y second\n#define R second\n\ntypedef pair&lt;long double, long double&gt; Point;\n\nint n, ans, e, v, sum, comps;\nlong double x[MAXN], r[MAXN];\nmap&lt;Point, int&gt; mp;\nset&lt;Point&gt; st, st2;\nvector&lt;Point&gt; circles;\nbool mark[MAXN];\nvector&lt;int&gt; adj[MAXN];\n\nbool equals(long double a, long double b) {\n\treturn fabs(a - b) &lt; EPS;\n}\n\nbool equals(const Point&amp; a, const Point&amp; b) {\n\treturn equals(a.first, b.first) &amp;&amp; equals(a.second, b.second);\n}\n\nvoid insertToSet(const Point&amp; p) {\n\tPoint p2 = Point(p.first - EPS, p.second - EPS);\n\tauto q = st.lower_bound(p2);\n\tif (q == st.end() || !equals(p, *q)) {\n\t\tst.insert(p);\n\t\tmp[p]++;\n\t} else if (q != st.end() &amp;&amp; equals(p, *q)) {\n\t\tmp[*q]++;\n\t}\n}\n\nvoid insertToSet2(const Point&amp; p) {\n\tPoint p2 = Point(p.first - EPS, p.second - EPS);\n\tauto q = st2.lower_bound(p2);\n\tif (q == st2.end() || !equals(p, *q)) {\n\t\tst2.insert(p);\n\t}\n}\n\nvoid dfs(int v) {\n\tmark[v] = true;\n\tfor (auto u: adj[v])\n\t\tif (!mark[u])\n\t\t\tdfs(u);\n}\n\nint main() {\n\tcin &gt;&gt; n;\n\tfor (int i = 0; i &lt; n; i++) {\n\t\tint x, r;\n\t\tcin &gt;&gt; x &gt;&gt; r;\n\t\tcircles.push_back(Point(x, r));\n\t}\n\tsort(circles.begin(), circles.end());\n\tcircles.erase(unique(circles.begin(), circles.end()), circles.end());\n\tn = circles.size();\n\tfor (int i = 0; i &lt; n; i++) {\n\t\tst2.clear();\n\t\tinsertToSet2(Point(circles[i].X - circles[i].R, 0));\n\t\tinsertToSet2(Point(circles[i].X + circles[i].R, 0));\n\t\tfor (int j = 0; j &lt; n; j++) {\n\t\t\tif (i == j)\n\t\t\t\tcontinue;\n\t\t\tlong double d = fabs(circles[i].X - circles[j].X);\n\t\t\tlong double rSum = circles[i].R + circles[j].R;\n\t\t\tlong double rDif = fabs(circles[i].R - circles[j].R);\n\t\t\tif (d + EPS &lt; rSum &amp;&amp; d - EPS &gt; rDif) {\n\t\t\t\tlong double r1 = circles[i].R;\n\t\t\t\tlong double r2 = circles[j].R;\n\t\t\t\tlong double x1 = circles[i].X;\n\t\t\t\tlong double x2 = circles[j].X;\n\t\t\t\tlong double pointX = (r1 * r1 - r2 * r2 - x1 * x1 + x2 * x2) \/ (2 * (x2 - x1));\n\t\t\t\tlong double tmp = r1 * r1 - (pointX - x1) * (pointX - x1);\n\t\t\t\tlong double pointY = sqrt(tmp);\n\t\t\t\tinsertToSet2(Point(pointX, -pointY));\n\t\t\t\tinsertToSet2(Point(pointX, +pointY));\n\t\t\t\tadj[i].push_back(j);\n\t\t\t}\n\t\t\telse if (equals(d, rSum) || equals(d, rDif)) {\n\t\t\t\tadj[i].push_back(j);\n\t\t\t}\n\t\t}\n\t\tPoint last = Point(-1e18, -1e18);\n\t\tfor (auto p: st2) {\n\t\t\tif (!equals(p, last))\n\t\t\t\tinsertToSet(p);\n\t\t\tlast = p;\n\t\t}\n\t}\n\tsum = 0;\n\tfor (auto p: st) {\n\t\tsum += 2 * mp[p];\n\t}\n\n\tv = 0;\n\tPoint last = Point(-1e18, -1e18);\n\n\tfor (auto p: st) {\n\t\tif (!equals(p, last)) {\n\t\t\t\/\/ cout &lt;&lt; p.X &lt;&lt; \" \" &lt;&lt; p.Y &lt;&lt; endl;\n\t\t\tv++;\n\t\t}\n\t\tlast = p;\n\t}\n\n\te = sum \/ 2;\n\tfor (int i = 0; i &lt; n; i++) {\n\t\tif (!mark[i]) {\n\t\t\tcomps++;\n\t\t\tdfs(i);\n\t\t}\n\t}\n\t\/\/ cout &lt;&lt; e &lt;&lt; \" \" &lt;&lt; v &lt;&lt; \" \" &lt;&lt; comps &lt;&lt; endl;\n\tans = e - v + 1 + comps;\n\tcout &lt;&lt; ans &lt;&lt; endl;\n\treturn 0;\n}<\/code><\/pre>\n\n\n\n<div style=\"height:35px\" aria-hidden=\"true\" class=\"wp-block-spacer\"><\/div>\n\n\n\n<h2 class=\"has-medium-font-size wp-block-heading\"><span class=\"ez-toc-section\" id=\"G_%E2%80%93_Network_Connections\"><\/span><strong><a href=\"https:\/\/quera.org\/problemset\/168947\/\" target=\"_blank\" rel=\"noreferrer noopener\">G \u2013 Network Connections<\/a><\/strong><span class=\"ez-toc-section-end\"><\/span><\/h2>\n\n\n\n<p class=\"wp-block-paragraph\">\u0645\u0633\u0626\u0644\u0647 \u0645\u0639\u0627\u062f\u0644 \u067e\u06cc\u062f\u0627 \u06a9\u0631\u062f\u0646 \u00ab\u062f\u0648\u0631\u062a\u0631\u06cc\u0646 \u062c\u062f \u0645\u0634\u062a\u0631\u06a9\u00bb (\u06cc\u0627 \u0647\u0645\u0627\u0646 LCA) \u0628\u0631\u0627\u06cc&nbsp;<span class=\"katex-eq\" data-katex-display=\"false\">k<\/span>&nbsp;\u0631\u0627\u0633\u060c \u062f\u0631 \u062f\u0631\u062e\u062a \u0627\u0633\u062a.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">\u0645\u0633\u0626\u0644\u0647 LCA \u0628\u0631\u0627\u06cc \u062f\u0648 \u0631\u0627\u0633 \u0642\u0627\u0628\u0644 \u062d\u0644 \u0627\u0633\u062a \u0648 \u0628\u0631\u0627\u06cc&nbsp;<span class=\"katex-eq\" data-katex-display=\"false\">k<\/span>&nbsp;\u0631\u0627\u0633 \u0645\u06cc\u200c\u062a\u0648\u0627\u0646\u06cc\u0645 \u0628\u0647 \u0635\u0648\u0631\u062a \u062f\u0648\u062a\u0627 \u062f\u0648\u062a\u0627 \u0627\u0646\u062c\u0627\u0645 \u062f\u0647\u06cc\u0645 \u062a\u0627 \u0628\u0647 \u0631\u0627\u0633 \u0645\u0648\u0631\u062f \u0646\u0638\u0631 \u0628\u0631\u0633\u06cc\u0645.<\/p>\n\n\n\n<div style=\"height:10px\" aria-hidden=\"true\" class=\"wp-block-spacer\"><\/div>\n\n\n\n<pre class=\"wp-block-code\"><code lang=\"cpp\" class=\"language-cpp line-numbers\">#include &lt;iostream&gt;\n#include &lt;cstring&gt;\n#include &lt;vector&gt;\n\nusing namespace std;\n\nconst int maxn = 1e5, maxl = 20;\nvector &lt;int&gt; adj[maxn];\nint h[maxn], par[maxn][maxl];\n\nvoid dfs(int v)\n{\n\tfor (int i = 1; par[v][i - 1] != -1; i++)\n\t\tpar[v][i] = par[par[v][i - 1]][i - 1];\n\n\tfor (int u : adj[v])\n\t\tif (u != par[v][0])\n\t\t{\n\t\t\tpar[u][0] = v;\n\t\t\th[u] = h[v] + 1;\n\t\t\tdfs(u);\n\t\t}\n}\n\nint lca(int v, int u)\n{\n\tif (h[v] &lt; h[u])\n\t\tswap(v, u);\n\n\tfor (int i = maxl - 1; i &gt;= 0; i--)\n\t\tif (par[v][i] != -1 &amp;&amp; h[par[v][i]] &gt;= h[u])\n\t\t\tv = par[v][i];\n\n\tif (v == u)\n\t\treturn v;\n\n\tfor (int i = maxl - 1; i &gt;= 0; i--)\n\t\tif (par[v][i] != par[u][i])\n\t\t\tv = par[v][i], u = par[u][i];\n\n\treturn par[v][0];\n}\n\nint main()\n{\n\tios_base::sync_with_stdio(false); cin.tie(0);\n\n\tint n, k;\n\tcin &gt;&gt; n &gt;&gt; k;\n\n\tfor (int i = 1; i &lt; n; i++)\n\t{\n\t\tint u, v;\n\t\tcin &gt;&gt; u &gt;&gt; v;\n\t\tu--, v--;\n\t\tadj[v].push_back(u);\n\t\tadj[u].push_back(v);\n\t}\n\n\tmemset(par, -1, sizeof par);\n\tdfs(0);\n\n\tint ans;\n\tcin &gt;&gt; ans;\n\tans--;\n\n\tfor (int i = 1; i &lt; k; i++)\n\t{\n\t\tint u;\n\t\tcin &gt;&gt; u;\n\t\tu--;\n\t\tans = lca(ans, u);\n\t}\n\n\tcout &lt;&lt; 1 + ans &lt;&lt; '\\n';\n\treturn 0;\n}<\/code><\/pre>\n\n\n\n<div style=\"height:35px\" aria-hidden=\"true\" class=\"wp-block-spacer\"><\/div>\n\n\n\n<h2 class=\"has-medium-font-size wp-block-heading\" id=\"h-h-music-shopping\"><span class=\"ez-toc-section\" id=\"H_%E2%80%93_Music_Shopping\"><\/span><strong><a href=\"https:\/\/quera.org\/problemset\/168948\/\" target=\"_blank\" rel=\"noreferrer noopener\">H \u2013 Music Shopping<\/a><\/strong><span class=\"ez-toc-section-end\"><\/span><\/h2>\n\n\n\n<p class=\"wp-block-paragraph\">\u0627\u0628\u062a\u062f\u0627 \u062a\u0631\u062a\u06cc\u0628 \u0622\u0647\u0646\u06af\u200c\u0647\u0627 \u0631\u0627 \u0637\u0648\u0631\u06cc \u062f\u0631 \u0646\u0638\u0631 \u0628\u06af\u06cc\u0631\u06cc\u062f \u06a9\u0647 \u0627\u0648\u0644 \u0647\u0645\u0647\u200c\u06cc \u0622\u0647\u0646\u06af\u200c\u0647\u0627\u06cc \u0622\u0644\u0628\u0648\u0645&nbsp;<span class=\"katex-eq\" data-katex-display=\"false\">1<\/span>\u060c \u0633\u067e\u0633 \u0647\u0645\u0647\u200c\u06cc \u0622\u0647\u0646\u06af\u200c\u0647\u0627\u06cc \u0622\u0644\u0628\u0648\u0645&nbsp;<span class=\"katex-eq\" data-katex-display=\"false\">2<\/span>&nbsp;\u0648&#8230; \u0622\u0645\u062f\u0647 \u0627\u0633\u062a.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">\u0641\u0631\u0636 \u06a9\u0646\u06cc\u062f&nbsp;<span class=\"katex-eq\" data-katex-display=\"false\">dp[i][j]<\/span>&nbsp;\u06cc\u0639\u0646\u06cc \u0627\u06af\u0631 \u0628\u062e\u0648\u0627\u0647\u06cc\u0645 \u0627\u0632 \u0622\u0647\u0646\u06af\u200c\u0647\u0627\u06cc&nbsp;<span class=\"katex-eq\" data-katex-display=\"false\">1<\/span>&nbsp;\u062a\u0627&nbsp;<span class=\"katex-eq\" data-katex-display=\"false\">i<\/span>&nbsp;\u062e\u0631\u06cc\u062f \u06a9\u0646\u06cc\u0645 \u0648&nbsp;<span class=\"katex-eq\" data-katex-display=\"false\">j<\/span>&nbsp;\u0648\u0627\u062d\u062f \u067e\u0648\u0644 \u062f\u0627\u0634\u062a\u0647 \u0628\u0627\u0634\u06cc\u0645\u060c \u062d\u062f\u0627\u06a9\u062b\u0631 \u0686\u0646\u062f \u0645\u0648\u0632\u06cc\u06a9 \u0645\u06cc\u200c\u062a\u0648\u0627\u0646 \u062e\u0631\u06cc\u062f.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">\u0628\u0631\u0627\u06cc \u0645\u062d\u0627\u0633\u0628\u0647 \u0645\u0642\u062f\u0627\u0631 \u0627\u06cc\u0646&nbsp;<span class=\"katex-eq\" data-katex-display=\"false\">dp[i][j]<\/span>&nbsp;\u062d\u0627\u0644\u062a\u200c\u0628\u0646\u062f\u06cc \u0632\u06cc\u0631 \u0631\u0627 \u0627\u0646\u062c\u0627\u0645 \u0645\u06cc\u200c\u062f\u0647\u06cc\u0645:<\/p>\n\n\n\n<p class=\"wp-block-paragraph\"><strong>\u062d\u0627\u0644\u062a \u06f1.<\/strong> \u0645\u0648\u0632\u06cc\u06a9\u200c\u0647\u0627\u06cc \u0622\u0644\u0628\u0648\u0645&nbsp;<span class=\"katex-eq\" data-katex-display=\"false\">i<\/span>&nbsp;\u0631\u0627 \u06cc\u06a9\u06cc \u06cc\u06a9\u06cc \u0645\u06cc\u200c\u062e\u0631\u06cc\u0645. \u0627\u06af\u0631 \u0645\u0642\u062f\u0627\u0631&nbsp;<span class=\"katex-eq\" data-katex-display=\"false\">j<\/span>&nbsp;\u06a9\u0645\u062a\u0631 \u0627\u0632 \u0647\u0632\u06cc\u0646\u0647 \u062e\u0631\u06cc\u062f \u0622\u0647\u0646\u06af \u0628\u0627\u0634\u062f:<\/p>\n\n\n\n<div class=\"wp-block-katex-display-block katex-eq\" data-katex-display=\"true\"><pre>dp[i][j]=dp[i\u22121][j]<\/pre><\/div>\n\n\n\n<p class=\"wp-block-paragraph\">\u062f\u0631 \u063a\u06cc\u0631 \u0627\u06cc\u0646\u200c\u0635\u0648\u0631\u062a \u0627\u06af\u0631 \u0647\u0632\u06cc\u0646\u0647\u200c\u06cc \u062e\u0631\u06cc\u062f \u062a\u0631\u06a9&nbsp;<span class=\"katex-eq\" data-katex-display=\"false\">i<\/span>\u0627\u0645 \u0628\u0631\u0627\u0628\u0631&nbsp;<span class=\"katex-eq\" data-katex-display=\"false\">s<\/span>&nbsp;\u0628\u0627\u0634\u062f \u0648&nbsp;<span class=\"katex-eq\" data-katex-display=\"false\">j\u2265s<\/span>&nbsp;\u0645\u06cc\u200c\u062a\u0648\u0627\u0646\u06cc\u0645 \u0622\u0646 \u0631\u0627 \u0628\u062e\u0631\u06cc\u0645 \u06cc\u0639\u0646\u06cc \u062f\u0627\u0631\u06cc\u0645: <\/p>\n\n\n\n<div class=\"wp-block-katex-display-block katex-eq\" data-katex-display=\"true\"><pre>dp[i][j]=dp[i\u22121][j\u2212s]+1<\/pre><\/div>\n\n\n\n<p class=\"wp-block-paragraph\"><strong>\u062d\u0627\u0644\u062a \u06f2.<\/strong> \u062a\u0645\u0627\u0645 \u0645\u0648\u0632\u06cc\u06a9\u200c\u0647\u0627\u06cc \u0622\u0644\u0628\u0648\u0645 \u0645\u0631\u0628\u0648\u0637 \u0628\u0647 \u0645\u0648\u0632\u06cc\u06a9&nbsp;<span class=\"katex-eq\" data-katex-display=\"false\">idx<\/span>&nbsp;\u0631\u0627 \u0628\u0647\u200c\u0635\u0648\u0631\u062a \u06cc\u06a9\u062c\u0627 \u0645\u06cc\u200c\u062e\u0631\u06cc\u0645. (\u0627\u06cc\u0646 \u062d\u0627\u0644\u062a \u0631\u0627 \u0641\u0642\u0637 \u0628\u0631\u0627\u06cc \u0645\u0648\u0632\u06cc\u06a9 \u0622\u062e\u0631 \u0622\u0644\u0628\u0648\u0645 \u0628\u0631\u0631\u0633\u06cc \u0645\u06cc\u200c\u06a9\u0646\u06cc\u0645.)<\/p>\n\n\n\n<div class=\"wp-block-katex-display-block katex-eq\" data-katex-display=\"true\"><pre>dp[i][j]=dp[i\u2212size(albums[i])][j\u2212albumPrice[i]]+size(albums[i])<\/pre><\/div>\n\n\n\n<p class=\"wp-block-paragraph\">\u0648 \u0628\u0647 \u0627\u06cc\u0646 \u062a\u0631\u062a\u06cc\u0628 \u067e\u0627\u0633\u062e \u0645\u0633\u0626\u0644\u0647 \u062f\u0631&nbsp;<span class=\"katex-eq\" data-katex-display=\"false\">dp[N][P]<\/span>&nbsp;\u062e\u0648\u0627\u0647\u062f \u0628\u0648\u062f. <\/p>\n\n\n\n<p class=\"wp-block-paragraph\">\u067e\u06cc\u0686\u06cc\u062f\u06af\u06cc \u0632\u0645\u0627\u0646\u06cc:&nbsp;<span class=\"katex-eq\" data-katex-display=\"false\">O(NP)<\/span><\/p>\n\n\n\n<div style=\"height:10px\" aria-hidden=\"true\" class=\"wp-block-spacer\"><\/div>\n\n\n\n<pre class=\"wp-block-code\"><code lang=\"cpp\" class=\"language-cpp line-numbers\">#include &lt;bits\/stdc++.h&gt;\n\nusing namespace std;\n\nconst int MAXN = 5010;\nconst int MAXPRICE = 5010;\n\nint n, m, totalPrice;\nvector&lt;long long&gt; albums[MAXN];\n\nlong long dp[MAXN][MAXPRICE], albumPrice[MAXN];\n\nint main() {\n\tcin &gt;&gt; n &gt;&gt; m &gt;&gt; totalPrice;\n\tfor (int i = 0; i &lt; n; i++) {\n\t\tint x, y;\n\t\tcin &gt;&gt; x &gt;&gt; y;\n\t\talbums[x].push_back(y);\n\t}\n\tfor (int i = 1; i &lt;= m; i++)\n\t\tcin &gt;&gt; albumPrice[i];\n\tint idx = 0;\n\tfor (int i = 1; i &lt;= m; i++) {\n\t\tfor (auto song: albums[i]) {\n\t\t\tidx++;\n\t\t\tfor (int price = 0; price &lt;= totalPrice; price++) {\n\t\t\t\tdp[idx][price] = max(dp[idx - 1][price], (price &gt;= song) ? dp[idx - 1][price - song] + 1 : 0);\n\t\t\t}\n\t\t}\n\t\tidx++;\n\t\tfor (int price = 0; price &lt;= totalPrice; price++) {\n\t\t\tdp[idx][price] = max(dp[idx - 1][price], (price &gt;= albumPrice[i]) ? dp[idx - (int)albums[i].size() - 1][price - albumPrice[i]] + (int)albums[i].size() : 0);\n\t\t}\n\t}\n\tcout &lt;&lt; dp[idx][totalPrice] &lt;&lt; endl;\n\treturn 0;\n}<\/code><\/pre>\n\n\n\n<div style=\"height:35px\" aria-hidden=\"true\" class=\"wp-block-spacer\"><\/div>\n\n\n\n<h2 class=\"has-medium-font-size wp-block-heading\" id=\"h-i-morning-run\"><span class=\"ez-toc-section\" id=\"I_%E2%80%93_Morning_Run\"><\/span><strong><a href=\"https:\/\/quera.org\/problemset\/168949\/\" target=\"_blank\" rel=\"noreferrer noopener\">I \u2013 Morning Run<\/a><\/strong><span class=\"ez-toc-section-end\"><\/span><\/h2>\n\n\n\n<p class=\"wp-block-paragraph\">\u0627\u06af\u0631 \u0628\u0631\u0627\u06cc \u0647\u0631 \u062f\u0648\u0646\u062f\u0647\u060c \u0646\u0645\u0648\u062f\u0627\u0631 \u0645\u06a9\u0627\u0646 \u0632\u0645\u0627\u0646 \u0622\u0646 \u0631\u0627 \u0631\u0633\u0645 \u06a9\u0646\u06cc\u0645\u061b \u06cc\u06a9 \u067e\u0627\u0631\u0647 \u062e\u0637 \u06a9\u0634\u06cc\u062f\u0647 \u0645\u06cc\u200c\u0634\u0648\u062f. \u0648 \u0632\u0645\u0627\u0646\u06cc \u062f\u0648 \u062f\u0648\u0646\u062f\u0647 \u0647\u0645\u062f\u06cc\u06af\u0631 \u0631\u0627 \u0645\u0644\u0627\u0642\u0627\u062a \u0645\u06cc\u200c\u06a9\u0646\u0646\u062f \u06a9\u0647 \u0627\u06cc\u0646 \u062f\u0648 \u067e\u0627\u0631\u0647\u200c\u062e\u0637 \u0628\u0627 \u0647\u0645 \u062a\u0642\u0627\u0637\u0639 \u06a9\u0631\u062f\u0647 \u0628\u0627\u0634\u0646\u062f.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">\u067e\u06cc\u0686\u06cc\u062f\u06af\u06cc \u0632\u0645\u0627\u0646\u06cc:&nbsp;<span class=\"katex-eq\" data-katex-display=\"false\">O(N^2)<\/span><\/p>\n\n\n\n<div style=\"height:10px\" aria-hidden=\"true\" class=\"wp-block-spacer\"><\/div>\n\n\n\n<pre class=\"wp-block-code\"><code lang=\"cpp\" class=\"language-cpp line-numbers\">#include &lt;bits\/stdc++.h&gt;\n\nusing namespace std;\n\ntypedef long long int LL;\ntypedef pair &lt;LL, LL&gt; point;\n\n#define X first\n#define Y second\n\nconst int maxn = 100;\nLL t[maxn], s[maxn], f[maxn];\n\nLL cross(point A, point B)\n{\n\treturn A.X * B.Y - A.Y * B.X;\n}\n\npoint mnus(point A, point B)\n{\n\treturn make_pair(A.X - B.X, A.Y - B.Y);\n}\n\nbool intersect(point A_1, point B_1, point A_2, point B_2)\n{\n\tLL c_1 = cross(mnus(B_1, A_1), mnus(B_2, A_1));\n\tLL c_2 = cross(mnus(B_1, A_1), mnus(A_2, A_1));\n\n\tif ((c_1 &gt; 0 &amp;&amp; c_2 &gt; 0) || (c_1 &lt; 0 &amp;&amp; c_2 &lt; 0))\n\t\treturn false;\n\n\tLL c_3 = cross(mnus(B_2, A_2), mnus(B_1, A_2));\n\tLL c_4 = cross(mnus(B_2, A_2), mnus(A_1, A_2));\n\n\tif ((c_3 &gt; 0 &amp;&amp; c_4 &gt; 0) || (c_3 &lt; 0 &amp;&amp; c_4 &lt; 0))\n\t\treturn false;\n\n\treturn true;\n}\n\nint main()\n{\n\tios_base::sync_with_stdio(false); cin.tie(0);\n\n\tint n;\n\tcin &gt;&gt; n;\n\tfor (int i = 0; i &lt; n; i++)\n\t\tcin &gt;&gt; t[i] &gt;&gt; s[i] &gt;&gt; f[i];\n\n\tfor (int i = 0; i &lt; n; i++)\n\t{\n\n\t\tpoint A_1 = make_pair(t[i], s[i]);\n\t\tpoint B_1 = make_pair(t[i] + abs(f[i] - s[i]), f[i]);\n\n\n\t\tint r = 0;\n\t\tfor (int j = 0; j &lt; n; j++)\n\t\t\tif (j != i)\n\t\t\t{\n\t\t\t\tpoint A_2 = make_pair(t[j], s[j]);\n\t\t\t\tpoint B_2 = make_pair(t[j] + abs(f[j] - s[j]), f[j]);\n\n\t\t\t\tif (intersect(A_1, B_1, A_2, B_2))\n\t\t\t\t\tr++;\n\t\t\t}\n\n\t\tcout &lt;&lt; r &lt;&lt; \" \\n\"[i == n - 1];\n\t}\n\n\treturn 0;\n}<\/code><\/pre>\n\n\n\n<div style=\"height:35px\" aria-hidden=\"true\" class=\"wp-block-spacer\"><\/div>\n\n\n\n<h2 class=\"has-medium-font-size wp-block-heading\" id=\"h-j-seasons\"><span class=\"ez-toc-section\" id=\"J_%E2%80%93_Seasons\"><\/span><strong><a href=\"https:\/\/quera.org\/problemset\/168950\/\" target=\"_blank\" rel=\"noreferrer noopener\">J \u2013 Seasons<\/a><\/strong><span class=\"ez-toc-section-end\"><\/span><\/h2>\n\n\n\n<p class=\"wp-block-paragraph\">\u062f\u0631 \u0627\u06cc\u0646 \u0633\u0648\u0627\u0644 \u06a9\u0627\u0641\u06cc \u0627\u0633\u062a \u0641\u0635\u0644 \u0645\u0631\u0628\u0648\u0637 \u0628\u0647 \u0647\u0631 \u0645\u0627\u0647 \u0631\u0627 \u0686\u0627\u067e \u06a9\u0646\u06cc\u062f.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">\u067e\u06cc\u0686\u06cc\u062f\u06af\u06cc \u0632\u0645\u0627\u0646\u06cc:&nbsp;<span class=\"katex-eq\" data-katex-display=\"false\">O(1)<\/span><\/p>\n\n\n\n<div style=\"height:10px\" aria-hidden=\"true\" class=\"wp-block-spacer\"><\/div>\n\n\n\n<pre class=\"wp-block-code\"><code lang=\"cpp\" class=\"language-cpp line-numbers\">#include&lt;bits\/stdc++.h&gt;\nusing namespace std;\n\nint main() {\n    string month;\n    cin &gt;&gt; month;\n    if (month == \"september\" || month == \"october\" || month == \"november\") {\n        cout &lt;&lt; \"spring\";\n    } else if (month == \"december\" || month == \"january\" || month == \"february\") {\n        cout &lt;&lt; \"summer\";\n    } else if (month == \"march\" || month == \"april\" || month == \"may\") {\n        cout &lt;&lt; \"autumn\";\n    } else if (month == \"june\" || month == \"july\" || month == \"august\") {\n        cout &lt;&lt; \"winter\";\n    }\n\n\n}<\/code><\/pre>\n\n\n\n<div style=\"height:35px\" aria-hidden=\"true\" class=\"wp-block-spacer\"><\/div>\n\n\n\n<h2 class=\"has-medium-font-size wp-block-heading\" id=\"h-k-the-sacred-number\"><span class=\"ez-toc-section\" id=\"K_%E2%80%93_The_Sacred_Number\"><\/span><strong><a href=\"https:\/\/quera.org\/problemset\/168951\/\" target=\"_blank\" rel=\"noreferrer noopener\">K \u2013 The Sacred Number<\/a><\/strong><span class=\"ez-toc-section-end\"><\/span><\/h2>\n\n\n\n<p class=\"wp-block-paragraph\">\u0645\u06cc\u200c\u062a\u0648\u0627\u0646 \u062b\u0627\u0628\u062a \u06a9\u0631\u062f \u06a9\u0647 \u062a\u0646\u0647\u0627 \u0628\u0647 \u0627\u0632\u0627\u06cc \u062d\u0627\u0644\u062a\u200c\u0647\u0627\u06cc\u06cc \u06a9\u0647&nbsp;<span class=\"katex-eq\" data-katex-display=\"false\">n<\/span>&nbsp;\u0645\u0636\u0631\u0628&nbsp;<span class=\"katex-eq\" data-katex-display=\"false\">7<\/span>&nbsp;\u0628\u0627\u0634\u062f \u0646\u0641\u0631 \u062f\u0648\u0645 \u0627\u0633\u062a\u0631\u0627\u062a\u0698\u06cc \u0628\u0631\u062f \u062f\u0627\u0631\u062f \u0648 \u062f\u0631 \u063a\u06cc\u0631\u0627\u06cc\u0646\u200c\u0635\u0648\u0631\u062a \u0646\u0641\u0631 \u0627\u0648\u0644 \u0628\u0631\u0646\u062f\u0647 \u0627\u0633\u062a\u0631\u0627\u062a\u0698\u06cc \u0628\u0631\u062f \u062e\u0648\u0627\u0647\u062f \u062f\u0627\u0634\u062a.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">\u0641\u0631\u0636 \u06a9\u0646\u06cc\u062f \u06a9\u0647&nbsp;<span class=\"katex-eq\" data-katex-display=\"false\">n<\/span>&nbsp;\u0645\u0636\u0631\u0628&nbsp;<span class=\"katex-eq\" data-katex-display=\"false\">7<\/span>&nbsp;\u0628\u0627\u0634\u062f. \u062f\u0631 \u0627\u06cc\u0646 \u0635\u0648\u0631\u062a \u0646\u0641\u0631 \u062f\u0648\u0645 \u0645\u06cc\u200c\u062a\u0648\u0627\u0646\u062f \u0628\u0639\u062f \u0627\u0632 \u0647\u0631 \u062d\u0631\u06a9\u062a \u0646\u0641\u0631 \u0627\u0648\u0644\u060c \u062d\u0631\u06a9\u062a \u062e\u0648\u062f \u0631\u0627 \u0645\u0634\u062e\u0635 \u06a9\u0646\u062f. \u0627\u06af\u0631 \u0646\u0641\u0631 \u0627\u0648\u0644 \u0639\u062f\u062f&nbsp;<span class=\"katex-eq\" data-katex-display=\"false\">k<\/span>&nbsp;\u0631\u0627 \u0628\u0631\u062f\u0627\u0634\u062a \u0646\u0641\u0631 \u062f\u0648\u0645 \u0639\u062f\u062f&nbsp;<span class=\"katex-eq\" data-katex-display=\"false\">7-k<\/span>&nbsp;\u0631\u0627 \u0628\u0631\u062f\u0627\u0631\u062f. \u062f\u0631 \u0627\u06cc\u0646 \u0635\u0648\u0631\u062a \u0647\u0645\u06cc\u0634\u0647 \u0646\u0641\u0631 \u062f\u0648\u0645 \u062d\u0631\u06a9\u062a\u06cc \u0628\u0631\u0627\u06cc \u0627\u0646\u062c\u0627\u0645 \u062f\u0627\u062f\u0646 \u062f\u0627\u0631\u062f. \u0628\u0627 \u062a\u0648\u062c\u0647 \u0628\u0647 \u0627\u06cc\u0646\u06a9\u0647 \u0628\u0627\u0632\u06cc \u067e\u0627\u06cc\u0627\u0646 \u067e\u0630\u06cc\u0631 \u0627\u0633\u062a\u060c \u0646\u0641\u0631 \u062f\u0648\u0645 \u0627\u0633\u062a\u0631\u0627\u062a\u0698\u06cc \u0628\u0631\u062f \u062f\u0627\u0631\u062f.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">\u0627\u06af\u0631&nbsp;<span class=\"katex-eq\" data-katex-display=\"false\">n<\/span>&nbsp;\u0645\u0636\u0631\u0628&nbsp;<span class=\"katex-eq\" data-katex-display=\"false\">7<\/span>&nbsp;\u0646\u0628\u0648\u062f\u060c \u06cc\u0639\u0646\u06cc \u0628\u0627\u0642\u06cc\u200c\u0645\u0627\u0646\u062f\u0647\u200c\u06cc \u0646\u0627\u0635\u0641\u0631&nbsp;<span class=\"katex-eq\" data-katex-display=\"false\">r<\/span>&nbsp;\u0628\u0631&nbsp;<span class=\"katex-eq\" data-katex-display=\"false\">7<\/span>&nbsp;\u062f\u0627\u0634\u062a\u060c \u0646\u0641\u0631 \u0627\u0648\u0644 \u0645\u06cc\u200c\u062a\u0648\u0627\u0646\u062f \u062f\u0631 \u0646\u0648\u0628\u062a \u0627\u0648\u0644 \u0645\u0642\u062f\u0627\u0631&nbsp;<span class=\"katex-eq\" data-katex-display=\"false\">r<\/span>&nbsp;\u0631\u0627 \u0628\u0631\u062f\u0627\u0631\u062f \u0648 \u0628\u0639\u062f \u0627\u0632 \u0622\u0646 \u0627\u0633\u062a\u0631\u0627\u062a\u0698\u06cc \u0645\u0634\u0627\u0628\u0647 \u0646\u0641\u0631 \u062f\u0648\u0645 \u062f\u0631 \u062d\u0627\u0644\u062a \u0645\u0636\u0631\u0628&nbsp;<span class=\"katex-eq\" data-katex-display=\"false\">7<\/span>&nbsp;\u0631\u0627 \u062f\u0631 \u067e\u06cc \u0628\u06af\u06cc\u0631\u062f. \u0628\u0647 \u0627\u06cc\u0646 \u062a\u0631\u062a\u06cc\u0628 \u0646\u0641\u0631 \u0627\u0648\u0644 \u062f\u0631 \u0627\u06cc\u0646 \u062d\u0627\u0644\u062a \u0627\u0633\u062a\u0631\u0627\u062a\u0698\u06cc \u0628\u0631\u062f \u062f\u0627\u0631\u062f.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">\u067e\u06cc\u0686\u06cc\u062f\u06af\u06cc \u0632\u0645\u0627\u0646\u06cc:&nbsp;<span class=\"katex-eq\" data-katex-display=\"false\">O(1)<\/span><\/p>\n\n\n\n<div style=\"height:10px\" aria-hidden=\"true\" class=\"wp-block-spacer\"><\/div>\n\n\n\n<pre class=\"wp-block-code\"><code lang=\"cpp\" class=\"language-cpp line-numbers\">#include &lt;bits\/stdc++.h&gt;\n\nusing namespace std;\n\nint main()\n{\n\tint n;\n\tcin &gt;&gt; n;\n\tcout &lt;&lt; ((n % 7 == 0) ? \"Mat\" : \"Pat\") &lt;&lt; endl;\n\treturn 0;\n}<\/code><\/pre>\n\n\n\n<div style=\"height:35px\" aria-hidden=\"true\" class=\"wp-block-spacer\"><\/div>\n\n\n\n<h2 class=\"has-medium-font-size wp-block-heading\" id=\"h-l-n-bonacci-numbers\"><span class=\"ez-toc-section\" id=\"L_%E2%80%93_N-Bonacci_Numbers\"><\/span><strong><a href=\"https:\/\/quera.org\/problemset\/168952\/\" target=\"_blank\" rel=\"noreferrer noopener\">L \u2013 N-Bonacci Numbers<\/a><\/strong><span class=\"ez-toc-section-end\"><\/span><\/h2>\n\n\n\n<p class=\"wp-block-paragraph\">\u0628\u0627 \u0628\u0631\u0631\u0633\u06cc \u062f\u0646\u0628\u0627\u0644\u0647\u200c\u06cc&nbsp;<span class=\"katex-eq\" data-katex-display=\"false\">F<\/span>&nbsp;\u0648 \u0646\u062d\u0648\u0647\u200c\u06cc \u062a\u0639\u0631\u06cc\u0641 \u0622\u0646\u060c \u0645\u06cc\u200c\u062a\u0648\u0627\u0646 \u0646\u0634\u0627\u0646 \u062f\u0627\u062f \u06a9\u0647 \u0627\u06cc\u0646 \u062f\u0646\u0628\u0627\u0644\u0647&nbsp;<span class=\"katex-eq\" data-katex-display=\"false\">N+1<\/span> \u0645\u062a\u0646\u0627\u0648\u0628 \u0627\u0633\u062a \u0648 \u0627\u0632 \u0627\u06cc\u0646 \u062e\u0627\u0635\u06cc\u062a&nbsp;<span class=\"katex-eq\" data-katex-display=\"false\">F<\/span>&nbsp;\u0648 \u0646\u062d\u0648\u0647\u200c\u06cc \u062a\u0639\u0631\u06cc\u0641&nbsp;<span class=\"katex-eq\" data-katex-display=\"false\">S<\/span>&nbsp;\u0645\u06cc\u200c\u062a\u0648\u0627\u0646 \u0646\u062a\u06cc\u062c\u0647 \u06af\u0631\u0641\u062a \u06a9\u0647&nbsp;<span class=\"katex-eq\" data-katex-display=\"false\">S<\/span>&nbsp;\u0647\u0645&nbsp;<span class=\"katex-eq\" data-katex-display=\"false\">N+1<\/span> \u0645\u062a\u0646\u0627\u0648\u0628 \u0627\u0633\u062a.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">\u067e\u0633 \u06a9\u0627\u0641\u06cc \u0627\u0633\u062a \u0645\u0642\u062f\u0627\u0631&nbsp;<span class=\"katex-eq\" data-katex-display=\"false\">F<\/span>&nbsp;\u0648&nbsp;<span class=\"katex-eq\" data-katex-display=\"false\">S<\/span>&nbsp;\u0631\u0627 \u0641\u0642\u0637 \u0628\u0631\u0627\u06cc&nbsp;<span class=\"katex-eq\" data-katex-display=\"false\">N+1<\/span>&nbsp;\u062c\u0645\u0644\u0647\u200c\u06cc \u0627\u0648\u0644 \u0645\u062d\u0627\u0633\u0628\u0647 \u06a9\u0646\u06cc\u0645 \u062a\u0627 \u0628\u062a\u0648\u0627\u0646\u06cc\u0645 \u062c\u0648\u0627\u0628 \u0647\u0645\u0647\u200c\u06cc \u0633\u0648\u0627\u0644\u0627\u062a \u0631\u0627 \u0627\u0632&nbsp;<span class=\"katex-eq\" data-katex-display=\"false\">O(1)<\/span>&nbsp;\u0628\u062f\u0647\u06cc\u0645.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">\u067e\u06cc\u0686\u06cc\u062f\u06af\u06cc \u0632\u0645\u0627\u0646\u06cc:&nbsp;<span class=\"katex-eq\" data-katex-display=\"false\">O(N+Q)<\/span><\/p>\n\n\n\n<div style=\"height:10px\" aria-hidden=\"true\" class=\"wp-block-spacer\"><\/div>\n\n\n\n<pre class=\"wp-block-code\"><code lang=\"cpp\" class=\"language-cpp line-numbers\">\/\/ In the Name of Allah\n#include &lt;bits\/stdc++.h&gt;\n\nusing namespace std;\n\ntypedef long double LD;\ntypedef long long int LL;\ntypedef pair &lt;int,int&gt; pii;\n\n#define L first\n#define R second\n\nconst int maxn = 1e5 + 100;\nint f[maxn], s[maxn];\n\nint main() {\n\tios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);\n\tint n, q;\n\tcin &gt;&gt; n &gt;&gt; q;\n\tfor (int i = 1; i &lt;= n; i++)\n\t\tcin &gt;&gt; f[i], f[n + 1] ^= f[i];\n\n\tfor (int i = 1; i &lt;= n + 1; i++)\n\t\ts[i] = s[i - 1] ^ f[i];\n\n\twhile (q--) {\n\t\tint idx;\n\t\tcin &gt;&gt; idx;\n\t\tidx = ((idx - 1) % (n + 1)) + 1;\n\t\tcout &lt;&lt; s[idx] &lt;&lt; '\\n';\n\t}\n\n\treturn 0;\n}<\/code><\/pre>\n\n\n\n<div style=\"height:35px\" aria-hidden=\"true\" class=\"wp-block-spacer\"><\/div>\n","protected":false},"excerpt":{"rendered":"<p>\u0633\u0644\u0627\u0645! \u0645\u0633\u0627\u0628\u0642\u0627\u062a \u0627\u0644\u06af\u0648\u0631\u06cc\u062a\u0645\u06cc Newbies \u0632\u0645\u0633\u062a\u0648\u0646 \u0647\u0631 \u0633\u0627\u0644 \u062f\u0631 \u062f\u0627\u0646\u0634\u06af\u0627\u0647 \u0634\u0647\u06cc\u062f \u0628\u0647\u0634\u062a\u06cc \u0628\u0631\u06af\u0632\u0627\u0631 \u0645\u06cc\u0634\u0647. \u0633\u0637\u062d \u0633\u0624\u0627\u0644\u0627\u062a \u0627\u06cc\u0646 \u0645\u0633\u0627\u0628\u0642\u0647 \u0628\u0647 \u0646\u0633\u0628\u062a \u0645\u0633\u0627\u0628\u0642\u0627\u062a&#8230;<\/p>\n","protected":false},"author":22,"featured_media":42116,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[141,46,50],"tags":[],"class_list":["post-42076","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-contests-and-events","category-developer","category-quera-developer"],"_links":{"self":[{"href":"https:\/\/quera.org\/blog\/wp-json\/wp\/v2\/posts\/42076","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/quera.org\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/quera.org\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/quera.org\/blog\/wp-json\/wp\/v2\/users\/22"}],"replies":[{"embeddable":true,"href":"https:\/\/quera.org\/blog\/wp-json\/wp\/v2\/comments?post=42076"}],"version-history":[{"count":25,"href":"https:\/\/quera.org\/blog\/wp-json\/wp\/v2\/posts\/42076\/revisions"}],"predecessor-version":[{"id":42115,"href":"https:\/\/quera.org\/blog\/wp-json\/wp\/v2\/posts\/42076\/revisions\/42115"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/quera.org\/blog\/wp-json\/wp\/v2\/media\/42116"}],"wp:attachment":[{"href":"https:\/\/quera.org\/blog\/wp-json\/wp\/v2\/media?parent=42076"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/quera.org\/blog\/wp-json\/wp\/v2\/categories?post=42076"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/quera.org\/blog\/wp-json\/wp\/v2\/tags?post=42076"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}