{"id":287598,"date":"2018-08-16T14:12:51","date_gmt":"2018-08-16T10:12:51","guid":{"rendered":"http:\/\/savepearlharbor.com\/?p=287598"},"modified":"-0001-11-30T00:00:00","modified_gmt":"-0001-11-29T21:00:00","slug":"","status":"publish","type":"post","link":"https:\/\/savepearlharbor.com\/?p=287598","title":{"rendered":"\u0420\u0435\u0448\u0435\u043d\u0438\u0435 \u0446\u0432\u0435\u0442\u043d\u044b\u0445 \u044f\u043f\u043e\u043d\u0441\u043a\u0438\u0445 \u043a\u0440\u043e\u0441\u0441\u0432\u043e\u0440\u0434\u043e\u0432 \u0441\u043e \u0441\u043a\u043e\u0440\u043e\u0441\u0442\u044c\u044e \u0441\u0432\u0435\u0442\u0430"},"content":{"rendered":"\n<div data-io-article-url=\"https:\/\/habr.com\/post\/418069\/\" class=\"post__text post__text-html js-mediator-article\">\n<p>\u042f\u043f\u043e\u043d\u0441\u043a\u0438\u0435 \u043a\u0440\u043e\u0441\u0441\u0432\u043e\u0440\u0434\u044b (\u0442\u0430\u043a\u0436\u0435 \u043d\u043e\u043d\u043e\u0433\u0440\u0430\u043c\u043c\u044b) \u2014 \u043b\u043e\u0433\u0438\u0447\u0435\u0441\u043a\u0438\u0435 \u0433\u043e\u043b\u043e\u0432\u043e\u043b\u043e\u043c\u043a\u0438, \u0432 \u043a\u043e\u0442\u043e\u0440\u044b\u0445 \u0437\u0430\u0448\u0438\u0444\u0440\u043e\u0432\u0430\u043d\u043e \u043f\u0438\u043a\u0441\u0435\u043b\u044c\u043d\u043e\u0435 \u0438\u0437\u043e\u0431\u0440\u0430\u0436\u0435\u043d\u0438\u0435. \u0420\u0430\u0437\u0433\u0430\u0434\u044b\u0432\u0430\u0442\u044c \u043a\u0440\u043e\u0441\u0441\u0432\u043e\u0440\u0434 \u043d\u0443\u0436\u043d\u043e \u0441 \u043f\u043e\u043c\u043e\u0449\u044c\u044e \u0447\u0438\u0441\u0435\u043b, \u0440\u0430\u0441\u043f\u043e\u043b\u043e\u0436\u0435\u043d\u043d\u044b\u0445 \u0441\u043b\u0435\u0432\u0430 \u043e\u0442 \u0441\u0442\u0440\u043e\u043a \u0438 \u0441\u0432\u0435\u0440\u0445\u0443 \u043e\u0442 \u0441\u0442\u043e\u043b\u0431\u0446\u043e\u0432.<\/p>\n<p>  <\/p>\n<p>\u0420\u0430\u0437\u043c\u0435\u0440 \u043a\u0440\u043e\u0441\u0441\u0432\u043e\u0440\u0434\u043e\u0432 \u043c\u043e\u0436\u0435\u0442 \u0434\u043e\u0445\u043e\u0434\u0438\u0442\u044c \u0434\u043e 150&#215;150. \u0418\u0433\u0440\u043e\u043a \u0441 \u043f\u043e\u043c\u043e\u0449\u044c\u044e \u0441\u043f\u0435\u0446\u0438\u0430\u043b\u044c\u043d\u044b\u0445 \u043b\u043e\u0433\u0438\u0447\u0435\u0441\u043a\u0438\u0445 \u043f\u0440\u0438\u0435\u043c\u043e\u0432 \u0432\u044b\u0447\u0438\u0441\u043b\u044f\u0435\u0442 \u0446\u0432\u0435\u0442 \u043a\u0430\u0436\u0434\u043e\u0439 \u043a\u043b\u0435\u0442\u043a\u0438. \u0420\u0435\u0448\u0435\u043d\u0438\u0435 \u043c\u043e\u0436\u0435\u0442 \u0437\u0430\u043d\u044f\u0442\u044c \u043a\u0430\u043a \u043f\u0430\u0440\u0443 \u043c\u0438\u043d\u0443\u0442 \u043d\u0430 \u043a\u0440\u043e\u0441\u0441\u0432\u043e\u0440\u0434\u0430\u0445 \u0434\u043b\u044f \u043d\u0430\u0447\u0438\u043d\u0430\u044e\u0449\u0438\u0445, \u0442\u0430\u043a \u0438 \u0434\u0435\u0441\u044f\u0442\u043a\u0438 \u0447\u0430\u0441\u043e\u0432 \u043d\u0430 \u0441\u043b\u043e\u0436\u043d\u044b\u0445 \u0433\u043e\u043b\u043e\u0432\u043e\u043b\u043e\u043c\u043a\u0430\u0445.<\/p>\n<p>  <\/p>\n<p>\u0425\u043e\u0440\u043e\u0448\u0438\u0439 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u043c\u043e\u0436\u0435\u0442 \u0440\u0435\u0448\u0438\u0442\u044c \u0437\u0430\u0434\u0430\u0447\u0443 \u043d\u0430\u043c\u043d\u043e\u0433\u043e \u0431\u044b\u0441\u0442\u0440\u0435\u0435. \u0412 \u0442\u0435\u043a\u0441\u0442\u0435 \u043e\u043f\u0438\u0441\u0430\u043d\u043e, \u043a\u0430\u043a \u0441 \u043f\u043e\u043c\u043e\u0449\u044c\u044e \u043d\u0430\u0438\u0431\u043e\u043b\u0435\u0435 \u043f\u043e\u0434\u0445\u043e\u0434\u044f\u0449\u0438\u0445 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u043e\u0432 (\u043a\u043e\u0442\u043e\u0440\u044b\u0435 \u0432\u043e\u043e\u0431\u0449\u0435 \u043f\u0440\u0438\u0432\u043e\u0434\u044f\u0442 \u043a \u0440\u0435\u0448\u0435\u043d\u0438\u044e), \u0430 \u0442\u0430\u043a\u0436\u0435 \u0438\u0445 \u043e\u043f\u0442\u0438\u043c\u0438\u0437\u0430\u0446\u0438\u0439 \u0438 \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u043d\u0438\u044f \u043e\u0441\u043e\u0431\u0435\u043d\u043d\u043e\u0441\u0442\u0435\u0439 C++ (\u043a\u043e\u0442\u043e\u0440\u044b\u0435 \u0443\u043c\u0435\u043d\u044c\u0448\u0430\u044e\u0442 \u0432\u0440\u0435\u043c\u044f \u0440\u0430\u0431\u043e\u0442\u044b \u0432 \u043d\u0435\u0441\u043a\u043e\u043b\u044c\u043a\u043e \u0434\u0435\u0441\u044f\u0442\u043a\u043e\u0432 \u0440\u0430\u0437) \u043d\u0430\u043f\u0438\u0441\u0430\u0442\u044c \u0440\u0435\u0448\u0435\u043d\u0438\u0435, \u0440\u0430\u0431\u043e\u0442\u0430\u044e\u0449\u0435\u0435 \u043f\u043e\u0447\u0442\u0438 \u043c\u0433\u043d\u043e\u0432\u0435\u043d\u043d\u043e.<\/p>\n<p>  <\/p>\n<div style=\"text-align:center;\"><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/webt\/w1\/tw\/-c\/w1tw-caq1d9vswcrqfapdufcbfk.gif\"><\/div>\n<p><a name=\"habracut\"><\/a>  <\/p>\n<p><em>\u0412 \u043c\u043e\u0431\u0438\u043b\u044c\u043d\u043e\u0439 \u0432\u0435\u0440\u0441\u0438\u0438 \u0425\u0430\u0431\u0440\u0430 \u0444\u043e\u0440\u043c\u0443\u043b\u044b \u0432 \u0442\u0435\u043a\u0441\u0442\u0435 \u043c\u043e\u0433\u0443\u0442 \u043d\u0435 \u043f\u043e\u043a\u0430\u0437\u044b\u0432\u0430\u0442\u044c\u0441\u044f (\u043d\u0435 \u0432\u043e \u0432\u0441\u0435\u0445 \u043c\u043e\u0431\u0438\u043b\u044c\u043d\u044b\u0445 \u0431\u0440\u0430\u0443\u0437\u0435\u0440\u0430\u0445) \u2014 \u043f\u043e\u043b\u044c\u0437\u0443\u0439\u0442\u0435\u0441\u044c \u043f\u043e\u043b\u043d\u043e\u0439 \u0432\u0435\u0440\u0441\u0438\u0435\u0439 \u0438\u043b\u0438 \u0434\u0440\u0443\u0433\u0438\u043c \u043c\u043e\u0431\u0438\u043b\u044c\u043d\u044b\u043c \u0431\u0440\u0430\u0443\u0437\u0435\u0440\u043e\u043c, \u0435\u0441\u043b\u0438 \u0437\u0430\u043c\u0435\u0442\u0438\u043b\u0438 \u043f\u0440\u043e\u0431\u043b\u0435\u043c\u044b \u0441 \u0444\u043e\u0440\u043c\u0443\u043b\u0430\u043c\u0438<\/em><\/p>\n<p>  <\/p>\n<h2 id=\"pravila-igry\">\u041f\u0440\u0430\u0432\u0438\u043b\u0430 \u0438\u0433\u0440\u044b<\/h2>\n<p>  <\/p>\n<p>\u0418\u0437\u043d\u0430\u0447\u0430\u043b\u044c\u043d\u043e \u0445\u043e\u043b\u0441\u0442 \u043a\u0440\u043e\u0441\u0441\u0432\u043e\u0440\u0434\u0430 \u0431\u0435\u043b\u044b\u0439. \u0414\u043b\u044f \u0432\u0430\u043d\u0438\u043b\u044c\u043d\u044b\u0445 \u0447\u0435\u0440\u043d\u043e-\u0431\u0435\u043b\u044b\u0445 \u043a\u0440\u043e\u0441\u0441\u0432\u043e\u0440\u0434\u043e\u0432 \u043d\u0443\u0436\u043d\u043e \u0432\u043e\u0441\u0441\u0442\u0430\u043d\u043e\u0432\u0438\u0442\u044c \u043c\u0435\u0441\u0442\u043e\u043f\u043e\u043b\u043e\u0436\u0435\u043d\u0438\u044f \u0447\u0435\u0440\u043d\u044b\u0445 \u043a\u043b\u0435\u0442\u043e\u043a.<\/p>\n<p>  <\/p>\n<p>\u0412 \u0447\u0435\u0440\u043d\u043e-\u0431\u0435\u043b\u044b\u0445 \u043a\u0440\u043e\u0441\u0441\u0432\u043e\u0440\u0434\u0430\u0445 \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e \u0447\u0438\u0441\u0435\u043b \u0434\u043b\u044f \u043a\u0430\u0436\u0434\u043e\u0439 \u0441\u0442\u0440\u043e\u043a\u0438 (\u0441\u043b\u0435\u0432\u0430 \u043e\u0442 \u0445\u043e\u043b\u0441\u0442\u0430) \u0438\u043b\u0438 \u0434\u043b\u044f \u043a\u0430\u0436\u0434\u043e\u0433\u043e \u0441\u0442\u043e\u043b\u0431\u0446\u0430 (\u0441\u0432\u0435\u0440\u0445\u0443 \u043e\u0442 \u0445\u043e\u043b\u0441\u0442\u0430) \u043f\u043e\u043a\u0430\u0437\u044b\u0432\u0430\u0435\u0442, \u0441\u043a\u043e\u043b\u044c\u043a\u043e \u0433\u0440\u0443\u043f\u043f \u0447\u0435\u0440\u043d\u044b\u0445 \u043a\u043b\u0435\u0442\u043e\u043a \u043d\u0430\u0445\u043e\u0434\u044f\u0442\u0441\u044f \u0432 \u0441\u043e\u043e\u0442\u0432\u0435\u0442\u0441\u0442\u0432\u0443\u044e\u0449\u0438\u0445 \u0441\u0442\u0440\u043e\u043a\u0435 \u0438\u043b\u0438 \u0441\u0442\u043e\u043b\u0431\u0446\u0435, \u0430 \u0441\u0430\u043c\u0438 \u0447\u0438\u0441\u043b\u0430 \u2014 \u0441\u043a\u043e\u043b\u044c\u043a\u043e \u0441\u043b\u0438\u0442\u043d\u044b\u0445 \u043a\u043b\u0435\u0442\u043e\u043a \u0441\u043e\u0434\u0435\u0440\u0436\u0438\u0442 \u043a\u0430\u0436\u0434\u0430\u044f \u0438\u0437 \u044d\u0442\u0438\u0445 \u0433\u0440\u0443\u043f\u043f. \u041d\u0430\u0431\u043e\u0440 \u0447\u0438\u0441\u0435\u043b <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/68a\/34b\/e82\/68a34be82f4f2b68434da05c62e69266.svg\" alt=\"$[3, 2, 5]$\" data-tex=\"inline\"><\/math> \u0437\u043d\u0430\u0447\u0438\u0442, \u0447\u0442\u043e \u0432 \u043e\u043f\u0440\u0435\u0434\u0435\u043b\u0435\u043d\u043d\u043e\u043c \u0440\u044f\u0434\u0443 \u0435\u0441\u0442\u044c \u0442\u0440\u0438 \u043f\u043e\u0441\u043b\u0435\u0434\u043e\u0432\u0430\u0442\u0435\u043b\u044c\u043d\u044b\u0435 \u0433\u0440\u0443\u043f\u043f\u044b \u0438\u0437 <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/3e3\/28e\/c65\/3e328ec6538d48db0bbd8e0859e6d10a.svg\" alt=\"$3$\" data-tex=\"inline\"><\/math>, <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/dfd\/8a0\/d2f\/dfd8a0d2fe6ea30b4cde7f570eca349b.svg\" alt=\"$2$\" data-tex=\"inline\"><\/math> \u0438 <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/480\/820\/0cb\/4808200cb3668866f25a2e4437a6b74e.svg\" alt=\"$5$\" data-tex=\"inline\"><\/math> \u0447\u0435\u0440\u043d\u044b\u0445 \u043a\u043b\u0435\u0442\u043e\u043a \u043f\u043e\u0434\u0440\u044f\u0434. \u0413\u0440\u0443\u043f\u043f\u044b \u043c\u043e\u0433\u0443\u0442 \u0431\u044b\u0442\u044c \u0440\u0430\u0441\u043f\u043e\u043b\u043e\u0436\u0435\u043d\u044b \u0432 \u0440\u044f\u0434\u0443 \u043a\u0430\u043a \u043f\u043e\u043f\u0430\u043b\u043e, \u043d\u0435 \u043d\u0430\u0440\u0443\u0448\u0430\u044f \u043e\u0442\u043d\u043e\u0441\u0438\u0442\u0435\u043b\u044c\u043d\u044b\u0439 \u043f\u043e\u0440\u044f\u0434\u043e\u043a (\u0446\u0438\u0444\u0440\u044b \u0437\u0430\u0434\u0430\u044e\u0442 \u0438\u0445 \u0434\u043b\u0438\u043d\u0443, \u0430 \u043f\u043e\u0437\u0438\u0446\u0438\u044e \u043d\u0430\u0434\u043e \u0443\u0433\u0430\u0434\u0430\u0442\u044c), \u043d\u043e \u043e\u043d\u0438 \u043e\u0431\u044f\u0437\u0430\u0442\u0435\u043b\u044c\u043d\u043e \u0434\u043e\u043b\u0436\u043d\u044b \u0440\u0430\u0437\u0434\u0435\u043b\u044f\u0442\u044c\u0441\u044f \u0445\u043e\u0442\u044f \u0431\u044b \u043e\u0434\u043d\u043e\u0439 \u0431\u0435\u043b\u043e\u0439 \u043a\u043b\u0435\u0442\u043a\u043e\u0439.<\/p>\n<p>  <\/p>\n<div style=\"text-align:center;\"><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/webt\/bl\/w9\/zt\/blw9ztswh2gvpy0lfqr76ei_xcq.png\"><\/div>\n<p>  <\/p>\n<p><em>\u041a\u043e\u0440\u0440\u0435\u043a\u0442\u043d\u044b\u0439 \u043f\u0440\u0438\u043c\u0435\u0440<\/em><\/p>\n<p>  <\/p>\n<p>\u0412 \u0446\u0432\u0435\u0442\u043d\u044b\u0445 \u043a\u0440\u043e\u0441\u0441\u0432\u043e\u0440\u0434\u0430\u0445 \u0443 \u043a\u0430\u0436\u0434\u043e\u0439 \u0433\u0440\u0443\u043f\u043f\u044b \u0435\u0449\u0435 \u0435\u0441\u0442\u044c \u0441\u0432\u043e\u0439 \u0446\u0432\u0435\u0442 \u2014 \u043b\u044e\u0431\u043e\u0439, \u043a\u0440\u043e\u043c\u0435 \u0431\u0435\u043b\u043e\u0433\u043e, \u044d\u0442\u043e \u0444\u043e\u043d\u043e\u0432\u044b\u0439 \u0446\u0432\u0435\u0442. \u0421\u043e\u0441\u0435\u0434\u043d\u0438\u0435 \u0433\u0440\u0443\u043f\u043f\u044b <em>\u0440\u0430\u0437\u043d\u044b\u0445<\/em> \u0446\u0432\u0435\u0442\u043e\u0432 \u043c\u043e\u0433\u0443\u0442 \u0441\u0442\u043e\u044f\u0442\u044c \u0432\u043f\u043b\u043e\u0442\u043d\u0443\u044e, \u043d\u043e \u0434\u043b\u044f \u0441\u043e\u0441\u0435\u0434\u043d\u0438\u0445 \u0433\u0440\u0443\u043f\u043f <em>\u043e\u0434\u0438\u043d\u0430\u043a\u043e\u0432\u044b\u0445<\/em> \u0446\u0432\u0435\u0442\u043e\u0432 \u0440\u0430\u0437\u0434\u0435\u043b\u0435\u043d\u0438\u0435 \u0445\u043e\u0442\u044f \u0431\u044b \u043e\u0434\u043d\u043e\u0439 \u0431\u0435\u043b\u043e\u0439 \u043a\u043b\u0435\u0442\u043a\u043e\u0439 \u0435\u0449\u0435 \u043e\u0431\u044f\u0437\u0430\u0442\u0435\u043b\u044c\u043d\u043e.<\/p>\n<p>  <\/p>\n<h2 id=\"chto-ne-yavlyaetsya-yaponskim-krossvordom\">\u0427\u0442\u043e \u043d\u0435 \u044f\u0432\u043b\u044f\u0435\u0442\u0441\u044f \u044f\u043f\u043e\u043d\u0441\u043a\u0438\u043c \u043a\u0440\u043e\u0441\u0441\u0432\u043e\u0440\u0434\u043e\u043c<\/h2>\n<p>  <\/p>\n<p>\u041a\u0430\u0436\u0434\u043e\u0435 \u043f\u0438\u043a\u0441\u0435\u043b\u044c\u043d\u043e\u0435 \u0438\u0437\u043e\u0431\u0440\u0430\u0436\u0435\u043d\u0438\u0435 \u043c\u043e\u0436\u043d\u043e \u0437\u0430\u0448\u0438\u0444\u0440\u043e\u0432\u0430\u0442\u044c \u0432 \u0432\u0438\u0434\u0435 \u043a\u0440\u043e\u0441\u0441\u0432\u043e\u0440\u0434\u0430. \u041d\u043e \u0432\u043e\u0441\u0441\u0442\u0430\u043d\u043e\u0432\u0438\u0442\u044c \u043e\u0431\u0440\u0430\u0442\u043d\u043e \u043c\u043e\u0436\u0435\u0442 \u0431\u044b\u0442\u044c \u043d\u0435\u0432\u043e\u0437\u043c\u043e\u0436\u043d\u043e \u2014 \u043f\u043e\u043b\u0443\u0447\u0438\u0432\u0448\u0430\u044f\u0441\u044f \u0433\u043e\u043b\u043e\u0432\u043e\u043b\u043e\u043c\u043a\u0430 \u043c\u043e\u0436\u0435\u0442 \u043b\u0438\u0431\u043e \u0438\u043c\u0435\u0442\u044c \u0431\u043e\u043b\u0435\u0435 \u043e\u0434\u043d\u043e\u0433\u043e \u0440\u0435\u0448\u0435\u043d\u0438\u044f, \u043b\u0438\u0431\u043e \u0438\u043c\u0435\u0442\u044c \u043e\u0434\u043d\u043e \u0440\u0435\u0448\u0435\u043d\u0438\u0435, \u043d\u043e \u043d\u0435 \u043c\u043e\u0436\u0435\u0442 \u0431\u044b\u0442\u044c \u0440\u0435\u0448\u0435\u043d\u0430 \u043b\u043e\u0433\u0438\u0447\u0435\u0441\u043a\u0438\u043c \u043f\u0443\u0442\u0435\u043c. \u0422\u043e\u0433\u0434\u0430 \u043e\u0441\u0442\u0430\u0432\u0448\u0438\u0435\u0441\u044f \u043a\u043b\u0435\u0442\u043a\u0438 \u0432 \u043f\u0440\u043e\u0446\u0435\u0441\u0441\u0435 \u0438\u0433\u0440\u044b \u043f\u0440\u0438\u0445\u043e\u0434\u0438\u0442\u0441\u044f \u043e\u0442\u0433\u0430\u0434\u044b\u0432\u0430\u0442\u044c, \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u044f <s>\u043a\u0432\u0430\u043d\u0442\u043e\u0432\u044b\u0435 \u043a\u043e\u043c\u043f\u044c\u044e\u0442\u0435\u0440\u044b<\/s> \u0448\u0430\u043c\u0430\u043d\u0441\u043a\u0438\u0435 \u0442\u0435\u0445\u043d\u043e\u043b\u043e\u0433\u0438\u0438.<\/p>\n<p>  <\/p>\n<p>\u0422\u0430\u043a\u0438\u0435 \u043a\u0440\u043e\u0441\u0441\u0432\u043e\u0440\u0434\u044b \u044f\u0432\u043b\u044f\u044e\u0442\u0441\u044f \u043d\u0435 \u043a\u0440\u043e\u0441\u0441\u0432\u043e\u0440\u0434\u0430\u043c\u0438, \u0430 \u0433\u0440\u0430\u0444\u043e\u043c\u0430\u043d\u0438\u0435\u0439. \u0421\u0447\u0438\u0442\u0430\u0435\u0442\u0441\u044f, \u0447\u0442\u043e \u043a\u043e\u0440\u0440\u0435\u043a\u0442\u043d\u044b\u0439 \u043a\u0440\u043e\u0441\u0441\u0432\u043e\u0440\u0434 \u2014 \u0442\u0430\u043a\u043e\u0439, \u0447\u0442\u043e \u043b\u043e\u0433\u0438\u0447\u0435\u0441\u043a\u0438\u043c \u043f\u0443\u0442\u0435\u043c \u043c\u043e\u0436\u043d\u043e \u043f\u0440\u0438\u0439\u0442\u0438 \u043a \u0435\u0434\u0438\u043d\u0441\u0442\u0432\u0435\u043d\u043d\u043e\u043c\u0443 \u0440\u0435\u0448\u0435\u043d\u0438\u044e.<\/p>\n<p>  <\/p>\n<p>&#171;\u041b\u043e\u0433\u0438\u0447\u0435\u0441\u043a\u0438\u0439 \u043f\u0443\u0442\u044c&#187; \u2014 \u044d\u0442\u043e \u0432\u043e\u0437\u043c\u043e\u0436\u043d\u043e\u0441\u0442\u044c \u0432\u043e\u0441\u0441\u0442\u0430\u043d\u043e\u0432\u0438\u0442\u044c \u043a\u0430\u0436\u0434\u0443\u044e \u043a\u043b\u0435\u0442\u043a\u0443 \u043e\u0434\u043d\u0443 \u0437\u0430 \u0434\u0440\u0443\u0433\u043e\u0439, \u0440\u0430\u0441\u0441\u043c\u0430\u0442\u0440\u0438\u0432\u0430\u044f \u0441\u0442\u0440\u043e\u043a\u0443\/\u0441\u0442\u043e\u043b\u0431\u0435\u0446 \u043f\u043e \u043e\u0442\u0434\u0435\u043b\u044c\u043d\u043e\u0441\u0442\u0438, \u0438\u043b\u0438 \u0438\u0445 \u043f\u0435\u0440\u0435\u0441\u0435\u0447\u0435\u043d\u0438\u0435. \u0415\u0441\u043b\u0438 \u0442\u0430\u043a\u043e\u0439 \u0432\u043e\u0437\u043c\u043e\u0436\u043d\u043e\u0441\u0442\u0438 \u043d\u0435\u0442, \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e \u0440\u0430\u0441\u0441\u043c\u0430\u0442\u0440\u0438\u0432\u0430\u0435\u043c\u044b\u0445 \u0432\u0430\u0440\u0438\u0430\u043d\u0442\u043e\u0432 \u043e\u0442\u0432\u0435\u0442\u0430 \u043c\u043e\u0436\u0435\u0442 \u0431\u044b\u0442\u044c \u043e\u0447\u0435\u043d\u044c \u043c\u043d\u043e\u0433\u043e, \u043d\u0430\u043c\u043d\u043e\u0433\u043e \u0431\u043e\u043b\u044c\u0448\u0435, \u0447\u0435\u043c \u0447\u0435\u043b\u043e\u0432\u0435\u043a \u0441\u043c\u043e\u0436\u0435\u0442 \u043f\u043e\u0441\u0447\u0438\u0442\u0430\u0442\u044c \u0441\u0430\u043c.<\/p>\n<p>  <img decoding=\"async\" src=\"https:\/\/habrastorage.org\/webt\/qs\/nu\/2m\/qsnu2mmr0lutke0xzprtow8jv-i.png\">  <\/p>\n<p><em>\u041d\u0435\u043f\u0440\u0430\u0432\u0438\u043b\u044c\u043d\u0430\u044f \u043d\u043e\u043d\u043e\u0433\u0440\u0430\u043c\u043c\u0430 \u2014 \u0440\u0435\u0448\u0435\u043d\u0438\u0435 \u0435\u0434\u0438\u043d\u0441\u0442\u0432\u0435\u043d\u043d\u043e\u0435, \u043d\u043e \u0440\u0435\u0448\u0438\u0442\u044c \u043d\u043e\u0440\u043c\u0430\u043b\u044c\u043d\u043e \u043d\u0435\u043b\u044c\u0437\u044f. \u041e\u0440\u0430\u043d\u0436\u0435\u0432\u044b\u043c \u043f\u043e\u043c\u0435\u0447\u0435\u043d\u044b &#171;\u043d\u0435\u0440\u0435\u0448\u0430\u0435\u043c\u044b\u0435&#187; \u043a\u043b\u0435\u0442\u043a\u0438. \u0412\u0437\u044f\u0442\u043e \u0438\u0437 Wikipedia.<\/em><\/p>\n<p>  <\/p>\n<p>\u0422\u0430\u043a\u043e\u0435 \u043e\u0433\u0440\u0430\u043d\u0438\u0447\u0435\u043d\u0438\u0435 \u043e\u0431\u044a\u044f\u0441\u043d\u044f\u0435\u0442\u0441\u044f \u0442\u0430\u043a \u2014 \u0432 \u0441\u0430\u043c\u043e\u043c \u043e\u0431\u0449\u0435\u043c \u0441\u043b\u0443\u0447\u0430\u0435 \u044f\u043f\u043e\u043d\u0441\u043a\u0438\u0439 \u043a\u0440\u043e\u0441\u0441\u0432\u043e\u0440\u0434 \u044d\u0442\u043e NP-\u043f\u043e\u043b\u043d\u0430\u044f \u0437\u0430\u0434\u0430\u0447\u0430. \u041e\u0434\u043d\u0430\u043a\u043e, NP-\u043f\u043e\u043b\u043d\u043e\u0439 \u0437\u0430\u0434\u0430\u0447\u0435\u0439 \u0440\u0430\u0437\u0433\u0430\u0434\u044b\u0432\u0430\u043d\u0438\u0435 \u043d\u0435 \u0441\u0442\u0430\u043d\u043e\u0432\u0438\u0442\u0441\u044f, \u0435\u0441\u043b\u0438 \u0435\u0441\u0442\u044c \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c, \u0432 \u043a\u0430\u0436\u0434\u044b\u0439 \u043c\u043e\u043c\u0435\u043d\u0442 \u0432\u0440\u0435\u043c\u0435\u043d\u0438 \u043e\u0434\u043d\u043e\u0437\u043d\u0430\u0447\u043d\u043e \u0443\u043a\u0430\u0437\u044b\u0432\u0430\u044e\u0449\u0438\u0439, \u043a\u0430\u043a\u0438\u0435 \u043a\u043b\u0435\u0442\u043a\u0438 \u043e\u0442\u043a\u0440\u044b\u0442\u044c \u0434\u0430\u043b\u0435\u0435. \u0412\u0441\u0435 \u043c\u0435\u0442\u043e\u0434\u044b \u0440\u0430\u0437\u0433\u0430\u0434\u044b\u0432\u0430\u043d\u0438\u044f \u043a\u0440\u043e\u0441\u0441\u0432\u043e\u0440\u0434\u043e\u0432, \u043f\u0440\u0438\u043c\u0435\u043d\u044f\u0435\u043c\u044b\u0435 \u0447\u0435\u043b\u043e\u0432\u0435\u043a\u043e\u043c (\u0437\u0430 \u0438\u0441\u043a\u043b\u044e\u0447\u0435\u043d\u0438\u0435\u043c \u043c\u0435\u0442\u043e\u0434\u0430 <del>\u041c\u043e\u043d\u0442\u0435-\u041a\u0430\u0440\u043b\u043e<\/del> \u043f\u0440\u043e\u0431 \u0438 \u043e\u0448\u0438\u0431\u043e\u043a), \u043e\u0441\u043d\u043e\u0432\u044b\u0432\u0430\u044e\u0442\u0441\u044f \u0438\u043c\u0435\u043d\u043d\u043e \u043d\u0430 \u044d\u0442\u043e\u043c. <\/p>\n<p>  <\/p>\n<p>\u0423 \u043d\u0430\u0438\u0431\u043e\u043b\u0435\u0435 \u043f\u0440\u0430\u0432\u043e\u0441\u043b\u0430\u0432\u043d\u044b\u0445 \u043a\u0440\u043e\u0441\u0441\u0432\u043e\u0440\u0434\u043e\u0432 \u0448\u0438\u0440\u0438\u043d\u0430 \u0438 \u0432\u044b\u0441\u043e\u0442\u0430 \u0434\u0435\u043b\u0438\u0442\u0441\u044f \u043d\u0430 5, \u043d\u0435\u0442 \u0440\u044f\u0434\u043e\u0432, \u043a\u043e\u0442\u043e\u0440\u044b\u0445 \u043c\u043e\u0436\u043d\u043e \u043f\u043e\u0441\u0447\u0438\u0442\u0430\u0442\u044c \u043c\u0433\u043d\u043e\u0432\u0435\u043d\u043d\u043e (\u0442\u0430\u043a\u0438\u0435, \u0433\u0434\u0435 \u043b\u0438\u0431\u043e \u0446\u0432\u0435\u0442\u043d\u044b\u0435 \u043a\u043b\u0435\u0442\u043a\u0438 \u0437\u0430\u0431\u0438\u0432\u0430\u044e\u0442 \u0432\u0441\u0435 \u043c\u0435\u0441\u0442\u0430, \u043b\u0438\u0431\u043e \u0438\u0445 \u043d\u0435\u0442 \u0441\u043e\u0432\u0441\u0435\u043c), \u0438 \u043e\u0433\u0440\u0430\u043d\u0438\u0447\u0435\u043d\u043e \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e \u0434\u043e\u043f\u043e\u043b\u043d\u0438\u0442\u0435\u043b\u044c\u043d\u044b\u0445 \u0446\u0432\u0435\u0442\u043e\u0432. \u042d\u0442\u0438 \u0442\u0440\u0435\u0431\u043e\u0432\u0430\u043d\u0438\u044f \u043d\u0435 \u043e\u0431\u044f\u0437\u0430\u0442\u0435\u043b\u044c\u043d\u044b\u0435.<\/p>\n<p>  <\/p>\n<p>\u041d\u0430\u0438\u043f\u0440\u043e\u0441\u0442\u0435\u0439\u0448\u0438\u0439 \u043d\u0435\u043f\u0440\u0430\u0432\u0438\u043b\u044c\u043d\u044b\u0439 \u043a\u0440\u043e\u0441\u0441\u0432\u043e\u0440\u0434:<\/p>\n<p>  <\/p>\n<pre><code class=\"bash\">  |1 1| --+---+  1|   |  1|   | --+---+<\/code><\/pre>\n<p>  <\/p>\n<p>\u0427\u0430\u0441\u0442\u043e \u043d\u0435 \u0440\u0435\u0448\u0430\u044e\u0442\u0441\u044f \u0432\u0437\u0430\u0434 \u0437\u0430\u043a\u043e\u0434\u0438\u0440\u043e\u0432\u0430\u043d\u043d\u044b\u0435 \u043f\u0438\u043a\u0441\u0435\u043b\u044c\u043d\u044b\u0435 \u0430\u0440\u0442\u044b, \u0432 \u043a\u043e\u0442\u043e\u0440\u044b\u0445 \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u0435\u0442\u0441\u044f &#171;\u0448\u0430\u0445\u043c\u0430\u0442\u043d\u044b\u0439 \u043f\u043e\u0440\u044f\u0434\u043e\u043a&#187; \u0434\u043b\u044f \u0438\u043c\u0438\u0442\u0430\u0446\u0438\u0438 \u0433\u0440\u0430\u0434\u0438\u0435\u043d\u0442\u0430. \u041b\u0443\u0447\u0448\u0435 \u043f\u043e\u043d\u044f\u0442\u044c \u0431\u0443\u0434\u0435\u0442, \u0435\u0441\u043b\u0438 \u0432\u044b \u043d\u0430\u0431\u0435\u0440\u0435\u0442\u0435 \u0432 \u043f\u043e\u0438\u0441\u043a\u0435 &#171;pixelart gradient&#187;. \u0413\u0440\u0430\u0434\u0438\u0435\u043d\u0442 \u043a\u0430\u043a \u0440\u0430\u0437 \u043f\u043e\u0445\u043e\u0436 \u043d\u0430 \u044d\u0442\u043e\u0442 \u0444\u0435\u0439\u043b\u043e\u0432\u044b\u0439 \u043a\u0440\u043e\u0441\u0441\u0432\u043e\u0440\u0434 2&#215;2.<\/p>\n<p>  <\/p>\n<div style=\"text-align:center;\"><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/webt\/oz\/mm\/sj\/ozmmsj7dzmqdn0dwgmspwymmohy.gif\"><\/div>\n<p>  <\/p>\n<h2 id=\"vozmozhnye-varianty-resheniy\">\u0412\u043e\u0437\u043c\u043e\u0436\u043d\u044b\u0435 \u0432\u0430\u0440\u0438\u0430\u043d\u0442\u044b \u0440\u0435\u0448\u0435\u043d\u0438\u0439<\/h2>\n<p>  <\/p>\n<p>\u0423 \u043d\u0430\u0441 \u0435\u0441\u0442\u044c \u0440\u0430\u0437\u043c\u0435\u0440 \u043a\u0440\u043e\u0441\u0441\u0432\u043e\u0440\u0434\u0430, \u043e\u043f\u0438\u0441\u0430\u043d\u0438\u0435 \u0446\u0432\u0435\u0442\u043e\u0432 \u0438 \u0432\u0441\u0435\u0445 \u0441\u0442\u0440\u043e\u043a \u0438 \u0441\u0442\u043e\u043b\u0431\u0446\u043e\u0432. \u041a\u0430\u043a \u043c\u043e\u0436\u043d\u043e \u0441\u043e\u0431\u0440\u0430\u0442\u044c \u0438\u0437 \u044d\u0442\u043e\u0433\u043e \u043a\u0430\u0440\u0442\u0438\u043d\u043a\u0443:<\/p>\n<p>  <\/p>\n<h4 id=\"polnyy-perebor\">\u041f\u043e\u043b\u043d\u044b\u0439 \u043f\u0435\u0440\u0435\u0431\u043e\u0440<\/h4>\n<p>  <\/p>\n<p>\u0414\u043b\u044f \u043a\u0430\u0436\u0434\u043e\u0439 \u043a\u043b\u0435\u0442\u043a\u0438 \u043f\u0435\u0440\u0435\u0431\u0438\u0440\u0430\u0435\u043c \u0432\u0441\u0435 \u0432\u043e\u0437\u043c\u043e\u0436\u043d\u044b\u0435 \u0441\u043e\u0441\u0442\u043e\u044f\u043d\u0438\u044f \u0438 \u043f\u0440\u043e\u0432\u0435\u0440\u044f\u0435\u043c \u043d\u0430 \u0443\u0434\u043e\u0432\u043b\u0435\u0442\u0432\u043e\u0440\u0438\u0442\u0435\u043b\u044c\u043d\u043e\u0441\u0442\u044c. \u0421\u043b\u043e\u0436\u043d\u043e\u0441\u0442\u044c \u0442\u0430\u043a\u043e\u0433\u043e \u0440\u0435\u0448\u0435\u043d\u0438\u044f \u0434\u043b\u044f \u0447\u0435\u0440\u043d\u043e-\u0431\u0435\u043b\u043e\u0433\u043e \u043a\u0440\u043e\u0441\u0441\u0432\u043e\u0440\u0434\u0430 <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/6ea\/678\/1aa\/6ea6781aae04f0beb2c4236dbb1a9ed6.svg\" alt=\"$O(N*M*{2}^{N*M})$\" data-tex=\"inline\"><\/math>, \u0434\u043b\u044f \u0446\u0432\u0435\u0442\u043d\u043e\u0433\u043e <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/601\/d9e\/d06\/601d9ed06fa3195b2eec61c163d02772.svg\" alt=\"$O(N*M*{colors}^{N*M})$\" data-tex=\"inline\"><\/math>. \u041f\u043e \u0430\u043d\u0430\u043b\u043e\u0433\u0438\u0438 \u0441 <a href=\"https:\/\/ru.wikipedia.org\/wiki\/Bogosort\">\u043a\u043b\u043e\u0443\u043d\u0441\u043a\u043e\u0439 \u0441\u043e\u0440\u0442\u0438\u0440\u043e\u0432\u043a\u043e\u0439<\/a> \u044d\u0442\u043e \u0440\u0435\u0448\u0435\u043d\u0438\u0435 \u043c\u043e\u0436\u043d\u043e \u0442\u043e\u0436\u0435 \u043d\u0430\u0437\u0432\u0430\u0442\u044c \u043a\u043b\u043e\u0443\u043d\u0441\u043a\u0438\u043c. \u041e\u043d\u043e \u0433\u043e\u0434\u0438\u0442\u0441\u044f \u0434\u043b\u044f \u0440\u0430\u0437\u043c\u0435\u0440\u0430 5&#215;5.<\/p>\n<p>  <\/p>\n<h4 id=\"backtracking\">Backtracking<\/h4>\n<p>  <\/p>\n<p>\u041f\u0435\u0440\u0435\u0431\u0438\u0440\u0430\u044e\u0442\u0441\u044f \u0432\u0441\u0435 \u0432\u043e\u0437\u043c\u043e\u0436\u043d\u044b\u0435 \u043c\u0435\u0442\u043e\u0434\u044b \u0440\u0430\u0441\u0441\u0442\u0430\u043d\u043e\u0432\u043a\u0438 \u0433\u043e\u0440\u0438\u0437\u043e\u043d\u0442\u0430\u043b\u044c\u043d\u044b\u0445 \u0433\u0440\u0443\u043f\u043f \u043a\u043b\u0435\u0442\u043e\u043a. \u0421\u0442\u0430\u0432\u0438\u043c \u0433\u0440\u0443\u043f\u043f\u0443 \u043a\u043b\u0435\u0442\u043e\u043a \u0432 \u0441\u0442\u0440\u043e\u043a\u0435, \u043f\u0440\u043e\u0432\u0435\u0440\u044f\u0435\u043c, \u0447\u0442\u043e \u043e\u043d\u0430 \u043d\u0435 \u043b\u043e\u043c\u0430\u0435\u0442 \u043e\u043f\u0438\u0441\u0430\u043d\u0438\u0435 \u0433\u0440\u0443\u043f\u043f \u0441\u0442\u043e\u043b\u0431\u0446\u043e\u0432. \u0415\u0441\u043b\u0438 \u043b\u043e\u043c\u0430\u0435\u0442 \u2014 \u0441\u0442\u0430\u0432\u0438\u043c \u0434\u0430\u043b\u044c\u0448\u0435 \u043d\u0430 1 \u043a\u043b\u0435\u0442\u043a\u0443, \u043e\u043f\u044f\u0442\u044c \u043f\u0440\u043e\u0432\u0435\u0440\u044f\u0435\u043c. \u041f\u043e\u0441\u0442\u0430\u0432\u0438\u043b\u0438 \u2014 \u043f\u0435\u0440\u0435\u0445\u043e\u0434\u0438\u043c \u043a \u0441\u043b\u0435\u0434\u0443\u044e\u0449\u0435\u0439 \u0433\u0440\u0443\u043f\u043f\u0435. \u0415\u0441\u043b\u0438 \u0433\u0440\u0443\u043f\u043f\u0443 \u043f\u043e\u0441\u0442\u0430\u0432\u0438\u0442\u044c \u043d\u0435\u043b\u044c\u0437\u044f \u043d\u0438\u043a\u0430\u043a \u2014 \u043e\u0442\u043a\u0430\u0442\u044b\u0432\u0430\u0435\u043c \u0434\u0432\u0435 \u0433\u0440\u0443\u043f\u043f\u044b, \u043f\u0435\u0440\u0435\u0441\u0442\u0430\u0432\u043b\u044f\u0435\u043c \u043f\u0440\u0435\u0434\u044b\u0434\u0443\u0449\u0443\u044e \u0433\u0440\u0443\u043f\u043f\u0443, \u0438 \u0442\u0430\u043a \u0434\u0430\u043b\u0435\u0435, \u043f\u043e\u043a\u0430 \u043d\u0435 \u043f\u043e\u0441\u0442\u0430\u0432\u0438\u043c \u043f\u043e\u0441\u043b\u0435\u0434\u043d\u044e\u044e \u0433\u0440\u0443\u043f\u043f\u0443 \u0443\u0441\u043f\u0435\u0448\u043d\u043e.<\/p>\n<p>  <\/p>\n<h4 id=\"otdelno-dlya-kazhdogo-ryada\">\u041e\u0442\u0434\u0435\u043b\u044c\u043d\u043e \u0434\u043b\u044f \u043a\u0430\u0436\u0434\u043e\u0433\u043e \u0440\u044f\u0434\u0430<\/h4>\n<p>  <\/p>\n<p>\u042d\u0442\u043e \u0440\u0435\u0448\u0435\u043d\u0438\u0435 \u043d\u0430\u043c\u043d\u043e\u0433\u043e \u043b\u0443\u0447\u0448\u0435 \u0438 \u043e\u043d\u043e \u0438\u0441\u0442\u0438\u043d\u043d\u043e \u0432\u0435\u0440\u043d\u043e\u0435. \u041c\u044b \u043c\u043e\u0436\u0435\u043c \u043f\u0440\u043e\u0430\u043d\u0430\u043b\u0438\u0437\u0438\u0440\u043e\u0432\u0430\u0442\u044c \u043a\u0430\u0436\u0434\u0443\u044e \u0441\u0442\u0440\u043e\u043a\u0443 \u0438 \u043a\u0430\u0436\u0434\u044b\u0439 \u0441\u0442\u043e\u043b\u0431\u0435\u0446 \u043f\u043e \u043e\u0442\u0434\u0435\u043b\u044c\u043d\u043e\u0441\u0442\u0438. \u0423 \u043a\u0430\u0436\u0434\u043e\u0433\u043e \u0440\u044f\u0434\u0430 \u043f\u043e\u043f\u044b\u0442\u0430\u0435\u043c\u0441\u044f \u0440\u0430\u0441\u043a\u0440\u044b\u0442\u044c \u043c\u0430\u043a\u0441\u0438\u043c\u0443\u043c \u0438\u043d\u0444\u043e\u0440\u043c\u0430\u0446\u0438\u0438.<\/p>\n<p>  <\/p>\n<p>\u0410\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u0434\u043b\u044f \u043a\u0430\u0436\u0434\u043e\u0439 \u043a\u043b\u0435\u0442\u043a\u0438 \u0432 \u0440\u044f\u0434\u0443 \u0443\u0437\u043d\u0430\u0435\u0442 \u0431\u043e\u043b\u044c\u0448\u0435 \u0438\u043d\u0444\u043e\u0440\u043c\u0430\u0446\u0438\u0438 \u2014 \u043c\u043e\u0436\u0435\u0442 \u043e\u043a\u0430\u0437\u0430\u0442\u044c\u0441\u044f, \u0447\u0442\u043e \u0432 \u043a\u0430\u043a\u043e\u0439-\u0442\u043e \u0446\u0432\u0435\u0442 \u043a\u043b\u0435\u0442\u043a\u0443 \u043e\u043a\u0440\u0430\u0441\u0438\u0442\u044c \u043d\u0435\u0432\u043e\u0437\u043c\u043e\u0436\u043d\u043e, \u0433\u0440\u0443\u043f\u043f\u044b \u043d\u0435 \u0441\u043e\u0439\u0434\u0443\u0442\u0441\u044f. \u0421\u0440\u0430\u0437\u0443 \u0441\u0442\u0440\u043e\u043a\u0443 \u043f\u043e\u043b\u043d\u043e\u0441\u0442\u044c\u044e \u0440\u0430\u0441\u043a\u0440\u044b\u0442\u044c \u043d\u0435\u043b\u044c\u0437\u044f, \u043d\u043e \u043f\u043e\u043b\u0443\u0447\u0435\u043d\u043d\u0430\u044f \u0438\u043d\u0444\u043e\u0440\u043c\u0430\u0446\u0438\u044f &#171;\u043f\u043e\u043c\u043e\u0436\u0435\u0442&#187; \u0440\u0430\u0441\u043a\u0440\u044b\u0442\u044c\u0441\u044f \u043b\u0443\u0447\u0448\u0435 \u043d\u0435\u0441\u043a\u043e\u043b\u044c\u043a\u0438\u043c \u0441\u0442\u043e\u043b\u0431\u0446\u0430\u043c, \u0430 \u043a\u043e\u0433\u0434\u0430 \u043c\u044b \u043d\u0430\u0447\u043d\u0435\u043c \u0438\u0445 \u0430\u043d\u0430\u043b\u0438\u0437\u0438\u0440\u043e\u0432\u0430\u0442\u044c, \u0442\u0435 \u043e\u043f\u044f\u0442\u044c &#171;\u043f\u043e\u043c\u043e\u0433\u0443\u0442&#187; \u0441\u0442\u0440\u043e\u043a\u0430\u043c, \u0438 \u0442\u0430\u043a \u0432 \u0442\u0435\u0447\u0435\u043d\u0438\u0435 \u043d\u0435\u0441\u043a\u043e\u043b\u044c\u043a\u0438\u0445 \u0438\u0442\u0435\u0440\u0430\u0446\u0438\u0439, \u043f\u043e\u043a\u0430 \u0434\u043b\u044f \u0432\u0441\u0435\u0445 \u043a\u043b\u0435\u0442\u043e\u043a \u043d\u0435 \u043e\u0441\u0442\u0430\u043d\u0435\u0442\u0441\u044f \u043e\u0434\u0438\u043d \u0432\u043e\u0437\u043c\u043e\u0436\u043d\u044b\u0439 \u0446\u0432\u0435\u0442.<\/p>\n<p>  <\/p>\n<h2 id=\"istinno-vernoe-reshenie\">\u0418\u0441\u0442\u0438\u043d\u043d\u043e \u0432\u0435\u0440\u043d\u043e\u0435 \u0440\u0435\u0448\u0435\u043d\u0438\u0435<\/h2>\n<p>  <\/p>\n<h4 id=\"odna-stroka-dva-cveta\">\u041e\u0434\u043d\u0430 \u0441\u0442\u0440\u043e\u043a\u0430, \u0434\u0432\u0430 \u0446\u0432\u0435\u0442\u0430<\/h4>\n<p>  <\/p>\n<p>\u042d\u0444\u0444\u0435\u043a\u0442\u0438\u0432\u043d\u043e\u0435 \u043e\u0442\u0433\u0430\u0434\u044b\u0432\u0430\u043d\u0438\u0435 \u0447\u0435\u0440\u043d\u043e-\u0431\u0435\u043b\u043e\u0433\u043e &#171;\u043e\u0434\u043d\u043e\u0441\u0442\u0440\u043e\u0447\u043d\u0438\u043a\u0430&#187;, \u0434\u043b\u044f \u043a\u043e\u0442\u043e\u0440\u043e\u0433\u043e \u043d\u0435\u043a\u043e\u0442\u043e\u0440\u044b\u0435 \u043a\u043b\u0435\u0442\u043a\u0438 \u0443\u0436\u0435 \u043e\u0442\u0433\u0430\u0434\u0430\u043d\u044b \u2014 \u0432\u0435\u0441\u044c\u043c\u0430 \u0436\u0435\u0441\u0442\u043a\u0430\u044f \u0437\u0430\u0434\u0430\u0447\u0430. \u041e\u043d\u0430 \u0432\u0441\u0442\u0440\u0435\u0447\u0430\u043b\u0430\u0441\u044c \u0432 \u0442\u0430\u043a\u0438\u0445 \u043c\u0435\u0441\u0442\u0430\u0445, \u043a\u0430\u043a:<\/p>\n<p>  <\/p>\n<ul>\n<li><em>\u0427\u0435\u0442\u0432\u0435\u0440\u0442\u044c\u0444\u0438\u043d\u0430\u043b ACM ICPC 2006<\/em> \u2014 <a href=\"http:\/\/acm.timus.ru\/problem.aspx?space=1&amp;num=1508&amp;locale=ru\">\u0437\u0430\u0434\u0430\u0447\u0443 \u043c\u043e\u0436\u043d\u043e \u043f\u043e\u043f\u0440\u043e\u0431\u043e\u0432\u0430\u0442\u044c \u0440\u0435\u0448\u0438\u0442\u044c \u0441\u0430\u043c\u043e\u043c\u0443<\/a>. \u0422\u0430\u0439\u043c-\u043b\u0438\u043c\u0438\u0442 1 \u0441\u0435\u043a\u0443\u043d\u0434\u0430, \u043e\u0433\u0440\u0430\u043d\u0438\u0447\u0435\u043d\u0438\u0435 \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u0430 \u0433\u0440\u0443\u043f\u043f 400, \u0434\u043b\u0438\u043d\u044b \u0440\u044f\u0434\u0430 \u0442\u043e\u0436\u0435 400. \u0418\u043c\u0435\u0435\u0442 \u0441\u0438\u043b\u044c\u043d\u043e \u0432\u044b\u0441\u043e\u043a\u0438\u0439 \u0443\u0440\u043e\u0432\u0435\u043d\u044c \u0441\u043b\u043e\u0436\u043d\u043e\u0441\u0442\u0438 \u043f\u043e \u0441\u0440\u0430\u0432\u043d\u0435\u043d\u0438\u044e \u0441 \u0434\u0440\u0443\u0433\u0438\u043c\u0438 \u0437\u0430\u0434\u0430\u0447\u0430\u043c\u0438.<\/li>\n<li><em>International Olympiad in Informatics 2016<\/em> \u2014 <a href=\"http:\/\/ioinformatics.org\/locations\/ioi16\/contest\/day2\/paint\/paint-RUS.pdf\">\u0443\u0441\u043b\u043e\u0432\u0438\u0435<\/a>, <a href=\"https:\/\/contest.yandex.ru\/contest\/2647\/problems\/D\/\">\u0441\u0434\u0430\u0442\u044c \u0437\u0430\u0434\u0430\u0447\u0443<\/a>. \u0422\u0430\u0439\u043c-\u043b\u0438\u043c\u0438\u0442 2 \u0441\u0435\u043a\u0443\u043d\u0434\u044b, \u043e\u0433\u0440\u0430\u043d\u0438\u0447\u0435\u043d\u0438\u0435 \u043a\u043e\u043b-\u0432\u0430 \u0433\u0440\u0443\u043f\u043f 100, \u0434\u043b\u0438\u043d\u044b \u0440\u044f\u0434\u0430 200&#8217;000. \u0422\u0430\u043a\u0438\u0435 \u043e\u0433\u0440\u0430\u043d\u0438\u0447\u0435\u043d\u0438\u044f \u043e\u0432\u0435\u0440\u043a\u0438\u043b\u043b, \u043d\u043e \u0440\u0435\u0448\u0435\u043d\u0438\u0435 \u0437\u0430\u0434\u0430\u0447\u0438 \u0441 \u043e\u0433\u0440\u0430\u043d\u0438\u0447\u0435\u043d\u0438\u044f\u043c\u0438 ACM \u043d\u0430\u0431\u0438\u0440\u0430\u0435\u0442 80\/100 \u0431\u0430\u043b\u043b\u043e\u0432 \u0432 \u044d\u0442\u043e\u0439 \u0437\u0430\u0434\u0430\u0447\u0435. \u0422\u0443\u0442 \u0442\u043e\u0436\u0435 \u0443\u0440\u043e\u0432\u0435\u043d\u044c \u043d\u0435 \u043f\u043e\u0434\u043a\u0430\u0447\u0430\u043b, \u0448\u043a\u043e\u043b\u044c\u043d\u0438\u043a\u0438 \u0441\u043e \u0432\u0441\u0435\u0433\u043e \u043c\u0438\u0440\u0430 \u0441 \u0436\u0435\u0441\u0442\u043e\u043a\u0438\u043c \u0443\u0440\u043e\u0432\u043d\u0435\u043c IQ \u0442\u0440\u0435\u043d\u0438\u0440\u0443\u044e\u0442\u0441\u044f \u043d\u0435\u0441\u043a\u043e\u043b\u044c\u043a\u043e \u043b\u0435\u0442 \u0440\u0435\u0448\u0430\u0442\u044c \u0440\u0430\u0437\u043d\u0443\u044e \u0436\u0435\u0441\u0442\u044c, \u043f\u043e\u0442\u043e\u043c \u043f\u0440\u043e\u0445\u043e\u0434\u044f\u0442 \u043d\u0430 \u044d\u0442\u0443 \u043e\u043b\u0438\u043c\u043f\u0438\u0430\u0434\u0443 (\u043f\u0440\u043e\u0439\u0442\u0438 \u0434\u043e\u043b\u0436\u043d\u044b \u0442\u043e\u043b\u044c\u043a\u043e 4 \u0447\u0435\u043b\u043e\u0432\u0435\u043a\u0430 \u043e\u0442 \u0441\u0442\u0440\u0430\u043d\u044b), \u0440\u0435\u0448\u0430\u044e\u0442 2 \u0442\u0443\u0440\u0430 \u043f\u043e 5 \u0447\u0430\u0441\u043e\u0432 <del>\u0438 \u0432 \u0441\u043b\u0443\u0447\u0430\u0435 epic win (\u0431\u0440\u043e\u043d\u0437\u0430 \u0432 \u0440\u0430\u0437\u043d\u044b\u0435 \u0433\u043e\u0434\u044b \u0437\u0430 138-240 \u0431\u0430\u043b\u043b\u043e\u0432 \u0438\u0437 600) \u043f\u043e\u0441\u0442\u0443\u043f\u043b\u0435\u043d\u0438\u0435 \u0432 \u041e\u043a\u0441\u0444\u043e\u0440\u0434, \u043f\u043e\u0442\u043e\u043c \u043e\u0444\u0444\u0435\u0440\u044b \u043e\u0442 \u043f\u043e\u043d\u044f\u0442\u043d\u044b\u0445 \u043a\u043e\u043c\u043f\u0430\u043d\u0438\u0439 \u0432 \u043e\u0442\u0434\u0435\u043b \u043f\u043e\u0438\u0441\u043a\u0430, \u0434\u043e\u043b\u0433\u0430\u044f \u0438 \u0441\u0447\u0430\u0441\u0442\u043b\u0438\u0432\u0430\u044f \u0436\u0438\u0437\u043d\u044c \u0432 \u043e\u0431\u043d\u0438\u043c\u043a\u0443 \u0441 \u0434\u0430\u043a\u0438\u043c\u0430\u043a\u0443\u0440\u043e\u0439.<\/del><\/li>\n<\/ul>\n<p>  <\/p>\n<p>\u041c\u043e\u043d\u043e\u0445\u0440\u043e\u043c\u043d\u044b\u0439 \u043e\u0434\u043d\u043e\u0441\u0442\u0440\u043e\u0447\u043d\u0438\u043a \u0442\u043e\u0436\u0435 \u043c\u043e\u0436\u043d\u043e \u0440\u0435\u0448\u0430\u0442\u044c \u043f\u043e-\u0440\u0430\u0437\u043d\u043e\u043c\u0443, \u0438 \u0437\u0430 <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/995\/11b\/310\/99511b310df42ab15559ce4e7b9a7578.svg\" alt=\"$O(N*2^N)$\" data-tex=\"inline\"><\/math> (\u043f\u0435\u0440\u0435\u0431\u043e\u0440 \u0432\u0441\u0435\u0445 \u0432\u0430\u0440\u0438\u0430\u043d\u0442\u043e\u0432, \u043f\u0440\u043e\u0432\u0435\u0440\u043a\u0430 \u043d\u0430 \u043a\u043e\u0440\u0440\u0435\u043a\u0442\u043d\u043e\u0441\u0442\u044c, \u0432\u044b\u0434\u0435\u043b\u0435\u043d\u0438\u0435 \u043a\u043b\u0435\u0442\u043e\u043a, \u043a\u043e\u0442\u043e\u0440\u044b\u0435 \u0438\u043c\u0435\u044e\u0442 \u043e\u0434\u0438\u043d \u0438 \u0442\u043e\u0442 \u0436\u0435 \u0446\u0432\u0435\u0442 \u0432\u043e \u0432\u0441\u0435\u0445 \u0432\u0430\u0440\u0438\u0430\u043d\u0442\u0430\u0445), \u0438 \u0435\u0449\u0435 \u043a\u0430\u043a-\u0442\u043e \u043c\u0435\u043d\u0435\u0435 \u0442\u0443\u043f\u043e.<\/p>\n<p>  <\/p>\n<p>\u041e\u0441\u043d\u043e\u0432\u043d\u0430\u044f \u0438\u0434\u0435\u044f \u0432 \u0442\u043e\u043c, \u0447\u0442\u043e\u0431\u044b \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u0442\u044c \u0430\u043d\u0430\u043b\u043e\u0433 \u0431\u044d\u043a\u0442\u0440\u0435\u043a\u0438\u043d\u0433\u0430, \u043d\u043e \u0431\u0435\u0437 \u043b\u0438\u0448\u043d\u0438\u0445 \u0432\u044b\u0447\u0438\u0441\u043b\u0435\u043d\u0438\u0439. \u0415\u0441\u043b\u0438 \u043c\u044b \u043a\u0430\u043a-\u0442\u043e \u043f\u043e\u0441\u0442\u0430\u0432\u0438\u043b\u0438 \u043d\u0435\u0441\u043a\u043e\u043b\u044c\u043a\u043e \u0433\u0440\u0443\u043f\u043f \u0438 \u0441\u0435\u0439\u0447\u0430\u0441 \u043d\u0430\u0445\u043e\u0434\u0438\u043c\u0441\u044f \u0432 \u043a\u0430\u043a\u043e\u0439-\u0442\u043e \u043a\u043b\u0435\u0442\u043a\u0435, \u0442\u043e \u0442\u0440\u0435\u0431\u0443\u0435\u0442\u0441\u044f \u0443\u0437\u043d\u0430\u0442\u044c, \u043c\u043e\u0436\u043d\u043e \u043b\u0438 \u043f\u043e\u0441\u0442\u0430\u0432\u0438\u0442\u044c \u043e\u0441\u0442\u0430\u0432\u0448\u0438\u0435\u0441\u044f \u0433\u0440\u0443\u043f\u043f\u044b, \u043d\u0430\u0447\u0438\u043d\u0430\u044f \u0441 \u0442\u0435\u043a\u0443\u0449\u0435\u0439 \u043a\u043b\u0435\u0442\u043a\u0438.<\/p>\n<p>  <\/p>\n<div class=\"spoiler\"><b class=\"spoiler_title\">\u041f\u0441\u0435\u0432\u0434\u043e\u043a\u043e\u0434<\/b><\/p>\n<div class=\"spoiler_text\">\n<pre><code class=\"python\">def EpicWin(group, cell):                                                               if cell &gt;= last_cell: # \u0423\u0441\u043b\u043e\u0432\u0438\u0435 \u0432\u044b\u0438\u0433\u0440\u044b\u0448\u0430                                                return group == group_size                                                    win = False                                                                       # \u041c\u043e\u0436\u0435\u043c \u043b\u0438 \u0432\u0441\u0442\u0430\u0432\u0438\u0442\u044c \u0433\u0440\u0443\u043f\u043f\u0443 \u0432 \u044d\u0442\u043e\u0439 \u043f\u043e\u0437\u0438\u0446\u0438\u0438                                        if group &lt; group_size  # \u0413\u0440\u0443\u043f\u043f\u044b \u0435\u0449\u0435 \u0435\u0441\u0442\u044c                                                 and CanInsertBlack(cell, len[group])  # \u0412\u0441\u0442\u0430\u0432\u043a\u0430 \u0447\u0435\u0440\u043d\u043e\u0439 \u0433\u0440\u0443\u043f\u043f\u044b                    and CanInsertWhite(cell + len[group], 1)  # \u0412\u0441\u0442\u0430\u0432\u043a\u0430 \u0431\u0435\u043b\u043e\u0439 \u043a\u043b\u0435\u0442\u043a\u0438                 and EpicWin(group + 1, cell + len[group] + 1):  # \u041c\u043e\u0436\u043d\u043e \u0437\u0430\u043f\u043e\u043b\u043d\u0438\u0442\u044c \u0434\u0430\u043b\u0435\u0435         win = True                                                                       can_place_black[cell .. (cell + len[group] - 1)] = True                          can_place_white[cell + len[group]] = True;                                    # \u041c\u043e\u0436\u0435\u043c \u043b\u0438 \u0432\u0441\u0442\u0430\u0432\u0438\u0442\u044c \u0431\u0435\u043b\u0443\u044e \u043a\u043b\u0435\u0442\u043a\u0443 \u0432 \u044d\u0442\u043e\u0439 \u043f\u043e\u0437\u0438\u0446\u0438\u0438                                     if CanInsertWhite(cell, 1)                                                                  and EpicWin(group, cell + 1):                                                   win = True                                                                          can_place_white[cell] = True                                                     return win  EpicWin(0, 0)        <\/code><\/pre>\n<\/div>\n<\/div>\n<p>  <\/p>\n<p>\u0422\u0430\u043a\u043e\u0439 \u043f\u043e\u0434\u0445\u043e\u0434 \u043d\u0430\u0437\u044b\u0432\u0430\u0435\u0442\u0441\u044f <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\">\u0434\u0438\u043d\u0430\u043c\u0438\u0447\u0435\u0441\u043a\u0438\u043c \u043f\u0440\u043e\u0433\u0440\u0430\u043c\u043c\u0438\u0440\u043e\u0432\u0430\u043d\u0438\u0435\u043c<\/a>. \u041f\u0441\u0435\u0432\u0434\u043e\u043a\u043e\u0434 \u0443\u043f\u0440\u043e\u0449\u0435\u043d, \u0438 \u0442\u0430\u043c \u0434\u0430\u0436\u0435 \u0437\u0430\u043f\u043e\u043c\u0438\u043d\u0430\u043d\u0438\u0435 \u0432\u044b\u0447\u0438\u0441\u043b\u0435\u043d\u043d\u044b\u0445 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0439 \u043d\u0435 \u043f\u0440\u043e\u0438\u0437\u0432\u043e\u0434\u0438\u0442\u0441\u044f.<\/p>\n<p>  <\/p>\n<p>\u0424\u0443\u043d\u043a\u0446\u0438\u0438 <code>CanInsertBlack\/CanInsertWhite<\/code> \u043d\u0443\u0436\u043d\u044b, \u0447\u0442\u043e\u0431\u044b \u043f\u0440\u043e\u0432\u0435\u0440\u0438\u0442\u044c, \u043c\u043e\u0436\u043d\u043e \u043b\u0438 \u0442\u0435\u043e\u0440\u0435\u0442\u0438\u0447\u0435\u0441\u043a\u0438 \u043f\u043e\u0441\u0442\u0430\u0432\u0438\u0442\u044c \u0433\u0440\u0443\u043f\u043f\u0443 \u043d\u0443\u0436\u043d\u043e\u0433\u043e \u0440\u0430\u0437\u043c\u0435\u0440\u0430 \u0432 \u043d\u0443\u0436\u043d\u043e\u0435 \u043c\u0435\u0441\u0442\u043e. \u0412\u0441\u0435 \u0447\u0442\u043e \u0438\u043c \u043d\u0430\u0434\u043e \u0441\u0434\u0435\u043b\u0430\u0442\u044c \u2014 \u043f\u0440\u043e\u0432\u0435\u0440\u0438\u0442\u044c, \u0447\u0442\u043e \u0432 \u0443\u043a\u0430\u0437\u0430\u043d\u043d\u043e\u043c \u0438\u043d\u0442\u0435\u0440\u0432\u0430\u043b\u0435 \u043a\u043b\u0435\u0442\u043e\u043a \u043d\u0435\u0442 &#171;100% \u0431\u0435\u043b\u043e\u0439&#187; \u043a\u043b\u0435\u0442\u043a\u0438 (\u0434\u043b\u044f \u043f\u0435\u0440\u0432\u043e\u0439 \u0444\u0443\u043d\u043a\u0446\u0438\u0438) \u0438\u043b\u0438 &#171;100% \u0447\u0435\u0440\u043d\u043e\u0439&#187; (\u0434\u043b\u044f \u0432\u0442\u043e\u0440\u043e\u0439). \u0417\u043d\u0430\u0447\u0438\u0442, \u043e\u043d\u0438 \u043c\u043e\u0433\u0443\u0442 \u0440\u0430\u0431\u043e\u0442\u0430\u0442\u044c \u0437\u0430 <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/655\/b80\/5d6\/655b805d68b4b00a4e90f64eefbc6f1c.svg\" alt=\"$O(1)$\" data-tex=\"inline\"><\/math>, \u044d\u0442\u043e \u043c\u043e\u0436\u043d\u043e \u0441\u0434\u0435\u043b\u0430\u0442\u044c \u0441 \u043f\u043e\u043c\u043e\u0449\u044c\u044e \u0447\u0430\u0441\u0442\u0438\u0447\u043d\u044b\u0445 \u0441\u0443\u043c\u043c:<\/p>\n<p>  <\/p>\n<div class=\"spoiler\"><b class=\"spoiler_title\">CanInsertBlack<\/b><\/p>\n<div class=\"spoiler_text\">\n<pre><code class=\"python\">white_counter = [ 0, 0, ..., 0 ]  # \u041c\u0430\u0441\u0441\u0438\u0432 \u0434\u043b\u0438\u043d\u044b n                                def PrecalcWhite():                                                                  for i in range(0, (n-1)):                                                                 if is_anyway_white[i]:  # 1, \u0435\u0441\u043b\u0438 i-\u0430\u044f \u043a\u043b\u0435\u0442\u043a\u0430 100% \u0431\u0435\u043b\u0430\u044f                             white_counter[i]++                                                           if i &gt; 0:                                                                            white_counter[i] += white_counter[i - 1]                              def CanInsertBlack(cell, len):                                                       # \u041e\u043f\u0443\u0441\u043a\u0430\u0435\u043c \u043f\u0440\u043e\u0432\u0435\u0440\u043a\u0443 \u043a\u043e\u0440\u0440\u0435\u043a\u0442\u043d\u043e\u0441\u0442\u0438 \u0433\u0440\u0430\u043d\u0438\u0446 [cell, cell + len - 1]                   ans = white_counter[cell + len - 1]                                              if cell &gt; 0:                                                                         ans -= white_counter[cell - 1]                                               # \u0412 ans - \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e \u0431\u0435\u043b\u044b\u0445 \u043a\u043b\u0435\u0442\u043e\u043a \u043e\u0442 cell \u0434\u043e (cell + len - 1)                    return ans == 0        <\/code><\/pre>\n<\/div>\n<\/div>\n<p>  <\/p>\n<p>\u0422\u0430\u043a\u043e\u0435 \u0436\u0435 \u043a\u043e\u043b\u0434\u0443\u043d\u0441\u0442\u0432\u043e \u0441 \u0447\u0430\u0441\u0442\u0438\u0447\u043d\u044b\u043c\u0438 \u0441\u0443\u043c\u043c\u0430\u043c\u0438 \u0436\u0434\u0435\u0442 \u0441\u0442\u0440\u043e\u043a\u0438 \u0432\u0438\u0434\u0430<\/p>\n<p>  <\/p>\n<pre><code class=\"python\">can_place_black[cell .. (cell + len[group] - 1)] = True<\/code><\/pre>\n<p>  <\/p>\n<p>\u0422\u0443\u0442 \u043c\u043e\u0436\u043d\u043e \u0432\u043c\u0435\u0441\u0442\u043e <code>= True<\/code> \u0443\u0432\u0435\u043b\u0438\u0447\u0438\u0432\u0430\u0442\u044c \u0447\u0438\u0441\u043b\u043e \u043d\u0430 1. \u0410 \u0435\u0441\u043b\u0438 \u043d\u0430\u043c \u043d\u0430\u0434\u043e \u043f\u0440\u043e\u0438\u0437\u0432\u0435\u0441\u0442\u0438 \u043c\u043d\u043e\u0433\u043e \u043f\u0440\u0438\u0431\u0430\u0432\u043b\u0435\u043d\u0438\u0439 \u043d\u0430 \u043e\u0442\u0440\u0435\u0437\u043a\u0435 \u0432 \u043d\u0435\u043a\u043e\u043c \u043c\u0430\u0441\u0441\u0438\u0432\u0435 <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/d67\/c8a\/b12\/d67c8ab1243e9d8d651ff2879306d11d.svg\" alt=\"$array$\" data-tex=\"inline\"><\/math>, \u0438 \u043f\u0440\u0438\u0442\u043e\u043c \u044d\u0442\u043e\u0442 \u043c\u0430\u0441\u0441\u0438\u0432 \u043c\u044b \u043d\u0438\u043a\u0430\u043a \u043d\u0435 \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u0435\u043c \u043f\u0435\u0440\u0435\u0434 \u0440\u0430\u0437\u043d\u044b\u043c\u0438 \u043f\u0440\u0438\u0431\u0430\u0432\u043b\u0435\u043d\u0438\u044f\u043c\u0438 (\u043f\u0440\u043e \u0442\u0430\u043a\u043e\u0435 \u0433\u043e\u0432\u043e\u0440\u044f\u0442, \u0447\u0442\u043e \u044d\u0442\u0430 \u0437\u0430\u0434\u0430\u0447\u0430 &#171;\u0440\u0435\u0448\u0430\u0435\u0442\u0441\u044f \u043e\u0444\u0444\u043b\u0430\u0439\u043d&#187;), \u0442\u043e \u0432\u043c\u0435\u0441\u0442\u043e \u0446\u0438\u043a\u043b\u0430:<\/p>\n<p>  <\/p>\n<pre><code class=\"python\"># \u041c\u043d\u043e\u0433\u043e \u0440\u0430\u0437 \u0442\u0430\u043a\u043e\u0439 \u043a\u043e\u0434 for i in range(L, R + 1):     array[i]++<\/code><\/pre>\n<p>  <\/p>\n<p>\u041c\u043e\u0436\u043d\u043e \u0441\u0434\u0435\u043b\u0430\u0442\u044c \u0442\u0430\u043a:<\/p>\n<p>  <\/p>\n<pre><code class=\"python\"># \u041c\u043d\u043e\u0433\u043e \u0440\u0430\u0437 \u0442\u0430\u043a\u043e\u0439 \u043a\u043e\u0434 array[L]++ array[R + 1]-- # \u041f\u043e\u0441\u043b\u0435 \u0432\u0441\u0435\u0445 \u043f\u0440\u0438\u0431\u0430\u0432\u043b\u0435\u043d\u0438\u0439 for i in range(1, n):     array[i] += array[i - 1]<\/code><\/pre>\n<p>  <\/p>\n<p>\u0422\u0430\u043a\u0438\u043c \u043e\u0431\u0440\u0430\u0437\u043e\u043c, \u0440\u0430\u0431\u043e\u0442\u0430\u0435\u0442 \u0432\u0435\u0441\u044c \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u0437\u0430 <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/1b9\/294\/a7f\/1b9294a7f282e7766a8bb4eef7ec9974.svg\" alt=\"$O(k*n)$\" data-tex=\"inline\"><\/math>, \u0433\u0434\u0435 <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/16d\/a50\/7b2\/16da507b2fc389688ef0659939dcc647.svg\" alt=\"$k$\" data-tex=\"inline\"><\/math> \u2014 \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e \u0433\u0440\u0443\u043f\u043f \u0447\u0435\u0440\u043d\u044b\u0445 \u043a\u043b\u0435\u0442\u043e\u043a, <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/08d\/9fa\/efb\/08d9faefbe272bdf8fbb80773542e343.svg\" alt=\"$n$\" data-tex=\"inline\"><\/math> \u2014 \u0434\u043b\u0438\u043d\u0430 \u0441\u0442\u0440\u043e\u043a\u0438. \u0418 \u043c\u044b \u043f\u0440\u043e\u0445\u043e\u0434\u0438\u043c \u043d\u0430 \u043f\u043e\u043b\u0443\u0444\u0438\u043d\u0430\u043b ACM ICPC \u0438\u043b\u0438 \u043f\u043e\u043b\u0443\u0447\u0430\u0435\u043c \u0431\u0440\u043e\u043d\u0437\u0443 \u043c\u0435\u0436\u043d\u0430\u0440\u0430. <a href=\"https:\/\/github.com\/Izaron\/ACM-ICPC\/blob\/master\/Timus%20Online%20Judge\/Volume%206\/1508.%20Japanese%20Puzzle.java\">\u0420\u0435\u0448\u0435\u043d\u0438\u0435 ACM (Java)<\/a>. <a href=\"https:\/\/github.com\/Izaron\/ACM-ICPC\/blob\/master\/International%20Olympiad%20in%20Informatics\/IOI%202016\/paint.cpp\">\u0420\u0435\u0448\u0435\u043d\u0438\u0435 IOI (C++)<\/a>.<\/p>\n<p>  <\/p>\n<h4 id=\"odna-stroka-mnogo-cvetov\">\u041e\u0434\u043d\u0430 \u0441\u0442\u0440\u043e\u043a\u0430, \u043c\u043d\u043e\u0433\u043e \u0446\u0432\u0435\u0442\u043e\u0432<\/h4>\n<p>  <\/p>\n<p>\u041f\u0440\u0438 \u043f\u0435\u0440\u0435\u0445\u043e\u0434\u0435 \u043d\u0430 \u043c\u043d\u043e\u0433\u043e\u0446\u0432\u0435\u0442\u043d\u044b\u0435 \u043d\u043e\u043d\u043e\u0433\u0440\u0430\u043c\u043c\u044b, \u043a\u043e\u0442\u043e\u0440\u044b\u0445 \u0435\u0449\u0435 \u043d\u0435\u043f\u043e\u043d\u044f\u0442\u043d\u043e, \u043a\u0430\u043a \u0440\u0435\u0448\u0430\u0442\u044c, \u043c\u044b \u0443\u0437\u043d\u0430\u0435\u043c \u0441\u0442\u0440\u0430\u0448\u043d\u0443\u044e \u043f\u0440\u0430\u0432\u0434\u0443 \u2014 \u043e\u043a\u0430\u0437\u044b\u0432\u0430\u0435\u0442\u0441\u044f, \u043d\u0430 \u043a\u0430\u0436\u0434\u0443\u044e \u0441\u0442\u0440\u043e\u043a\u0443 \u043c\u0430\u0433\u0438\u0447\u0435\u0441\u043a\u0438\u043c \u043e\u0431\u0440\u0430\u0437\u043e\u043c \u0432\u043b\u0438\u044f\u044e\u0442 \u0432\u0441\u0435 \u0441\u0442\u043e\u043b\u0431\u0446\u044b! \u042d\u0442\u043e \u043f\u043e\u043d\u044f\u0442\u043d\u0435\u0435 \u0447\u0435\u0440\u0435\u0437 \u043f\u0440\u0438\u043c\u0435\u0440:<\/p>\n<p>  <\/p>\n<div style=\"text-align:center;\"><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/webt\/6m\/ve\/_d\/6mve_d8spu5wyqai1osmtppdgr8.png\"><\/div>\n<p>  <\/p>\n<p><em>\u0418\u0441\u0442\u043e\u0447\u043d\u0438\u043a \u2014 <a href=\"http:\/\/www.nonograms.ru\/methods\">\u041c\u0435\u0442\u043e\u0434\u044b \u0440\u0435\u0448\u0435\u043d\u0438\u044f \u044f\u043f\u043e\u043d\u0441\u043a\u0438\u0445 \u043a\u0440\u043e\u0441\u0441\u0432\u043e\u0440\u0434\u043e\u0432<\/a><\/em><\/p>\n<p>  <\/p>\n<p>\u0412 \u0442\u043e \u0432\u0440\u0435\u043c\u044f \u043a\u0430\u043a \u0434\u0432\u0443\u0445\u0446\u0432\u0435\u0442\u043d\u044b\u0435 \u043d\u043e\u043d\u043e\u0433\u0440\u0430\u043c\u043c\u044b \u043d\u043e\u0440\u043c\u0430\u043b\u044c\u043d\u043e \u043e\u0431\u0445\u043e\u0434\u0438\u043b\u0438\u0441\u044c \u0431\u0435\u0437 \u044d\u0442\u043e\u0433\u043e, \u0438\u043c \u043d\u0435 \u043d\u0430\u0434\u043e \u0431\u044b\u043b\u043e \u043e\u0433\u043b\u044f\u0434\u044b\u0432\u0430\u0442\u044c\u0441\u044f \u043d\u0430 \u043e\u0440\u0442\u043e\u0433\u043e\u043d\u0430\u043b\u044c\u043d\u044b\u0445 \u0434\u0440\u0443\u0437\u0435\u0439.<br \/>  \u041d\u0430 \u043a\u0430\u0440\u0442\u0438\u043d\u043a\u0435 \u0432\u0438\u0434\u043d\u043e, \u0447\u0442\u043e \u0443 \u043b\u0435\u0432\u043e\u0433\u043e \u043f\u0440\u0438\u043c\u0435\u0440\u0430 \u0442\u0440\u0438 \u043a\u0440\u0430\u0439\u043d\u0438\u0435 \u043f\u0440\u0430\u0432\u044b\u0435 \u043a\u043b\u0435\u0442\u043a\u0438 \u043f\u0443\u0441\u0442\u044b\u0435, \u043f\u043e\u0442\u043e\u043c\u0443 \u0447\u0442\u043e \u043f\u043e\u043b\u043e\u043c\u0430\u0435\u0442\u0441\u044f \u043a\u043e\u043d\u0444\u0438\u0433\u0443\u0440\u0430\u0446\u0438\u044f, \u0435\u0441\u043b\u0438 \u043e\u043a\u0440\u0430\u0441\u0438\u0442\u044c \u044d\u0442\u0438 \u043a\u043b\u0435\u0442\u043a\u0438 \u0432 <del>\u0442\u0435 \u0446\u0432\u0435\u0442\u0430, \u0432 \u043a\u043e\u0442\u043e\u0440\u044b\u0445 \u043e\u043a\u0440\u0430\u0441\u0438\u0442\u044c \u0441\u0435\u0431\u044f<\/del> \u043d\u0435-\u0431\u0435\u043b\u044b\u0439 \u0446\u0432\u0435\u0442.<\/p>\n<p>  <\/p>\n<p>\u041d\u043e \u044d\u0442\u043e\u0442 \u043f\u0440\u0438\u043a\u043e\u043b \u043c\u0430\u0442\u0435\u043c\u0430\u0442\u0438\u0447\u0435\u0441\u043a\u0438 \u0440\u0430\u0437\u0440\u0435\u0448\u0438\u043c \u2014 \u043d\u0430\u0434\u043e \u043a\u0430\u0436\u0434\u043e\u0439 \u043a\u043b\u0435\u0442\u043a\u0435 \u0432\u044b\u0434\u0430\u0442\u044c \u0447\u0438\u0441\u043b\u043e, \u0433\u0434\u0435 <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/bf8\/3b5\/32c\/bf83b532cd867d34004f8eded8c5c79a.svg\" alt=\"$i$\" data-tex=\"inline\"><\/math>-\u0439 \u0431\u0438\u0442 \u0431\u0443\u0434\u0435\u0442 \u043e\u0437\u043d\u0430\u0447\u0430\u0442\u044c, \u043c\u043e\u0436\u043d\u043e \u043b\u0438 \u0434\u0430\u0442\u044c \u044d\u0442\u043e\u0439 \u043a\u043b\u0435\u0442\u043a\u0435 <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/bf8\/3b5\/32c\/bf83b532cd867d34004f8eded8c5c79a.svg\" alt=\"$i$\" data-tex=\"inline\"><\/math>-\u0439 \u0446\u0432\u0435\u0442. \u0418\u0437\u043d\u0430\u0447\u0430\u043b\u044c\u043d\u043e \u0443 \u0432\u0441\u0435\u0445 \u043a\u043b\u0435\u0442\u043e\u043a \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0435 <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/49d\/0f9\/d68\/49d0f9d68e1cc46443f0479177b3eeb5.svg\" alt=\"$2^{colors} - 1$\" data-tex=\"inline\"><\/math>. \u0420\u0435\u0448\u0435\u043d\u0438\u0435 \u0434\u0438\u043d\u0430\u043c\u0438\u043a\u0438 \u043f\u043e\u043c\u0435\u043d\u044f\u0435\u0442\u0441\u044f \u043d\u0435 \u043e\u0447\u0435\u043d\u044c \u0441\u0438\u043b\u044c\u043d\u043e.<\/p>\n<p>  <\/p>\n<p>\u041c\u043e\u0436\u043d\u043e \u0431\u0443\u0434\u0435\u0442 \u043d\u0430\u0431\u043b\u044e\u0434\u0430\u0442\u044c \u0441\u043b\u0435\u0434\u0443\u044e\u0449\u0438\u0439 \u044d\u0444\u0444\u0435\u043a\u0442: \u0432 \u044d\u0442\u043e\u043c \u0436\u0435 \u043b\u0435\u0432\u043e\u043c \u043f\u0440\u0438\u043c\u0435\u0440\u0435, \u043f\u043e \u0432\u0435\u0440\u0441\u0438\u0438 \u0441\u0442\u0440\u043e\u043a, \u043a\u0440\u0430\u0439\u043d\u044f\u044f \u0441\u043f\u0440\u0430\u0432\u0430 \u043a\u043b\u0435\u0442\u043a\u0430 \u043c\u043e\u0436\u0435\u0442 \u0438\u043c\u0435\u0442\u044c \u043b\u0438\u0431\u043e \u0441\u0438\u043d\u0438\u0439 \u043b\u0438\u0431\u043e \u0431\u0435\u043b\u044b\u0439 \u0446\u0432\u0435\u0442.<br \/>  \u041f\u043e \u0432\u0435\u0440\u0441\u0438\u0438 \u0441\u0442\u043e\u043b\u0431\u0446\u043e\u0432, \u044d\u0442\u0430 \u043a\u043b\u0435\u0442\u043a\u0430 \u0438\u043c\u0435\u0435\u0442 \u043b\u0438\u0431\u043e \u0437\u0435\u043b\u0435\u043d\u044b\u0439, \u043b\u0438\u0431\u043e \u0431\u0435\u043b\u044b\u0439 \u0446\u0432\u0435\u0442.<br \/>  \u041f\u043e \u0432\u0435\u0440\u0441\u0438\u0438 \u0437\u0434\u0440\u0430\u0432\u043e\u0433\u043e \u0441\u043c\u044b\u0441\u043b\u0430, \u044d\u0442\u0430 \u043a\u043b\u0435\u0442\u043a\u0430 \u0431\u0443\u0434\u0435\u0442 \u0438\u043c\u0435\u0442\u044c \u0442\u043e\u043b\u044c\u043a\u043e \u0431\u0435\u043b\u044b\u0439 \u0446\u0432\u0435\u0442. \u0418 \u0434\u0430\u043b\u044c\u0448\u0435 \u043c\u044b \u043f\u0440\u043e\u0434\u043e\u043b\u0436\u0430\u0435\u043c \u0432\u044b\u0447\u0438\u0441\u043b\u044f\u0442\u044c \u043e\u0442\u0432\u0435\u0442.<\/p>\n<p>  <\/p>\n<p>\u0415\u0441\u043b\u0438 \u0441\u0447\u0438\u0442\u0430\u0442\u044c \u043d\u0443\u043b\u0435\u0432\u043e\u0439 \u0431\u0438\u0442 &#171;\u0431\u0435\u043b\u044b\u043c&#187;, \u043f\u0435\u0440\u0432\u044b\u0439 &#171;\u0441\u0438\u043d\u0438\u043c&#187;, \u0432\u0442\u043e\u0440\u043e\u0439 &#171;\u0437\u0435\u043b\u0435\u043d\u044b\u0439&#187;, \u0442\u043e \u0441\u0442\u0440\u043e\u043a\u0430 \u0432\u044b\u0447\u0438\u0441\u043b\u0438\u043b\u0430 \u0434\u043b\u044f \u043f\u043e\u0441\u043b\u0435\u0434\u043d\u0435\u0439 \u043a\u043b\u0435\u0442\u043a\u0438 \u0441\u043e\u0441\u0442\u043e\u044f\u043d\u0438\u0435 <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/31f\/c6e\/0dc\/31fc6e0dcd38074f3ec8ac7a3d3bb35f.svg\" alt=\"$011$\" data-tex=\"inline\"><\/math>, \u0430 \u0441\u0442\u043e\u043b\u0431\u0435\u0446 <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/45f\/345\/fac\/45f345facdb7bebfb7e62b1a35e76d0d.svg\" alt=\"$101$\" data-tex=\"inline\"><\/math>. \u0417\u043d\u0430\u0447\u0438\u0442, \u0440\u0435\u0430\u043b\u044c\u043d\u043e \u0443 \u044d\u0442\u043e\u0439 \u043a\u043b\u0435\u0442\u043a\u0438 \u0441\u043e\u0441\u0442\u043e\u044f\u043d\u0438\u0435 <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/1c9\/c1b\/8e1\/1c9c1b8e1304890be6e9b166d8dcc390.svg\" alt=\"$011\\&amp;101 = 001$\" data-tex=\"inline\"><\/math><\/p>\n<p>  <\/p>\n<div class=\"spoiler\"><b class=\"spoiler_title\">\u041f\u0441\u0435\u0432\u0434\u043e\u043a\u043e\u0434<\/b><\/p>\n<div class=\"spoiler_text\">\n<pre><code class=\"python\">source = [...]  # \u041d\u0430\u0447\u0430\u043b\u044c\u043d\u044b\u0435 \u0441\u043e\u0441\u0442\u043e\u044f\u043d\u0438\u044f result = [0, 0, ..., 0]  # \u0418\u0442\u043e\u0433\u043e\u0432\u044b\u0435 \u0441\u043e\u0441\u0442\u043e\u044f\u043d\u0438\u044f len = [...]  # \u0414\u043b\u0438\u043d\u044b \u0433\u0440\u0443\u043f\u043f \u043a\u043b\u0435\u0442\u043e\u043a clrs = [...]  # \u0426\u0432\u0435\u0442\u0430 \u0433\u0440\u0443\u043f\u043f \u043a\u043b\u0435\u0442\u043e\u043a  def CanInsertColor(color, cell, len):                                                       for i in range(cell, cell + len):         if (source[i] &amp; (1 &lt;&lt; color)) == 0:  # \u0412 \u043d\u0435\u043a\u043e\u0442\u043e\u0440\u043e\u0439 \u043a\u043b\u0435\u0442\u043a\u0435 \u0446\u0432\u0435\u0442 color \u043f\u043e\u0441\u0442\u0430\u0432\u0438\u0442\u044c \u043d\u0435 \u043c\u043e\u0436\u0435\u043c             return False;     return True  def PlaceColor(color, cell, len):                                                                                                                           for i in range(cell, cell + len):                                                    result[i] |= (1 &lt;&lt; color)  # \u0414\u043e\u0431\u0430\u0432\u043b\u044f\u0435\u043c \u0446\u0432\u0435\u0442 color \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u0435\u0439 OR  def EpicWinExtended(group, cell):                                                    if cell &gt;= last_cell: # \u0423\u0441\u043b\u043e\u0432\u0438\u0435 \u0432\u044b\u0438\u0433\u0440\u044b\u0448\u0430                                             return group == group_size                                                    win = False                                                                       # \u041c\u043e\u0436\u0435\u043c \u043b\u0438 \u0432\u0441\u0442\u0430\u0432\u0438\u0442\u044c \u0433\u0440\u0443\u043f\u043f\u0443 \u0432 \u044d\u0442\u043e\u0439 \u043f\u043e\u0437\u0438\u0446\u0438\u0438                                        if group &lt; group_size  # \u0413\u0440\u0443\u043f\u043f\u044b \u0435\u0449\u0435 \u0435\u0441\u0442\u044c                                                 and CanInsertColor(clrs[group], cell, len[group])  # \u0412\u0441\u0442\u0430\u0432\u043a\u0430 \u0447\u0435\u0440\u043d\u043e\u0439 \u0433\u0440\u0443\u043f\u043f\u044b             and SequenceCheck()  # \u0415\u0441\u043b\u0438 \u0441\u043b\u0435\u0434\u0443\u044e\u0449\u0430\u044f \u0433\u0440\u0443\u043f\u043f\u0430 \u0438\u043c\u0435\u0435\u0442 \u0442\u043e\u0442 \u0436\u0435 \u0446\u0432\u0435\u0442, \u043f\u0440\u043e\u0432\u0435\u0440\u044f\u0435\u043c                                  # \u0447\u0442\u043e \u043c\u043e\u0436\u0435\u043c \u043f\u043e\u0441\u043b\u0435 \u044d\u0442\u043e\u0439 \u0433\u0440\u0443\u043f\u043f\u044b \u043f\u043e\u0441\u0442\u0430\u0432\u0438\u0442\u044c \u0431\u0435\u043b\u0443\u044e \u043a\u043b\u0435\u0442\u043a\u0443             and EpicWin(group + 1, cell + len[group]):  # \u041c\u043e\u0436\u043d\u043e \u0437\u0430\u043f\u043e\u043b\u043d\u0438\u0442\u044c \u0434\u0430\u043b\u0435\u0435          win = True                                                                       PlaceColor(clrs[group], cell, len[group])                                        PlaceColor(0, cell + len[group], 1)  # \u0411\u0435\u043b\u0430\u044f \u043a\u043b\u0435\u0442\u043a\u0430 - \u0442\u043e\u043b\u044c\u043a\u043e \u0435\u0441\u043b\u0438 \u043d\u0443\u0436\u043d\u043e       # \u041c\u043e\u0436\u0435\u043c \u043b\u0438 \u0432\u0441\u0442\u0430\u0432\u0438\u0442\u044c \u0431\u0435\u043b\u0443\u044e \u043a\u043b\u0435\u0442\u043a\u0443 \u0432 \u044d\u0442\u043e\u0439 \u043f\u043e\u0437\u0438\u0446\u0438\u0438                                  # \u0411\u0435\u043b\u0430\u044f \u043a\u043b\u0435\u0442\u043a\u0430 - \u0431\u0438\u0442 0                                                           if CanInsertWhite(0, cell, 1)                                                            and EpicWinExtended(group, cell + 1):                                                                                                               win = True                                                                       PlaceColor(0, cell, 1)                                                        return win                      <\/code><\/pre>\n<\/div>\n<\/div>\n<p>  <\/p>\n<h4 id=\"mnogo-strok-mnogo-cvetov\">\u041c\u043d\u043e\u0433\u043e \u0441\u0442\u0440\u043e\u043a, \u043c\u043d\u043e\u0433\u043e \u0446\u0432\u0435\u0442\u043e\u0432<\/h4>\n<p>  <\/p>\n<p>\u041f\u043e\u0441\u0442\u043e\u044f\u043d\u043d\u043e \u0434\u0435\u043b\u0430\u0435\u043c \u043e\u0431\u043d\u043e\u0432\u043b\u0435\u043d\u0438\u0435 \u0441\u043e\u0441\u0442\u043e\u044f\u043d\u0438\u0439 \u0432\u0441\u0435\u0445 \u0441\u0442\u0440\u043e\u043a \u0438 \u0441\u0442\u043e\u043b\u0431\u0446\u043e\u0432, \u043e\u043f\u0438\u0441\u0430\u043d\u043d\u043e\u0435 \u0432 \u043f\u0440\u043e\u0448\u043b\u043e\u043c \u043f\u0443\u043d\u043a\u0442\u0435, \u043f\u043e\u043a\u0430 \u043d\u0435 \u043e\u0441\u0442\u0430\u043d\u0435\u0442\u0441\u044f \u043d\u0438 \u043e\u0434\u043d\u043e\u0439 \u043a\u043b\u0435\u0442\u043a\u0438 \u0441 \u0431\u043e\u043b\u044c\u0448\u0435 \u0447\u0435\u043c \u043e\u0434\u043d\u0438\u043c \u0431\u0438\u0442\u043e\u043c. \u0412 \u043a\u0430\u0436\u0434\u043e\u0439 \u0438\u0442\u0435\u0440\u0430\u0446\u0438\u0438 \u043f\u043e\u0441\u043b\u0435 \u043e\u0431\u043d\u043e\u0432\u043b\u0435\u043d\u0438\u044f \u0432\u0441\u0435\u0445 \u0441\u0442\u0440\u043e\u043a \u0438 \u0441\u0442\u043e\u043b\u0431\u0446\u043e\u0432, \u043e\u0431\u043d\u043e\u0432\u043b\u044f\u0435\u043c \u0441\u043e\u0441\u0442\u043e\u044f\u043d\u0438\u044f \u0432\u0441\u0435\u0445 \u043a\u043b\u0435\u0442\u043e\u043a \u0432 \u043d\u0438\u0445 \u0447\u0435\u0440\u0435\u0437 \u0432\u0437\u0430\u0438\u043c\u043d\u044b\u0439 AND.<\/p>\n<p>  <\/p>\n<h2 id=\"pervye-rezultaty\">\u041f\u0435\u0440\u0432\u044b\u0435 \u0440\u0435\u0437\u0443\u043b\u044c\u0442\u0430\u0442\u044b<\/h2>\n<p>  <\/p>\n<p>\u0414\u043e\u043f\u0443\u0441\u0442\u0438\u043c, \u0447\u0442\u043e \u043a\u043e\u0434 \u043c\u044b \u043f\u0438\u0441\u0430\u043b\u0438 \u043d\u0435 \u043a\u0430\u043a \u0434\u044f\u0442\u043b\u044b, \u0442\u043e \u0435\u0441\u0442\u044c \u043d\u0438\u043a\u0443\u0434\u0430 \u043f\u043e \u043e\u0448\u0438\u0431\u043a\u0435 \u043e\u0431\u044a\u0435\u043a\u0442\u044b \u043d\u0435 \u043a\u043e\u043f\u0438\u0440\u0443\u0435\u043c \u0432\u043c\u0435\u0441\u0442\u043e \u043f\u0435\u0440\u0435\u0434\u0430\u0447\u0438 \u043f\u043e \u0441\u0441\u044b\u043b\u043a\u0435, \u043d\u0438\u0433\u0434\u0435 \u0432 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0435 \u043d\u0435 \u043a\u043e\u0441\u044f\u0447\u0438\u043c, \u0432\u0435\u043b\u043e\u0441\u0438\u043f\u0435\u0434\u043e\u0432 \u043d\u0435 \u0438\u0437\u043e\u0431\u0440\u0435\u0442\u0430\u0435\u043c, \u0434\u043b\u044f \u0431\u0438\u0442\u043e\u0432\u044b\u0445 \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u0439 \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u0435\u043c <code>__builtin_popcount<\/code> \u0438 <code>__builtin_ctz<\/code> (<a href=\"https:\/\/gcc.gnu.org\/onlinedocs\/gcc\/Other-Builtins.html\">\u043e\u0441\u043e\u0431\u0435\u043d\u043d\u043e\u0441\u0442\u0438 gcc<\/a>), \u0432\u0441\u0435 \u0430\u043a\u043a\u0443\u0440\u0430\u0442\u043d\u043e \u0438 \u0447\u0438\u0441\u0442\u043e.<\/p>\n<p>  <\/p>\n<p>\u041f\u043e\u0441\u043c\u043e\u0442\u0440\u0438\u043c \u043d\u0430 \u0432\u0440\u0435\u043c\u044f \u0440\u0430\u0431\u043e\u0442\u044b \u043f\u0440\u043e\u0433\u0440\u0430\u043c\u043c\u044b, \u043a\u043e\u0442\u043e\u0440\u0430\u044f \u0441\u0447\u0438\u0442\u044b\u0432\u0430\u0435\u0442 \u0438\u0437 \u0444\u0430\u0439\u043b\u0430 \u0433\u043e\u043b\u043e\u0432\u043e\u043b\u043e\u043c\u043a\u0443 \u0438 \u0440\u0435\u0448\u0430\u0435\u0442 \u0435\u0435 \u043f\u043e\u043b\u043d\u043e\u0441\u0442\u044c\u044e. \u0421\u0442\u043e\u0438\u0442 \u043e\u0446\u0435\u043d\u0438\u0442\u044c \u0434\u043e\u0441\u0442\u043e\u0438\u043d\u0441\u0442\u0432\u0430 \u043c\u0430\u0448\u0438\u043d\u043a\u0438, \u043d\u0430 \u043a\u043e\u0442\u043e\u0440\u043e\u0439 \u0432\u0441\u0435 \u044d\u0442\u043e \u0434\u043e\u0431\u0440\u043e \u043f\u0438\u0441\u0430\u043b\u043e\u0441\u044c \u0438 \u0442\u0435\u0441\u0442\u0438\u0440\u043e\u0432\u0430\u043b\u0430\u0441\u044c:<\/p>\n<p>  <\/p>\n<div class=\"spoiler\"><b class=\"spoiler_title\">\u0421\u043f\u0435\u0446\u0438\u0444\u0438\u043a\u0430\u0446\u0438\u044f \u0434\u0432\u0438\u0436\u043a\u0430 \u043c\u043e\u0435\u0433\u043e 1932 Harley Davidson Model B Classic Motorcycle<\/b><\/p>\n<div class=\"spoiler_text\">\n<pre><code class=\"bash\">RAM - 4GB \u041f\u0440\u043e\u0446\u0435\u0441\u0441\u043e\u0440 - AMD E1-2500, \u0447\u0430\u0441\u0442\u043e\u0442\u0430 1400MHz \u041a\u044d\u0448 L1 - 128KiB, 1GHz \u041a\u044d\u0448 L2 - 1MiB, 1GHz \u042f\u0434\u0435\u0440 - 2, \u043f\u043e\u0442\u043e\u043a\u043e\u0432 - 2 \u041f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u043b\u0435\u043d \u043a\u0430\u043a \u00ab\u043c\u0430\u043b\u043e\u043f\u0440\u043e\u0438\u0437\u0432\u043e\u0434\u0438\u0442\u0435\u043b\u044c\u043d\u0430\u044f SoC \u0434\u043b\u044f \u043a\u043e\u043c\u043f\u0430\u043a\u0442\u043d\u044b\u0445 \u043d\u043e\u0443\u0442\u0431\u0443\u043a\u043e\u0432\u00bb \u0432 \u0441\u0435\u0440\u0435\u0434\u0438\u043d\u0435 2013 \u0433\u043e\u0434\u0430 \u0421\u0442\u043e\u0438\u043c\u043e\u0441\u0442\u044c \u043f\u0440\u043e\u0446\u0435\u0441\u0441\u043e\u0440\u0430 28 \u0434\u043e\u043b\u043b\u0430\u0440\u043e\u0432<\/code><\/pre>\n<\/div>\n<\/div>\n<p>  <\/p>\n<p>\u041f\u043e\u043d\u044f\u0442\u043d\u043e, \u0447\u0442\u043e \u0442\u0430\u043a\u043e\u0439 \u0441\u0443\u043f\u0435\u0440\u043a\u043e\u043c\u043f\u044c\u044e\u0442\u0435\u0440 \u0431\u044b\u043b \u0432\u044b\u0431\u0440\u0430\u043d, \u043f\u043e\u0442\u043e\u043c\u0443 \u0447\u0442\u043e \u043e\u043f\u0442\u0438\u043c\u0438\u0437\u0430\u0446\u0438\u0438 \u043d\u0430 \u043d\u0435\u043c \u0438\u043c\u0435\u044e\u0442 \u0431\u043e\u043b\u044c\u0448\u0438\u0439 \u044d\u0444\u0444\u0435\u043a\u0442, \u0447\u0435\u043c \u043d\u0430 \u043b\u0435\u0442\u0430\u044e\u0449\u0435\u0439 \u0448\u0430\u0439\u0442\u0430\u043d-\u043c\u0430\u0448\u0438\u043d\u0435.<\/p>\n<p>  <\/p>\n<p>\u0418\u0442\u0430\u043a, \u043f\u043e\u0441\u043b\u0435 \u043f\u0440\u043e\u0433\u043e\u043d\u0430 \u043d\u0430\u0448\u0435\u0433\u043e \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0430 \u043d\u0430 \u0441\u0430\u043c\u043e\u043c \u0441\u043b\u043e\u0436\u043d\u043e\u043c \u043a\u0440\u043e\u0441\u0441\u0432\u043e\u0440\u0434\u0435 (\u043f\u043e \u0432\u0435\u0440\u0441\u0438\u0438 nonograms.ru), \u043f\u043e\u043b\u0443\u0447\u0430\u0435\u043c \u043d\u0435 \u043e\u0447\u0435\u043d\u044c \u0445\u043e\u0440\u043e\u0448\u0438\u0439 \u0440\u0435\u0437\u0443\u043b\u044c\u0442\u0430\u0442 \u2014 \u043e\u0442 <strong>47<\/strong> \u0434\u043e <strong>60<\/strong> \u0441\u0435\u043a\u0443\u043d\u0434 (\u0432 \u044d\u0442\u043e \u0432\u0445\u043e\u0434\u0438\u0442 \u0441\u0447\u0438\u0442\u044b\u0432\u0430\u043d\u0438\u0435 \u0438\u0437 \u0444\u0430\u0439\u043b\u0430 \u0438 \u0440\u0435\u0448\u0435\u043d\u0438\u0435). \u041d\u0430\u0434\u043e \u0437\u0430\u043c\u0435\u0442\u0438\u0442\u044c, \u0447\u0442\u043e &#171;\u0441\u043b\u043e\u0436\u043d\u043e\u0441\u0442\u044c&#187; \u043d\u0430 \u0441\u0430\u0439\u0442\u0435 \u043f\u043e\u0441\u0447\u0438\u0442\u0430\u043d\u0430 \u0445\u043e\u0440\u043e\u0448\u043e \u2014 \u044d\u0442\u043e\u0442 \u0436\u0435 \u043a\u0440\u043e\u0441\u0441\u0432\u043e\u0440\u0434 \u0432\u043e \u0432\u0441\u0435\u0445 \u0432\u0435\u0440\u0441\u0438\u044f\u0445 \u043f\u0440\u043e\u0433\u0440\u0430\u043c\u043c\u044b \u0442\u0430\u043a \u0436\u0435 \u0431\u044b\u043b \u0441\u0430\u043c\u044b\u043c \u0442\u044f\u0436\u0435\u043b\u044b\u043c, \u0434\u0440\u0443\u0433\u0438\u0435 \u043d\u0430\u0438\u0431\u043e\u043b\u0435\u0435 \u0441\u043b\u043e\u0436\u043d\u044b\u0435 \u043a\u0440\u043e\u0441\u0441\u0432\u043e\u0440\u0434\u044b \u043f\u043e \u043c\u043d\u0435\u043d\u0438\u044e \u0430\u0440\u0445\u0438\u0432\u0430 \u0434\u0435\u0440\u0436\u0430\u043b\u0438\u0441\u044c \u0432 \u0442\u043e\u043f\u0435 \u043f\u043e \u0432\u0440\u0435\u043c\u0435\u043d\u0438.<\/p>\n<p>  <\/p>\n<div class=\"spoiler\"><b class=\"spoiler_title\">\u0426\u0432\u0435\u0442\u043d\u043e\u0439 \u043a\u0440\u043e\u0441\u0441\u0432\u043e\u0440\u0434 \u21169596, \u043d\u0430\u0438\u0431\u043e\u043b\u044c\u0448\u0430\u044f \u0441\u043b\u043e\u0436\u043d\u043e\u0441\u0442\u044c<\/b><\/p>\n<div class=\"spoiler_text\">\n<div style=\"text-align:center;\"><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/webt\/ar\/7n\/rx\/ar7nrxtbzch1wk8bsihz0puldt8.png\"><\/div>\n<\/div>\n<\/div>\n<p>  <\/p>\n<p>\u0414\u043b\u044f \u0431\u044b\u0441\u0442\u0440\u043e\u0433\u043e \u0442\u0435\u0441\u0442\u0438\u0440\u043e\u0432\u0430\u043d\u0438\u044f \u0431\u044b\u043b\u0430 \u0441\u0434\u0435\u043b\u0430\u043d\u0430 \u0444\u0443\u043d\u043a\u0446\u0438\u043e\u043d\u0430\u043b\u044c\u043d\u043e\u0441\u0442\u044c \u0434\u043b\u044f \u0431\u0435\u043d\u0447\u043c\u0430\u0440\u043a\u0430. \u0414\u043b\u044f \u043f\u043e\u043b\u0443\u0447\u0435\u043d\u0438\u044f \u0434\u0430\u043d\u043d\u044b\u0445 \u0434\u043b\u044f \u043d\u0435\u0433\u043e \u044f \u0441\u043f\u0435\u0446\u0438\u0430\u043b\u044c\u043d\u044b\u043c \u0441\u043a\u0440\u0438\u043f\u0442\u043e\u043c \u0441\u043f\u0430\u0440\u0441\u0438\u043b <strong>4683<\/strong> \u0446\u0432\u0435\u0442\u043d\u044b\u0445 \u043a\u0440\u043e\u0441\u0441\u0432\u043e\u0440\u0434\u0430 (\u0438\u0437 <strong>10906<\/strong>) \u0438 <strong>1406<\/strong> \u0447\u0435\u0440\u043d\u043e-\u0431\u0435\u043b\u044b\u0445 (\u0438\u0437 <strong>8293<\/strong>) \u0441 nonograms.ru (\u044d\u0442\u043e \u043e\u0434\u0438\u043d \u0438\u0437 \u043a\u0440\u0443\u043f\u043d\u0435\u0439\u0448\u0438\u0445 \u0430\u0440\u0445\u0438\u0432\u043e\u0432 \u043d\u043e\u043d\u043e\u0433\u0440\u0430\u043c\u043c \u0432 \u0438\u043d\u0442\u0435\u0440\u043d\u0435\u0442\u0435) \u0438 \u0441\u043e\u0445\u0440\u0430\u043d\u0438\u043b \u0438\u0445 \u0432 \u0444\u043e\u0440\u043c\u0430\u0442\u0435, \u043f\u043e\u043d\u044f\u0442\u043d\u043e\u043c \u043f\u0440\u043e\u0433\u0440\u0430\u043c\u043c\u0435. \u041c\u043e\u0436\u043d\u043e \u0441\u0447\u0438\u0442\u0430\u0442\u044c, \u0447\u0442\u043e \u044d\u0442\u0438 \u043a\u0440\u043e\u0441\u0441\u0432\u043e\u0440\u0434\u044b \u044f\u0432\u043b\u044f\u044e\u0442\u0441\u044f \u0441\u043b\u0443\u0447\u0430\u0439\u043d\u043e\u0439 \u0432\u044b\u0431\u043e\u0440\u043a\u043e\u0439, \u043f\u043e\u044d\u0442\u043e\u043c\u0443 \u0431\u0435\u043d\u0447\u043c\u0430\u0440\u043a \u043f\u043e\u043a\u0430\u0437\u0430\u043b \u0431\u044b \u0430\u0434\u0435\u043a\u0432\u0430\u0442\u043d\u044b\u0435 \u0441\u0440\u0435\u0434\u043d\u0438\u0435 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u044f. \u0422\u0430\u043a\u0436\u0435 \u043d\u043e\u043c\u0435\u0440\u0430 \u043f\u0430\u0440\u044b \u0434\u044e\u0436\u0438\u043d \u0441\u0430\u043c\u044b\u0445 &#171;\u0441\u043b\u043e\u0436\u043d\u044b\u0445&#187; \u043a\u0440\u043e\u0441\u0441\u0432\u043e\u0440\u0434\u043e\u0432 (\u0442\u0430\u043a\u0436\u0435 \u0441\u0430\u043c\u044b\u0445 \u0431\u043e\u043b\u044c\u0448\u0438\u0445 \u043f\u043e \u0440\u0430\u0437\u043c\u0435\u0440\u0443 \u0438 \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u0443 \u0446\u0432\u0435\u0442\u043e\u0432) \u0437\u0430\u043f\u0438\u0441\u0430\u043b \u0432 \u0441\u043a\u0440\u0438\u043f\u0442 \u0434\u043b\u044f \u0437\u0430\u0433\u0440\u0443\u0437\u043a\u0438 \u0440\u0443\u0447\u043a\u0430\u043c\u0438.<\/p>\n<p>  <\/p>\n<div style=\"text-align:center;\"><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/webt\/ox\/xt\/nd\/oxxtnd1jdlth72q0zqnj3ic1kew.png\"><\/div>\n<p>  <\/p>\n<h2 id=\"optimizaciya\">\u041e\u043f\u0442\u0438\u043c\u0438\u0437\u0430\u0446\u0438\u044f<\/h2>\n<p>  <\/p>\n<p>\u0417\u0434\u0435\u0441\u044c \u043f\u043e\u043a\u0430\u0437\u0430\u043d\u044b \u0432\u043e\u0437\u043c\u043e\u0436\u043d\u044b\u0435 \u043f\u0440\u0438\u0435\u043c\u044b \u0434\u043b\u044f \u043e\u043f\u0442\u0438\u043c\u0438\u0437\u0430\u0446\u0438\u0438, \u043a\u043e\u0442\u043e\u0440\u044b\u0435 \u0431\u044b\u043b\u0438 \u0441\u0434\u0435\u043b\u0430\u043d\u044b (1)\u0432\u043e \u0432\u0440\u0435\u043c\u044f \u043d\u0430\u043f\u0438\u0441\u0430\u043d\u0438\u044f \u0432\u0441\u0435\u0433\u043e \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0430, (2)\u0434\u043b\u044f \u0443\u0436\u0438\u043c\u0430\u043d\u0438\u044f \u0432\u0440\u0435\u043c\u0435\u043d\u0438 \u0440\u0430\u0431\u043e\u0442\u044b \u0441 \u043f\u043e\u043b\u043c\u0438\u043d\u0443\u0442\u044b \u0434\u043e \u0434\u043e\u043b\u0435\u0439 \u0441\u0435\u043a\u0443\u043d\u0434\u044b, (3)\u0442\u0435 \u043e\u043f\u0442\u0438\u043c\u0438\u0437\u0430\u0446\u0438\u0438, \u043a\u043e\u0442\u043e\u0440\u044b\u0435 \u043c\u043e\u0433\u0443\u0442 \u0431\u044b\u0442\u044c \u043f\u043e\u043b\u0435\u0437\u043d\u044b \u0434\u0430\u043b\u0435\u0435.<\/p>\n<p>  <\/p>\n<h4 id=\"vo-vremya-napisaniya-algoritma\">\u0412\u043e \u0432\u0440\u0435\u043c\u044f \u043d\u0430\u043f\u0438\u0441\u0430\u043d\u0438\u044f \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0430<\/h4>\n<p>  <\/p>\n<ul>\n<li>\u0421\u043f\u0435\u0446\u0438\u0430\u043b\u044c\u043d\u044b\u0435 \u0444\u0443\u043d\u043a\u0446\u0438\u0438 \u0434\u043b\u044f \u0431\u0438\u0442\u043e\u0432\u044b\u0445 \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u0439, \u0432 \u043d\u0430\u0448\u0435\u043c \u0441\u043b\u0443\u0447\u0430\u0435 <code>__builtin_popcount<\/code> \u0434\u043b\u044f \u043f\u043e\u0434\u0441\u0447\u0435\u0442\u0430 \u0435\u0434\u0438\u043d\u0438\u0446 \u0432 \u0434\u0432\u043e\u0438\u0447\u043d\u043e\u0439 \u0437\u0430\u043f\u0438\u0441\u0438 \u0447\u0438\u0441\u043b\u0430, \u0438 <code>__builtin_ctz<\/code> \u0434\u043b\u044f \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u0430 \u043d\u0443\u043b\u0435\u0439 \u043f\u0435\u0440\u0435\u0434 \u043f\u0435\u0440\u0432\u043e\u0439 \u0441\u0430\u043c\u043e\u0439 \u043c\u043b\u0430\u0434\u0448\u0435\u0439 \u0435\u0434\u0438\u043d\u0438\u0446\u0435\u0439. \u0422\u0430\u043a\u0438\u0445 \u0444\u0443\u043d\u043a\u0446\u0438\u0439 \u043c\u043e\u0436\u0435\u0442 \u043d\u0435 \u043e\u043a\u0430\u0437\u0430\u0442\u044c\u0441\u044f \u0432 \u043d\u0435\u043a\u043e\u0442\u043e\u0440\u044b\u0445 \u043a\u043e\u043c\u043f\u0438\u043b\u044f\u0442\u043e\u0440\u0430\u0445. \u0414\u043b\u044f Windows \u043f\u043e\u0434\u043e\u0439\u0434\u0443\u0442 \u0442\u0430\u043a\u0438\u0435 \u0430\u043d\u0430\u043b\u043e\u0433\u0438:<\/li>\n<\/ul>\n<p>  <\/p>\n<div class=\"spoiler\"><b class=\"spoiler_title\">Windows popcount<\/b><\/p>\n<div class=\"spoiler_text\">\n<pre><code class=\"cpp\">#ifdef _MSC_VER                                                                                                 #  include &lt;intrin.h&gt;                                                                                           #  define __builtin_popcount __popcnt                                                                           #endif   <\/code><\/pre>\n<\/div>\n<\/div>\n<p>  <\/p>\n<ul>\n<li>\u041e\u0440\u0433\u0430\u043d\u0438\u0437\u0430\u0446\u0438\u044f \u043c\u0430\u0441\u0441\u0438\u0432\u043e\u0432 \u2014 \u043c\u0435\u043d\u044c\u0448\u0438\u0439 \u0440\u0430\u0437\u043c\u0435\u0440 \u0441\u0442\u043e\u0438\u0442 \u0432\u043d\u0430\u0447\u0430\u043b\u0435. \u041d\u0430\u043f\u0440\u0438\u043c\u0435\u0440, \u043b\u0443\u0447\u0448\u0435 \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u0442\u044c \u043c\u0430\u0441\u0441\u0438\u0432 [2][3][500][1024], \u0447\u0435\u043c [1024][500][3][2].<\/li>\n<li>\u0421\u0430\u043c\u043e\u0435 \u0433\u043b\u0430\u0432\u043d\u043e\u0435 \u2014 \u043e\u0431\u0449\u0430\u044f \u0430\u0434\u0435\u043a\u0432\u0430\u0442\u043d\u043e\u0441\u0442\u044c \u043a\u043e\u0434\u0430 \u0438 \u0438\u0437\u0431\u0435\u0433\u0430\u043d\u0438\u0435 \u043b\u0438\u0448\u043d\u0438\u0445 \u0437\u0430\u0431\u043e\u0442 \u0434\u043b\u044f \u0432\u044b\u0447\u0438\u0441\u043b\u0435\u043d\u0438\u0439.<\/li>\n<\/ul>\n<p>  <\/p>\n<h4 id=\"chto-umenshaet-vremya-raboty\">\u0427\u0442\u043e \u0443\u043c\u0435\u043d\u044c\u0448\u0430\u0435\u0442 \u0432\u0440\u0435\u043c\u044f \u0440\u0430\u0431\u043e\u0442\u044b<\/h4>\n<p>  <\/p>\n<ul>\n<li>\u0424\u043b\u0430\u0433 -O2 \u043f\u0440\u0438 \u043a\u043e\u043c\u043f\u0438\u043b\u044f\u0446\u0438\u0438.<\/li>\n<li>\u0427\u0442\u043e\u0431\u044b \u043d\u0435 \u0431\u0440\u043e\u0441\u0430\u0442\u044c \u0432 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u043f\u043e\u043b\u043d\u043e\u0441\u0442\u044c\u044e \u0440\u0435\u0448\u0435\u043d\u043d\u0443\u044e \u0441\u0442\u0440\u043e\u043a\u0443\/\u0441\u0442\u043e\u043b\u0431\u0435\u0446 \u0437\u0430\u043d\u043e\u0432\u043e, \u043c\u043e\u0436\u043d\u043e \u0432 \u043e\u0442\u0434\u0435\u043b\u044c\u043d\u043e\u043c std::vector\/\u043c\u0430\u0441\u0441\u0438\u0432\u0435 \u0437\u0430\u0432\u0435\u0441\u0442\u0438 \u0444\u043b\u0430\u0433\u0438 \u0434\u043b\u044f \u043a\u0430\u0436\u0434\u043e\u0433\u043e \u0440\u044f\u0434\u0430, \u043f\u043e\u043c\u0435\u0447\u0430\u0442\u044c \u0438\u0445 \u043f\u0440\u0438 \u043f\u043e\u043b\u043d\u043e\u043c \u0440\u0435\u0448\u0435\u043d\u0438\u0438, \u0438 \u043d\u0435 \u0434\u0430\u0432\u0430\u0442\u044c \u0438\u0434\u0442\u0438 \u0434\u0430\u043b\u044c\u0448\u0435, \u0435\u0441\u043b\u0438 \u0440\u0435\u0448\u0430\u0442\u044c \u0443\u0436\u0435 \u043d\u0435\u0447\u0435\u0433\u043e.<\/li>\n<li>\u0421\u043f\u0435\u0446\u0438\u0444\u0438\u043a\u0430 \u043c\u043d\u043e\u0433\u043e\u043f\u043e\u0432\u0442\u043e\u0440\u043d\u043e\u0433\u043e \u0440\u0435\u0448\u0435\u043d\u0438\u044f \u0437\u0430\u0434\u0430\u0447\u0438 \u043d\u0430 \u0434\u0438\u043d\u0430\u043c\u0438\u043a\u0443 \u043f\u0440\u0435\u0434\u043f\u043e\u043b\u0430\u0433\u0430\u0435\u0442, \u0447\u0442\u043e \u0441\u043f\u0435\u0446\u0438\u0430\u043b\u044c\u043d\u044b\u0439 \u043c\u0430\u0441\u0441\u0438\u0432, \u043a\u043e\u0442\u043e\u0440\u044b\u0439 \u0441\u043e\u0434\u0435\u0440\u0436\u0438\u0442 \u0444\u043b\u0430\u0433\u0438, \u043f\u043e\u043c\u0435\u0447\u0430\u044e\u0449\u0438\u0435 \u0443\u0436\u0435 &#171;\u0432\u044b\u0447\u0438\u0441\u043b\u0435\u043d\u043d\u044b\u0435&#187; \u043a\u0443\u0441\u043a\u0438 \u0437\u0430\u0434\u0430\u0447\u0438, \u0441\u043b\u0435\u0434\u0443\u0435\u0442 \u043e\u0431\u043d\u0443\u043b\u044f\u0442\u044c \u043a\u0430\u0436\u0434\u044b\u0439 \u0440\u0430\u0437 \u043f\u0440\u0438 \u043d\u043e\u0432\u043e\u043c \u0440\u0435\u0448\u0435\u043d\u0438\u0438. \u0412 \u043d\u0430\u0448\u0435\u043c \u0441\u043b\u0443\u0447\u0430\u0435 \u044d\u0442\u043e \u0434\u0432\u0443\u043c\u0435\u0440\u043d\u044b\u0439 \u043c\u0430\u0441\u0441\u0438\u0432\/\u0432\u0435\u043a\u0442\u043e\u0440, \u0433\u0434\u0435 \u043f\u0435\u0440\u0432\u043e\u0435 \u0438\u0437\u043c\u0435\u0440\u0435\u043d\u0438\u0435 \u2014 \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e \u0433\u0440\u0443\u043f\u043f, \u0432\u0442\u043e\u0440\u043e\u0435 \u2014 \u0442\u0435\u043a\u0443\u0449\u0430\u044f \u043a\u043b\u0435\u0442\u043a\u0430 (\u0441\u043c. \u043f\u0441\u0435\u0432\u0434\u043e\u043a\u043e\u0434 EpicWin \u0441\u0432\u0435\u0440\u0445\u0443, \u0433\u0434\u0435 \u044d\u0442\u043e\u0433\u043e \u043c\u0430\u0441\u0441\u0438\u0432\u0430 \u043d\u0435\u0442, \u043d\u043e \u0438\u0434\u0435\u044f \u044f\u0441\u043d\u0430). \u0412\u043c\u0435\u0441\u0442\u043e \u043e\u0431\u043d\u0443\u043b\u0435\u043d\u0438\u044f \u043c\u043e\u0436\u043d\u043e \u0441\u0434\u0435\u043b\u0430\u0442\u044c \u0442\u0430\u043a \u2014 \u043f\u0443\u0441\u0442\u044c \u0443 \u043d\u0430\u0441 \u0431\u0443\u0434\u0435\u0442 \u043f\u0435\u0440\u0435\u043c\u0435\u043d\u043d\u0430\u044f-&#171;\u0442\u0430\u0439\u043c\u0435\u0440&#187;, \u0430 \u043c\u0430\u0441\u0441\u0438\u0432 \u0441\u043e\u0441\u0442\u043e\u0438\u0442 \u0438\u0437 \u0447\u0438\u0441\u0435\u043b, \u043f\u043e\u043a\u0430\u0437\u044b\u0432\u0430\u044e\u0449\u0438\u0445 \u043f\u043e\u0441\u043b\u0435\u0434\u043d\u0435\u0435 &#171;\u0432\u0440\u0435\u043c\u044f&#187;, \u043a\u043e\u0433\u0434\u0430 \u044d\u0442\u043e\u0442 \u043a\u0443\u0441\u043e\u043a \u043f\u0435\u0440\u0435\u0441\u0447\u0438\u0442\u044b\u0432\u0430\u043b\u0441\u044f \u0432 \u043f\u043e\u0441\u043b\u0435\u0434\u043d\u0438\u0439 \u0440\u0430\u0437. \u041f\u0440\u0438 \u0437\u0430\u043f\u0443\u0441\u043a\u0435 \u043d\u043e\u0432\u043e\u0439 \u0437\u0430\u0434\u0430\u0447\u0438 &#171;\u0442\u0430\u0439\u043c\u0435\u0440&#187; \u0443\u0432\u0435\u043b\u0438\u0447\u0438\u0432\u0430\u0435\u0442\u0441\u044f \u043d\u0430 1. \u0412\u043c\u0435\u0441\u0442\u043e \u043f\u0440\u043e\u0432\u0435\u0440\u043a\u0438 \u0431\u0443\u043b\u0435\u0432\u043e\u0433\u043e \u0444\u043b\u0430\u0433\u0430 \u0441\u043b\u0435\u0434\u0443\u0435\u0442 \u043f\u0440\u043e\u0432\u0435\u0440\u044f\u0442\u044c \u0440\u0430\u0432\u0435\u043d\u0441\u0442\u0432\u043e \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u0430 \u043c\u0430\u0441\u0441\u0438\u0432\u0430 \u0438 &#171;\u0442\u0430\u0439\u043c\u0435\u0440\u0430&#187;. \u042d\u0442\u043e \u044d\u0444\u0444\u0435\u043a\u0442\u0438\u0432\u043d\u043e \u043e\u0441\u043e\u0431\u0435\u043d\u043d\u043e \u0432 \u0442\u0435\u0445 \u0441\u043b\u0443\u0447\u0430\u044f\u0445, \u043a\u043e\u0433\u0434\u0430 \u0434\u0430\u043b\u0435\u043a\u043e \u043d\u0435 \u0432\u0441\u0435 \u0432\u043e\u0437\u043c\u043e\u0436\u043d\u044b\u0435 \u0441\u043e\u0441\u0442\u043e\u044f\u043d\u0438\u044f \u043f\u043e\u043a\u0440\u044b\u0432\u0430\u044e\u0442\u0441\u044f \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u043e\u043c (\u0430 \u0437\u043d\u0430\u0447\u0438\u0442, \u043e\u0431\u043d\u0443\u043b\u0435\u043d\u0438\u0435 \u043c\u0430\u0441\u0441\u0438\u0432\u0430 &#171;\u0441\u0447\u0438\u0442\u0430\u043b\u0438 \u043b\u0438 \u043c\u044b \u0443\u0436\u0435 \u044d\u0442\u043e&#187; \u0437\u0430\u043d\u0438\u043c\u0430\u0435\u0442 \u0437\u0434\u043e\u0440\u043e\u0432\u044b\u0439 \u043a\u0443\u0441\u043e\u043a \u0432\u0440\u0435\u043c\u0435\u043d\u0438).<\/li>\n<li>\u0417\u0430\u043c\u0435\u043d\u0430 \u043d\u0435\u0441\u043b\u043e\u0436\u043d\u044b\u0445 \u043e\u0434\u043d\u043e\u0442\u0438\u043f\u043d\u044b\u0445 \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u0439 (\u0446\u0438\u043a\u043b\u044b \u0441 \u043f\u0440\u0438\u0441\u0432\u0430\u0438\u0432\u0430\u043d\u0438\u0435\u043c \u0438 \u0442.\u0434.) \u043d\u0430 \u0430\u043d\u0430\u043b\u043e\u0433\u0438 \u0432 STL \u0438\u043b\u0438 \u0431\u043e\u043b\u0435\u0435 \u0430\u0434\u0435\u043a\u0432\u0430\u0442\u043d\u044b\u0435 \u0432\u0435\u0449\u0438. \u0418\u043d\u043e\u0433\u0434\u0430 \u0440\u0430\u0431\u043e\u0442\u0430\u0435\u0442 \u0431\u044b\u0441\u0442\u0440\u0435\u0435 \u0432\u0435\u043b\u043e\u0441\u0438\u043f\u0435\u0434\u0430.<\/li>\n<li><code>std::vector&lt;bool&gt;<\/code> \u0432 \u0421++ \u0441\u0436\u0438\u043c\u0430\u0435\u0442 \u0432\u0441\u0435 \u0431\u0443\u043b\u0435\u0432\u044b\u0435 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u044f \u0434\u043e \u043e\u0442\u0434\u0435\u043b\u044c\u043d\u044b\u0445 \u0431\u0438\u0442\u043e\u0432 \u0432 \u0447\u0438\u0441\u043b\u0430\u0445, \u0447\u0442\u043e \u0440\u0430\u0431\u043e\u0442\u0430\u0435\u0442 \u043f\u0440\u0438 \u0434\u043e\u0441\u0442\u0443\u043f\u0435 \u0447\u0443\u0442\u044c \u043c\u0435\u0434\u043b\u0435\u043d\u043d\u0435\u0435, \u0447\u0435\u043c \u0435\u0441\u043b\u0438 \u0431\u044b \u044d\u0442\u043e \u0431\u044b\u043b\u043e \u043e\u0431\u044b\u0447\u043d\u043e\u0435 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0435 \u043f\u043e \u0430\u0434\u0440\u0435\u0441\u0443. \u0415\u0441\u043b\u0438 \u043f\u0440\u043e\u0433\u0440\u0430\u043c\u043c\u0430 \u043d\u0443 \u043e\u0447\u0435\u043d\u044c-\u043e\u0447\u0435\u043d\u044c \u0447\u0430\u0441\u0442\u043e \u043e\u0431\u0440\u0430\u0449\u0430\u0435\u0442\u0441\u044f \u043a \u0442\u0430\u043a\u0438\u043c \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u044f\u043c, \u0442\u043e \u0437\u0430\u043c\u0435\u043d\u0430 bool \u043d\u0430 \u0446\u0435\u043b\u043e\u0447\u0438\u0441\u043b\u0435\u043d\u043d\u044b\u0439 \u0442\u0438\u043f \u043c\u043e\u0436\u0435\u0442 \u0445\u043e\u0440\u043e\u0448\u043e \u043f\u043e\u0432\u043b\u0438\u044f\u0442\u044c \u043d\u0430 \u043f\u0440\u043e\u0438\u0437\u0432\u043e\u0434\u0438\u0442\u0435\u043b\u044c\u043d\u043e\u0441\u0442\u044c.<\/li>\n<li>\u041e\u0441\u0442\u0430\u043b\u044c\u043d\u044b\u0435 \u0441\u043b\u0430\u0431\u044b\u0435 \u043c\u0435\u0441\u0442\u0430 \u043c\u043e\u0436\u043d\u043e \u0438\u0441\u043a\u0430\u0442\u044c \u0447\u0435\u0440\u0435\u0437 \u043f\u0440\u043e\u0444\u0430\u0439\u043b\u0435\u0440\u044b \u0438 \u043f\u0440\u0430\u0432\u0438\u0442\u044c \u0438\u0445. \u042f \u0441\u0430\u043c \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u044e Valgrind, \u0435\u0433\u043e \u0430\u043d\u0430\u043b\u0438\u0437 \u043f\u0440\u043e\u0438\u0437\u0432\u043e\u0434\u0438\u0442\u0435\u043b\u044c\u043d\u043e\u0441\u0442\u0438 \u0443\u0434\u043e\u0431\u043d\u043e \u0441\u043c\u043e\u0442\u0440\u0435\u0442\u044c \u0447\u0435\u0440\u0435\u0437 kCachegrind. \u041f\u0440\u043e\u0444\u0430\u0439\u043b\u0435\u0440\u044b \u0432\u0441\u0442\u0440\u043e\u0435\u043d\u044b \u0432\u043e \u043c\u043d\u043e\u0433\u0438\u0435 IDE.<\/li>\n<\/ul>\n<p>  <\/p>\n<p>\u042d\u0442\u0438\u0445 \u043f\u0440\u0430\u0432\u043e\u043a \u043e\u043a\u0430\u0437\u0430\u043b\u043e\u0441\u044c \u0434\u043e\u0441\u0442\u0430\u0442\u043e\u0447\u043d\u043e, \u0447\u0442\u043e\u0431\u044b \u043f\u043e\u043b\u0443\u0447\u0438\u0442\u044c \u0442\u0430\u043a\u0438\u0435 \u0434\u0430\u043d\u043d\u044b\u0435 \u043d\u0430 \u0431\u0435\u043d\u0447\u043c\u0430\u0440\u043a\u0435:<\/p>\n<p>  <\/p>\n<div class=\"spoiler\"><b class=\"spoiler_title\">\u0426\u0432\u0435\u0442\u043d\u044b\u0435 \u043d\u043e\u043d\u043e\u0433\u0440\u0430\u043c\u043c\u044b<\/b><\/p>\n<div class=\"spoiler_text\">\n<pre><code class=\"bash\">izaron@izaron:~\/nonograms\/build$ .\/nonograms_solver -x ..\/..\/nonogram\/source2\/ -e [2018-08-04 22:57:40.432] [Nonograms] [info] Starting a benchmark... [2018-08-04 22:58:03.820] [Nonograms] [info] Average time: 0.00497556, Median time: 0.00302781, Max time: 0.215925 [2018-08-04 22:58:03.820] [Nonograms] [info] Top 10 heaviest nonograms: [2018-08-04 22:58:03.820] [Nonograms] [info] 0.215925 seconds, file 9596 [2018-08-04 22:58:03.820] [Nonograms] [info] 0.164579 seconds, file 4462 [2018-08-04 22:58:03.820] [Nonograms] [info] 0.105828 seconds, file 15831 [2018-08-04 22:58:03.820] [Nonograms] [info] 0.08827 seconds, file 18353 [2018-08-04 22:58:03.820] [Nonograms] [info] 0.0874717 seconds, file 10590 [2018-08-04 22:58:03.820] [Nonograms] [info] 0.0831248 seconds, file 4649 [2018-08-04 22:58:03.820] [Nonograms] [info] 0.0782811 seconds, file 11922 [2018-08-04 22:58:03.820] [Nonograms] [info] 0.0734325 seconds, file 4655 [2018-08-04 22:58:03.820] [Nonograms] [info] 0.071352 seconds, file 10828 [2018-08-04 22:58:03.820] [Nonograms] [info] 0.0708263 seconds, file 11824<\/code><\/pre>\n<\/div>\n<\/div>\n<p>  <\/p>\n<div class=\"spoiler\"><b class=\"spoiler_title\">\u0427\u0435\u0440\u043d\u043e-\u0431\u0435\u043b\u044b\u0435 \u043d\u043e\u043d\u043e\u0433\u0440\u0430\u043c\u043c\u044b<\/b><\/p>\n<div class=\"spoiler_text\">\n<pre><code class=\"bash\">izaron@izaron:~\/nonograms\/build$ .\/nonograms_solver -x ..\/..\/nonogram\/source\/ -e -b [2018-08-04 22:59:56.308] [Nonograms] [info] Starting a benchmark... [2018-08-04 23:00:09.781] [Nonograms] [info] Average time: 0.0095679, Median time: 0.00239274, Max time: 0.607341 [2018-08-04 23:00:09.781] [Nonograms] [info] Top 10 heaviest nonograms: [2018-08-04 23:00:09.781] [Nonograms] [info] 0.607341 seconds, file 5126 [2018-08-04 23:00:09.781] [Nonograms] [info] 0.458932 seconds, file 19510 [2018-08-04 23:00:09.781] [Nonograms] [info] 0.452245 seconds, file 5114 [2018-08-04 23:00:09.781] [Nonograms] [info] 0.19975 seconds, file 18627 [2018-08-04 23:00:09.781] [Nonograms] [info] 0.163028 seconds, file 5876 [2018-08-04 23:00:09.781] [Nonograms] [info] 0.161675 seconds, file 17403 [2018-08-04 23:00:09.781] [Nonograms] [info] 0.153693 seconds, file 12771 [2018-08-04 23:00:09.781] [Nonograms] [info] 0.146731 seconds, file 5178 [2018-08-04 23:00:09.781] [Nonograms] [info] 0.142732 seconds, file 18244 [2018-08-04 23:00:09.781] [Nonograms] [info] 0.136131 seconds, file 19385<\/code><\/pre>\n<\/div>\n<\/div>\n<p>  <\/p>\n<p>\u041c\u043e\u0436\u043d\u043e \u0437\u0430\u043c\u0435\u0442\u0438\u0442\u044c, \u0447\u0442\u043e \u0432 \u0441\u0440\u0435\u0434\u043d\u0435\u043c \u0447\u0435\u0440\u043d\u043e-\u0431\u0435\u043b\u044b\u0435 \u043a\u0440\u043e\u0441\u0441\u0432\u043e\u0440\u0434\u044b &#171;\u0441\u043b\u043e\u0436\u043d\u0435\u0435&#187; \u0446\u0432\u0435\u0442\u043d\u044b\u0445. \u042d\u0442\u043e \u043f\u043e\u0434\u0442\u0432\u0435\u0440\u0436\u0434\u0430\u0435\u0442 \u043d\u0430\u0431\u043b\u044e\u0434\u0435\u043d\u0438\u044f \u043b\u044e\u0431\u0438\u0442\u0435\u043b\u0435\u0439 \u0438\u0433\u0440\u044b, \u043a\u043e\u0442\u043e\u0440\u044b\u0435 \u0442\u0430\u043a\u0436\u0435 \u0441\u0447\u0438\u0442\u0430\u044e\u0442, \u0447\u0442\u043e &#171;\u0446\u0432\u0435\u0442\u043d\u044b\u0435&#187; \u0440\u0435\u0448\u0430\u044e\u0442\u0441\u044f \u0432 \u0441\u0440\u0435\u0434\u043d\u0435\u043c \u043b\u0435\u0433\u0447\u0435.<\/p>\n<p>  <\/p>\n<p>\u0422\u0430\u043a\u0438\u043c \u043e\u0431\u0440\u0430\u0437\u043e\u043c, \u0431\u0435\u0437 \u0440\u0430\u0434\u0438\u043a\u0430\u043b\u044c\u043d\u044b\u0445 \u043f\u0440\u0430\u0432\u043e\u043a (\u0442\u0430\u043a\u0438\u0445 \u043a\u0430\u043a \u043f\u0435\u0440\u0435\u043f\u0438\u0441\u044b\u0432\u0430\u043d\u0438\u0435 \u0432\u0441\u0435\u0433\u043e \u043a\u043e\u0434\u0430 \u043d\u0430 \u043d\u0430 \u0421 \u0438\u043b\u0438 \u0430\u0441\u0441\u0435\u043c\u0431\u043b\u0435\u0440\u043d\u044b\u0445 \u0432\u0441\u0442\u0430\u0432\u043e\u043a \u0441 fastcall \u0438 \u043e\u043f\u0443\u0441\u043a\u0430\u043d\u0438\u0435\u043c \u0443\u043a\u0430\u0437\u0430\u0442\u0435\u043b\u044f \u0444\u0440\u0435\u0439\u043c\u0430) \u043c\u043e\u0436\u043d\u043e \u0434\u043e\u0441\u0442\u0438\u0447\u044c \u0432\u044b\u0441\u043e\u043a\u043e\u0439 \u043f\u0440\u043e\u0438\u0437\u0432\u043e\u0434\u0438\u0442\u0435\u043b\u044c\u043d\u043e\u0441\u0442\u044c\u044e, \u0437\u0430\u043c\u0435\u0442\u0438\u043c, \u043d\u0430 \u0432\u0435\u0441\u044c\u043c\u0430 \u0441\u043a\u0440\u043e\u043c\u043d\u043e\u043c \u043a\u043e\u043c\u043f\u044c\u044e\u0442\u0435\u0440\u0435. \u041a \u043e\u043f\u0442\u0438\u043c\u0438\u0437\u0430\u0446\u0438\u044f\u043c \u043c\u043e\u0436\u0435\u0442 \u0431\u044b\u0442\u044c \u043f\u0440\u0438\u043c\u0435\u043d\u0438\u043c \u043f\u0440\u0438\u043d\u0446\u0438\u043f \u041f\u0430\u0440\u0435\u0442\u043e \u2014 \u043e\u043a\u0430\u0436\u0435\u0442\u0441\u044f, \u0447\u0442\u043e \u043c\u0435\u043b\u043a\u0430\u044f \u043e\u043f\u0442\u0438\u043c\u0438\u0437\u0430\u0446\u0438\u044f \u0432\u043b\u0438\u044f\u0435\u0442 \u0441\u0438\u043b\u044c\u043d\u043e, \u043f\u043e\u0442\u043e\u043c\u0443 \u0447\u0442\u043e \u044d\u0442\u043e\u0442 \u043a\u0443\u0441\u043e\u043a \u043a\u043e\u0434\u0430 \u043a\u0440\u0438\u0442\u0438\u0447\u0435\u043d \u0438 \u0432\u044b\u0437\u044b\u0432\u0430\u0435\u0442\u0441\u044f \u043e\u0447\u0435\u043d\u044c \u0447\u0430\u0441\u0442\u043e.<\/p>\n<p>  <\/p>\n<h4 id=\"dalneyshaya-optimizaciya\">\u0414\u0430\u043b\u044c\u043d\u0435\u0439\u0448\u0430\u044f \u043e\u043f\u0442\u0438\u043c\u0438\u0437\u0430\u0446\u0438\u044f<\/h4>\n<p>  <\/p>\n<p>\u0421\u043b\u0435\u0434\u0443\u044e\u0449\u0438\u0435 \u043c\u0435\u0442\u043e\u0434\u044b \u043c\u043e\u0433\u0443\u0442 \u0441\u0438\u043b\u044c\u043d\u043e \u0443\u043b\u0443\u0447\u0448\u0438\u0442\u044c \u043f\u0440\u043e\u0438\u0437\u0432\u043e\u0434\u0438\u0442\u0435\u043b\u044c\u043d\u043e\u0441\u0442\u044c \u043f\u0440\u043e\u0433\u0440\u0430\u043c\u043c\u044b. \u041d\u0435\u043a\u043e\u0442\u043e\u0440\u044b\u0435 \u0438\u0437 \u043d\u0438\u0445 \u0440\u0430\u0431\u043e\u0442\u0430\u044e\u0442 \u043d\u0435 \u0432\u043e \u0432\u0441\u0435\u0445 \u0441\u043b\u0443\u0447\u0430\u044f\u0445, \u0430 \u043f\u0440\u0438 \u043d\u0435\u043a\u043e\u0442\u043e\u0440\u044b\u0445 \u0443\u0441\u043b\u043e\u0432\u0438\u044f\u0445.<\/p>\n<p>  <\/p>\n<ul>\n<li>\u041f\u0435\u0440\u0435\u043f\u0438\u0441\u044b\u0432\u0430\u043d\u0438\u0435 \u043a\u043e\u0434\u0430 \u043d\u0430 C-style \u0438 \u043f\u0440\u043e\u0447\u0438\u0439 1972 \u0433\u043e\u0434. \u0417\u0430\u043c\u0435\u043d\u044f\u0435\u043c ifstream \u043d\u0430 \u0441\u0438\u0448\u043d\u044b\u0439 \u0430\u043d\u0430\u043b\u043e\u0433, \u0432\u0435\u043a\u0442\u043e\u0440\u044b \u043d\u0430 \u043c\u0430\u0441\u0441\u0438\u0432\u044b, \u0443\u0447\u0438\u043c \u0432\u0441\u0435 \u043e\u043f\u0446\u0438\u0438 \u043a\u043e\u043c\u043f\u0438\u043b\u044f\u0442\u043e\u0440\u0430 \u0438 \u0431\u043e\u0440\u0435\u043c\u0441\u044f \u0437\u0430 \u043a\u0430\u0436\u0434\u044b\u0439 \u0442\u0430\u043a\u0442 \u043f\u0440\u043e\u0446\u0435\u0441\u0441\u043e\u0440\u0430.<\/li>\n<li>\u0420\u0430\u0441\u043f\u0430\u0440\u0430\u043b\u043b\u0435\u043b\u0438\u0432\u0430\u043d\u0438\u0435. \u041d\u0430\u043f\u0440\u0438\u043c\u0435\u0440, \u0432 \u043a\u043e\u0434\u0435 \u0435\u0441\u0442\u044c \u043a\u0443\u0441\u043e\u043a, \u0433\u0434\u0435 \u043f\u043e\u0441\u043b\u0435\u0434\u043e\u0432\u0430\u0442\u0435\u043b\u044c\u043d\u043e \u043e\u0431\u043d\u043e\u0432\u043b\u044f\u044e\u0442\u0441\u044f \u0441\u0442\u0440\u043e\u043a\u0438, \u043f\u043e\u0442\u043e\u043c \u0441\u0442\u043e\u043b\u0431\u0446\u044b:<\/li>\n<\/ul>\n<p>  <\/p>\n<div class=\"spoiler\"><b class=\"spoiler_title\">bool Puzzle::UpdateState(&#8230;)<\/b><\/p>\n<div class=\"spoiler_text\">\n<pre><code class=\"cpp\">    ...     if (!UpdateGroupsState(solver, dead_rows, row_groups, row_masks)) {                                                                                        return false;                                                                   }                                                                                   if (!UpdateGroupsState(solver, dead_cols, col_groups, col_masks)) {                    return false;                                                                   }                                                                                  return true;<\/code><\/pre>\n<\/div>\n<\/div>\n<p>  <\/p>\n<p>\u042d\u0442\u0438 \u0444\u0443\u043d\u043a\u0446\u0438\u0438 \u043d\u0435\u0437\u0430\u0432\u0438\u0441\u0438\u043c\u044b \u0434\u0440\u0443\u0433 \u043e\u0442 \u0434\u0440\u0443\u0433\u0430 \u0438 \u0443 \u043d\u0438\u0445 \u043d\u0435\u0442 \u043e\u0431\u0449\u0435\u0439 \u043f\u0430\u043c\u044f\u0442\u0438, \u043a\u0440\u043e\u043c\u0435 \u043f\u0435\u0440\u0435\u043c\u0435\u043d\u043d\u043e\u0439 solver (\u0442\u0438\u043f OneLineSolver), \u0442\u0430\u043a \u0447\u0442\u043e \u043c\u043e\u0436\u043d\u043e \u0441\u043e\u0437\u0434\u0430\u0442\u044c \u0434\u0432\u0430 \u043e\u0431\u044a\u0435\u043a\u0442\u0430 &#171;\u0440\u0435\u0448\u0430\u0442\u0435\u043b\u044f&#187; (\u0437\u0434\u0435\u0441\u044c \u043e\u0447\u0435\u0432\u0438\u0434\u043d\u043e \u0442\u043e\u043b\u044c\u043a\u043e \u043e\u0434\u0438\u043d \u2014 solver) \u0438 \u0437\u0430\u043f\u0443\u0441\u0442\u0438\u0442\u044c \u0434\u0432\u0430 \u043f\u043e\u0442\u043e\u043a\u0430 \u0432 \u044d\u0442\u043e\u0439 \u0436\u0435 \u0444\u0443\u043d\u043a\u0446\u0438\u0438. \u042d\u0444\u0444\u0435\u043a\u0442 \u0442\u0430\u043a\u043e\u0439 \u2014 \u0432 \u0446\u0432\u0435\u0442\u043d\u044b\u0445 \u043a\u0440\u043e\u0441\u0441\u0432\u043e\u0440\u0434\u0430\u0445 &#171;\u0441\u0430\u043c\u044b\u0439 \u0442\u044f\u0436\u0435\u043b\u044b\u0439&#187; \u0440\u0435\u0448\u0430\u0435\u0442\u0441\u044f \u0432 \u0434\u0432\u0430 \u0440\u0430\u0437\u0430 \u0431\u044b\u0441\u0442\u0440\u0435\u0435, \u0432 \u0447\u0435\u0440\u043d\u043e-\u0431\u0435\u043b\u044b\u0445 \u0442\u0430\u043a\u043e\u0439 \u0436\u0435 \u043d\u0430 \u0442\u0440\u0435\u0442\u044c \u0431\u044b\u0441\u0442\u0440\u0435\u0435, \u0430 \u0441\u0440\u0435\u0434\u043d\u0435\u0435 \u0432\u0440\u0435\u043c\u044f \u0443\u0432\u0435\u043b\u0438\u0447\u0438\u043b\u043e\u0441\u044c, \u0437\u0430 \u0441\u0447\u0435\u0442 \u0441\u0440\u0430\u0432\u043d\u0438\u0442\u0435\u043b\u044c\u043d\u043e \u0431\u043e\u043b\u044c\u0448\u0438\u0445 \u0437\u0430\u0442\u0440\u0430\u0442 \u043d\u0430 \u0441\u043e\u0437\u0434\u0430\u043d\u0438\u0435 \u043f\u043e\u0442\u043e\u043a\u043e\u0432.<\/p>\n<p>  <\/p>\n<p>\u041d\u043e \u0432\u043e\u043e\u0431\u0449\u0435 \u044f \u0431\u044b \u043d\u0435 \u0441\u043e\u0432\u0435\u0442\u043e\u0432\u0430\u043b \u0434\u0435\u043b\u0430\u0442\u044c \u043f\u0440\u044f\u043c\u043e \u0442\u0430\u043a \u0432 \u0442\u0435\u043a\u0443\u0449\u0435\u0439 \u043f\u0440\u043e\u0433\u0440\u0430\u043c\u043c\u0435 \u0438 \u0441\u043f\u043e\u043a\u043e\u0439\u043d\u043e \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u0442\u044c \u2014 \u0432\u043e-\u043f\u0435\u0440\u0432\u044b\u0445, \u0441\u043e\u0437\u0434\u0430\u043d\u0438\u0435 \u043f\u043e\u0442\u043e\u043a\u043e\u0432 \u0437\u0430\u0442\u0440\u0430\u0442\u043d\u0430\u044f \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u044f, \u043d\u0435 \u0441\u0442\u043e\u0438\u0442 \u043f\u043e\u0441\u0442\u043e\u044f\u043d\u043d\u043e \u0441\u043e\u0437\u0434\u0430\u0432\u0430\u0442\u044c \u043f\u043e\u0442\u043e\u043a\u0438 \u0434\u043b\u044f \u043c\u0438\u043a\u0440\u043e\u0441\u0435\u043a\u0443\u043d\u0434\u043d\u044b\u0445 \u0437\u0430\u0434\u0430\u0447, \u0432\u043e-\u0432\u0442\u043e\u0440\u044b\u0445, \u043f\u0440\u0438 \u043d\u0435\u043a\u043e\u0442\u043e\u0440\u043e\u0439 \u043a\u043e\u043c\u0431\u0438\u043d\u0430\u0446\u0438\u0438 \u0430\u0440\u0433\u0443\u043c\u0435\u043d\u0442\u043e\u0432 \u043f\u0440\u043e\u0433\u0440\u0430\u043c\u043c\u044b, \u043f\u043e\u0442\u043e\u043a\u0438 \u043c\u043e\u0433\u0443\u0442 \u043e\u0431\u0440\u0430\u0449\u0430\u0442\u044c\u0441\u044f \u043e\u0434\u043d\u043e\u0432\u0440\u0435\u043c\u0435\u043d\u043d\u043e \u043a \u043a\u0430\u043a\u043e\u0439-\u0442\u043e \u0432\u043d\u0435\u0448\u043d\u0435\u0439 \u043f\u0430\u043c\u044f\u0442\u0438, \u043d\u0430\u043f\u0440\u0438\u043c\u0435\u0440 \u043f\u0440\u0438 \u0441\u043e\u0437\u0434\u0430\u043d\u0438\u0438 \u043a\u0430\u0440\u0442\u0438\u043d\u043e\u043a \u0440\u0435\u0448\u0435\u043d\u0438\u044f \u2014 \u044d\u0442\u043e \u043d\u0430\u0434\u043e \u0431\u044b \u0443\u0447\u0435\u0441\u0442\u044c \u0438 \u043e\u0431\u0435\u0437\u043e\u043f\u0430\u0441\u0438\u0442\u044c.<\/p>\n<p>  <\/p>\n<p>\u0415\u0441\u043b\u0438 \u0431\u044b \u0437\u0430\u0434\u0430\u0447\u0430 \u0431\u044b\u043b\u0430 \u0441\u0435\u0440\u044c\u0435\u0437\u043d\u043e\u0439 \u0438 \u0443 \u043c\u0435\u043d\u044f \u0431\u044b\u043b\u043e \u0431\u044b \u043c\u043d\u043e\u0433\u043e \u0434\u0430\u043d\u043d\u044b\u0445 \u0438 \u043c\u043d\u043e\u0433\u043e\u044f\u0434\u0435\u0440\u043d\u044b\u0435 \u043c\u0430\u0448\u0438\u043d\u044b, \u044f \u0431\u044b \u043f\u043e\u0448\u0435\u043b \u0435\u0449\u0435 \u0434\u0430\u043b\u044c\u0448\u0435 \u2014 \u043c\u043e\u0436\u043d\u043e \u0437\u0430\u0432\u0435\u0441\u0442\u0438 \u043d\u0435\u0441\u043a\u043e\u043b\u044c\u043a\u043e \u043f\u043e\u0441\u0442\u043e\u044f\u043d\u043d\u044b\u0445 \u043f\u043e\u0442\u043e\u043a\u043e\u0432, \u0443 \u043a\u0430\u0436\u0434\u043e\u0433\u043e \u0431\u0443\u0434\u0435\u0442 \u0441\u0432\u043e\u0439 \u043e\u0431\u044a\u0435\u043a\u0442 OneLineSolver, \u0438 \u0435\u0449\u0435 \u043e\u0434\u043d\u0430 thread-safe \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u0430, \u043a\u043e\u0442\u043e\u0440\u0430\u044f \u0440\u0443\u043b\u0438\u0442 \u0440\u0430\u0441\u043f\u0440\u0435\u0434\u0435\u043b\u0435\u043d\u0438\u0435\u043c \u0440\u0430\u0431\u043e\u0442\u044b \u0438 \u043f\u043e \u0437\u0430\u043f\u0440\u043e\u0441\u0443 \u043a \u043d\u0435\u0439 \u0432\u044b\u0434\u0430\u0435\u0442 \u0440\u0435\u0444\u0435\u0440\u0435\u043d\u0441 \u043d\u0430 \u043e\u0447\u0435\u0440\u0435\u0434\u043d\u0443\u044e \u0441\u0442\u0440\u043e\u043a\u0443\/\u0441\u0442\u043e\u043b\u0431\u0435\u0446 \u0434\u043b\u044f \u0440\u0435\u0448\u0435\u043d\u0438\u044f. \u041f\u043e\u0442\u043e\u043a\u0438 \u043f\u043e\u0441\u043b\u0435 \u0440\u0435\u0448\u0435\u043d\u0438\u044f \u043e\u0447\u0435\u0440\u0435\u0434\u043d\u043e\u0439 \u0437\u0430\u0434\u0430\u0447\u0438 \u043e\u0431\u0440\u0430\u0449\u0430\u044e\u0442\u0441\u044f \u043a \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u0435 \u0437\u0430\u043d\u043e\u0432\u043e, \u0447\u0442\u043e\u0431\u044b \u0440\u0435\u0448\u0430\u0442\u044c \u0447\u0442\u043e-\u0442\u043e \u0435\u0449\u0435. \u041a\u0430\u043a\u0443\u044e-\u0442\u043e \u0437\u0430\u0434\u0430\u0447\u0443-\u043d\u043e\u043d\u043e\u0433\u0440\u0430\u043c\u043c\u0443 \u0432 \u043f\u0440\u0438\u043d\u0446\u0438\u043f\u0435 \u043c\u043e\u0436\u043d\u043e \u043d\u0430\u0447\u0430\u0442\u044c \u0440\u0435\u0448\u0430\u0442\u044c, \u043d\u0435 \u0437\u0430\u043a\u043e\u043d\u0447\u0438\u0432 \u043f\u0440\u0435\u0434\u044b\u0434\u0443\u0449\u0435\u0439, \u043d\u0430\u043f\u0440\u0438\u043c\u0435\u0440 \u043a\u043e\u0433\u0434\u0430 \u044d\u0442\u0430 \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u0430 \u0437\u0430\u043d\u0438\u043c\u0430\u0435\u0442\u0441\u044f \u0432\u0437\u0430\u0438\u043c\u043d\u044b\u043c AND \u0432\u0441\u0435\u0445 \u043a\u043b\u0435\u0442\u043e\u043a, \u0438 \u0442\u043e\u0433\u0434\u0430 \u043a\u0430\u043a\u0438\u0435-\u0442\u043e \u043f\u043e\u0442\u043e\u043a\u0438 \u0441\u0432\u043e\u0431\u043e\u0434\u043d\u044b \u0438 \u043d\u0438\u0447\u0435\u0433\u043e \u043d\u0435 \u0434\u0435\u043b\u0430\u044e\u0442. \u0415\u0449\u0435 \u0440\u0430\u0441\u043f\u0430\u0440\u0430\u043b\u043b\u0435\u043b\u0438\u0432\u0430\u043d\u0438\u0435 \u043c\u043e\u0436\u043d\u043e \u043f\u0440\u043e\u0432\u0435\u0441\u0442\u0438 \u043d\u0430 \u0433\u0440\u0430\u0444\u0438\u0447\u0435\u0441\u043a\u043e\u043c \u043f\u0440\u043e\u0446\u0435\u0441\u0441\u043e\u0440\u0435 \u0447\u0435\u0440\u0435\u0437 CUDA \u2014 \u0432\u0430\u0440\u0438\u0430\u043d\u0442\u043e\u0432 \u043c\u043d\u043e\u0433\u043e.<\/p>\n<p>  <\/p>\n<ul>\n<li>\u0418\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u043d\u0438\u0435 \u043a\u043b\u0430\u0441\u0441\u0438\u0447\u0435\u0441\u043a\u0438\u0445 \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440 \u0434\u0430\u043d\u043d\u044b\u0445. \u041e\u0431\u0440\u0430\u0442\u0438\u0442\u0435 \u0432\u043d\u0438\u043c\u0430\u043d\u0438\u0435 \u2014 \u043a\u043e\u0433\u0434\u0430 \u044f \u043f\u043e\u043a\u0430\u0437\u044b\u0432\u0430\u043b \u043f\u0441\u0435\u0432\u0434\u043e\u043a\u043e\u0434 \u0440\u0435\u0448\u0435\u043d\u0438\u044f \u0434\u043b\u044f \u0446\u0432\u0435\u0442\u043d\u044b\u0445 \u043d\u043e\u043d\u043e\u0433\u0440\u0430\u043c\u043c, \u0444\u0443\u043d\u043a\u0446\u0438\u0438 CanInsertColor \u0438 PlaceColor \u0440\u0430\u0431\u043e\u0442\u0430\u044e\u0442 \u0432\u043e\u0432\u0441\u0435 \u043d\u0435 \u0437\u0430 <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/655\/b80\/5d6\/655b805d68b4b00a4e90f64eefbc6f1c.svg\" alt=\"$O(1)$\" data-tex=\"inline\"><\/math>, \u0432 \u043e\u0442\u043b\u0438\u0447\u0438\u0435 \u043e\u0442 \u0447\u0435\u0440\u043d\u043e-\u0431\u0435\u043b\u044b\u0445 \u043d\u043e\u043d\u043e\u0433\u0440\u0430\u043c\u043c. \u0412\u044b\u0433\u043b\u044f\u0434\u0438\u0442 \u0432 \u043f\u0440\u043e\u0433\u0440\u0430\u043c\u043c\u0435 \u044d\u0442\u043e \u0442\u0430\u043a:<\/li>\n<\/ul>\n<p>  <\/p>\n<div class=\"spoiler\"><b class=\"spoiler_title\">CanPlaceColor \u0438 SetPlaceColor<\/b><\/p>\n<div class=\"spoiler_text\">\n<pre><code class=\"cpp\">bool OneLineSolver::CanPlaceColor(const vector&lt;int&gt;&amp; cells, int color,                   int lbound, int rbound) {                                                    \/\/ Went out of the border                                                        if (rbound &gt;= cells.size()) {                                                        return false;                                                                }                                                                                 \/\/ We can paint a block of cells with a certain color if and only if it is       \/\/ possible for all cells to have this color (that means, if every cell          \/\/ from the block has color-th bit set to 1)                                                                                                            int mask = 1 &lt;&lt; color;                                                                                                                                  for (int i = lbound; i &lt;= rbound; ++i) {                                             if (!(cells[i] &amp; mask)) {                                                            return false;                                                                }                                                                            }                                                                                return true; }  void OneLineSolver::SetPlaceColor(int color, int lbound, int rbound) {                                                                                      \/\/ Every cell from the block now can have this color                             for (int i = lbound; i &lt;= rbound; ++i) {                                             result_cells_[i] |= (1 &lt;&lt; color);                                            }                                                                            } <\/code><\/pre>\n<\/div>\n<\/div>\n<p>  <\/p>\n<p>\u0422\u043e \u0435\u0441\u0442\u044c \u0440\u0430\u0431\u043e\u0442\u0430\u0435\u0442 \u0437\u0430 \u043b\u0438\u043d\u0438\u044e, \u0437\u0430 <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/11b\/bac\/909\/11bbac909816a3563f0b61feec7a26f4.svg\" alt=\"$O(N)$\" data-tex=\"inline\"><\/math> (\u041f\u043e\u0437\u0436\u0435 \u0431\u0443\u0434\u0435\u0442 \u043e\u0431\u044a\u044f\u0441\u043d\u0435\u043d\u0438\u0435 \u0441\u043c\u044b\u0441\u043b\u0430 \u0438\u043c\u0435\u043d\u043d\u043e \u0442\u0430\u043a\u043e\u0433\u043e \u043a\u043e\u0434\u0430).<\/p>\n<p>  <\/p>\n<p>\u041f\u043e\u0441\u043c\u043e\u0442\u0440\u0438\u043c, \u043a\u0430\u043a \u043c\u043e\u0436\u043d\u043e \u043f\u043e\u043b\u0443\u0447\u0438\u0442\u044c \u043b\u0443\u0447\u0448\u0443\u044e \u0441\u043b\u043e\u0436\u043d\u043e\u0441\u0442\u044c. \u0412\u043e\u0437\u044c\u043c\u0435\u043c <code>CanPlaceColor<\/code>. \u042d\u0442\u0430 \u0444\u0443\u043d\u043a\u0446\u0438\u044f \u043f\u0440\u043e\u0432\u0435\u0440\u044f\u0435\u0442, \u0447\u0442\u043e \u0441\u0440\u0435\u0434\u0438 \u0432\u0441\u0435\u0445 \u0447\u0438\u0441\u0435\u043b \u0432\u0435\u043a\u0442\u043e\u0440\u0430 \u0432 \u043e\u0442\u0440\u0435\u0437\u043a\u0435 <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/4a3\/7cc\/a6b\/4a37cca6b014ffcd18897f2ee518129a.svg\" alt=\"$[lbound, rbound]$\" data-tex=\"inline\"><\/math> \u0431\u0438\u0442 \u043d\u043e\u043c\u0435\u0440 <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/7ca\/973\/9e6\/7ca9739e6935c6e44a79cad7d992b6fa.svg\" alt=\"$color$\" data-tex=\"inline\"><\/math> \u0443\u0441\u0442\u0430\u043d\u043e\u0432\u043b\u0435\u043d \u0432 1. \u042d\u043a\u0432\u0438\u0432\u0430\u043b\u0435\u043d\u0442\u043d\u043e \u044d\u0442\u043e\u043c\u0443 \u043c\u043e\u0436\u043d\u043e \u0432\u0437\u044f\u0442\u044c <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/242\/f9e\/785\/242f9e78537e6713fbd6bb9b7419ec69.svg\" alt=\"$AND$\" data-tex=\"inline\"><\/math> <strong>\u0432\u0441\u0435\u0445<\/strong> \u0447\u0438\u0441\u0435\u043b \u044d\u0442\u043e\u0433\u043e \u043e\u0442\u0440\u0435\u0437\u043a\u0430 \u0438 \u043f\u0440\u043e\u0432\u0435\u0440\u0438\u0442\u044c \u0431\u0438\u0442 \u043d\u043e\u043c\u0435\u0440 <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/7ca\/973\/9e6\/7ca9739e6935c6e44a79cad7d992b6fa.svg\" alt=\"$color$\" data-tex=\"inline\"><\/math>. \u0418\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u044f \u0442\u043e\u0442 \u0444\u0430\u043a\u0442, \u0447\u0442\u043e \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u044f <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/242\/f9e\/785\/242f9e78537e6713fbd6bb9b7419ec69.svg\" alt=\"$AND$\" data-tex=\"inline\"><\/math> <a href=\"https:\/\/ru.wikipedia.org\/wiki\/%D0%9A%D0%BE%D0%BC%D0%BC%D1%83%D1%82%D0%B0%D1%82%D0%B8%D0%B2%D0%BD%D0%B0%D1%8F_%D0%BE%D0%BF%D0%B5%D1%80%D0%B0%D1%86%D0%B8%D1%8F\">\u043a\u043e\u043c\u043c\u0443\u0442\u0430\u0442\u0438\u0432\u043d\u0430\u044f<\/a>, \u0442\u0430\u043a\u0436\u0435 \u043a\u0430\u043a \u0441\u0443\u043c\u043c\u0430, \u043c\u0438\u043d\u0438\u043c\u0443\u043c\/\u043c\u0430\u043a\u0441\u0438\u043c\u0443\u043c, \u043f\u0440\u043e\u0438\u0437\u0432\u0435\u0434\u0435\u043d\u0438\u0435, \u0438\u043b\u0438 \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u044f <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/24f\/2bd\/e49\/24f2bde496ea3523b0b2fc9b6e9e630c.svg\" alt=\"$XOR$\" data-tex=\"inline\"><\/math>, \u0434\u043b\u044f \u0431\u044b\u0441\u0442\u0440\u043e\u0433\u043e \u043f\u043e\u0434\u0441\u0447\u0435\u0442\u0430 <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/242\/f9e\/785\/242f9e78537e6713fbd6bb9b7419ec69.svg\" alt=\"$AND$\" data-tex=\"inline\"><\/math> \u0432\u0441\u0435\u0433\u043e \u043e\u0442\u0440\u0435\u0437\u043a\u0430 \u043c\u043e\u0436\u043d\u043e \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u0442\u044c \u043f\u043e\u0447\u0442\u0438 \u043b\u044e\u0431\u0443\u044e \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u0443 \u0434\u0430\u043d\u043d\u044b\u0445, \u0440\u0430\u0431\u043e\u0442\u0430\u044e\u0449\u0443\u044e \u0441 \u043a\u043e\u043c\u043c\u0443\u0442\u0430\u0442\u0438\u0432\u043d\u044b\u043c\u0438 \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u044f\u043c\u0438 \u043d\u0430 \u043e\u0442\u0440\u0435\u0437\u043a\u0435. \u042d\u0442\u043e:<\/p>\n<p>  <\/p>\n<ol>\n<li>SQRT-\u0434\u0435\u043a\u043e\u043c\u043f\u043e\u0437\u0438\u0446\u0438\u044f. \u041f\u0440\u0435\u0434\u043f\u043e\u0434\u0441\u0447\u0435\u0442 <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/4bf\/5b9\/aa3\/4bf5b9aa3cf274a87683c5290c902a97.svg\" alt=\"$O(\\sqrt{N})$\" data-tex=\"inline\"><\/math>, \u0437\u0430\u043f\u0440\u043e\u0441 <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/4bf\/5b9\/aa3\/4bf5b9aa3cf274a87683c5290c902a97.svg\" alt=\"$O(\\sqrt{N})$\" data-tex=\"inline\"><\/math>. <a href=\"https:\/\/habr.com\/post\/138946\/\">\u0421\u0442\u0430\u0442\u044c\u044f \u043d\u0430 \u0425\u0430\u0431\u0440\u0435<\/a>.<\/li>\n<li>\u0414\u0435\u0440\u0435\u0432\u043e \u043e\u0442\u0440\u0435\u0437\u043a\u043e\u0432. \u041f\u0440\u0435\u0434\u043f\u043e\u0434\u0441\u0447\u0435\u0442 <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/7b9\/f3b\/a34\/7b9f3ba340d0185e0342013999f57068.svg\" alt=\"$O(N\\log{N})$\" data-tex=\"inline\"><\/math>, \u0437\u0430\u043f\u0440\u043e\u0441 <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/8bb\/3f6\/026\/8bb3f6026dcdf43d670ec7ac60acfc07.svg\" alt=\"$O(\\log{N})$\" data-tex=\"inline\"><\/math>. \u0421\u043e\u0442\u043d\u0438 \u0441\u0442\u0430\u0442\u0435\u0439 \u0432 \u0438\u043d\u0442\u0435\u0440\u043d\u0435\u0442\u0435.<\/li>\n<li>\u0420\u0430\u0437\u0440\u0435\u0436\u0435\u043d\u043d\u0430\u044f \u0442\u0430\u0431\u043b\u0438\u0446\u0430 (Sparse Table). \u041f\u0440\u0435\u0434\u043f\u043e\u0434\u0441\u0447\u0435\u0442 <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/7b9\/f3b\/a34\/7b9f3ba340d0185e0342013999f57068.svg\" alt=\"$O(N\\log{N})$\" data-tex=\"inline\"><\/math>, \u0437\u0430\u043f\u0440\u043e\u0441 <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/655\/b80\/5d6\/655b805d68b4b00a4e90f64eefbc6f1c.svg\" alt=\"$O(1)$\" data-tex=\"inline\"><\/math>. <a href=\"http:\/\/neerc.ifmo.ru\/wiki\/index.php?title=%D0%A0%D0%B5%D1%88%D0%B5%D0%BD%D0%B8%D0%B5_RMQ_%D1%81_%D0%BF%D0%BE%D0%BC%D0%BE%D1%89%D1%8C%D1%8E_%D1%80%D0%B0%D0%B7%D1%80%D0%B5%D0%B6%D0%B5%D0%BD%D0%BD%D0%BE%D0%B9_%D1%82%D0%B0%D0%B1%D0%BB%D0%B8%D1%86%D1%8B\">\u0421\u0442\u0430\u0442\u044c\u044f<\/a>.<\/li>\n<\/ol>\n<p>  <\/p>\n<p>\u041a \u0441\u043e\u0436\u0430\u043b\u0435\u043d\u0438\u044e, \u043e\u0441\u043e\u0431\u043e \u0441\u0438\u043b\u044c\u043d\u044b\u0435 \u043a\u043e\u043b\u0434\u0443\u043d\u0441\u0442\u0432\u0430 \u043a\u0430\u043a \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u0424\u0430\u0440\u0430\u043a\u0430-\u041a\u043e\u043b\u0442\u043e\u043d\u0430 \u0438 \u0411\u0435\u043d\u0434\u0435\u0440\u0430 (\u043f\u0440\u0435\u0434\u043f\u043e\u0434\u0441\u0447\u0435\u0442 <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/11b\/bac\/909\/11bbac909816a3563f0b61feec7a26f4.svg\" alt=\"$O(N)$\" data-tex=\"inline\"><\/math>, \u0437\u0430\u043f\u0440\u043e\u0441 <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/655\/b80\/5d6\/655b805d68b4b00a4e90f64eefbc6f1c.svg\" alt=\"$O(1)$\" data-tex=\"inline\"><\/math>) \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u0442\u044c \u043d\u0435\u043b\u044c\u0437\u044f, \u0442\u0430\u043a \u043a\u0430\u043a \u0432\u043a\u0443\u0440\u0438\u0432 <a href=\"http:\/\/neerc.ifmo.ru\/wiki\/index.php?title=%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%A4%D0%B0%D1%80%D0%B0%D0%BA%D0%B0-%D0%9A%D0%BE%D0%BB%D1%82%D0%BE%D0%BD%D0%B0_%D0%B8_%D0%91%D0%B5%D0%BD%D0%B4%D0%B5%D1%80%D0%B0\">\u0441\u0442\u0430\u0442\u044c\u0438<\/a>, \u043c\u043e\u0436\u043d\u043e \u043f\u043e\u043d\u044f\u0442\u044c, \u043e\u043d\u0438 \u0441\u043e\u0437\u0434\u0430\u043d\u044b \u0442\u043e\u043b\u044c\u043a\u043e \u0434\u043b\u044f \u0442\u0430\u043a\u0438\u0445 \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u0439 <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/ddc\/188\/28e\/ddc18828e11c4110c4dffc6b5177cf1b.svg\" alt=\"$\\varphi$\" data-tex=\"inline\"><\/math>, \u0447\u0442\u043e <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/95b\/53f\/ef0\/95b53fef0346ff45f6b7fda40ca5554c.svg\" alt=\"$\\varphi(\\alpha, \\beta) \\in \\{\\alpha, \\beta\\}$\" data-tex=\"inline\"><\/math>, \u0442\u043e \u0435\u0441\u0442\u044c \u0440\u0435\u0437\u0443\u043b\u044c\u0442\u0430\u0442 \u043a\u043e\u043c\u043c\u0443\u0442\u0430\u0442\u0438\u0432\u043d\u043e\u0439 \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u0438 \u2014 \u043e\u0434\u0438\u043d \u0438\u0437 \u0430\u0440\u0433\u0443\u043c\u0435\u043d\u0442\u043e\u0432 (\u0436\u0430\u043b\u044c, \u0430 \u0442\u0430\u043a \u0445\u043e\u0442\u0435\u043b\u043e\u0441\u044c&#8230;)<\/p>\n<p>  <\/p>\n<p>\u0422\u0435\u043f\u0435\u0440\u044c \u0432\u043e\u0437\u044c\u043c\u0435\u043c <code>SetPlaceColor<\/code>. \u0422\u0443\u0442 \u043d\u0430\u0434\u043e \u043f\u0440\u043e\u0438\u0437\u0432\u0435\u0441\u0442\u0438 \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u044e \u043d\u0430 \u043e\u0442\u0440\u0435\u0437\u043a\u0435 \u043c\u0430\u0441\u0441\u0438\u0432\u0430. \u042d\u0442\u043e \u0442\u043e\u0436\u0435 \u043c\u043e\u0436\u043d\u043e \u0434\u0435\u043b\u0430\u0442\u044c \u0441 SQRT-\u0434\u0435\u043a\u043e\u043c\u043f\u043e\u0437\u0438\u0446\u0438\u0435\u0439 \u0438\u043b\u0438 \u0434\u0435\u0440\u0435\u0432\u043e\u043c \u043e\u0442\u0440\u0435\u0437\u043a\u043e\u0432 \u0441 \u043b\u0435\u043d\u0438\u0432\u044b\u043c \u043e\u0431\u043d\u043e\u0432\u043b\u0435\u043d\u0438\u0435\u043c (\u043e\u043d\u043e \u0436\u0435 &#171;\u0441 \u043f\u0440\u043e\u0442\u0430\u043b\u043a\u0438\u0432\u0430\u043d\u0438\u0435\u043c&#187;). \u0410 \u0434\u043b\u044f \u043e\u0431\u0435\u0438\u0445 \u0444\u0443\u043d\u043a\u0446\u0438\u0439 \u043e\u0434\u043d\u043e\u0432\u0440\u0435\u043c\u0435\u043d\u043d\u043e \u043c\u043e\u0436\u043d\u043e \u0435\u0449\u0435 \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u0442\u044c \u0443\u0431\u0435\u0440-\u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u0443 <a href=\"http:\/\/neerc.ifmo.ru\/wiki\/index.php?title=%D0%94%D0%B5%D0%BA%D0%B0%D1%80%D1%82%D0%BE%D0%B2%D0%BE_%D0%B4%D0%B5%D1%80%D0%B5%D0%B2%D0%BE_%D0%BF%D0%BE_%D0%BD%D0%B5%D1%8F%D0%B2%D0%BD%D0%BE%D0%BC%D1%83_%D0%BA%D0%BB%D1%8E%D1%87%D1%83\">\u0434\u0435\u043a\u0430\u0440\u0442\u043e\u0432\u043e \u0434\u0435\u0440\u0435\u0432\u043e \u043f\u043e \u043d\u0435\u044f\u0432\u043d\u043e\u043c\u0443 \u043a\u043b\u044e\u0447\u0443<\/a> \u0441 \u043e\u0431\u043d\u043e\u0432\u043b\u0435\u043d\u0438\u0435\u043c \u0438 \u0437\u0430\u043f\u0440\u043e\u0441\u043e\u043c \u0437\u0430 \u043b\u043e\u0433\u0430\u0440\u0438\u0444\u043c.<\/p>\n<p>  <\/p>\n<p>\u0415\u0449\u0435 \u043c\u043e\u0436\u043d\u043e \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u0442\u044c \u0440\u0430\u0441\u0448\u0438\u0440\u0435\u043d\u0438\u0435 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0430 \u0434\u043b\u044f \u0447\u0435\u0440\u043d\u043e\u0433\u043e-\u0431\u0435\u043b\u043e\u0433\u043e \u043a\u0440\u043e\u0441\u0441\u0432\u043e\u0440\u0434\u0430 \u2014 \u0447\u0430\u0441\u0442\u0438\u0447\u043d\u044b\u0435 \u0441\u0443\u043c\u043c\u044b \u0434\u043b\u044f \u0432\u0441\u0435\u0445 \u0446\u0432\u0435\u0442\u043e\u0432.<\/p>\n<p>  <\/p>\n<p>\u0418\u0442\u0430\u043a, \u0432\u043e\u0437\u043d\u0438\u043a\u0430\u0435\u0442 \u0432\u043e\u043f\u0440\u043e\u0441 \u2014 <em>\u043f\u043e\u0447\u0435\u043c\u0443<\/em> \u043c\u044b \u043d\u0435 \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u0435\u043c \u0432\u0441\u0435 \u044d\u0442\u043e \u0431\u043e\u0433\u0430\u0442\u0441\u0442\u0432\u043e \u043a\u043e\u043c\u043f\u043b\u044e\u043a\u0442\u0435\u0440\u043d \u0441\u0430\u0435\u043d\u0441, \u0430 \u0434\u0435\u043b\u0430\u0435\u043c \u0437\u0430 \u043b\u0438\u043d\u0438\u044e? \u041d\u0430 \u044d\u0442\u043e \u0435\u0441\u0442\u044c \u043d\u0435\u0441\u043a\u043e\u043b\u044c\u043a\u043e \u043e\u0442\u0432\u0435\u0442\u043e\u0432:<\/p>\n<p>  <\/p>\n<ol>\n<li>\u041c\u0435\u043d\u044c\u0448\u0430\u044f \u0441\u043b\u043e\u0436\u043d\u043e\u0441\u0442\u044c \u0432\u044b\u0447\u0438\u0441\u043b\u0435\u043d\u0438\u0439 \u043d\u0435 \u0437\u043d\u0430\u0447\u0438\u0442 \u043c\u0435\u043d\u044c\u0448\u0435\u0435 \u0432\u0440\u0435\u043c\u044f \u0440\u0430\u0431\u043e\u0442\u044b. \u0410\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u0437\u0430 <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/e56\/03a\/930\/e5603a93005472b55d2da276e235df4c.svg\" alt=\"$\\log$\" data-tex=\"inline\"><\/math> \u043c\u043e\u0436\u0435\u0442 \u043f\u043e\u0442\u0440\u0435\u0431\u043e\u0432\u0430\u0442\u044c \u0440\u0430\u0437\u043b\u0438\u0447\u043d\u044b\u0445 \u043f\u0440\u0435\u043f\u043e\u0434\u0441\u0447\u0435\u0442\u043e\u0432, \u0432\u044b\u0434\u0435\u043b\u0435\u043d\u0438\u0439 \u043f\u0430\u043c\u044f\u0442\u0438, \u0434\u0440\u0443\u0433\u043e\u0439 \u0442\u0440\u044f\u0441\u043a\u0438 \u0440\u0435\u0441\u0443\u0440\u0441\u043e\u0432 \u2014 \u0443 \u044d\u0442\u043e\u0433\u043e \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0430 \u043c\u043e\u0436\u0435\u0442 \u0431\u044b\u0442\u044c \u0434\u043e\u0432\u043e\u043b\u044c\u043d\u043e \u0432\u044b\u0441\u043e\u043a\u0430\u044f \u043a\u043e\u043d\u0441\u0442\u0430\u043d\u0442\u0430 (\u043d\u0435 \u0432 \u0441\u043c\u044b\u0441\u043b\u0435 magic number \u0432 \u043d\u0435\u0439\u0440\u043e\u043d\u043e\u0447\u043a\u0430\u0445, \u0430 \u0430\u0444\u0444\u0435\u043a\u0442 \u043f\u043e \u0432\u0440\u0435\u043c\u0435\u043d\u0438 \u0440\u0430\u0431\u043e\u0442\u044b). \u041e\u0447\u0435\u0432\u0438\u0434\u043d\u043e, \u0447\u0442\u043e \u0435\u0441\u043b\u0438 <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/414\/608\/79e\/41460879e1e9db3758b40a97c3a756c2.svg\" alt=\"$N=10^{5}$\" data-tex=\"inline\"><\/math>, \u0442\u043e \u0443\u0441\u043b\u043e\u0432\u043d\u044b\u0439 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u0437\u0430 <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/8ba\/850\/44a\/8ba85044aceb43a1ded7e5f02e9bdf16.svg\" alt=\"$O(N^2)$\" data-tex=\"inline\"><\/math> \u0431\u0443\u0434\u0435\u0442 \u0440\u0430\u0431\u043e\u0442\u0430\u0442\u044c \u0443\u0441\u043b\u043e\u0432\u043d\u044b\u0435 10 \u0441\u0435\u043a\u0443\u043d\u0434, \u0430 \u0443\u0441\u043b\u043e\u0432\u043d\u044b\u0439 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/7b9\/f3b\/a34\/7b9f3ba340d0185e0342013999f57068.svg\" alt=\"$O(N\\log{N})$\" data-tex=\"inline\"><\/math> \u0437\u0430 \u0443\u0441\u043b\u043e\u0432\u043d\u044b\u0435 0.150 \u0441\u0435\u043a\u0443\u043d\u0434, \u043d\u043e \u0432\u0441\u0435 \u043c\u043e\u0436\u0435\u0442 \u043f\u043e\u043c\u0435\u043d\u044f\u0442\u044c\u0441\u044f \u043f\u0440\u0438 \u0434\u043e\u0441\u0442\u0430\u0442\u043e\u0447\u043d\u043e \u043c\u0430\u043b\u0435\u043d\u044c\u043a\u0438\u0445 <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/1e8\/0c3\/b30\/1e80c3b3087c0a57b68ad11261a9ec2b.svg\" alt=\"$N$\" data-tex=\"inline\"><\/math>, \u043e\u0441\u043e\u0431\u0435\u043d\u043d\u043e \u043a\u043e\u0433\u0434\u0430 \u0442\u0430\u043a\u0438\u0445 \u0432\u044b\u0447\u0438\u0441\u043b\u0435\u043d\u0438\u0439 \u043c\u043d\u043e\u0433\u043e. \u0415\u0449\u0435 \u043d\u0435\u043f\u043e\u043d\u044f\u0442\u043d\u0435\u0435, \u043a\u043e\u0433\u0434\u0430 \u0441\u043b\u043e\u0436\u043d\u043e\u0441\u0442\u0438 \u043e\u0447\u0435\u043d\u044c \u043f\u043e\u0445\u043e\u0436\u0438\u0435 \u0438 \u043e\u0434\u043d\u043e\u0439 \u0441\u043b\u043e\u0436\u043d\u043e\u0441\u0442\u0438 \u0441\u043b\u043e\u0436\u043d\u043e \u043f\u0435\u0440\u0435\u0431\u0438\u0442\u044c \u0434\u0440\u0443\u0433\u0443\u044e \u0441\u043b\u043e\u0436\u043d\u043e\u0441\u0442\u044c (\u0441\u043b\u043e\u0436\u043d\u044b\u0435 \u043f\u0440\u0438\u043a\u043e\u043b\u044b): <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/bdf\/4e9\/45d\/bdf4e945dc34f9bca7521b298a9c0e69.svg\" alt=\"$O(N\\sqrt{N})$\" data-tex=\"inline\"><\/math> versus <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/fca\/43a\/a79\/fca43aa79257dd29ae3bd4d8564d098d.svg\" alt=\"$O(N\\log^2{N})$\" data-tex=\"inline\"><\/math>. \u0412 \u043d\u0430\u0448\u0435\u0439 \u0437\u0430\u0434\u0430\u0447\u0435 <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/1e8\/0c3\/b30\/1e80c3b3087c0a57b68ad11261a9ec2b.svg\" alt=\"$N$\" data-tex=\"inline\"><\/math> (\u0434\u043b\u0438\u043d\u0430 \u0440\u044f\u0434\u0430) \u043e\u0447\u0435\u043d\u044c \u043c\u0430\u043b\u0435\u043d\u044c\u043a\u043e\u0435 \u2014 \u0432 \u0441\u0440\u0435\u0434\u043d\u0435\u043c \u043e\u043a\u043e\u043b\u043e 15-30.<\/li>\n<li>\u0417\u0430\u043f\u0440\u043e\u0441\u043e\u0432 \u043c\u043e\u0436\u0435\u0442 \u043e\u043a\u0430\u0437\u0430\u0442\u044c\u0441\u044f \u0434\u043e\u0441\u0442\u0430\u0442\u043e\u0447\u043d\u043e \u043c\u0430\u043b\u043e, \u0447\u0442\u043e\u0431\u044b \u043f\u0440\u0435\u0434\u043f\u043e\u0441\u0447\u0435\u0442\u044b \u0431\u044b\u043b\u0438 \u0431\u0435\u0441\u043f\u043e\u043b\u0435\u0437\u043d\u044b\u043c\u0438 \u0438 \u0436\u0440\u0430\u043b\u0438 \u0440\u0435\u0441\u0443\u0440\u0441\u044b \u043f\u0440\u043e\u0441\u0442\u043e \u0442\u0430\u043a.<\/li>\n<\/ol>\n<p>  <\/p>\n<p>\u0422\u043e \u0435\u0441\u0442\u044c \u043e\u0431\u044a\u044f\u0441\u043d\u0435\u043d\u0438\u0435 \u043f\u0440\u043e\u0441\u0442\u043e\u0435 \u2014 \u043e\u0431\u0430 \u044d\u0442\u0438\u0445 \u043f\u0443\u043d\u043a\u0442\u0430 \u0432\u044b\u043f\u043e\u043b\u043d\u044f\u044e\u0442\u0441\u044f \u0438 \u0432\u0441\u0442\u0430\u0432\u043a\u0430 \u044d\u0442\u0438\u0445 \u0447\u0443\u0434\u0435\u0441 \u043f\u0440\u043e\u0433\u0440\u0430\u043c\u043c\u0435\u0440\u0441\u043a\u043e\u0439 \u043c\u044b\u0441\u043b\u0438 \u0432\u043c\u0435\u0441\u0442\u043e \u0442\u0443\u043f\u043e\u0433\u043e \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0430 \u043b\u0438\u0431\u043e \u043e\u0447\u0435\u043d\u044c \u0441\u043b\u0430\u0431\u043e \u043e\u043f\u0442\u0438\u043c\u0438\u0437\u0438\u0440\u0443\u0435\u0442 \u043f\u0440\u043e\u0433\u0440\u0430\u043c\u043c\u0443, \u043b\u0438\u0431\u043e \u0442\u043e\u043b\u044c\u043a\u043e \u0443\u0432\u0435\u043b\u0438\u0447\u0438\u0432\u0430\u0435\u0442 \u0432\u0440\u0435\u043c\u044f \u0440\u0430\u0431\u043e\u0442\u044b \u0438\u0437-\u0437\u0430 \u0441\u043f\u0435\u0446\u0438\u0444\u0438\u043a\u0438 \u0432\u044b\u0447\u0438\u0441\u043b\u0435\u043d\u0438\u0439 \u2014 \u043e\u0447\u0435\u043d\u044c \u043c\u0430\u043b\u0435\u043d\u044c\u043a\u043e\u0433\u043e <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/1e8\/0c3\/b30\/1e80c3b3087c0a57b68ad11261a9ec2b.svg\" alt=\"$N$\" data-tex=\"inline\"><\/math> \u0438 \u043d\u0435 \u0442\u0430\u043a\u043e\u0433\u043e \u0431\u043e\u043b\u044c\u0448\u043e\u0433\u043e \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u0430 \u0437\u0430\u043f\u0440\u043e\u0441\u043e\u0432, \u0447\u0442\u043e\u0431\u044b \u043e\u043d\u0438 \u0433\u0440\u0443\u0437\u0438\u043b\u0438 \u043f\u0440\u043e\u0446\u0435\u0441\u0441\u043e\u0440. \u0424\u0430\u043a\u0442 \u043f\u0440\u043e \u0437\u0430\u043f\u0440\u043e\u0441\u044b \u0434\u043e\u043a\u0430\u0437\u044b\u0432\u0430\u0435\u0442 \u0442\u043e, \u0447\u0442\u043e \u043f\u043e \u043c\u043d\u0435\u043d\u0438\u044e \u043f\u0440\u043e\u0444\u0430\u0439\u043b\u0435\u0440\u0430 \u0442\u0435 \u0444\u0443\u043d\u043a\u0446\u0438\u0438 \u0437\u0430\u043d\u0438\u043c\u0430\u044e\u0442 ~25% \u0438 ~11% \u0432\u0440\u0435\u043c\u0435\u043d\u0438 \u0441\u043e\u043e\u0442\u0432\u0435\u0442\u0441\u0442\u0432\u0435\u043d\u043d\u043e, \u0442\u043e \u0435\u0441\u0442\u044c \u0434\u043e\u0432\u043e\u043b\u044c\u043d\u043e \u043c\u0430\u043b\u043e \u0434\u043b\u044f \u0442\u0430\u043a\u043e\u0433\u043e \u043f\u043e\u0442\u0435\u043d\u0446\u0438\u0430\u043b\u044c\u043d\u043e \u0441\u043b\u0430\u0431\u043e\u0433\u043e \u043c\u0435\u0441\u0442\u0430 \u043f\u0440\u043e\u0433\u0440\u0430\u043c\u043c\u044b. \u0414\u0430\u0436\u0435 \u0435\u0441\u043b\u0438 \u0443 \u043d\u0430\u0441 \u0438\u0437-\u0437\u0430 \u044d\u0442\u043e\u0433\u043e \u0432\u043e\u0437\u043d\u0438\u043a\u0430\u0435\u0442 \u0431\u043e\u043b\u044c\u0448\u0430\u044f \u043e\u0446\u0435\u043d\u043a\u0430 \u0441\u043b\u043e\u0436\u043d\u043e\u0441\u0442\u0438 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0430, \u0441\u0442\u043e\u0438\u0442 \u043f\u043e\u043d\u0438\u043c\u0430\u0442\u044c, \u0447\u0442\u043e \u0432 \u0442\u0430\u043a\u0438\u0445 \u0442\u0438\u043f\u0430\u0445 \u0437\u0430\u0434\u0430\u0447 \u044d\u0442\u043e \u043e\u0446\u0435\u043d\u043a\u0430 \u0441\u0432\u0435\u0440\u0445\u0443, \u0430 \u0440\u0435\u0430\u043b\u044c\u043d\u043e\u0435 \u0432\u0440\u0435\u043c\u044f \u0440\u0430\u0431\u043e\u0442\u044b \u043d\u0430 \u0440\u0430\u043d\u0434\u043e\u043c\u043d\u043e\u043c \u043a\u0440\u043e\u0441\u0441\u0432\u043e\u0440\u0434\u0435 \u0432\u0441\u0435\u0433\u0434\u0430 \u043f\u0440\u0435\u043c\u043d\u043e\u0433\u043e \u043d\u0438\u0436\u0435.<\/p>\n<p>  <\/p>\n<p>\u041d\u043e \u043d\u0435 \u0441\u0442\u043e\u0438\u0442 \u0437\u0430\u0431\u044b\u0432\u0430\u0442\u044c \u043f\u0440\u043e \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u044b \u0434\u0430\u043d\u043d\u044b\u0445 \u2014 \u043e\u043d\u0438 \u043c\u043e\u0433\u0443\u0442 \u043f\u0440\u0438\u0433\u043e\u0434\u0438\u0442\u044c\u0441\u044f \u0432 \u0434\u0440\u0443\u0433\u0438\u0445 \u0441\u043b\u0443\u0447\u0430\u044f\u0445, \u0442\u0430\u043a \u0447\u0442\u043e \u044f \u0432\u043a\u043b\u044e\u0447\u0438\u043b \u0438\u0445 \u0432 \u0441\u043f\u0438\u0441\u043e\u043a \u043e\u043f\u0442\u0438\u043c\u0438\u0437\u0430\u0446\u0438\u0439. \u041f\u0435\u0440\u0435\u0445\u043e\u0434\u0438\u043c \u043a \u0441\u043b\u0435\u0434\u0443\u044e\u0449\u0435\u043c\u0443 \u043f\u043e \u0441\u043f\u0438\u0441\u043a\u0443.<\/p>\n<p>  <\/p>\n<ul>\n<li>\u041f\u0440\u0430\u0432\u043a\u0438 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0430. \u041c\u043e\u0436\u0435\u0442 \u043e\u043a\u0430\u0437\u0430\u0442\u044c\u0441\u044f \u0442\u0430\u043a, \u0447\u0442\u043e \u0432 \u0441\u0440\u0435\u0434\u043d\u0435\u043c \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u043d\u0430 \u044d\u0442\u0438\u0445 \u0432\u0445\u043e\u0434\u043d\u044b\u0445 \u0434\u0430\u043d\u043d\u044b\u0445 \u043e\u0447\u0435\u043d\u044c \u043d\u0435\u043f\u043b\u043e\u0445\u043e \u043d\u0430\u0447\u0438\u043d\u0430\u0435\u0442 \u0440\u0430\u0431\u043e\u0442\u0430\u0442\u044c, \u0435\u0441\u043b\u0438 \u043f\u043e\u043c\u0435\u043d\u044f\u0442\u044c \u0447\u0442\u043e-\u0442\u043e \u043d\u0435\u043e\u0447\u0435\u0432\u0438\u0434\u043d\u043e\u0435. \u0412 \u043d\u0430\u0448\u0435\u043c \u0441\u043b\u0443\u0447\u0430\u0435 \u044d\u0442\u0438\u043c \u043c\u043e\u0436\u0435\u0442 \u0431\u044b\u0442\u044c \u0442\u0430\u043a\u043e\u0435: \u043b\u043e\u0433\u0438\u0447\u043d\u043e \u0436\u0435 \u043f\u0440\u0435\u0434\u043f\u043e\u043b\u043e\u0436\u0438\u0442\u044c, \u0447\u0442\u043e \u0435\u0441\u043b\u0438 \u043c\u044b \u0443\u0441\u043f\u0435\u0448\u043d\u043e \u043e\u0431\u043d\u043e\u0432\u0438\u043b\u0438 \u0434\u0430\u043d\u043d\u044b\u0435 \u0432 \u0441\u0442\u0440\u043e\u043a\u0435, \u0442\u043e \u043e\u0431\u043d\u043e\u0432\u043b\u0435\u043d\u043d\u044b\u0435 \u0432 \u043d\u0435\u043c \u043a\u043b\u0435\u0442\u043a\u0438 \u0441\u043a\u043e\u0440\u0435\u0435 \u0432\u0441\u0435\u0433\u043e &#171;\u0442\u0440\u0438\u0433\u0433\u0435\u0440\u044f\u0442&#187; \u0441\u043e\u043e\u0442\u0432\u0435\u0442\u0441\u0442\u0432\u0443\u044e\u0449\u0438\u0435 \u0441\u0442\u043e\u043b\u0431\u0446\u044b? \u0417\u043d\u0430\u0447\u0438\u0442, \u043b\u0443\u0447\u0448\u0435 \u044d\u0442\u0438 \u0441\u0442\u043e\u043b\u0431\u0446\u044b \u043e\u0431\u043d\u043e\u0432\u0438\u0442\u044c \u0431\u044b\u0441\u0442\u0440\u0435\u0435 \u0432\u0441\u0435\u0445, \u0441\u0440\u0430\u0437\u0443 \u043f\u043e\u0441\u043b\u0435 \u044d\u0442\u043e\u0439 \u0441\u0442\u0440\u043e\u043a\u0438! \u0422\u043e \u0435\u0441\u0442\u044c \u043e\u0431\u0440\u0430\u0437\u0443\u0435\u0442\u0441\u044f \u043e\u0447\u0435\u0440\u0435\u0434\u044c \u0438\u0437 \u0442\u0430\u043a\u0438\u0445 \u043f\u043e\u0434\u0437\u0430\u0434\u0430\u0447. \u042f \u043d\u0435 \u043f\u0440\u043e\u0431\u043e\u0432\u0430\u043b \u0438\u043c\u0435\u043d\u043d\u043e \u0442\u0430\u043a\u043e\u0439 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c, \u043c\u043e\u0436\u0435\u0442 \u044d\u0442\u043e \u0440\u0435\u0430\u043b\u044c\u043d\u043e \u0431\u044b\u0441\u0442\u0440\u0435\u0435 \u043d\u0430 \u043d\u0430\u0448\u0435\u043c \u0434\u0430\u0442\u0430\u0441\u0435\u0442\u0435.<\/li>\n<li>\u0412\u043d\u0435\u0437\u0430\u043f\u043d\u044b\u0435 \u0438\u0437\u043c\u0435\u043d\u0435\u043d\u0438\u044f \u0442\u0435\u0445\u0437\u0430\u0434\u0430\u043d\u0438\u044f (\u043e\u043a\u0430\u0436\u0435\u0442\u0441\u044f, \u0447\u0442\u043e \u043f\u043e\u0441\u0442\u0443\u043f\u0430\u044e\u0442 \u043a\u0440\u043e\u0441\u0441\u0432\u043e\u0440\u0434\u044b \u043f\u043e 1337 \u0446\u0432\u0435\u0442\u043e\u0432 \u0438\u043b\u0438 \u0440\u0430\u0437\u043c\u0435\u0440\u043e\u043c 1000&#215;1000) \u0442\u043e\u0436\u0435 \u0442\u0440\u0435\u0431\u0443\u044e\u0442 \u043e\u043f\u0442\u0438\u043c\u0438\u0437\u0430\u0446\u0438\u0438. \u0414\u043b\u044f \u0431\u043e\u043b\u044c\u0448\u043e\u0433\u043e \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e \u0446\u0432\u0435\u0442\u043e\u0432 \u043c\u043e\u0436\u043d\u043e \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u0442\u044c \u0431\u044b\u0441\u0442\u0440\u044b\u0439 <a href=\"https:\/\/en.cppreference.com\/w\/cpp\/utility\/bitset\">std::bitset<\/a>, \u0434\u043b\u044f \u0440\u0430\u0437\u043c\u0435\u0440\u0430 \u2014 \u0442\u0435 \u0436\u0435 \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u044b \u0434\u0430\u043d\u043d\u044b\u0445, \u0438 \u0442\u0430\u043a \u0434\u0430\u043b\u0435\u0435.<\/li>\n<\/ul>\n<p>  <\/p>\n<p>\u0412 \u043e\u0431\u0449\u0435\u043c, \u0432\u043e\u0442 \u0442\u0430\u043a\u0438\u0435 \u043f\u0440\u0438\u043a\u043e\u043b\u044c\u043d\u044b\u0435 \u043e\u043f\u0442\u0438\u043c\u0438\u0437\u0430\u0446\u0438\u0438. &#171;\u041f\u0438\u0445\u0430\u043d\u0438\u0435&#187; \u0431\u0435\u0434\u043d\u043e\u0433\u043e \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0430 \u0432 \u0437\u0430\u0432\u0438\u0441\u0438\u043c\u043e\u0441\u0442\u0438 \u043e\u0442 \u0443\u0441\u043b\u043e\u0432\u0438\u0439 \u044d\u0442\u043e \u0432\u0435\u0441\u0435\u043b\u043e \u0438 \u043f\u043e\u0437\u043d\u0430\u0432\u0430\u0442\u0435\u043b\u044c\u043d\u043e. \u041c\u043e\u0436\u043d\u043e \u0443\u0437\u043d\u0430\u0442\u044c \u043f\u0440\u043e \u0440\u0430\u0437\u043d\u044b\u0435 \u043a\u0440\u0443\u0442\u044b\u0435 \u0432\u0435\u0449\u0438, \u043a\u0430\u043a \u0432\u0441\u0442\u0440\u043e\u0435\u043d\u043d\u043e\u0435 \u0434\u0435\u043a\u0430\u0440\u0442\u043e\u0432\u043e \u0434\u0435\u0440\u0435\u0432\u043e \u043f\u043e \u043d\u0435\u044f\u0432\u043d\u043e\u043c\u0443 \u043a\u043b\u044e\u0447\u0443 \u0432 C++ (\u044d\u0442\u043e <a href=\"https:\/\/habr.com\/post\/144736\/\">rope<\/a>, \u043d\u043e \u0432\u0435\u043b\u043e\u0441\u0438\u043f\u0435\u0434\u043d\u0430\u044f \u043f\u0438\u0441\u0430\u043d\u0438\u043d\u0430 \u043f\u0440\u0430\u043a\u0442\u0438\u0447\u0435\u0441\u043a\u0438 \u0432\u0441\u0435\u0433\u0434\u0430 \u0440\u0430\u0431\u043e\u0442\u0430\u0435\u0442 \u0431\u044b\u0441\u0442\u0440\u0435\u0435), <a href=\"http:\/\/codeforces.com\/blog\/entry\/11080\">\u043e\u0441\u043e\u0431\u044b\u0435 \u0432\u0441\u0442\u0440\u043e\u0435\u043d\u043d\u044b\u0435 \u0441\u043e\u0440\u0442\u0430 \u0434\u0435\u0440\u0435\u0432\u044c\u0435\u0432<\/a> \u0438 <a href=\"http:\/\/codeforces.com\/topic\/61081\/\">\u0441\u043f\u0440\u044f\u0442\u0430\u043d\u043d\u044b\u0439 hashtable<\/a>, \u0440\u0430\u0431\u043e\u0442\u0430\u044e\u0449\u0438\u0439 \u0432 3-6 \u0440\u0430\u0437\u0430 \u0431\u044b\u0441\u0442\u0440\u0435\u0435 \u043f\u043e \u0432\u0441\u0442\u0430\u0432\u043a\u0435\/\u0443\u0434\u0430\u043b\u0435\u043d\u0438\u044e \u0438 \u0432 4-10 \u0440\u0430\u0437 \u043f\u043e \u0437\u0430\u043f\u0438\u0441\u0438\/\u0447\u0442\u0435\u043d\u0438\u044e, \u0447\u0435\u043c unordered_map. \u041d\u0435 \u0433\u043e\u0432\u043e\u0440\u044f \u0443\u0436\u0435 \u043f\u0440\u043e \u0440\u0430\u0437\u043b\u0438\u0447\u043d\u044b\u0435 \u043d\u0435\u0441\u0442\u0430\u043d\u0434\u0430\u0440\u0442\u043d\u044b\u0435 \u043c\u0430\u0437\u0430\u0444\u0430\u043a\u0438 \u0441\u043e \u0441\u0442\u043e\u0440\u043e\u043d\u044b, \u043d\u0430\u043f\u0440\u0438\u043c\u0435\u0440 \u0438\u0437 boost.<\/p>\n<p>  <\/p>\n<h2 id=\"rofl-omitting-format-language\">ROFL Omitting Format Language<\/h2>\n<p>  <\/p>\n<div style=\"text-align:center;\"><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/webt\/rc\/vp\/jm\/rcvpjmbinhow4aakwya-xgt3rm4.png\"><\/div>\n<p>  <\/p>\n<p>\u0412\u0434\u043e\u0445\u043d\u043e\u0432\u0438\u0432\u0448\u0438\u0441\u044c \u0433\u0435\u043d\u0438\u044f\u043c\u0438 \u0434\u0430\u0432\u043d\u043e \u043c\u0438\u043d\u0443\u0432\u0448\u0438\u0445 \u0434\u043d\u0435\u0439 \u0438 \u0438\u0445 \u043c\u044b\u0441\u043b\u0438\u0442\u0435\u043b\u044c\u043d\u044b\u043c\u0438 \u043f\u0440\u043e\u0434\u0443\u043a\u0442\u0430\u043c\u0438, \u0432 \u0447\u0430\u0441\u0442\u043d\u043e\u0441\u0442\u0438 \u0441\u043e\u0432\u0435\u0440\u0448\u0435\u043d\u043d\u043e \u043d\u043e\u0432\u044b\u043c\u0438 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0430\u043c\u0438 \u0430\u0440\u0445\u0438\u0432\u0430\u0446\u0438\u0438 \u0438 \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u043e\u043d\u043a\u0430\u043c\u0438 \u0441 \u043d\u0435\u0441\u043a\u0443\u0447\u043d\u044b\u043c\u0438 \u043e\u0431\u043e\u044f\u043c\u0438, \u044f \u0442\u0430\u043a\u0436\u0435 \u043f\u0440\u0438\u0434\u0443\u043c\u0430\u043b \u043f\u0440\u0438\u043d\u0446\u0438\u043f\u0438\u0430\u043b\u044c\u043d\u043e \u043d\u043e\u0432\u044b\u0439 \u0444\u043e\u0440\u043c\u0430\u0442 \u043a\u0430\u0440\u0442\u0438\u043d\u043e\u043a, \u043e\u0441\u043d\u043e\u0432\u0430\u043d\u043d\u044b\u0439 \u043d\u0430 \u044f\u043f\u043e\u043d\u0441\u043a\u0438\u0445 \u043a\u0440\u043e\u0441\u0441\u0432\u043e\u0440\u0434\u0430\u0445 \u0438 \u044d\u0444\u0444\u0435\u043a\u0442\u0435 \u0414\u0430\u043d\u043d\u0438\u043d\u0433\u0430-\u041a\u0440\u044e\u0433\u0435\u0440\u0430.<\/p>\n<p>  <\/p>\n<p>ROFL \u2014 \u0440\u0435\u043a\u0443\u0440\u0441\u0438\u0432\u043d\u044b\u0439 \u0430\u043a\u0440\u043e\u043d\u0438\u043c, \u043f\u0440\u044f\u043c\u043e \u043a\u0430\u043a &#171;GNU&#8217;s Not Unix&#187;. \u0421\u043e\u0431\u0441\u0442\u0432\u0435\u043d\u043d\u043e, \u0441\u043c\u044b\u0441\u043b \u0444\u043e\u0440\u043c\u0430\u0442\u0430 \u0432 \u0442\u043e\u043c, \u0447\u0442\u043e \u043a\u0430\u0440\u0442\u0438\u043d\u043a\u0430 \u043a\u043e\u0434\u0438\u0440\u0443\u0435\u0442\u0441\u044f \u0432 \u0432\u0438\u0434\u0435 \u044f\u043f\u043e\u043d\u0441\u043a\u043e\u0433\u043e \u043a\u0440\u043e\u0441\u0441\u0432\u043e\u0440\u0434\u0430, \u0430 \u0440\u0435\u0434\u0430\u043a\u0442\u043e\u0440, \u0447\u0442\u043e\u0431\u044b \u043f\u0440\u043e\u0447\u0438\u0442\u0430\u0442\u044c \u0435\u0435, \u0434\u043e\u043b\u0436\u0435\u043d \u0440\u0435\u0448\u0438\u0442\u044c \u044d\u0442\u043e\u0442 \u043a\u0440\u043e\u0441\u0441\u0432\u043e\u0440\u0434. \u041e\u0442\u0441\u044e\u0434\u0430 \u0438 \u0441\u043b\u043e\u0432\u043e Omitting \u0432 \u043d\u0430\u0437\u0432\u0430\u043d\u0438\u0438 \u2014 \u0444\u043e\u0440\u043c\u0430\u0442 \u043a\u0430\u043a \u0431\u044b \u0441\u043a\u0440\u044b\u0432\u0430\u0435\u0442 \u0438\u0441\u0442\u0438\u043d\u043d\u043e\u0435 \u043f\u043e\u043b\u043e\u0436\u0435\u043d\u0438\u0435 \u0434\u0435\u043b \u0432 \u043a\u0430\u0440\u0442\u0438\u043d\u043a\u0435 (\u0447\u0442\u043e, \u043a\u0441\u0442\u0430\u0442\u0438, \u043c\u043e\u0436\u0435\u0442 \u0431\u044b\u0442\u044c \u043f\u043e\u043b\u0435\u0437\u043d\u044b\u043c \u0432 \u043a\u0440\u0438\u043f\u0442\u043e\u0433\u0440\u0430\u0444\u0438\u0438: \u043c\u043e\u0436\u043d\u043e \u043f\u0435\u0440\u0435\u0434\u0430\u0432\u0430\u0442\u044c \u044f\u043f\u043e\u043d\u0441\u043a\u0438\u0435 \u043a\u0440\u043e\u0441\u0441\u0432\u043e\u0440\u0434\u044b \u0441 \u0437\u0430\u0448\u0438\u0444\u0440\u043e\u0432\u0430\u043d\u043d\u044b\u043c\u0438 \u0432 \u043d\u0435\u043c \u043f\u0430\u0440\u043e\u043b\u044f\u043c\u0438 \u2014 \u0432\u0441\u0435 \u0445\u0430\u043a\u0435\u0440\u044b \u043f\u043e\u0432\u0435\u0441\u044f\u0442\u0441\u044f).<\/p>\n<p>  <\/p>\n<p>\u041b\u0443\u0447\u0448\u0435, \u0435\u0441\u043b\u0438 \u0444\u043e\u0440\u043c\u0430\u0442 \u0431\u044b\u043b \u0431\u044b \u043f\u043e\u0445\u043e\u0436 \u043d\u0430 <a href=\"https:\/\/matroska.org\/technical\/specs\/index.html\">Matroska<\/a> \u2014 \u0432 \u043d\u0430\u0447\u0430\u043b\u0435 \u0444\u0430\u0439\u043b\u0430 4 \u0431\u0430\u0439\u0442\u0430 [52][4F][46][4C], \u0437\u0430\u0442\u0435\u043c \u0432 \u0442\u0440\u0435\u0445 \u0431\u0430\u0439\u0442\u0430\u0445 \u0440\u0430\u0437\u043c\u0435\u0440 \u043a\u0430\u0440\u0442\u0438\u043d\u043a\u0438 \u0438 \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e \u0446\u0432\u0435\u0442\u043e\u0432, \u043f\u043e\u0442\u043e\u043c \u043e\u043f\u0438\u0441\u0430\u043d\u0438\u0435 \u0446\u0432\u0435\u0442\u043e\u0432, \u043f\u043e\u0442\u043e\u043c \u0446\u0432\u0435\u0442\u0430, \u043a\u0430\u0436\u0434\u044b\u0439 \u043f\u043e 3 \u0431\u0430\u0439\u0442\u0430, \u0438 \u043f\u043e\u0442\u043e\u043c \u043e\u043f\u0438\u0441\u0430\u043d\u0438\u0435 \u0432\u0441\u0435\u0445 \u0433\u0440\u0443\u043f\u043f \u2014 \u0434\u043b\u0438\u043d\u0430, \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e \u043a\u043b\u0435\u0442\u043e\u043a \u0438 \u0446\u0432\u0435\u0442.<\/p>\n<p>  <\/p>\n<p>\u0424\u043e\u0440\u043c\u0430\u0442 \u0441\u0432\u043e\u0431\u043e\u0434\u043d\u044b\u0439, \u043b\u0438\u0446\u0435\u043d\u0437\u0438\u044f MIT, \u0444\u0438\u043d\u0430\u043d\u0441\u043e\u0432\u044b\u0435 \u043e\u0442\u0447\u0438\u0441\u043b\u0435\u043d\u0438\u044f \u0434\u043e\u0431\u0440\u043e\u0432\u043e\u043b\u044c\u043d\u044b\u0435 \u2014 \u043c\u043d\u0435 \u043d\u0430 \u043a\u043e\u0444\u0435, \u043a\u0430\u043a \u0430\u0432\u0442\u043e\u0440\u0443.<\/p>\n<p>  <\/p>\n<h2 id=\"ishodniki\">\u0418\u0441\u0445\u043e\u0434\u043d\u0438\u043a\u0438<\/h2>\n<p>  <\/p>\n<p>\u0418\u0441\u0445\u043e\u0434\u043d\u0438\u043a\u0438 \u043f\u0440\u043e\u0433\u0440\u0430\u043c\u043c\u044b \u043b\u0435\u0436\u0430\u0442 \u043d\u0430 <a href=\"https:\/\/github.com\/Izaron\/Nonograms\">GitHub<\/a>. \u0423 \u043f\u0440\u043e\u0433\u0440\u0430\u043c\u043c\u044b \u0435\u0441\u0442\u044c \u043c\u043d\u043e\u0436\u0435\u0441\u0442\u0432\u043e \u0432\u043e\u0437\u043c\u043e\u0436\u043d\u044b\u0445 \u0430\u0440\u0433\u0443\u043c\u0435\u043d\u0442\u043e\u0432, \u0433\u0435\u043d\u0435\u0440\u0430\u0446\u0438\u044f \u043a\u0440\u043e\u0441\u0441\u0432\u043e\u0440\u0434\u0430 \u0438\u0437 \u043a\u0430\u0440\u0442\u0438\u043d\u043a\u0438, \u0433\u0435\u043d\u0435\u0440\u0430\u0446\u0438\u044f \u043a\u0430\u0440\u0442\u0438\u043d\u043e\u043a \u0438\u0437 \u043a\u0440\u043e\u0441\u0441\u0432\u043e\u0440\u0434\u0430 (\u043a\u0441\u0442\u0430\u0442\u0438, \u043f\u043e\u0447\u0442\u0438 \u0432\u0441\u0435 \u043a\u0430\u0440\u0442\u0438\u043d\u043a\u0438 \u0432 \u0441\u0442\u0430\u0442\u044c\u0435 \u0441\u0433\u0435\u043d\u0435\u0440\u0438\u0440\u043e\u0432\u0430\u043d\u044b \u0447\u0435\u0440\u0435\u0437 \u044d\u0442\u043e\u0442 \u043a\u043e\u0434). \u0414\u043e\u043f\u043e\u043b\u043d\u0438\u0442\u0435\u043b\u044c\u043d\u044b\u043c\u0438 \u0431\u0438\u0431\u043b\u0438\u043e\u0442\u0435\u043a\u0430\u043c\u0438 \u0431\u044b\u043b\u0438 <a href=\"https:\/\/github.com\/ImageMagick\/ImageMagick\">Magick++<\/a> \u0438 <a href=\"https:\/\/github.com\/Taywee\/args\">args<\/a>.<\/p>\n<p>  <\/p>\n<p>\u0412 \u0440\u0435\u043f\u043e\u0437\u0438\u0442\u043e\u0440\u0438\u0438 \u043a\u0430\u0440\u0442\u0438\u043d\u043a\u0438 \u0434\u043b\u044f \u043a\u0440\u043e\u0441\u0441\u0432\u043e\u0440\u0434\u0430 \u044f \u0434\u043e\u0431\u0430\u0432\u0438\u043b \u043d\u0435\u0441\u043a\u043e\u043b\u044c\u043a\u043e <a href=\"https:\/\/github.com\/Izaron\/Nonograms\/tree\/master\/puzzles\">\u043f\u0440\u0438\u043c\u0435\u0440\u043e\u0432<\/a>, \u0432\u0437\u044f\u0442\u044b\u0445 \u0438\u0437 \u0438\u043d\u0442\u0435\u0440\u043d\u0435\u0442\u0430 (\u043e\u043d\u0438 \u043d\u0435 \u044f\u0432\u043b\u044f\u044e\u0442\u0441\u044f \u0447\u0430\u0441\u0442\u044c\u044e \u043f\u0440\u043e\u0435\u043a\u0442\u0430). \u0421\u043f\u0430\u0440\u0441\u0435\u043d\u043d\u044b\u0435 \u0442\u044b\u0441\u044f\u0447\u0438 \u0441 nonograms.ru \u043d\u0438\u043a\u0443\u0434\u0430 \u043d\u0435 \u0432\u044b\u043a\u043b\u0430\u0434\u044b\u0432\u0430\u043b \u0438 \u043d\u0435 \u0431\u0443\u0434\u0443, \u0447\u0442\u043e\u0431\u044b \u0438\u0445 \u043d\u0435 \u043f\u043e\u0442\u044b\u0440\u0438\u043b\u0438, \u043f\u043e\u0442\u043e\u043c\u0443 \u0447\u0442\u043e \u043e\u043d\u0438 \u043c\u043e\u0433\u0443\u0442 \u0431\u044b\u0442\u044c \u0437\u0430\u0449\u0438\u0449\u0435\u043d\u044b \u043f\u0440\u0430\u0432\u0430\u043c\u0438 \u0438 \u0442\u044b\u0440\u044f\u0442\u0435\u043b\u044f \u043c\u043e\u0433\u0443\u0442 \u043e\u0436\u0438\u0434\u0430\u0442\u044c \u0438\u043d\u0442\u0435\u0440\u0435\u0441\u043d\u044b\u0435 \u043f\u043e\u0441\u043b\u0435\u0434\u0441\u0442\u0432\u0438\u044f.<\/p>\n<p>  <\/p>\n<p>\u041e\u0441\u043e\u0431\u0443\u044e \u0431\u043b\u0430\u0433\u043e\u0434\u0430\u0440\u043d\u043e\u0441\u0442\u044c \u0445\u043e\u0447\u0443 \u0432\u044b\u0440\u0430\u0437\u0438\u0442\u044c \u0430\u0432\u0442\u043e\u0440\u0443 nonograms.ru \u0427\u0443\u0433\u0443\u043d\u043d\u043e\u043c\u0443 \u041a.\u0410. <a href=\"https:\/\/habr.com\/users\/kyberprizrak\/\" class=\"user_link\">KyberPrizrak<\/a>, \u0437\u0430 \u0441\u043e\u0437\u0434\u0430\u043d\u0438\u0435 \u043f\u0440\u0435\u043a\u0440\u0430\u0441\u043d\u043e\u0433\u043e, \u043b\u0443\u0447\u0448\u0435\u0433\u043e \u0438 \u043e\u0434\u043d\u043e\u0433\u043e \u0438\u0437 \u043a\u0440\u0443\u043f\u043d\u0435\u0439\u0448\u0438\u0445 \u0432 \u0438\u043d\u0442\u0435\u0440\u043d\u0435\u0442\u0435 \u0441\u0430\u0439\u0442\u0430 \u043f\u043e \u043d\u043e\u043d\u043e\u0433\u0440\u0430\u043c\u043c\u0430\u043c, \u0438 \u0437\u0430 \u0440\u0430\u0437\u0440\u0435\u0448\u0435\u043d\u0438\u0435 \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u0442\u044c \u043c\u0430\u0442\u0435\u0440\u0438\u0430\u043b\u044b \u0434\u043b\u044f \u0441\u0442\u0430\u0442\u044c\u0438! \u0412\u0441\u0435 \u043f\u0440\u0438\u043c\u0435\u0440\u044b \u0432 \u044d\u0442\u043e\u0439 \u0441\u0442\u0430\u0442\u044c\u0435 \u044f \u0432\u0437\u044f\u043b \u0441 nonograms.ru, \u0432\u043e\u0442 <a href=\"https:\/\/gist.github.com\/Izaron\/518f6b8659d1385ce7047ae477881e8e\">\u0441\u043f\u0438\u0441\u043e\u043a<\/a> \u0438\u0441\u0442\u043e\u0447\u043d\u0438\u043a\u043e\u0432.<\/p>\n<p>  <\/p>\n<p><a href=\"https:\/\/github.com\/Izaron\/Nonograms\">\u0418\u0441\u0445\u043e\u0434\u043d\u0438\u043a\u0438<\/a>.<\/p>\n<p>  <\/p>\n<div style=\"text-align:center;\"><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/webt\/es\/zg\/il\/eszgil8btd-jjgaszlinfz2oodm.png\"><\/div>\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\/418069\/\"> https:\/\/habr.com\/post\/418069\/<\/a><\/p>\n","protected":false},"excerpt":{"rendered":"\n<div data-io-article-url=\"https:\/\/habr.com\/post\/418069\/\" class=\"post__text post__text-html js-mediator-article\">\n<p>\u042f\u043f\u043e\u043d\u0441\u043a\u0438\u0435 \u043a\u0440\u043e\u0441\u0441\u0432\u043e\u0440\u0434\u044b (\u0442\u0430\u043a\u0436\u0435 \u043d\u043e\u043d\u043e\u0433\u0440\u0430\u043c\u043c\u044b) \u2014 \u043b\u043e\u0433\u0438\u0447\u0435\u0441\u043a\u0438\u0435 \u0433\u043e\u043b\u043e\u0432\u043e\u043b\u043e\u043c\u043a\u0438, \u0432 \u043a\u043e\u0442\u043e\u0440\u044b\u0445 \u0437\u0430\u0448\u0438\u0444\u0440\u043e\u0432\u0430\u043d\u043e \u043f\u0438\u043a\u0441\u0435\u043b\u044c\u043d\u043e\u0435 \u0438\u0437\u043e\u0431\u0440\u0430\u0436\u0435\u043d\u0438\u0435. \u0420\u0430\u0437\u0433\u0430\u0434\u044b\u0432\u0430\u0442\u044c \u043a\u0440\u043e\u0441\u0441\u0432\u043e\u0440\u0434 \u043d\u0443\u0436\u043d\u043e \u0441 \u043f\u043e\u043c\u043e\u0449\u044c\u044e \u0447\u0438\u0441\u0435\u043b, \u0440\u0430\u0441\u043f\u043e\u043b\u043e\u0436\u0435\u043d\u043d\u044b\u0445 \u0441\u043b\u0435\u0432\u0430 \u043e\u0442 \u0441\u0442\u0440\u043e\u043a \u0438 \u0441\u0432\u0435\u0440\u0445\u0443 \u043e\u0442 \u0441\u0442\u043e\u043b\u0431\u0446\u043e\u0432.<\/p>\n<p>  <\/p>\n<p>\u0420\u0430\u0437\u043c\u0435\u0440 \u043a\u0440\u043e\u0441\u0441\u0432\u043e\u0440\u0434\u043e\u0432 \u043c\u043e\u0436\u0435\u0442 \u0434\u043e\u0445\u043e\u0434\u0438\u0442\u044c \u0434\u043e 150&#215;150. \u0418\u0433\u0440\u043e\u043a \u0441 \u043f\u043e\u043c\u043e\u0449\u044c\u044e \u0441\u043f\u0435\u0446\u0438\u0430\u043b\u044c\u043d\u044b\u0445 \u043b\u043e\u0433\u0438\u0447\u0435\u0441\u043a\u0438\u0445 \u043f\u0440\u0438\u0435\u043c\u043e\u0432 \u0432\u044b\u0447\u0438\u0441\u043b\u044f\u0435\u0442 \u0446\u0432\u0435\u0442 \u043a\u0430\u0436\u0434\u043e\u0439 \u043a\u043b\u0435\u0442\u043a\u0438. \u0420\u0435\u0448\u0435\u043d\u0438\u0435 \u043c\u043e\u0436\u0435\u0442 \u0437\u0430\u043d\u044f\u0442\u044c \u043a\u0430\u043a \u043f\u0430\u0440\u0443 \u043c\u0438\u043d\u0443\u0442 \u043d\u0430 \u043a\u0440\u043e\u0441\u0441\u0432\u043e\u0440\u0434\u0430\u0445 \u0434\u043b\u044f \u043d\u0430\u0447\u0438\u043d\u0430\u044e\u0449\u0438\u0445, \u0442\u0430\u043a \u0438 \u0434\u0435\u0441\u044f\u0442\u043a\u0438 \u0447\u0430\u0441\u043e\u0432 \u043d\u0430 \u0441\u043b\u043e\u0436\u043d\u044b\u0445 \u0433\u043e\u043b\u043e\u0432\u043e\u043b\u043e\u043c\u043a\u0430\u0445.<\/p>\n<p>  <\/p>\n<p>\u0425\u043e\u0440\u043e\u0448\u0438\u0439 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u043c\u043e\u0436\u0435\u0442 \u0440\u0435\u0448\u0438\u0442\u044c \u0437\u0430\u0434\u0430\u0447\u0443 \u043d\u0430\u043c\u043d\u043e\u0433\u043e \u0431\u044b\u0441\u0442\u0440\u0435\u0435. \u0412 \u0442\u0435\u043a\u0441\u0442\u0435 \u043e\u043f\u0438\u0441\u0430\u043d\u043e, \u043a\u0430\u043a \u0441 \u043f\u043e\u043c\u043e\u0449\u044c\u044e \u043d\u0430\u0438\u0431\u043e\u043b\u0435\u0435 \u043f\u043e\u0434\u0445\u043e\u0434\u044f\u0449\u0438\u0445 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u043e\u0432 (\u043a\u043e\u0442\u043e\u0440\u044b\u0435 \u0432\u043e\u043e\u0431\u0449\u0435 \u043f\u0440\u0438\u0432\u043e\u0434\u044f\u0442 \u043a \u0440\u0435\u0448\u0435\u043d\u0438\u044e), \u0430 \u0442\u0430\u043a\u0436\u0435 \u0438\u0445 \u043e\u043f\u0442\u0438\u043c\u0438\u0437\u0430\u0446\u0438\u0439 \u0438 \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u043d\u0438\u044f \u043e\u0441\u043e\u0431\u0435\u043d\u043d\u043e\u0441\u0442\u0435\u0439 C++ (\u043a\u043e\u0442\u043e\u0440\u044b\u0435 \u0443\u043c\u0435\u043d\u044c\u0448\u0430\u044e\u0442 \u0432\u0440\u0435\u043c\u044f \u0440\u0430\u0431\u043e\u0442\u044b \u0432 \u043d\u0435\u0441\u043a\u043e\u043b\u044c\u043a\u043e \u0434\u0435\u0441\u044f\u0442\u043a\u043e\u0432 \u0440\u0430\u0437) \u043d\u0430\u043f\u0438\u0441\u0430\u0442\u044c \u0440\u0435\u0448\u0435\u043d\u0438\u0435, \u0440\u0430\u0431\u043e\u0442\u0430\u044e\u0449\u0435\u0435 \u043f\u043e\u0447\u0442\u0438 \u043c\u0433\u043d\u043e\u0432\u0435\u043d\u043d\u043e.<\/p>\n<p>  <\/p>\n<div style=\"text-align:center;\"><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/webt\/w1\/tw\/-c\/w1tw-caq1d9vswcrqfapdufcbfk.gif\"><\/div>\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-287598","post","type-post","status-publish","format-standard","hentry"],"_links":{"self":[{"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=\/wp\/v2\/posts\/287598","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=287598"}],"version-history":[{"count":0,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=\/wp\/v2\/posts\/287598\/revisions"}],"wp:attachment":[{"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=287598"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=287598"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=287598"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}