{"id":287814,"date":"2018-08-16T14:17:09","date_gmt":"2018-08-16T10:17:09","guid":{"rendered":"http:\/\/savepearlharbor.com\/?p=287814"},"modified":"-0001-11-30T00:00:00","modified_gmt":"-0001-11-29T21:00:00","slug":"","status":"publish","type":"post","link":"https:\/\/savepearlharbor.com\/?p=287814","title":{"rendered":"\u0414\u0438\u043d\u0430\u043c\u0438\u0447\u0435\u0441\u043a\u043e\u0435 \u043f\u0440\u043e\u0433\u0440\u0430\u043c\u043c\u0438\u0440\u043e\u0432\u0430\u043d\u0438\u0435 \u0432 \u043e\u043b\u0438\u043c\u043f\u0438\u0430\u0434\u043d\u044b\u0445 \u0437\u0430\u0434\u0430\u0447\u0430\u0445"},"content":{"rendered":"\n<div data-io-article-url=\"https:\/\/habr.com\/post\/418867\/\" class=\"post__text post__text-html js-mediator-article\">\u041f\u0440\u0438\u0432\u0435\u0442! <\/p>\n<p>  \u041d\u0435\u0434\u0430\u0432\u043d\u043e \u0440\u0435\u0448\u0430\u043b \u0437\u0430\u0434\u0430\u0447\u0438 \u0441 \u0430\u0440\u0445\u0438\u0432\u0430 <a href=\"http:\/\/acm.timus.ru\/\">Timus Online Judge<\/a> \u0438 \u043d\u0430\u0442\u043a\u043d\u0443\u043b\u0441\u044f \u043d\u0430 \u0440\u0430\u0437\u0434\u0435\u043b \u043f\u043e\u0434 \u043d\u0430\u0437\u0432\u0430\u043d\u0438\u0435\u043c <i>\u0437\u0430\u0434\u0430\u0447\u0438 \u0434\u0438\u043d\u0430\u043c\u0438\u0447\u0435\u0441\u043a\u043e\u0433\u043e \u043f\u0440\u043e\u0433\u0440\u0430\u043c\u043c\u0438\u0440\u043e\u0432\u0430\u043d\u0438\u044f<\/i>. \u0417\u0430\u0434\u0430\u0447\u0438 \u0442\u0430\u043a\u043e\u0433\u043e \u0442\u0438\u043f\u0430 \u0432\u044b\u0437\u044b\u0432\u0430\u044e\u0442 \u0443 \u043c\u0435\u043d\u044f \u043e\u0441\u043e\u0431\u044b\u0439 \u0438\u043d\u0442\u0435\u0440\u0435\u0441, \u043f\u043e\u0442\u043e\u043c\u0443 \u0447\u0442\u043e \u0437\u0430\u0447\u0430\u0441\u0442\u0443\u044e \u0442\u0430\u043a\u043e\u0439 \u043f\u043e\u0434\u0445\u043e\u0434 \u043e\u0431\u0435\u0441\u043f\u0435\u0447\u0438\u0432\u0430\u0435\u0442 \u0431\u044b\u0441\u0442\u0440\u043e\u0442\u0443 \u0438 \u044d\u043b\u0435\u0433\u0430\u043d\u0442\u043d\u043e\u0441\u0442\u044c \u0440\u0435\u0448\u0435\u043d\u0438\u044f. \u0427\u0442\u043e \u0436\u0435 \u0442\u0430\u043a\u043e\u0435 \u2014 \u0434\u0438\u043d\u0430\u043c\u0438\u0447\u0435\u0441\u043a\u043e\u0435 \u043f\u0440\u043e\u0433\u0440\u0430\u043c\u043c\u0438\u0440\u043e\u0432\u0430\u043d\u0438\u0435? <\/p>\n<p>  \u0414\u0438\u043d\u0430\u043c\u0438\u0447\u0435\u0441\u043a\u043e\u0435 \u043f\u0440\u043e\u0433\u0440\u0430\u043c\u043c\u0438\u0440\u043e\u0432\u0430\u043d\u0438\u0435 \u2014 \u044d\u0442\u043e \u043f\u043e\u0434\u0445\u043e\u0434 \u043a \u0440\u0435\u0448\u0435\u043d\u0438\u044e \u0437\u0430\u0434\u0430\u0447, \u043f\u0440\u0438 \u043a\u043e\u0442\u043e\u0440\u043e\u043c \u043f\u0440\u043e\u0438\u0441\u0445\u043e\u0434\u0438\u0442 \u0440\u0430\u0437\u0431\u0438\u0435\u043d\u0438\u0435 \u043d\u0430 \u043f\u043e\u0434\u0437\u0430\u0434\u0430\u0447\u0438, \u043a\u043e\u0442\u043e\u0440\u044b\u0435 \u00ab\u043f\u0440\u043e\u0449\u0435\u00bb \u0432 \u0441\u0440\u0430\u0432\u043d\u0435\u043d\u0438\u0438 \u0441 \u0438\u0441\u0445\u043e\u0434\u043d\u043e\u0439. \u0421\u043b\u043e\u0432\u043e \u00ab\u0434\u0438\u043d\u0430\u043c\u0438\u0447\u0435\u0441\u043a\u0438\u0439\u00bb \u0431\u043b\u0438\u0437\u043a\u043e \u043f\u043e \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u044e \u043a \u00ab\u0438\u043d\u0434\u0443\u043a\u0442\u0438\u0432\u043d\u044b\u0439\u00bb: \u043f\u0440\u0435\u0434\u043f\u043e\u043b\u0430\u0433\u0430\u0435\u0442\u0441\u044f, \u0447\u0442\u043e \u0438\u0437\u0432\u0435\u0441\u0442\u0435\u043d \u043e\u0442\u0432\u0435\u0442 \u0434\u043b\u044f \u043a\u0430\u043a\u043e\u0433\u043e-\u0442\u043e \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u044f <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/16d\/a50\/7b2\/16da507b2fc389688ef0659939dcc647.svg\" alt=\"$k$\" data-tex=\"inline\"><\/math>, \u0438 \u0445\u043e\u0447\u0435\u0442\u0441\u044f \u043d\u0430\u0439\u0442\u0438 \u043e\u0442\u0432\u0435\u0442 \u0434\u043b\u044f <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/44c\/562\/936\/44c562936a615ceeecfca5c080e31de8.svg\" alt=\"$k+1$\" data-tex=\"inline\"><\/math>. \u0412 \u043c\u0430\u0442\u0435\u043c\u0430\u0442\u0438\u043a\u0435 \u044d\u0442\u043e \u043d\u0430\u0437\u044b\u0432\u0430\u0435\u0442\u0441\u044f \u0438\u043d\u0434\u0443\u043a\u0442\u0438\u0432\u043d\u044b\u043c \u043f\u0435\u0440\u0435\u0445\u043e\u0434\u043e\u043c, \u0438 \u0441\u043e\u0441\u0442\u0430\u0432\u043b\u044f\u0435\u0442 \u043e\u0441\u043d\u043e\u0432\u043d\u0443\u044e \u0438\u0434\u0435\u044e \u0434\u0438\u043d\u0430\u043c\u0438\u0447\u0435\u0441\u043a\u043e\u0433\u043e \u043f\u0440\u043e\u0433\u0440\u0430\u043c\u043c\u0438\u0440\u043e\u0432\u0430\u043d\u0438\u044f. <\/p>\n<h2>\u041f\u0440\u043e\u0441\u0442\u044b\u0435 \u043f\u0440\u0438\u043c\u0435\u0440\u044b<\/h2>\n<p>  \u041d\u0430\u0438\u0431\u043e\u043b\u0435\u0435 \u044f\u0440\u043a\u043e\u0439 \u0438 \u043f\u043e\u043a\u0430\u0437\u0430\u0442\u0435\u043b\u044c\u043d\u043e\u0439 \u0437\u0430\u0434\u0430\u0447\u0435\u0439 \u044f\u0432\u043b\u044f\u0435\u0442\u0441\u044f \u0437\u0430\u0434\u0430\u0447\u0430 \u0432\u044b\u0447\u0438\u0441\u043b\u0435\u043d\u0438\u044f <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/08d\/9fa\/efb\/08d9faefbe272bdf8fbb80773542e343.svg\" alt=\"$n$\" data-tex=\"inline\"><\/math>-\u043e\u0433\u043e \u0447\u0438\u0441\u043b\u0430 \u043f\u043e\u0441\u043b\u0435\u0434\u043e\u0432\u0430\u0442\u0435\u043b\u044c\u043d\u043e\u0441\u0442\u0438 \u0424\u0438\u0431\u043e\u043d\u0430\u0447\u0447\u0438. <a name=\"habracut\"><\/a> \u0418\u0437\u0432\u0435\u0441\u0442\u043d\u043e, \u0447\u0442\u043e \u043f\u043e\u0441\u043b\u0435\u0434\u043e\u0432\u0430\u0442\u0435\u043b\u044c\u043d\u043e\u0441\u0442\u044c \u043e\u0431\u043b\u0430\u0434\u0430\u0435\u0442 \u0442\u0430\u043a\u0438\u043c\u0438 \u0441\u0432\u043e\u0439\u0441\u0442\u0432\u0430\u043c\u0438: <\/p>\n<p><math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/6e2\/15f\/1c8\/6e215f1c80a9fbc6fde64594c97f2063.svg\" alt=\"$ F_0 = F_1 = 1,\\ F_n = F_{n-1} + F_{n-2}.$\" data-tex=\"display\"><\/math><\/p>\n<p>  \u041e\u0442\u0441\u044e\u0434\u0430 \u0441\u0440\u0430\u0437\u0443 \u0432\u044b\u0442\u0435\u043a\u0430\u0435\u0442 \u0440\u0435\u043a\u0443\u0440\u0440\u0435\u043d\u0442\u043d\u0430\u044f \u0444\u043e\u0440\u043c\u0443\u043b\u0430:<\/p>\n<pre><code class=\"java\">int Fibonacci(int n) { \tif(n == 1 || n == 2) return 1; \treturn Fibonacci(n-1) + Fibonacci(n-2); }<\/code><\/pre>\n<p>  \u0415\u0441\u043b\u0438 \u0440\u0435\u043a\u0443\u0440\u0441\u0438\u044f \u0438\u0449\u0435\u0442 \u0447\u0438\u0441\u043b\u043e \u00ab\u0441 \u043a\u043e\u043d\u0446\u0430\u00bb, \u0442\u043e \u0441\u043b\u0435\u0434\u0443\u0449\u0438\u0439 \u043c\u0435\u0442\u043e\u0434 \u043f\u043e\u0441\u043b\u0435\u0434\u043e\u0432\u0430\u0442\u0435\u043b\u044c\u043d\u043e \u0432\u044b\u0447\u0438\u0441\u043b\u044f\u0435\u0442 \u0432\u0441\u0435 \u0447\u0438\u0441\u043b\u0430, \u0440\u0430\u0441\u043f\u043e\u043b\u043e\u0436\u0435\u043d\u043d\u044b\u0435 \u043c\u0435\u0436\u0434\u0443 <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/f9c\/3c8\/e48\/f9c3c8e488ead4696749012f5ece6d13.svg\" alt=\"$0$\" data-tex=\"inline\"><\/math> \u0438 <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/08d\/9fa\/efb\/08d9faefbe272bdf8fbb80773542e343.svg\" alt=\"$n$\" data-tex=\"inline\"><\/math>:<\/p>\n<pre><code class=\"java\">int dpFibonacci(int n) { \tint prev1 = 1; \tint prev2 = 1; \tint curr = 0; \tfor(int j = 2; j &lt; n; j++) { \t\tcurr = prev1 + prev2; \t\tprev1 = prev2; \t\tprev2 = curr; \t} \t\treturn curr; }<\/code><\/pre>\n<p>  \u041f\u043e\u043d\u044f\u0442\u043d\u043e, \u0447\u0442\u043e \u043f\u0440\u0438 \u0434\u043e\u0441\u0442\u0430\u0442\u043e\u0447\u043d\u043e \u0431\u043e\u043b\u044c\u0448\u0438\u0445 <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/08d\/9fa\/efb\/08d9faefbe272bdf8fbb80773542e343.svg\" alt=\"$n$\" data-tex=\"inline\"><\/math> \u044d\u0442\u043e\u0442 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u0440\u0430\u0431\u043e\u0442\u0430\u0435\u0442 \u043d\u0430\u043c\u043d\u043e\u0433\u043e \u0431\u044b\u0441\u0442\u0440\u0435\u0435: \u043e\u043d \u043d\u0435 \u0432\u044b\u0447\u0438\u0441\u043b\u044f\u0435\u0442 \u043f\u0440\u043e\u043c\u0435\u0436\u0443\u0442\u043e\u0447\u043d\u044b\u0435 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u044f \u043f\u043e \u043d\u0435\u0441\u043a\u043e\u043b\u044c\u043a\u0443 \u0440\u0430\u0437. \u0420\u0430\u0441\u0441\u043c\u043e\u0442\u0440\u0438\u043c \u0447\u0443\u0442\u044c \u0431\u043e\u043b\u0435\u0435 \u0441\u043b\u043e\u0436\u043d\u044b\u0439 \u043f\u0440\u0438\u043c\u0435\u0440. <\/p>\n<p>  <b>\u041f\u0440\u0438\u043c\u0435\u0440 1.<\/b> \u0412\u044b \u0448\u0430\u0433\u0430\u0435\u0442\u0435 \u043f\u043e \u043f\u043b\u0430\u0442\u043d\u043e\u0439 \u043b\u0435\u0441\u0442\u043d\u0438\u0446\u0435. \u0427\u0442\u043e\u0431\u044b \u043d\u0430\u0441\u0442\u0443\u043f\u0438\u0442\u044c \u043d\u0430 <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/bf8\/3b5\/32c\/bf83b532cd867d34004f8eded8c5c79a.svg\" alt=\"$i$\" data-tex=\"inline\"><\/math>-\u0443\u044e \u0441\u0442\u0443\u043f\u0435\u043d\u044c\u043a\u0443, \u043d\u0435\u043e\u0431\u0445\u043e\u0434\u0438\u043c\u043e \u0437\u0430\u043f\u043b\u0430\u0442\u0438\u0442\u044c <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/122\/b00\/691\/122b006916bcacd39b883735fa907bfa.svg\" alt=\"$a_i$\" data-tex=\"inline\"><\/math> \u043c\u043e\u043d\u0435\u0442. \u0412\u044b \u043c\u043e\u0436\u0435\u0442\u0435 \u043f\u0435\u0440\u0435\u0448\u0430\u0433\u0438\u0432\u0430\u0442\u044c \u043d\u0430 \u0441\u043b\u0435\u0434\u0443\u044e\u0449\u0443\u044e \u0441\u0442\u0443\u043f\u0435\u043d\u044c \u0438\u043b\u0438 \u043f\u0435\u0440\u0435\u043f\u0440\u044b\u0433\u0438\u0432\u0430\u0442\u044c \u0447\u0435\u0440\u0435\u0437 \u043e\u0434\u043d\u0443. \u0417\u0430\u0434\u0430\u0447\u0430: \u043f\u0440\u043e\u0439\u0442\u0438 <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/08d\/9fa\/efb\/08d9faefbe272bdf8fbb80773542e343.svg\" alt=\"$n$\" data-tex=\"inline\"><\/math> \u0441\u0442\u0443\u043f\u0435\u043d\u0435\u043a \u0438 \u043f\u043e\u0442\u0440\u0430\u0442\u0438\u0442\u044c \u043a\u0430\u043a \u043c\u043e\u0436\u043d\u043e \u043c\u0435\u043d\u044c\u0448\u0435 \u043c\u043e\u043d\u0435\u0442.<\/p>\n<p>  \u041f\u043e\u043d\u044f\u0442\u043d\u043e, \u0447\u0442\u043e \u043f\u0435\u0440\u0435\u0448\u0430\u0433\u0438\u0432\u0430\u044f \u0447\u0435\u0440\u0435\u0437 \u043a\u0430\u0436\u0434\u0443\u044e \u0441\u0442\u0443\u043f\u0435\u043d\u044c, \u043c\u044b \u043c\u0438\u043d\u0438\u043c\u0438\u0437\u0443\u0440\u0435\u043c \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e \u00ab\u043f\u043b\u0430\u0442\u0435\u0436\u0435\u0439\u00bb, \u043d\u043e \u043c\u043e\u0436\u0435\u043c \u043d\u0430\u0440\u0432\u0430\u0442\u044c\u0441\u044f \u043d\u0430 \u043e\u0447\u0435\u043d\u044c \u0434\u043e\u0440\u043e\u0433\u0443\u044e \u0441\u0442\u0443\u043f\u0435\u043d\u044c, \u043a\u043e\u0442\u043e\u0440\u0443\u044e \u0445\u043e\u0442\u0435\u043b\u043e\u0441\u044c \u0431\u044b \u0438\u0437\u0431\u0435\u0436\u0430\u0442\u044c. \u0421\u043e\u0437\u0434\u0430\u0434\u0438\u043c \u043c\u0430\u0441\u0441\u0438\u0432 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0439 <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/35e\/a85\/36b\/35ea8536b3e6152e60442ccecbc46812.svg\" alt=\"$d$\" data-tex=\"inline\"><\/math>, \u0432 \u043a\u043e\u0442\u043e\u0440\u043e\u043c \u043d\u0430 <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/b82\/8e2\/475\/b828e2475a3a56280b895f35eb250ea2.svg\" alt=\"$j$\" data-tex=\"inline\"><\/math>-\u043e\u043c \u043c\u0435\u0441\u0442\u0435 \u0431\u0443\u0434\u0435\u0442 (\u043c\u0438\u043d\u0438\u043c\u0430\u043b\u044c\u043d\u043e\u0435) \u0447\u0438\u0441\u043b\u043e \u043c\u043e\u043d\u0435\u0442, \u043a\u043e\u0442\u043e\u0440\u044b\u0435 \u043d\u0435\u043e\u0431\u0445\u043e\u0434\u0438\u043c\u043e \u043f\u043e\u0442\u0440\u0430\u0442\u0438\u0442\u044c, \u0447\u0442\u043e\u0431\u044b \u0434\u043e\u0431\u0440\u0430\u0442\u044c\u0441\u044f \u0434\u043e <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/b82\/8e2\/475\/b828e2475a3a56280b895f35eb250ea2.svg\" alt=\"$j$\" data-tex=\"inline\"><\/math>-\u043e\u0439 \u0441\u0442\u0443\u043f\u0435\u043d\u044c\u043a\u0438. \u0421\u0440\u0430\u0437\u0443 \u044f\u0441\u043d\u043e, \u0447\u0442\u043e <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/a0c\/9c8\/982\/a0c9c8982d4274c1d25d81daab406bb0.svg\" alt=\"$d_1 = a_1, \\ d_2 = a_2$\" data-tex=\"inline\"><\/math>. \u0410 \u0434\u0430\u043b\u044c\u0448\u0435 \u0431\u0443\u0434\u0435\u043c \u0431\u0440\u0430\u0442\u044c \u043c\u0438\u043d\u0438\u043c\u0443\u043c \u0438\u0437 \u0434\u0432\u0443\u0445 \u043f\u0440\u0435\u0434\u044b\u0434\u0443\u0449\u0438\u0445 \u0441\u0442\u0443\u043f\u0435\u043d\u0435\u043a \u0438 \u0434\u043e\u0431\u0430\u0432\u043b\u044f\u0442\u044c \u0441\u0442\u043e\u0438\u043c\u043e\u0441\u0442\u044c \u0441\u0430\u043c\u043e\u0439 \u0441\u0442\u0443\u043f\u0435\u043d\u044c\u043a\u0438: <\/p>\n<p><math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/e37\/62b\/869\/e3762b8699c7ce6e0cf09b4f10f54286.svg\" alt=\"$d_i = \\min \\left(d_{i-1}, d_{i-2}\\right) + a_{i}.$\" data-tex=\"display\"><\/math><\/p>\n<p>  \u041d\u0435\u043c\u043d\u043e\u0433\u043e \u0438\u0437\u043c\u0435\u043d\u0438\u043c \u0443\u0441\u043b\u043e\u0432\u0438\u044f \u0437\u0430\u0434\u0430\u0447\u0438: \u043f\u0440\u0435\u0434\u043f\u043e\u043b\u043e\u0436\u0438\u043c, \u0447\u0442\u043e \u043d\u0430 \u043a\u0430\u043a\u0438\u0445-\u0442\u043e \u0441\u0442\u0443\u043f\u0435\u043d\u044c\u043a\u0430\u0445 \u0432\u044b \u043c\u043e\u0436\u0435\u0442\u0435 \u043f\u043e\u043b\u0443\u0447\u0430\u0442\u044c \u043c\u043e\u043d\u0435\u0442\u044b (\u044d\u0442\u043e \u0431\u0443\u0434\u0435\u0442 \u043e\u0437\u043d\u0430\u0447\u0430\u0442\u044c, \u0447\u0442\u043e <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/39d\/a47\/bf1\/39da47bf1b69f4b6f23736b41393ac1d.svg\" alt=\"$a_k &lt; 0$\" data-tex=\"inline\"><\/math>). \u0427\u0442\u043e \u043d\u0435\u043e\u0431\u0445\u043e\u0434\u0438\u043c\u043e \u0438\u0437\u043c\u0435\u043d\u0438\u0442\u044c \u0432 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0435, \u0447\u0442\u043e\u0431\u044b \u043e\u043d \u0434\u0430\u0432\u0430\u043b \u043f\u0440\u0430\u0432\u0438\u043b\u044c\u043d\u044b\u0439 \u0440\u0435\u0437\u0443\u043b\u044c\u0442\u0430\u0442?<\/p>\n<div class=\"spoiler\"><b class=\"spoiler_title\">\u0420\u0435\u0448\u0435\u043d\u0438\u0435<\/b><\/p>\n<div class=\"spoiler_text\">\u041d\u0443\u0436\u043d\u043e \u0438\u0437\u043c\u0435\u043d\u0438\u0442\u044c \u0442\u043e\u043b\u044c\u043a\u043e \u00ab\u043d\u0430\u0447\u0430\u043b\u043e\u00bb \u043d\u0430\u0448\u0435\u0439 \u0434\u0438\u043d\u0430\u043c\u0438\u043a\u0438. \u0415\u0441\u043b\u0438 \u043f\u0435\u0440\u0432\u0430\u044f \u043b\u0435\u0441\u0442\u043d\u0438\u0446\u0430 \u043d\u0435 \u043f\u0440\u0438\u043d\u043e\u0441\u0438\u0442 \u043d\u0430\u043c \u043c\u043e\u043d\u0435\u0442, \u0442\u043e \u0436\u0435\u043b\u0430\u0442\u0435\u043b\u044c\u043d\u043e \u043f\u0435\u0440\u0435\u043f\u0440\u044b\u0433\u043d\u0443\u0442\u044c \u0447\u0435\u0440\u0435\u0437 \u043d\u0435\u0435, \u043e\u0434\u043d\u0430\u043a\u043e, \u0435\u0441\u043b\u0438 <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/960\/440\/288\/960440288c448dc4f818043c0566f981.svg\" alt=\"$a_1 &lt; 0$\" data-tex=\"inline\"><\/math>, \u0442\u043e \u043b\u0443\u0447\u0448\u0435 \u043d\u0430\u0441\u0442\u0443\u043f\u0438\u0442\u044c \u0438 \u0441\u043e\u0431\u0440\u0430\u0442\u044c \u0441\u0432\u043e\u0438 \u043c\u043e\u043d\u0435\u0442\u043a\u0438. \u0418\u0442\u0430\u043a, <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/5d2\/630\/6e1\/5d26306e1799970d4b3036a2214c0fde.svg\" alt=\"$d_2 = \\min\\left(0, d_1\\right) + a_2$\" data-tex=\"inline\"><\/math>.  <\/div>\n<\/div>\n<p>  \u0420\u0430\u0441\u0441\u043c\u043e\u0442\u0440\u0438\u043c \u0434\u0440\u0443\u0433\u043e\u0439 \u043f\u0440\u0438\u043c\u0435\u0440, \u0432 \u043a\u043e\u0442\u043e\u0440\u043e\u043c \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u0435\u0442\u0441\u044f \u00ab\u0434\u0432\u0443\u043c\u0435\u0440\u043d\u0430\u044f\u00bb \u0434\u0438\u043d\u0430\u043c\u0438\u043a\u0430. <\/p>\n<p>  <b>\u041f\u0440\u0438\u043c\u0435\u0440 2.<\/b> \u0412 \u043b\u0430\u0431\u0438\u0440\u0438\u043d\u0442\u0435 \u0438\u043c\u0435\u0435\u0442\u0441\u044f <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/038\/f9e\/5bf\/038f9e5bf254d47500d869632af1d6ea.svg\" alt=\"$n\\times m$\" data-tex=\"inline\"><\/math> \u043a\u043e\u043c\u043d\u0430\u0442, \u0432 \u043a\u0430\u0436\u0434\u043e\u0439 \u0438\u0437 \u043a\u043e\u0442\u043e\u0440\u044b\u0445 \u043d\u0430\u0445\u043e\u0434\u0438\u0442\u0441\u044f \u0437\u043e\u043b\u043e\u0442\u043e (\u0432 \u043a\u043b\u0435\u0442\u043a\u0435 <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/aa1\/84d\/68d\/aa184d68d45155402576665ad494ecc3.svg\" alt=\"$(i,j)$\" data-tex=\"inline\"><\/math> \u043b\u0435\u0436\u0438\u0442 <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/9f1\/b0a\/4a1\/9f1b0a4a138133c49de7e2547828295e.svg\" alt=\"$a_{ij}$\" data-tex=\"inline\"><\/math> \u0437\u043e\u043b\u043e\u0442\u0430). \u0417\u0430\u0434\u0430\u0447\u0430 \u2014 \u043e\u043f\u0440\u0435\u0434\u0435\u043b\u0438\u0442\u044c, \u043a\u0430\u043a\u043e\u0435 \u043c\u0430\u043a\u0441\u0438\u043c\u0430\u043b\u044c\u043d\u043e\u0435 \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e \u0437\u043e\u043b\u043e\u0442\u0430 \u043c\u043e\u0436\u043d\u043e \u0441\u043e\u0431\u0440\u0430\u0442\u044c \u043f\u0440\u0438 \u043e\u043f\u0442\u0438\u043c\u0430\u043b\u044c\u043d\u043e\u043c \u043c\u0430\u0440\u0448\u0440\u0443\u0442\u0435 \u0438\u0437 \u0442\u043e\u0447\u043a\u0438 <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/7bd\/4dc\/fda\/7bd4dcfdaca65306e56a1ac89735cec9.svg\" alt=\"$(0,0)$\" data-tex=\"inline\"><\/math> \u0432 \u0442\u043e\u0447\u043a\u0443 <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/acf\/2fb\/46e\/acf2fb46e564b887fb0a5aa548d0ec39.svg\" alt=\"$(n,m)$\" data-tex=\"inline\"><\/math>, \u0435\u0441\u043b\u0438 \u0438\u0434\u0442\u0438 \u043c\u043e\u0436\u043d\u043e \u043b\u0438\u0431\u043e \u0432\u043d\u0438\u0437, \u043b\u0438\u0431\u043e \u043d\u0430\u043f\u0440\u0430\u0432\u043e. <\/p>\n<p>  \u0418\u0442\u0430\u043a, \u043c\u044b \u0445\u043e\u0442\u0438\u043c \u0443\u0437\u043d\u0430\u0442\u044c \u043e\u043f\u0442\u0438\u043c\u0430\u043b\u044c\u043d\u044b\u0439 \u043c\u0430\u0440\u0448\u0440\u0443\u0442 \u0432 \u043a\u043b\u0435\u0442\u043a\u0443 <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/aa1\/84d\/68d\/aa184d68d45155402576665ad494ecc3.svg\" alt=\"$(i,j)$\" data-tex=\"inline\"><\/math>. \u0421\u044e\u0434\u0430 \u043c\u044b \u043c\u043e\u0436\u0435\u043c \u043f\u043e\u043f\u0430\u0441\u0442\u044c \u0438\u0437 \u0434\u0432\u0443\u0445 \u043a\u043b\u0435\u0442\u043e\u043a \u2014 <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/722\/8ee\/a15\/7228eea153ce9e15289a6259862845f0.svg\" alt=\"$(i-1, j)$\" data-tex=\"inline\"><\/math> \u0438 <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/e38\/7b3\/803\/e387b3803a017534479804a669c0df8c.svg\" alt=\"$(i, j-1)$\" data-tex=\"inline\"><\/math>. \u0421 \u0443\u0447\u0435\u0442\u043e\u043c \u0442\u043e\u0433\u043e, \u0447\u0442\u043e \u043e\u043f\u0442\u0438\u043c\u0430\u043b\u044c\u043d\u044b\u0435 \u043c\u0430\u0440\u0448\u0440\u0443\u0442\u044b \u0434\u043b\u044f \u044d\u0442\u0438\u0445 \u0434\u0432\u0443\u0445 \u043a\u043b\u0435\u0442\u043e\u043a \u0438\u0437\u0432\u0435\u0441\u0442\u043d\u044b (\u043e\u043d\u0438 \u0445\u0440\u0430\u043d\u044f\u0442\u0441\u044f \u0432 \u043a\u0430\u043a\u043e\u0439-\u0442\u043e \u0442\u0430\u0431\u043b\u0438\u0446\u0435 <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/35e\/a85\/36b\/35ea8536b3e6152e60442ccecbc46812.svg\" alt=\"$d$\" data-tex=\"inline\"><\/math>), \u0442\u043e \u043e\u0442\u0432\u0435\u0442 \u0434\u043b\u044f \u043a\u043b\u0435\u0442\u043a\u0438 <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/aa1\/84d\/68d\/aa184d68d45155402576665ad494ecc3.svg\" alt=\"$(i,j)$\" data-tex=\"inline\"><\/math> \u043f\u043e\u043b\u0443\u0447\u0430\u0435\u0442\u0441\u044f \u0441\u043b\u0435\u0434\u0443\u044e\u0449\u0438\u043c \u043e\u0431\u0440\u0430\u0437\u043e\u043c:   <\/p>\n<p><math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/329\/bec\/38f\/329bec38f434db51fb29799ab67ab7c8.svg\" alt=\"$ d_{ij} = \\max \\left(d_{i-1j}, d_{ij-1}\\right) + a_{ij}.$\" data-tex=\"display\"><\/math><\/p>\n<p>  \u042d\u0442\u0430 \u0435\u0449\u0435 \u043e\u0434\u043d\u0430 \u043a\u043b\u0430\u0441\u0441\u0438\u0447\u0435\u0441\u043a\u0430\u044f \u0437\u0430\u0434\u0430\u0447\u0430 \u0434\u0438\u043d\u0430\u043c\u0438\u0447\u0435\u0441\u043a\u043e\u0433\u043e \u043f\u0440\u043e\u0433\u0440\u0430\u043c\u043c\u0438\u0440\u043e\u0432\u0430\u043d\u0438\u044f, \u043c\u043e\u0434\u0438\u0444\u0438\u043a\u0430\u0446\u0438\u0438 \u043a\u043e\u0442\u043e\u0440\u043e\u0439 \u0434\u043e\u0432\u043e\u043b\u044c\u043d\u043e \u0447\u0430\u0441\u0442\u043e \u0432\u0441\u0442\u0440\u0435\u0447\u0430\u044e\u0442\u0441\u044f \u0432 \u0437\u0430\u0434\u0430\u0447\u0430\u0445 \u0441\u043f\u043e\u0440\u0442\u0438\u0432\u043d\u043e\u0433\u043e \u043f\u0440\u043e\u0433\u0440\u0430\u043c\u043c\u0438\u0440\u043e\u0432\u0430\u043d\u0438\u044f. \u0411\u043e\u043b\u0435\u0435 \u043f\u043e\u0434\u0440\u043e\u0431\u043d\u043e \u0430\u043d\u0430\u043b\u043e\u0433\u0438\u0447\u043d\u0430\u044f \u0437\u0430\u0434\u0430\u0447\u0430 \u043e\u0431\u044a\u044f\u0441\u043d\u044f\u0435\u0442\u0441\u044f <a href=\"https:\/\/habr.com\/post\/113108\/\">\u0437\u0434\u0435\u0441\u044c<\/a>.<\/p>\n<h2>\u0411\u043e\u043b\u0435\u0435 \u0441\u043b\u043e\u0436\u043d\u044b\u0435 \u0437\u0430\u0434\u0430\u0447\u0438<\/h2>\n<p> \u041f\u0440\u0438 \u0436\u0435\u043b\u0430\u043d\u0438\u0438 \u0434\u0438\u043d\u0430\u043c\u0438\u0447\u0435\u0441\u043a\u0438\u0439 \u043f\u043e\u0434\u0445\u043e\u0434 \u043c\u043e\u0436\u043d\u043e \u043f\u0440\u0438\u043a\u0440\u0443\u0442\u0438\u0442\u044c \u043a\u0443\u0434\u0430 \u0432\u0437\u0434\u0443\u043c\u0430\u0435\u0442\u0441\u044f. \u0420\u0430\u0441\u0441\u043c\u043e\u0442\u0440\u0438\u043c <a href=\"http:\/\/acm.timus.ru\/problem.aspx?space=1&amp;num=1073\">\u0437\u0430\u0434\u0430\u0447\u0443<\/a> \u0441 \u0430\u0440\u0445\u0438\u0432\u0430 Timus Online Judge.<\/p>\n<p>  \u041c\u0430\u0442\u0435\u043c\u0430\u0442\u0438\u0447\u0435\u0441\u043a\u0430\u044f \u0444\u043e\u0440\u043c\u0443\u043b\u0438\u0440\u043e\u0432\u043a\u0430 \u0437\u0430\u0434\u0430\u0447\u0438 \u0442\u0430\u043a\u0430\u044f: \u0442\u0440\u0435\u0431\u0443\u0435\u0442\u0441\u044f \u043d\u0430\u0439\u0442\u0438 \u043c\u0438\u043d\u0438\u043c\u0430\u043b\u044c\u043d\u043e\u0435 \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e \u0441\u043b\u0430\u0433\u0430\u0435\u043c\u044b\u0445, \u043d\u0435\u043e\u0431\u0445\u043e\u0434\u0438\u043c\u044b\u0445 \u0434\u043b\u044f \u0440\u0430\u0437\u043b\u043e\u0436\u0435\u043d\u0438\u044f \u0437\u0430\u0434\u0430\u043d\u043d\u043e\u0433\u043e \u0447\u0438\u0441\u043b\u0430 \u043d\u0430 \u043f\u043e\u043b\u043d\u044b\u0435 \u043a\u0432\u0430\u0434\u0440\u0430\u0442\u044b.<\/p>\n<p>  \u041a\u0430\u043a \u0438 \u0440\u0430\u043d\u044c\u0448\u0435, \u043f\u0440\u0435\u0434\u043f\u043e\u043b\u043e\u0436\u0438\u043c, \u0447\u0442\u043e \u043d\u0430\u043c \u0438\u0437\u0432\u0435\u0441\u0442\u043d\u044b \u043e\u0442\u0432\u0435\u0442\u044b \u0434\u043b\u044f \u0432\u0441\u0435\u0445 \u0447\u0438\u0441\u0435\u043b <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/16c\/295\/9cf\/16c2959cfeb37a78592f521cd14387fa.svg\" alt=\"$k-1$\" data-tex=\"inline\"><\/math>, \u043a\u043e\u0442\u043e\u0440\u044b\u0435 \u0445\u0440\u0430\u043d\u044f\u0442\u0441\u044f \u0432 \u043a\u0430\u043a\u043e\u043c-\u043d\u0438\u0431\u0443\u0434\u044c \u043c\u0430\u0441\u0441\u0438\u0432\u0435 <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/35e\/a85\/36b\/35ea8536b3e6152e60442ccecbc46812.svg\" alt=\"$d$\" data-tex=\"inline\"><\/math>, \u0438 \u043d\u0430\u043c \u0431\u044b \u0445\u043e\u0442\u0435\u043b\u043e\u0441\u044c \u043d\u0430\u0439\u0442\u0438 <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/d6f\/2c9\/fcd\/d6f2c9fcd664ff80a6f44ac617ab45fa.svg\" alt=\"$d_{k}$\" data-tex=\"inline\"><\/math>.<\/p>\n<p>  \u0412\u043e\u0437\u044c\u043c\u0435\u043c \u044d\u0442\u043e \u0447\u0438\u0441\u043b\u043e <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/16d\/a50\/7b2\/16da507b2fc389688ef0659939dcc647.svg\" alt=\"$k$\" data-tex=\"inline\"><\/math> \u0438 \u043f\u0440\u043e\u0430\u043d\u0430\u043b\u0438\u0437\u0438\u0440\u0443\u0435\u043c, \u043a\u0430\u043a\u0438\u0435 \u043c\u043e\u0433\u0443\u0442 \u0431\u044b\u0442\u044c \u0441\u0438\u0442\u0443\u0430\u0446\u0438\u0438: <\/p>\n<ol>\n<li> <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/16d\/a50\/7b2\/16da507b2fc389688ef0659939dcc647.svg\" alt=\"$k$\" data-tex=\"inline\"><\/math> \u044f\u0432\u043b\u044f\u0435\u0442\u0441\u044f \u043f\u043e\u043b\u043d\u044b\u043c \u043a\u0432\u0430\u0434\u0440\u0430\u0442\u043e\u043c. \u0412 \u044d\u0442\u043e\u043c \u0441\u043b\u0443\u0447\u0430\u0435 <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/77c\/67b\/526\/77c67b526221822e785421a1aef7f912.svg\" alt=\"$d_{k} = 1$\" data-tex=\"inline\"><\/math>.<\/li>\n<li> \u0412\u043e\u0437\u043c\u043e\u0436\u043d\u043e, \u043f\u0440\u0435\u0434\u044b\u0434\u0443\u0449\u0435\u0435 \u0447\u0438\u0441\u043b\u043e <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/16c\/295\/9cf\/16c2959cfeb37a78592f521cd14387fa.svg\" alt=\"$k-1$\" data-tex=\"inline\"><\/math> \u0431\u044b\u043b\u043e \u043f\u043e\u043b\u043d\u044b\u043c \u043a\u0432\u0430\u0434\u0440\u0430\u0442\u043e\u043c. \u0422\u043e\u0433\u0434\u0430 <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/0aa\/704\/8bd\/0aa7048bd04b7f512d0ee23df3edf222.svg\" alt=\"$d_{k} = d_{k-1} + 1$\" data-tex=\"inline\"><\/math>.<\/li>\n<\/ol>\n<p>  \u0412\u043e\u043e\u0431\u0449\u0435, \u0432\u0430\u0440\u0438\u0430\u043d\u0442 \u043f\u0440\u0438\u0431\u0430\u0432\u043b\u0435\u043d\u0438\u044f \u0435\u0434\u0438\u043d\u0438\u0446\u044b \u043a \u043f\u0440\u0435\u0434\u044b\u0434\u0443\u0449\u0435\u043c\u0443 \u043a\u0430\u0436\u0435\u0442\u0441\u044f \u043d\u0435 \u0442\u0430\u043a\u0438\u043c \u0443\u0436 \u043f\u043b\u043e\u0445\u0438\u043c.<\/p>\n<p>  \u041f\u043e\u0441\u0442\u0443\u043f\u0438\u043c \u0441\u043b\u0435\u0434\u0443\u044e\u0449\u0438\u043c \u043e\u0431\u0440\u0430\u0437\u043e\u043c: \u0431\u0443\u0434\u0435\u043c \u0438\u0441\u043a\u0430\u0442\u044c \u0440\u0430\u0437\u043b\u043e\u0436\u0435\u043d\u0438\u0435 <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/a7b\/197\/ac3\/a7b197ac3f3d9d4f0b095ce86300c48b.svg\" alt=\"$k = q^2 + s$\" data-tex=\"inline\"><\/math> \u0442\u0430\u043a\u043e\u0435, \u0447\u0442\u043e <\/p>\n<p><math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/9a8\/c14\/f5d\/9a8c14f5d29e2e4fe5e2b25dc6551335.svg\" alt=\"$d_{q^2} + d_s &lt; d_{k-1} + 1.$\" data-tex=\"display\"><\/math><\/p>\n<p> \u0422\u0430\u043a \u043a\u0430\u043a <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/7f6\/d5a\/e59\/7f6d5ae593f2bb2d18fbe81725bc9f29.svg\" alt=\"$q^2$\" data-tex=\"inline\"><\/math> \u2014 \u043f\u043e\u043b\u043d\u044b\u0439 \u043a\u0432\u0430\u0434\u0440\u0430\u0442, \u0442\u043e <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/627\/bce\/0c1\/627bce0c182060a50956fcb87b8d610e.svg\" alt=\"$d_{q^2} = 1$\" data-tex=\"inline\"><\/math>, \u0438 <\/p>\n<p><math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/6ac\/e7f\/010\/6ace7f01087edd0958c0cdb96892848a.svg\" alt=\"$d_s &lt; d_{k-1},$\" data-tex=\"display\"><\/math><\/p>\n<p> \u0442\u043e \u0435\u0441\u0442\u044c \u043c\u044b \u043d\u0430\u0448\u043b\u0438 \u0440\u0430\u0437\u0431\u0438\u0435\u043d\u0438\u0435, \u043a\u043e\u0442\u043e\u0440\u043e\u0435 \u043f\u0440\u043e\u0441\u0442\u043e-\u043d\u0430\u043f\u0440\u043e\u0441\u0442\u043e \u043b\u0443\u0447\u0448\u0435, \u0447\u0435\u043c <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/3a7\/839\/35b\/3a783935b347ceb65ffd3aaa32f01d39.svg\" alt=\"$d_{k-1} + 1$\" data-tex=\"inline\"><\/math>, \u0438 \u043e\u0442\u0432\u0435\u0442 \u0432 \u044d\u0442\u043e\u043c \u0441\u043b\u0443\u0447\u0430\u0435 \u0431\u0443\u0434\u0435\u0442 <\/p>\n<p><math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/bb6\/e40\/f2f\/bb6e40f2f23cba0e0224e38ae6e8a5ac.svg\" alt=\"$d_k = d_{s} + d_{q^2} = d_s + 1.$\" data-tex=\"display\"><\/math><\/p>\n<div class=\"spoiler\"><b class=\"spoiler_title\">\u041f\u0440\u0438\u043c\u0435\u0440 \u043a\u043e\u0434\u0430 \u043d\u0430 Java, \u0440\u0435\u0430\u043b\u0438\u0437\u0443\u044e\u0449\u0438\u0439 \u0434\u0430\u043d\u043d\u044b\u0439 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c:<\/b><\/p>\n<div class=\"spoiler_text\">\n<pre><code class=\"java\">for(int k = 1; k &lt;= n; k++) { \tint best = d[k - 1] + 1; \/\/ \u043f\u0440\u0438\u043d\u0438\u043c\u0430\u0435\u043c \u044d\u0442\u043e\u0442 \u0432\u0430\u0440\u0438\u0430\u043d\u0442 \u0437\u0430 \u043d\u0430\u0438\u043b\u0443\u0447\u0448\u0438\u0439 \tint q = 1; \twhile(k - q*q &gt;= 0) {  \/\/ k = q*q + s \t\tif(k - q*q == 0) { \/\/ k - \u043f\u043e\u043b\u043d\u044b\u0439 \u043a\u0432\u0430\u0434\u0440\u0430\u0442 \t\t\tbest = 1; \t\t\tbreak; \t\t} else if(d[k - q*q] &lt; best) best = d[k - q*q] + 1;  \t\t \t\tq++; \t} \td[k] = best; } <\/code><\/pre>\n<p>  <\/div>\n<\/div>\n<p>  \u0420\u0430\u0441\u0441\u043c\u043e\u0442\u0440\u0438\u043c \u0441\u043b\u0435\u0434\u0443\u044e\u0449\u0443\u044e <a href=\"http:\/\/acm.timus.ru\/problem.aspx?space=1&amp;num=1017\">\u0437\u0430\u0434\u0430\u0447\u0443<\/a>. \u0426\u0435\u043b\u044c \u2014 \u043f\u043e\u0441\u0442\u0440\u043e\u0438\u0442\u044c \u043b\u0435\u0441\u0442\u043d\u0438\u0446\u0443 \u0438\u0437 <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/1e8\/0c3\/b30\/1e80c3b3087c0a57b68ad11261a9ec2b.svg\" alt=\"$N$\" data-tex=\"inline\"><\/math> \u043a\u0443\u0431\u0438\u043a\u043e\u0432 \u043f\u043e \u043f\u0440\u0430\u0432\u0438\u043b\u0430\u043c:<\/p>\n<ol>\n<li>\u043b\u0435\u0441\u0442\u043d\u0438\u0446\u0430 \u0438\u043c\u0435\u0435\u0442 \u043c\u0438\u043d\u0438\u043c\u0443\u043c \u0434\u0432\u0435 \u0441\u0442\u0443\u043f\u0435\u043d\u0438;<\/li>\n<li>\u043b\u0435\u0441\u0442\u043d\u0438\u0446\u0430 \u043d\u0435 \u043c\u043e\u0436\u0435\u0442 \u0438\u043c\u0435\u0442\u044c \u0434\u0432\u0435 \u043e\u0434\u0438\u043d\u0430\u043a\u043e\u0432\u044b\u0435 \u0441\u0442\u0443\u043f\u0435\u043d\u0438;<\/li>\n<li>\u0441\u0442\u0443\u043f\u0435\u043d\u0438 \u043b\u0435\u0441\u0442\u043d\u0438\u0446\u044b \u0438\u0434\u0443\u0442 \u0432 \u043f\u043e\u0440\u044f\u0434\u043a\u0435 \u0432\u043e\u0437\u0440\u0430\u0441\u0442\u0430\u043d\u0438\u044f (\u0442\u043e \u0435\u0441\u0442\u044c \u0441\u043b\u0435\u0434\u0443\u044e\u0449\u0430\u044f \u0431\u043e\u043b\u044c\u0448\u0435, \u0447\u0435\u043c \u043f\u0440\u0435\u0434\u044b\u0434\u0443\u0449\u0430\u044f).<\/li>\n<\/ol>\n<p>  \u041d\u0430 \u044d\u0442\u043e\u0442 \u0440\u0430\u0437 \u0431\u0443\u0434\u0435\u043c \u0441\u0442\u0440\u043e\u0438\u0442\u044c \u0434\u0432\u0443\u043c\u0435\u0440\u043d\u0443\u044e \u0434\u0438\u043d\u0430\u043c\u0438\u043a\u0443. \u0421\u043e\u0437\u0434\u0430\u0434\u0438\u043c \u0442\u0430\u0431\u0438\u0446\u0443 <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/35e\/a85\/36b\/35ea8536b3e6152e60442ccecbc46812.svg\" alt=\"$d$\" data-tex=\"inline\"><\/math>, \u0432 \u043a\u043e\u0442\u043e\u0440\u043e\u0439 \u043d\u0430 \u043f\u043e\u0437\u0438\u0446\u0438\u0438 <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/aa1\/84d\/68d\/aa184d68d45155402576665ad494ecc3.svg\" alt=\"$(i,j)$\" data-tex=\"inline\"><\/math> \u0431\u0443\u0434\u0435\u0442 \u043b\u0435\u0436\u0430\u0442\u044c \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e \u043b\u0435\u0441\u0442\u043d\u0438\u0446, \u0441\u043e\u0441\u0442\u043e\u044f\u0449\u0438\u0445 \u0438\u0437 <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/bf8\/3b5\/32c\/bf83b532cd867d34004f8eded8c5c79a.svg\" alt=\"$i$\" data-tex=\"inline\"><\/math> \u043a\u0443\u0431\u0438\u043a\u043e\u0432, \u0432\u044b\u0441\u043e\u0442\u0430 \u043a\u043e\u0442\u043e\u0440\u044b\u0445 \u043d\u0435 \u043f\u0440\u0435\u0432\u043e\u0441\u0445\u043e\u0434\u0438\u0442 <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/b82\/8e2\/475\/b828e2475a3a56280b895f35eb250ea2.svg\" alt=\"$j$\" data-tex=\"inline\"><\/math>. \u0415\u0441\u043b\u0438 \u043f\u043e\u043b\u0443\u0447\u0438\u0442\u0441\u044f, \u0442\u043e \u043e\u0442\u0432\u0435\u0442\u043e\u043c \u043a \u043d\u0430\u0448\u0435\u0439 \u0437\u0430\u0434\u0430\u0447\u0435 \u0431\u0443\u0434\u0435\u0442 \u0441\u0443\u043c\u043c\u0430 <\/p>\n<p><math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/903\/d3a\/199\/903d3a199455eba7416b35c998024bb8.svg\" alt=\"$\\sum\\limits_{j=1}^n d_{nj}.$\" data-tex=\"display\"><\/math><\/p>\n<p>  \u0418\u0442\u0430\u043a, \u0431\u0443\u0434\u0435\u043c \u0440\u0435\u0448\u0430\u0442\u044c \u0437\u0430\u0434\u0430\u0447\u0443 \u043f\u043e \u043d\u0430\u0445\u043e\u0436\u0434\u0435\u043d\u0438\u044e \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u0430 \u043b\u0435\u0441\u0442\u043d\u0438\u0446, \u0441\u043e\u0441\u0442\u0430\u0432\u043b\u0435\u043d\u043d\u044b\u0445 \u0438\u0437 <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/bf8\/3b5\/32c\/bf83b532cd867d34004f8eded8c5c79a.svg\" alt=\"$i$\" data-tex=\"inline\"><\/math> \u043a\u0443\u0431\u0438\u043a\u043e\u0432, \u043a\u043e\u0442\u043e\u0440\u044b\u0435 \u0438\u043c\u0435\u044e\u0442 \u0432\u044b\u0441\u043e\u0442\u0443 <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/b82\/8e2\/475\/b828e2475a3a56280b895f35eb250ea2.svg\" alt=\"$j$\" data-tex=\"inline\"><\/math>. \u041d\u0430 \u043a\u0430\u0440\u0442\u0438\u043d\u043a\u0435 \u043f\u043e\u043a\u0430\u0437\u0430\u043d\u044b \u043b\u0435\u0441\u0442\u043d\u0438\u0446\u044b, \u043a\u043e\u0442\u043e\u0440\u044b\u0435 \u043f\u043e\u043f\u0430\u0434\u0443\u0442 \u0432 <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/692\/28c\/8fb\/69228c8fbd0ec73bc5ed26eb409b07bb.svg\" alt=\"$d_{74}$\" data-tex=\"inline\"><\/math>:<br \/>  <img decoding=\"async\" src=\"https:\/\/habrastorage.org\/webt\/_h\/cy\/l9\/_hcyl9c5amyllphpuilsqzy0pxc.jpeg\"><br \/>  \u041f\u043e\u0441\u043a\u043e\u043b\u044c\u043a\u0443 \u043d\u0430\u043c \u0438\u0437\u0432\u0435\u0441\u0442\u043d\u044b \u0432\u0441\u0435 \u043b\u0435\u0441\u0442\u043d\u0438\u0446\u044b, \u043a\u043e\u0442\u043e\u0440\u044b\u0435 \u0441\u043e\u0441\u0442\u043e\u044f\u0442 \u0438\u0437 \u043c\u0435\u043d\u044c\u0448\u0435\u0433\u043e \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u0430 \u043a\u0443\u0431\u0438\u043a\u043e\u0432, \u0442\u043e \u00ab\u043e\u0442\u0449\u0435\u043f\u0438\u043c\u00bb \u043e\u0442 \u043b\u0435\u0441\u0442\u043d\u0438\u0446\u044b <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/aa1\/84d\/68d\/aa184d68d45155402576665ad494ecc3.svg\" alt=\"$(i,j)$\" data-tex=\"inline\"><\/math> \u043f\u0440\u0430\u0432\u044b\u0439 \u0441\u0442\u043e\u043b\u0431\u0438\u043a. \u0412 \u0440\u0435\u0437\u0443\u043b\u044c\u0442\u0430\u0442\u0435 \u043f\u043e\u043b\u0443\u0447\u0438\u0442\u0441\u044f \u043b\u0435\u0441\u0442\u043d\u0438\u0446\u0430 c <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/5f9\/c8b\/755\/5f9c8b755f3d9b4d1968f0e89fa630cb.svg\" alt=\"$i-j$\" data-tex=\"inline\"><\/math> \u043a\u0443\u0431\u0438\u043a\u0430\u043c\u0438. \u041f\u0440\u0438\u043c\u0435\u0440 \u0434\u043b\u044f <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/5e6\/bd4\/16c\/5e6bd416cba4332b8c2818869758eb51.svg\" alt=\"$i = 9, \\ j = 4$\" data-tex=\"inline\"><\/math>:<br \/>  <img decoding=\"async\" src=\"https:\/\/habrastorage.org\/webt\/al\/wk\/q9\/alwkq9vsxwenchkmlyyixnp_7qe.jpeg\"><br \/>  \u041d\u043e \u0434\u043b\u044f \u0442\u0430\u043a\u0438\u0445 \u043b\u0435\u0441\u0442\u043d\u0438\u0446 \u0440\u0435\u0437\u0443\u043b\u044c\u0442\u0430\u0442 \u0443\u0436\u0435 \u0438\u0437\u0432\u0435\u0441\u0442\u0435\u043d, \u043f\u043e\u044d\u0442\u043e\u043c\u0443 \u043f\u0435\u0440\u0435\u0431\u0435\u0440\u0435\u043c \u0432\u0441\u0435 \u0442\u0430\u043a\u0438\u0435 \u043b\u0435\u0441\u0442\u043d\u0438\u0446\u044b \u0446\u0438\u043a\u043b\u043e\u043c \u043f\u043e <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/16d\/a50\/7b2\/16da507b2fc389688ef0659939dcc647.svg\" alt=\"$k$\" data-tex=\"inline\"><\/math> \u0438 \u0441\u043b\u043e\u0436\u0438\u043c \u0432\u0441\u0435 \u0440\u0435\u0437\u0443\u043b\u044c\u0442\u0430\u0442\u044b. \u0422\u0430\u043a\u0438\u043c \u043e\u0431\u0440\u0430\u0437\u043e\u043c, <\/p>\n<p><math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/b75\/b84\/afc\/b75b84afca7adfaba8645ae506947956.svg\" alt=\"$d_{ij} = \\sum\\limits_{k=1}^{j-1} d_{i-jk}.$\" data-tex=\"display\"><\/math><\/p>\n<p>  \u0422\u0435\u043f\u0435\u0440\u044c \u0431\u0443\u0434\u0435\u043c \u043f\u0435\u0440\u0435\u0431\u0438\u0440\u0430\u0442\u044c \u0432\u044b\u0441\u043e\u0442\u044b \u043b\u0435\u0441\u0442\u043d\u0438\u0446: <\/p>\n<p><math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/75e\/88e\/6a3\/75e88e6a32b797902e15ec2039fb98be.svg\" alt=\"$d_{ij} = \\sum\\limits_{k=1}^{j-1} d_{i-jk}, \\ j = \\overline{1,i}.$\" data-tex=\"display\"><\/math><\/p>\n<p> \u041e\u043a\u043e\u043d\u0447\u0430\u0442\u0435\u043b\u044c\u043d\u043e, \u0438\u0437\u043c\u0435\u043d\u044f\u044f <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/bf8\/3b5\/32c\/bf83b532cd867d34004f8eded8c5c79a.svg\" alt=\"$i$\" data-tex=\"inline\"><\/math> \u043e\u0442 <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/3e4\/c77\/a6e\/3e4c77a6e7c579a778fa84a18b6f4be0.svg\" alt=\"$1$\" data-tex=\"inline\"><\/math> \u0434\u043e <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/08d\/9fa\/efb\/08d9faefbe272bdf8fbb80773542e343.svg\" alt=\"$n$\" data-tex=\"inline\"><\/math>, \u043f\u043e\u043b\u0443\u0447\u0438\u043c \u043e\u0442\u0432\u0435\u0442.<\/p>\n<p>  <b>\u0412\u0430\u0436\u043d\u043e<\/b>: \u0432 \u043f\u0440\u043e\u0446\u0435\u0441\u0441\u0435 \u043f\u043e\u0441\u0442\u0440\u043e\u0435\u043d\u0438\u044f \u043d\u0430\u0448\u0435\u0439 \u043c\u0430\u0442\u0440\u0438\u0446\u044b \u043d\u0435\u043e\u0431\u0445\u043e\u0434\u0438\u043c\u043e \u0443\u0447\u0438\u0442\u044b\u0432\u0430\u0442\u044c <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/ac5\/fa5\/1bd\/ac5fa51bd250a4b06d0eb64302e61a72.svg\" alt=\"$d_{ii} = 1$\" data-tex=\"inline\"><\/math>, \u0442\u0430\u043a \u043a\u0430\u043a \u0432 \u043f\u0440\u043e\u0442\u0438\u0432\u043d\u043e\u043c \u0441\u043b\u0443\u0447\u0430\u0435 \u0431\u0443\u0434\u0443\u0442 \u00ab\u0442\u0435\u0440\u044f\u0442\u044c\u0441\u044f\u00bb \u043d\u0435\u043a\u043e\u0442\u043e\u0440\u044b\u0435 \u0432\u0438\u0434\u044b \u043b\u0435\u0441\u0442\u043d\u0438\u0446 (\u043f\u0440\u0438 \u00ab\u043e\u0442\u0449\u0435\u043f\u043b\u0435\u043d\u0438\u0438\u00bb), \u043d\u043e \u0440\u0430\u0437\u0443\u043c\u0435\u0435\u0442\u0441\u044f, \u0447\u0442\u043e \u0442\u0430\u043a\u0430\u044f \u043b\u0435\u0441\u0442\u043d\u0438\u0446\u0430 \u043d\u0435 \u0443\u0434\u043e\u0432\u043b\u0435\u0442\u0432\u043e\u0440\u044f\u0435\u0442 \u0443\u0441\u043b\u043e\u0432\u0438\u044f\u043c \u0437\u0430\u0434\u0430\u0447\u0438, \u043f\u043e\u044d\u0442\u043e\u043c\u0443 \u0432 \u043e\u0442\u0432\u0435\u0442\u0435 \u0431\u0443\u0434\u0435\u0442 \u0447\u0438\u0441\u043b\u043e <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/bca\/a7b\/8c6\/bcaa7b8c63629dcb33f72bfd1de17664.svg\" alt=\"$d_{nn} - 1$\" data-tex=\"inline\"><\/math>.<\/p>\n<div class=\"spoiler\"><b class=\"spoiler_title\">\u041f\u0440\u0438\u043c\u0435\u0440 \u043a\u043e\u0434\u0430 \u043d\u0430 Java, \u0440\u0435\u0430\u043b\u0438\u0437\u0443\u044e\u0449\u0438\u0439 \u0434\u0430\u043d\u043d\u044b\u0439 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c:<\/b><\/p>\n<div class=\"spoiler_text\">  <\/p>\n<pre><code class=\"java\">dp = new long[n + 1][n+1]; d[1][1] = 1; d[2][1] = 0; d[2][2] = 1; for(int i = 3; i &lt; n + 1; i++) { \tfor(int j = 2; j &lt;i; j++) { \t\tlong cnt = 0; \t\tfor(int k = 1; k &lt; j; k++) { \t\t\tcnt += d[i - j][k]; \t\t} \t\td[i][j] = cnt; \t} \td[i][i] = 1; \/\/ \u0434\u043e\u0431\u0430\u0432\u043b\u044f\u0435\u043c \u0444\u0438\u043a\u0442\u0438\u0432\u043d\u0443\u044e \u043b\u0435\u0441\u0442\u043d\u0438\u0446\u0443 \t\t\t }  long answer = 0L; for(int i = 0; i &lt;= n; i++) { \tanswer += d[n][i]; } answer--; \/\/ \u0432\u0441\u043f\u043e\u043c\u0438\u043d\u0430\u0435\u043c \u043f\u0440\u043e \u0444\u0438\u043a\u0442\u0438\u0432\u043d\u0443\u044e \u043b\u0435\u0441\u0442\u043d\u0438\u0446\u0443 <\/code><\/pre>\n<p>  <\/div>\n<\/div>\n<p>  \u0421\u043b\u0435\u0434\u0443\u044e\u0449\u0430\u044f <a href=\"http:\/\/acm.timus.ru\/problem.aspx?space=1&amp;num=1537\">\u0437\u0430\u0434\u0430\u0447\u0430<\/a> \u0440\u0435\u0448\u0430\u0435\u0442\u0441\u044f \u0441 \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u043d\u0438\u0435\u043c \u043e\u0434\u043d\u043e\u043c\u0435\u0440\u043d\u043e\u0433\u043e \u043c\u0430\u0441\u0441\u0438\u0432\u0430. <\/p>\n<p>  \u0418\u0442\u0430\u043a, \u0447\u0442\u043e \u043c\u044b \u0438\u043c\u0435\u0435\u043c. \u041f\u0435\u0440\u0432\u044b\u0439 \u044d\u043d\u0442 \u0437\u043d\u0430\u0435\u0442 2 \u0441\u043b\u043e\u0432\u0430. \u041a\u0430\u0436\u0434\u044b\u0439 \u044d\u043d\u0442 \u043e\u0431\u0443\u0447\u0430\u0435\u0442 \u0432\u0441\u0435\u043c \u0441\u043b\u043e\u0432\u0430\u043c, \u043a\u043e\u0442\u043e\u0440\u044b\u0435 \u0437\u043d\u0430\u0435\u0442 \u0441\u0430\u043c, \u0434\u0432\u0443\u0445 \u044d\u043d\u0442\u043e\u0432: \u043c\u043e\u043b\u043e\u0434\u043e\u0433\u043e \u0438 \u0441\u0442\u0430\u0440\u043e\u0433\u043e. \u0412 \u0441\u0432\u043e\u044e \u043e\u0447\u0435\u0440\u0435\u0434\u044c, \u043c\u043e\u043b\u043e\u0434\u043e\u0433\u043e \u043e\u0431\u0443\u0447\u0438\u043b\u0438 \u0435\u0449\u0435 \u0441\u0442\u043e\u043b\u044c\u043a\u0438\u043c \u0436\u0435 \u0441\u043b\u043e\u0432\u0430\u043c, \u0441\u043a\u043e\u043b\u044c\u043a\u043e \u043e\u043d \u0443\u0436\u0435 \u0437\u043d\u0430\u0435\u0442, \u0430 \u0441\u0442\u0430\u0440\u043e\u0433\u043e \u043e\u0431\u0443\u0447\u0438\u043b\u0438 \u0442\u043e\u043b\u044c\u043a\u043e \u043e\u0434\u043d\u043e\u043c\u0443 \u0441\u043b\u043e\u0432\u0443. \u041d\u0435\u043e\u0431\u0445\u043e\u0434\u0438\u043c\u043e \u0443\u0437\u043d\u0430\u0442\u044c, \u0441\u043a\u043e\u043b\u044c\u043a\u043e \u044d\u043d\u0442\u043e\u0432 \u0437\u043d\u0430\u0435\u0442 \u0432 \u0442\u043e\u0447\u043d\u043e\u0441\u0442\u0438 <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/8b1\/9d8\/49a\/8b19d849a66473b36d68c78d06462129.svg\" alt=\"$K$\" data-tex=\"inline\"><\/math> \u0441\u043b\u043e\u0432 (\u043d\u0435\u043e\u0431\u0445\u043e\u0434\u0438\u043c\u043e \u0432\u044b\u0432\u0435\u0441\u0442\u0438 \u0447\u0438\u0441\u043b\u043e \u044d\u0442\u0438\u0445 \u044d\u043d\u0442\u043e\u0432 \u043f\u043e \u043c\u043e\u0434\u0443\u043b\u044e <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/c3d\/2f2\/c44\/c3d2f2c44fc42edea27de7f8f67b4829.svg\" alt=\"$P$\" data-tex=\"inline\"><\/math>).<\/p>\n<p>  \u0420\u0435\u0448\u0435\u043d\u0438\u0435 \u0434\u043e\u0432\u043e\u043b\u044c\u043d\u043e \u043f\u0440\u043e\u0441\u0442\u043e\u0435. \u0421\u043e\u0437\u0434\u0430\u0434\u0438\u043c \u043c\u0430\u0441\u0441\u0438\u0432 <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/35e\/a85\/36b\/35ea8536b3e6152e60442ccecbc46812.svg\" alt=\"$d$\" data-tex=\"inline\"><\/math>, \u0432 \u043a\u043e\u0442\u043e\u0440\u043e\u043c \u043d\u0430 <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/bf8\/3b5\/32c\/bf83b532cd867d34004f8eded8c5c79a.svg\" alt=\"$i$\" data-tex=\"inline\"><\/math>-\u043e\u043c \u043c\u0435\u0441\u0442\u0435 \u0431\u0443\u0434\u0435\u043c \u0445\u0440\u0430\u043d\u0438\u0442\u044c \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e \u044d\u043d\u0442\u043e\u0432 (\u043f\u043e \u043c\u043e\u0434\u0443\u043b\u044e <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/c3d\/2f2\/c44\/c3d2f2c44fc42edea27de7f8f67b4829.svg\" alt=\"$P$\" data-tex=\"inline\"><\/math>), \u043a\u043e\u0442\u043e\u0440\u044b\u0435 \u0437\u043d\u0430\u044e\u0442 <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/bf8\/3b5\/32c\/bf83b532cd867d34004f8eded8c5c79a.svg\" alt=\"$i$\" data-tex=\"inline\"><\/math> \u0441\u043b\u043e\u0432. \u0412\u0441\u0435 \u043d\u0430\u0447\u0438\u043d\u0430\u0435\u0442\u0441\u044f \u0441 \u043f\u0435\u0440\u0432\u043e\u0433\u043e \u044d\u043d\u0442\u0430, \u043a\u043e\u0442\u043e\u0440\u044b\u0439 \u0437\u043d\u0430\u0435\u0442 \u0434\u0432\u0430 \u0441\u043b\u043e\u0432\u0430, \u043f\u043e\u044d\u0442\u043e\u043c\u0443 <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/5ed\/8e6\/677\/5ed8e6677c27b3dfcdd2839306e32865.svg\" alt=\"$d_2 = 1$\" data-tex=\"inline\"><\/math>. \u0410 \u0434\u0430\u043b\u044c\u0448\u0435 \u0432\u0441\u0435 \u043f\u0440\u043e\u0441\u0442\u043e: <\/p>\n<ul>\n<li> \u0412\u0441\u0435 \u044d\u043d\u0442\u044b, \u043a\u043e\u0442\u043e\u0440\u044b\u0435 \u0437\u043d\u0430\u044e\u0442 \u043d\u0435\u0447\u0435\u0442\u043d\u043e\u0435 \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e \u0441\u043b\u043e\u0432, \u044f\u0432\u043b\u044f\u044e\u0442\u0441\u044f \u0441\u0442\u0430\u0440\u044b\u043c\u0438 \u0438 \u043c\u043e\u0433\u043b\u0438 \u043d\u0430\u0443\u0447\u0438\u0442\u044c\u0441\u044f \u0442\u043e\u043b\u044c\u043a\u043e \u043e\u0442 \u043f\u0440\u0435\u0434\u044b\u0434\u0443\u0449\u0438\u0445. \u041f\u043e\u044d\u0442\u043e\u043c\u0443 \u0434\u043b\u044f \u043d\u0435\u0447\u0435\u0442\u043d\u044b\u0445 <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/df1\/dd5\/885\/df1dd58850fc7baba818cfc4a6cfe082.svg\" alt=\"$i: \\ d_i = d_{i-1};$\" data-tex=\"inline\"><\/math> <\/li>\n<li> \u0427\u0442\u043e \u043a\u0430\u0441\u0430\u0435\u0442\u0441\u044f \u044d\u043d\u0442\u043e\u0432, \u043a\u043e\u0442\u043e\u0440\u044b\u0435 \u0437\u043d\u0430\u044e\u0442 \u0447\u0435\u0442\u043d\u043e\u0435 \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e \u0441\u043b\u043e\u0432 \u2014 \u0442\u0430\u043a \u044d\u0442\u043e \u0432\u0441\u0435 \u0442\u0435, \u043a\u0442\u043e \u043f\u043e\u043b\u0443\u0447\u0438\u043b \u0441\u0442\u043e\u043b\u044c\u043a\u043e \u0436\u0435 \u0441\u043b\u043e\u0432 \u043e\u0442 \u044d\u043b\u044c\u0444\u043e\u0432 (\u043c\u043e\u043b\u043e\u0434\u044b\u0435) <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/ae4\/dc5\/c6f\/ae4dc5c6fd4ec28ba4b81a2ec09d88b9.svg\" alt=\"$+$\" data-tex=\"inline\"><\/math> \u0442\u0435, \u043a\u0442\u043e \u043d\u0430\u0443\u0447\u0438\u043b\u0441\u044f \u043e\u0442 \u043f\u0440\u0435\u0434\u044b\u0434\u0443\u0449\u0438\u0445 (\u0441\u0442\u0430\u0440\u044b\u0435); \u0442\u043e \u0435\u0441\u0442\u044c \u0434\u043b\u044f \u0447\u0435\u0442\u043d\u043e\u0433\u043e <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/bf8\/3b5\/32c\/bf83b532cd867d34004f8eded8c5c79a.svg\" alt=\"$i$\" data-tex=\"inline\"><\/math> \u0438\u043c\u0435\u0435\u043c <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/94f\/69d\/c64\/94f69dc642c9eba0c49b722b6df765ef.svg\" alt=\"$d_i = d_{{i\\backslash 2}} + d_{i-1}$\" data-tex=\"inline\"><\/math>. <\/li>\n<\/ul>\n<p>  \u041e\u0441\u0442\u0430\u043b\u043e\u0441\u044c \u0440\u0430\u0437\u043e\u0431\u0440\u0430\u0442\u044c\u0441\u044f \u0441 \u0432\u044b\u0447\u0438\u0441\u043b\u0435\u043d\u0438\u0435\u043c \u043f\u043e \u043c\u043e\u0434\u0443\u043b\u044e. \u0414\u043b\u044f \u0442\u043e\u0433\u043e, \u0447\u0442\u043e\u0431\u044b \u043d\u0435 \u0445\u0440\u0430\u043d\u0438\u0442\u044c \u043e\u0433\u0440\u043e\u043c\u043d\u044b\u0435 \u0447\u0438\u0441\u043b\u0430, \u0431\u0443\u0434\u0435\u043c \u0441\u0440\u0430\u0437\u0443 \u0437\u0430\u043f\u043e\u043c\u0438\u043d\u0430\u0442\u044c \u0432\u0441\u0435 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u044f \u043f\u043e \u043c\u043e\u0434\u0443\u043b\u044e. <\/p>\n<div class=\"spoiler\"><b class=\"spoiler_title\">\u041f\u0440\u0438\u043c\u0435\u0440 \u043a\u043e\u0434\u0430 \u043d\u0430 Java, \u0440\u0435\u0430\u043b\u0438\u0437\u0443\u044e\u0449\u0438\u0439 \u0434\u0430\u043d\u043d\u044b\u0439 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c:<\/b><\/p>\n<div class=\"spoiler_text\">\n<pre><code class=\"java\">int[] d = new int[K + 1]; if(K &gt;= 2) d[2] = 1; if(P != 1) { \tfor(int i = 3; i &lt;= K; i++) { \t\tif(i % 2 != 0) { \t\t\td[i] = d[i - 1]; \t\t} \t\telse { \t\t\td[i] = ((d[i\/2] % P) + d[i - 1] % P) % P; \t\t} \t} } else d[K] = 0; <\/code><\/pre>\n<p>  <\/div>\n<\/div>\n<p>  \u0418\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u0435\u043c\u044b\u0435 \u0440\u0435\u0441\u0443\u0440\u0441\u044b: <\/p>\n<ol>\n<li><a href=\"http:\/\/acm.timus.ru\/\">Timus Online Judge;<\/a><\/li>\n<li><a href=\"https:\/\/ru.wikipedia.org\/wiki\/%D0%94%D0%B8%D0%BD%D0%B0%D0%BC%D0%B8%D1%87%D0%B5%D1%81%D0%BA%D0%BE%D0%B5_%D0%BF%D1%80%D0%BE%D0%B3%D1%80%D0%B0%D0%BC%D0%BC%D0%B8%D1%80%D0%BE%D0%B2%D0%B0%D0%BD%D0%B8%D0%B5\">\u041d\u0435\u043c\u043d\u043e\u0433\u043e<\/a> \u043e \u0434\u0438\u043d\u0430\u043c\u0438\u0447\u0435\u0441\u043a\u043e\u043c \u043f\u0440\u043e\u0433\u0440\u0430\u043c\u043c\u0438\u0440\u043e\u0432\u0430\u043d\u0438\u0438;<\/li>\n<li><a href=\"https:\/\/ru.wikipedia.org\/wiki\/%D0%A1%D1%80%D0%B0%D0%B2%D0%BD%D0%B5%D0%BD%D0%B8%D0%B5_%D0%BF%D0%BE_%D0%BC%D0%BE%D0%B4%D1%83%D0%BB%D1%8E#%D0%A1%D0%B2%D0%BE%D0%B9%D1%81%D1%82%D0%B2%D0%B0_%D1%81%D1%80%D0%B0%D0%B2%D0%BD%D0%B8%D0%BC%D0%BE%D1%81%D1%82%D0%B8_%D0%BF%D0%BE_%D0%BC%D0%BE%D0%B4%D1%83%D0%BB%D1%8E\">\u0421\u0432\u043e\u0439\u0441\u0442\u0432\u0430<\/a> \u0441\u0440\u0430\u0432\u043d\u0435\u043d\u0438\u044f \u043f\u043e \u043c\u043e\u0434\u0443\u043b\u044e.<\/li>\n<\/ol>\n<\/div>\n<p>        <script class=\"js-mediator-script\">!function(e){function t(t,n){if(!(n in e)){for(var r,a=e.document,i=a.scripts,o=i.length;o--;)if(-1!==i[o].src.indexOf(t)){r=i[o];break}if(!r){r=a.createElement(\"script\"),r.type=\"text\/javascript\",r.async=!0,r.defer=!0,r.src=t,r.charset=\"UTF-8\";var d=function(){var e=a.getElementsByTagName(\"script\")[0];e.parentNode.insertBefore(r,e)};\"[object Opera]\"==e.opera?a.addEventListener?a.addEventListener(\"DOMContentLoaded\",d,!1):e.attachEvent(\"onload\",d):d()}}}t(\"\/\/mediator.mail.ru\/script\/2820404\/\",\"_mediator\")}(window);<\/script>     <br \/> \u0441\u0441\u044b\u043b\u043a\u0430 \u043d\u0430 \u043e\u0440\u0438\u0433\u0438\u043d\u0430\u043b \u0441\u0442\u0430\u0442\u044c\u0438 <a href=\"https:\/\/habr.com\/post\/418867\/\"> https:\/\/habr.com\/post\/418867\/<\/a><\/p>\n","protected":false},"excerpt":{"rendered":"\n<div data-io-article-url=\"https:\/\/habr.com\/post\/418867\/\" class=\"post__text post__text-html js-mediator-article\">\u041f\u0440\u0438\u0432\u0435\u0442! <\/p>\n<p>  \u041d\u0435\u0434\u0430\u0432\u043d\u043e \u0440\u0435\u0448\u0430\u043b \u0437\u0430\u0434\u0430\u0447\u0438 \u0441 \u0430\u0440\u0445\u0438\u0432\u0430 <a href=\"http:\/\/acm.timus.ru\/\">Timus Online Judge<\/a> \u0438 \u043d\u0430\u0442\u043a\u043d\u0443\u043b\u0441\u044f \u043d\u0430 \u0440\u0430\u0437\u0434\u0435\u043b \u043f\u043e\u0434 \u043d\u0430\u0437\u0432\u0430\u043d\u0438\u0435\u043c <i>\u0437\u0430\u0434\u0430\u0447\u0438 \u0434\u0438\u043d\u0430\u043c\u0438\u0447\u0435\u0441\u043a\u043e\u0433\u043e \u043f\u0440\u043e\u0433\u0440\u0430\u043c\u043c\u0438\u0440\u043e\u0432\u0430\u043d\u0438\u044f<\/i>. \u0417\u0430\u0434\u0430\u0447\u0438 \u0442\u0430\u043a\u043e\u0433\u043e \u0442\u0438\u043f\u0430 \u0432\u044b\u0437\u044b\u0432\u0430\u044e\u0442 \u0443 \u043c\u0435\u043d\u044f \u043e\u0441\u043e\u0431\u044b\u0439 \u0438\u043d\u0442\u0435\u0440\u0435\u0441, \u043f\u043e\u0442\u043e\u043c\u0443 \u0447\u0442\u043e \u0437\u0430\u0447\u0430\u0441\u0442\u0443\u044e \u0442\u0430\u043a\u043e\u0439 \u043f\u043e\u0434\u0445\u043e\u0434 \u043e\u0431\u0435\u0441\u043f\u0435\u0447\u0438\u0432\u0430\u0435\u0442 \u0431\u044b\u0441\u0442\u0440\u043e\u0442\u0443 \u0438 \u044d\u043b\u0435\u0433\u0430\u043d\u0442\u043d\u043e\u0441\u0442\u044c \u0440\u0435\u0448\u0435\u043d\u0438\u044f. \u0427\u0442\u043e \u0436\u0435 \u0442\u0430\u043a\u043e\u0435 \u2014 \u0434\u0438\u043d\u0430\u043c\u0438\u0447\u0435\u0441\u043a\u043e\u0435 \u043f\u0440\u043e\u0433\u0440\u0430\u043c\u043c\u0438\u0440\u043e\u0432\u0430\u043d\u0438\u0435? <\/p>\n<p>  \u0414\u0438\u043d\u0430\u043c\u0438\u0447\u0435\u0441\u043a\u043e\u0435 \u043f\u0440\u043e\u0433\u0440\u0430\u043c\u043c\u0438\u0440\u043e\u0432\u0430\u043d\u0438\u0435 \u2014 \u044d\u0442\u043e \u043f\u043e\u0434\u0445\u043e\u0434 \u043a \u0440\u0435\u0448\u0435\u043d\u0438\u044e \u0437\u0430\u0434\u0430\u0447, \u043f\u0440\u0438 \u043a\u043e\u0442\u043e\u0440\u043e\u043c \u043f\u0440\u043e\u0438\u0441\u0445\u043e\u0434\u0438\u0442 \u0440\u0430\u0437\u0431\u0438\u0435\u043d\u0438\u0435 \u043d\u0430 \u043f\u043e\u0434\u0437\u0430\u0434\u0430\u0447\u0438, \u043a\u043e\u0442\u043e\u0440\u044b\u0435 \u00ab\u043f\u0440\u043e\u0449\u0435\u00bb \u0432 \u0441\u0440\u0430\u0432\u043d\u0435\u043d\u0438\u0438 \u0441 \u0438\u0441\u0445\u043e\u0434\u043d\u043e\u0439. \u0421\u043b\u043e\u0432\u043e \u00ab\u0434\u0438\u043d\u0430\u043c\u0438\u0447\u0435\u0441\u043a\u0438\u0439\u00bb \u0431\u043b\u0438\u0437\u043a\u043e \u043f\u043e \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u044e \u043a \u00ab\u0438\u043d\u0434\u0443\u043a\u0442\u0438\u0432\u043d\u044b\u0439\u00bb: \u043f\u0440\u0435\u0434\u043f\u043e\u043b\u0430\u0433\u0430\u0435\u0442\u0441\u044f, \u0447\u0442\u043e \u0438\u0437\u0432\u0435\u0441\u0442\u0435\u043d \u043e\u0442\u0432\u0435\u0442 \u0434\u043b\u044f \u043a\u0430\u043a\u043e\u0433\u043e-\u0442\u043e \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u044f <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/16d\/a50\/7b2\/16da507b2fc389688ef0659939dcc647.svg\" alt=\"$k$\" data-tex=\"inline\"><\/math>, \u0438 \u0445\u043e\u0447\u0435\u0442\u0441\u044f \u043d\u0430\u0439\u0442\u0438 \u043e\u0442\u0432\u0435\u0442 \u0434\u043b\u044f <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/44c\/562\/936\/44c562936a615ceeecfca5c080e31de8.svg\" alt=\"$k+1$\" data-tex=\"inline\"><\/math>. \u0412 \u043c\u0430\u0442\u0435\u043c\u0430\u0442\u0438\u043a\u0435 \u044d\u0442\u043e \u043d\u0430\u0437\u044b\u0432\u0430\u0435\u0442\u0441\u044f \u0438\u043d\u0434\u0443\u043a\u0442\u0438\u0432\u043d\u044b\u043c \u043f\u0435\u0440\u0435\u0445\u043e\u0434\u043e\u043c, \u0438 \u0441\u043e\u0441\u0442\u0430\u0432\u043b\u044f\u0435\u0442 \u043e\u0441\u043d\u043e\u0432\u043d\u0443\u044e \u0438\u0434\u0435\u044e \u0434\u0438\u043d\u0430\u043c\u0438\u0447\u0435\u0441\u043a\u043e\u0433\u043e \u043f\u0440\u043e\u0433\u0440\u0430\u043c\u043c\u0438\u0440\u043e\u0432\u0430\u043d\u0438\u044f. <\/p>\n<h2>\u041f\u0440\u043e\u0441\u0442\u044b\u0435 \u043f\u0440\u0438\u043c\u0435\u0440\u044b<\/h2>\n<p>  \u041d\u0430\u0438\u0431\u043e\u043b\u0435\u0435 \u044f\u0440\u043a\u043e\u0439 \u0438 \u043f\u043e\u043a\u0430\u0437\u0430\u0442\u0435\u043b\u044c\u043d\u043e\u0439 \u0437\u0430\u0434\u0430\u0447\u0435\u0439 \u044f\u0432\u043b\u044f\u0435\u0442\u0441\u044f \u0437\u0430\u0434\u0430\u0447\u0430 \u0432\u044b\u0447\u0438\u0441\u043b\u0435\u043d\u0438\u044f <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/08d\/9fa\/efb\/08d9faefbe272bdf8fbb80773542e343.svg\" alt=\"$n$\" data-tex=\"inline\"><\/math>-\u043e\u0433\u043e \u0447\u0438\u0441\u043b\u0430 \u043f\u043e\u0441\u043b\u0435\u0434\u043e\u0432\u0430\u0442\u0435\u043b\u044c\u043d\u043e\u0441\u0442\u0438 \u0424\u0438\u0431\u043e\u043d\u0430\u0447\u0447\u0438. <\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[],"tags":[],"class_list":["post-287814","post","type-post","status-publish","format-standard","hentry"],"_links":{"self":[{"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=\/wp\/v2\/posts\/287814","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=287814"}],"version-history":[{"count":0,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=\/wp\/v2\/posts\/287814\/revisions"}],"wp:attachment":[{"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=287814"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=287814"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=287814"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}