{"id":295204,"date":"2019-11-26T09:00:29","date_gmt":"2019-11-26T09:00:29","guid":{"rendered":"http:\/\/savepearlharbor.com\/?p=295204"},"modified":"-0001-11-30T00:00:00","modified_gmt":"-0001-11-29T21:00:00","slug":"","status":"publish","type":"post","link":"https:\/\/savepearlharbor.com\/?p=295204","title":{"rendered":"\u0412\u0442\u043e\u0440\u043e\u0439 \u0447\u0435\u043c\u043f\u0438\u043e\u043d\u0430\u0442 \u043f\u043e\u00a0\u043f\u0440\u043e\u0433\u0440\u0430\u043c\u043c\u0438\u0440\u043e\u0432\u0430\u043d\u0438\u044e: \u0440\u0430\u0437\u0431\u0438\u0440\u0430\u0435\u043c \u0437\u0430\u0434\u0430\u0447\u0438 ML-\u0442\u0440\u0435\u043a\u0430"},"content":{"rendered":"\n<div class=\"post__text post__text-html js-mediator-article\" id=\"post-content-body\" data-io-article-url=\"https:\/\/habr.com\/ru\/company\/yandex\/blog\/477452\/\"><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/webt\/ri\/tp\/iv\/ritpivveq5sfetymakd2icpummo.jpeg\" width=\"340\" align=\"right\">\u0412 \u043e\u043a\u0442\u044f\u0431\u0440\u0435 \u0441\u043e\u0441\u0442\u043e\u044f\u043b\u0441\u044f \u0432\u0442\u043e\u0440\u043e\u0439 \u0447\u0435\u043c\u043f\u0438\u043e\u043d\u0430\u0442 \u043f\u043e \u043f\u0440\u043e\u0433\u0440\u0430\u043c\u043c\u0438\u0440\u043e\u0432\u0430\u043d\u0438\u044e. \u041c\u044b \u043f\u043e\u043b\u0443\u0447\u0438\u043b\u0438 12 500 \u0437\u0430\u044f\u0432\u043e\u043a, \u0431\u043e\u043b\u0435\u0435 6000 \u0447\u0435\u043b\u043e\u0432\u0435\u043a \u043f\u043e\u043f\u0440\u043e\u0431\u043e\u0432\u0430\u043b\u0438 \u0441\u0432\u043e\u0438 \u0441\u0438\u043b\u044b \u0432 \u0441\u043e\u0440\u0435\u0432\u043d\u043e\u0432\u0430\u043d\u0438\u044f\u0445. \u0412 \u044d\u0442\u043e\u0442 \u0440\u0430\u0437 \u0443\u0447\u0430\u0441\u0442\u043d\u0438\u043a\u0438 \u043c\u043e\u0433\u043b\u0438 \u0432\u044b\u0431\u0440\u0430\u0442\u044c \u043e\u0434\u0438\u043d \u0438\u0437 \u0441\u043b\u0435\u0434\u0443\u044e\u0449\u0438\u0445 \u0442\u0440\u0435\u043a\u043e\u0432: \u0431\u044d\u043a\u0435\u043d\u0434, \u0444\u0440\u043e\u043d\u0442\u0435\u043d\u0434, \u043c\u043e\u0431\u0438\u043b\u044c\u043d\u0443\u044e \u0440\u0430\u0437\u0440\u0430\u0431\u043e\u0442\u043a\u0443 \u0438 \u043c\u0430\u0448\u0438\u043d\u043d\u043e\u0435 \u043e\u0431\u0443\u0447\u0435\u043d\u0438\u0435. \u0412 \u043a\u0430\u0436\u0434\u043e\u043c \u0442\u0440\u0435\u043a\u0435 \u0442\u0440\u0435\u0431\u043e\u0432\u0430\u043b\u043e\u0441\u044c \u043f\u0440\u043e\u0439\u0442\u0438 \u043a\u0432\u0430\u043b\u0438\u0444\u0438\u043a\u0430\u0446\u0438\u043e\u043d\u043d\u044b\u0439 \u044d\u0442\u0430\u043f \u0438 \u0444\u0438\u043d\u0430\u043b.<\/p>\n<p>  \u041f\u043e \u0442\u0440\u0430\u0434\u0438\u0446\u0438\u0438 \u043c\u044b \u043e\u043f\u0443\u0431\u043b\u0438\u043a\u0443\u0435\u043c \u0440\u0430\u0437\u0431\u043e\u0440\u044b \u0442\u0440\u0435\u043a\u043e\u0432 \u043d\u0430 \u0425\u0430\u0431\u0440\u0435. \u041d\u0430\u0447\u043d\u0451\u043c \u0441 \u0437\u0430\u0434\u0430\u0447 \u043a\u0432\u0430\u043b\u0438\u0444\u0438\u043a\u0430\u0446\u0438\u043e\u043d\u043d\u043e\u0433\u043e \u044d\u0442\u0430\u043f\u0430 \u043f\u043e \u043c\u0430\u0448\u0438\u043d\u043d\u043e\u043c\u0443 \u043e\u0431\u0443\u0447\u0435\u043d\u0438\u044e. \u041a\u043e\u043c\u0430\u043d\u0434\u0430 \u043f\u043e\u0434\u0433\u043e\u0442\u043e\u0432\u0438\u043b\u0430 \u043f\u044f\u0442\u044c \u0442\u0430\u043a\u0438\u0445 \u0437\u0430\u0434\u0430\u0447, \u0438\u0437 \u043a\u043e\u0442\u043e\u0440\u044b\u0445 \u0441\u043e\u0441\u0442\u0430\u0432\u0438\u043b\u0430 \u0434\u0432\u0430 \u0432\u0430\u0440\u0438\u0430\u043d\u0442\u0430 \u043f\u043e \u0442\u0440\u0438 \u0437\u0430\u0434\u0430\u0447\u0438: \u0432 \u043f\u0435\u0440\u0432\u043e\u043c \u0432\u0430\u0440\u0438\u0430\u043d\u0442\u0435 \u0431\u044b\u043b\u0438 \u0437\u0430\u0434\u0430\u0447\u0438 A1, B1 \u0438 C, \u0432\u043e \u0432\u0442\u043e\u0440\u043e\u043c \u2014 A2, B2 \u0438 C. \u0412\u0430\u0440\u0438\u0430\u043d\u0442\u044b \u0441\u043b\u0443\u0447\u0430\u0439\u043d\u043e \u0440\u0430\u0441\u043f\u0440\u0435\u0434\u0435\u043b\u044f\u043b\u0438\u0441\u044c \u043c\u0435\u0436\u0434\u0443 \u0443\u0447\u0430\u0441\u0442\u043d\u0438\u043a\u0430\u043c\u0438. \u0410\u0432\u0442\u043e\u0440 \u0437\u0430\u0434\u0430\u0447\u0438 C \u2014 \u043d\u0430\u0448 \u0440\u0430\u0437\u0440\u0430\u0431\u043e\u0442\u0447\u0438\u043a \u041f\u0430\u0432\u0435\u043b \u041f\u0430\u0440\u0445\u043e\u043c\u0435\u043d\u043a\u043e, \u043e\u0441\u0442\u0430\u043b\u044c\u043d\u044b\u0435 \u0437\u0430\u0434\u0430\u0447\u0438 \u0441\u043e\u0441\u0442\u0430\u0432\u0438\u043b \u0435\u0433\u043e \u043a\u043e\u043b\u043b\u0435\u0433\u0430 \u041d\u0438\u043a\u0438\u0442\u0430 \u0421\u0435\u043d\u0434\u0435\u0440\u043e\u0432\u0438\u0447. <\/p>\n<p>  \u0417\u0430 \u043f\u0435\u0440\u0432\u0443\u044e \u043f\u0440\u043e\u0441\u0442\u0443\u044e \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0438\u0447\u0435\u0441\u043a\u0443\u044e \u0437\u0430\u0434\u0430\u0447\u0443 (A1\/A2) \u0443\u0447\u0430\u0441\u0442\u043d\u0438\u043a\u0438 \u043c\u043e\u0433\u043b\u0438 \u043f\u043e\u043b\u0443\u0447\u0438\u0442\u044c 50 \u0431\u0430\u043b\u043b\u043e\u0432, \u043f\u0440\u0430\u0432\u0438\u043b\u044c\u043d\u043e \u0440\u0435\u0430\u043b\u0438\u0437\u043e\u0432\u0430\u0432 \u043f\u0435\u0440\u0435\u0431\u043e\u0440 \u043f\u043e \u043e\u0442\u0432\u0435\u0442\u0443. \u0417\u0430 \u0432\u0442\u043e\u0440\u0443\u044e \u0437\u0430\u0434\u0430\u0447\u0443 (B1\/B2) \u043c\u044b \u0434\u0430\u0432\u0430\u043b\u0438 \u043e\u0442 10 \u0434\u043e 100 \u0431\u0430\u043b\u043b\u043e\u0432 \u2014 \u0432 \u0437\u0430\u0432\u0438\u0441\u0438\u043c\u043e\u0441\u0442\u0438 \u043e\u0442 \u044d\u0444\u0444\u0435\u043a\u0442\u0438\u0432\u043d\u043e\u0441\u0442\u0438 \u0440\u0435\u0448\u0435\u043d\u0438\u044f. \u0427\u0442\u043e\u0431\u044b \u043f\u043e\u043b\u0443\u0447\u0438\u0442\u044c 100 \u0431\u0430\u043b\u043b\u043e\u0432, \u0442\u0440\u0435\u0431\u043e\u0432\u0430\u043b\u043e\u0441\u044c \u0440\u0435\u0430\u043b\u0438\u0437\u043e\u0432\u0430\u0442\u044c \u043c\u0435\u0442\u043e\u0434 \u0434\u0438\u043d\u0430\u043c\u0438\u0447\u0435\u0441\u043a\u043e\u0433\u043e \u043f\u0440\u043e\u0433\u0440\u0430\u043c\u043c\u0438\u0440\u043e\u0432\u0430\u043d\u0438\u044f. \u0422\u0440\u0435\u0442\u044c\u044f \u0437\u0430\u0434\u0430\u0447\u0430 \u0431\u044b\u043b\u0430 \u043f\u043e\u0441\u0432\u044f\u0449\u0435\u043d\u0430 \u043f\u043e\u0441\u0442\u0440\u043e\u0435\u043d\u0438\u044e \u043a\u043b\u0438\u043a\u043e\u0432\u043e\u0439 \u043c\u043e\u0434\u0435\u043b\u0438 \u043f\u043e \u043f\u0440\u0435\u0434\u043e\u0441\u0442\u0430\u0432\u043b\u0435\u043d\u043d\u044b\u043c \u043e\u0431\u0443\u0447\u0430\u044e\u0449\u0438\u043c \u0434\u0430\u043d\u043d\u044b\u043c. \u0412 \u043d\u0435\u0439 \u0442\u0440\u0435\u0431\u043e\u0432\u0430\u043b\u043e\u0441\u044c \u043f\u0440\u0438\u043c\u0435\u043d\u0438\u0442\u044c \u043c\u0435\u0442\u043e\u0434\u044b \u0440\u0430\u0431\u043e\u0442\u044b \u0441 \u043a\u0430\u0442\u0435\u0433\u043e\u0440\u0438\u0430\u043b\u044c\u043d\u044b\u043c\u0438 \u043f\u0440\u0438\u0437\u043d\u0430\u043a\u0430\u043c\u0438 \u0438 \u0432\u043e\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u0442\u044c\u0441\u044f \u043d\u0435\u043b\u0438\u043d\u0435\u0439\u043d\u043e\u0439 \u043c\u043e\u0434\u0435\u043b\u044c\u044e \u043e\u0431\u0443\u0447\u0435\u043d\u0438\u044f (\u043d\u0430\u043f\u0440\u0438\u043c\u0435\u0440, \u0433\u0440\u0430\u0434\u0438\u0435\u043d\u0442\u043d\u044b\u043c \u0431\u0443\u0441\u0442\u0438\u043d\u0433\u043e\u043c). \u0417\u0430 \u0437\u0430\u0434\u0430\u0447\u0443 \u043c\u043e\u0436\u043d\u043e \u0431\u044b\u043b\u043e \u043f\u043e\u043b\u0443\u0447\u0438\u0442\u044c \u0434\u043e 150 \u0431\u0430\u043b\u043b\u043e\u0432 \u2014 \u0432 \u0437\u0430\u0432\u0438\u0441\u0438\u043c\u043e\u0441\u0442\u0438 \u043e\u0442 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u044f \u0444\u0443\u043d\u043a\u0446\u0438\u0438 \u043f\u043e\u0442\u0435\u0440\u044c \u043d\u0430 \u0442\u0435\u0441\u0442\u043e\u0432\u043e\u0439 \u0432\u044b\u0431\u043e\u0440\u043a\u0435.<br \/>  <a name=\"habracut\"><\/a>  <\/p>\n<h2>\u04101. \u0412\u043e\u0441\u0441\u0442\u0430\u043d\u043e\u0432\u0438 \u0434\u043b\u0438\u043d\u0443 \u043a\u0430\u0440\u0443\u0441\u0435\u043b\u0438<\/h2>\n<p>  <\/p>\n<h4>\u0423\u0441\u043b\u043e\u0432\u0438\u0435<\/h4>\n<div class=\"scrollable-table\">\n<table>\n<tr>\n<td>\u041e\u0433\u0440\u0430\u043d\u0438\u0447\u0435\u043d\u0438\u0435 \u0432\u0440\u0435\u043c\u0435\u043d\u0438<\/td>\n<td>1 \u0441<\/td>\n<\/tr>\n<tr>\n<td>\u041e\u0433\u0440\u0430\u043d\u0438\u0447\u0435\u043d\u0438\u0435 \u043f\u0430\u043c\u044f\u0442\u0438<\/td>\n<td>256 \u041c\u0411<\/td>\n<\/tr>\n<tr>\n<td>\u0412\u0432\u043e\u0434<\/td>\n<td>\u0441\u0442\u0430\u043d\u0434\u0430\u0440\u0442\u043d\u044b\u0439 \u0432\u0432\u043e\u0434 \u0438\u043b\u0438 input.txt<\/td>\n<\/tr>\n<tr>\n<td>\u0412\u044b\u0432\u043e\u0434<\/td>\n<td>\u0441\u0442\u0430\u043d\u0434\u0430\u0440\u0442\u043d\u044b\u0439 \u0432\u044b\u0432\u043e\u0434 \u0438\u043b\u0438 output.txt<\/td>\n<\/tr>\n<\/table>\n<\/div>\n<p>\u0420\u0435\u043a\u043e\u043c\u0435\u043d\u0434\u0430\u0442\u0435\u043b\u044c\u043d\u0430\u044f \u0441\u0438\u0441\u0442\u0435\u043c\u0430 \u0434\u043e\u043b\u0436\u043d\u0430 \u044d\u0444\u0444\u0435\u043a\u0442\u0438\u0432\u043d\u043e \u043e\u043f\u0440\u0435\u0434\u0435\u043b\u044f\u0442\u044c \u0438\u043d\u0442\u0435\u0440\u0435\u0441\u044b \u043b\u044e\u0434\u0435\u0439. \u0418 \u043f\u043e\u043c\u0438\u043c\u043e \u043c\u0435\u0442\u043e\u0434\u043e\u0432 \u043c\u0430\u0448\u0438\u043d\u043d\u043e\u0433\u043e \u043e\u0431\u0443\u0447\u0435\u043d\u0438\u044f, \u0434\u043b\u044f \u0432\u044b\u043f\u043e\u043b\u043d\u0435\u043d\u0438\u044f \u044d\u0442\u043e\u0439 \u0437\u0430\u0434\u0430\u0447\u0438 \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u044e\u0442\u0441\u044f \u0441\u043f\u0435\u0446\u0438\u0430\u043b\u044c\u043d\u044b\u0435 \u0438\u043d\u0442\u0435\u0440\u0444\u0435\u0439\u0441\u043d\u044b\u0435 \u0440\u0435\u0448\u0435\u043d\u0438\u044f, \u043a\u043e\u0442\u043e\u0440\u044b\u0435 \u044f\u0432\u043d\u044b\u043c \u043e\u0431\u0440\u0430\u0437\u043e\u043c \u0441\u043f\u0440\u0430\u0448\u0438\u0432\u0430\u044e\u0442 \u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u0442\u0435\u043b\u044f, \u0447\u0442\u043e \u0435\u043c\u0443 \u0438\u043d\u0442\u0435\u0440\u0435\u0441\u043d\u043e. \u041e\u0434\u043d\u0438\u043c \u0438\u0437 \u0442\u0430\u043a\u0438\u0445 \u0440\u0435\u0448\u0435\u043d\u0438\u0439 \u044f\u0432\u043b\u044f\u0435\u0442\u0441\u044f \u043a\u0430\u0440\u0443\u0441\u0435\u043b\u044c.<\/p>\n<p>  \u041a\u0430\u0440\u0443\u0441\u0435\u043b\u044c\u00a0\u2014 \u044d\u0442\u043e \u0433\u043e\u0440\u0438\u0437\u043e\u043d\u0442\u0430\u043b\u044c\u043d\u0430\u044f \u043b\u0435\u043d\u0442\u0430 \u0438\u0437 \u043a\u0430\u0440\u0442\u043e\u0447\u0435\u043a, \u043a\u0430\u0436\u0434\u0430\u044f \u0438\u0437 \u043a\u043e\u0442\u043e\u0440\u044b\u0445 \u043f\u0440\u0435\u0434\u043b\u0430\u0433\u0430\u0435\u0442 \u043f\u043e\u0434\u043f\u0438\u0441\u0430\u0442\u044c\u0441\u044f \u043d\u0430 \u043a\u043e\u043d\u043a\u0440\u0435\u0442\u043d\u044b\u0439 \u0438\u0441\u0442\u043e\u0447\u043d\u0438\u043a \u0438\u043b\u0438 \u0442\u0435\u043c\u0443. \u041e\u0434\u043d\u0430 \u0438 \u0442\u0430 \u0436\u0435 \u043a\u0430\u0440\u0442\u043e\u0447\u043a\u0430 \u043c\u043e\u0436\u0435\u0442 \u0432\u0441\u0442\u0440\u0435\u0447\u0430\u0442\u044c\u0441\u044f \u0432 \u043a\u0430\u0440\u0443\u0441\u0435\u043b\u0438 \u043d\u0435\u0441\u043a\u043e\u043b\u044c\u043a\u043e \u0440\u0430\u0437. \u041a\u0430\u0440\u0443\u0441\u0435\u043b\u044c \u043c\u043e\u0436\u043d\u043e \u043f\u0440\u043e\u043a\u0440\u0443\u0447\u0438\u0432\u0430\u0442\u044c \u0441\u043b\u0435\u0432\u0430 \u043d\u0430\u043f\u0440\u0430\u0432\u043e, \u043f\u0440\u0438 \u044d\u0442\u043e\u043c \u043f\u043e\u0441\u043b\u0435 \u043f\u043e\u0441\u043b\u0435\u0434\u043d\u0435\u0439 \u043a\u0430\u0440\u0442\u043e\u0447\u043a\u0438 \u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u0442\u0435\u043b\u044c \u0441\u043d\u043e\u0432\u0430 \u0432\u0438\u0434\u0438\u0442 \u043f\u0435\u0440\u0432\u0443\u044e. \u0414\u043b\u044f \u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u0442\u0435\u043b\u044f \u043f\u0435\u0440\u0435\u0445\u043e\u0434 \u043e\u0442 \u043f\u043e\u0441\u043b\u0435\u0434\u043d\u0435\u0439 \u043a\u0430\u0440\u0442\u043e\u0447\u043a\u0438 \u043a \u043f\u0435\u0440\u0432\u043e\u0439 \u043d\u0435\u0437\u0430\u043c\u0435\u0442\u0435\u043d, \u0441 \u0435\u0433\u043e \u0442\u043e\u0447\u043a\u0438 \u0437\u0440\u0435\u043d\u0438\u044f \u043b\u0435\u043d\u0442\u0430 \u0431\u0435\u0441\u043a\u043e\u043d\u0435\u0447\u043d\u0430.<\/p>\n<p>  \u0412 \u043a\u0430\u043a\u043e\u0439-\u0442\u043e \u043c\u043e\u043c\u0435\u043d\u0442 \u043b\u044e\u0431\u043e\u043f\u044b\u0442\u043d\u044b\u0439 \u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u0442\u0435\u043b\u044c \u0412\u0430\u0441\u0438\u043b\u0438\u0439 \u0437\u0430\u043c\u0435\u0442\u0438\u043b, \u0447\u0442\u043e \u043b\u0435\u043d\u0442\u0430 \u043d\u0430 \u0441\u0430\u043c\u043e\u043c \u0434\u0435\u043b\u0435 \u0437\u0430\u0446\u0438\u043a\u043b\u0435\u043d\u0430, \u0438 \u0440\u0435\u0448\u0438\u043b \u0432\u044b\u044f\u0441\u043d\u0438\u0442\u044c \u0438\u0441\u0442\u0438\u043d\u043d\u0443\u044e \u0434\u043b\u0438\u043d\u0443 \u043a\u0430\u0440\u0443\u0441\u0435\u043b\u0438. \u0414\u043b\u044f \u044d\u0442\u043e\u0433\u043e \u043e\u043d \u0441\u0442\u0430\u043b \u043f\u0440\u043e\u043a\u0440\u0443\u0447\u0438\u0432\u0430\u0442\u044c \u043b\u0435\u043d\u0442\u0443 \u0438 \u043f\u043e\u0441\u043b\u0435\u0434\u043e\u0432\u0430\u0442\u0435\u043b\u044c\u043d\u043e \u0432\u044b\u043f\u0438\u0441\u044b\u0432\u0430\u0442\u044c \u0432\u0441\u0442\u0440\u0435\u0447\u0430\u044e\u0449\u0438\u0435\u0441\u044f \u043a\u0430\u0440\u0442\u043e\u0447\u043a\u0438, \u0434\u043b\u044f \u043f\u0440\u043e\u0441\u0442\u043e\u0442\u044b \u043e\u0431\u043e\u0437\u043d\u0430\u0447\u0430\u044f \u043a\u0430\u0436\u0434\u0443\u044e \u043a\u0430\u0440\u0442\u043e\u0447\u043a\u0443 \u0441\u0442\u0440\u043e\u0447\u043d\u043e\u0439 \u043b\u0430\u0442\u0438\u043d\u0441\u043a\u043e\u0439 \u0431\u0443\u043a\u0432\u043e\u0439. \u0422\u0430\u043a \u0412\u0430\u0441\u0438\u043b\u0438\u0439 \u0432\u044b\u043f\u0438\u0441\u0430\u043b \u043f\u0435\u0440\u0432\u044b\u0435 n \u043a\u0430\u0440\u0442\u043e\u0447\u0435\u043a \u043d\u0430 \u043b\u0438\u0441\u0442\u043e\u043a \u0431\u0443\u043c\u0430\u0433\u0438. \u0413\u0430\u0440\u0430\u043d\u0442\u0438\u0440\u0443\u0435\u0442\u0441\u044f, \u0447\u0442\u043e \u043e\u043d \u043f\u0440\u043e\u0441\u043c\u043e\u0442\u0440\u0435\u043b \u0432\u0441\u0435 \u043a\u0430\u0440\u0442\u043e\u0447\u043a\u0438 \u043a\u0430\u0440\u0443\u0441\u0435\u043b\u0438 \u0445\u043e\u0442\u044f \u0431\u044b \u043e\u0434\u0438\u043d \u0440\u0430\u0437. \u041f\u043e\u0442\u043e\u043c \u0412\u0430\u0441\u0438\u043b\u0438\u0439 \u043b\u0451\u0433 \u0441\u043f\u0430\u0442\u044c, \u0430 \u0443\u0442\u0440\u043e\u043c \u043e\u0431\u043d\u0430\u0440\u0443\u0436\u0438\u043b, \u0447\u0442\u043e \u043a\u0442\u043e-\u0442\u043e \u043f\u0440\u043e\u043b\u0438\u043b \u0441\u0442\u0430\u043a\u0430\u043d \u0441 \u0432\u043e\u0434\u043e\u0439 \u043d\u0430 \u0435\u0433\u043e \u0437\u0430\u043f\u0438\u0441\u0438 \u0438 \u043d\u0435\u043a\u043e\u0442\u043e\u0440\u044b\u0435 \u0431\u0443\u043a\u0432\u044b \u0442\u0435\u043f\u0435\u0440\u044c \u043d\u0435\u0432\u043e\u0437\u043c\u043e\u0436\u043d\u043e \u0440\u0430\u0441\u043f\u043e\u0437\u043d\u0430\u0442\u044c.<\/p>\n<p>  \u041f\u043e \u043e\u0441\u0442\u0430\u0432\u0448\u0435\u0439\u0441\u044f \u0438\u043d\u0444\u043e\u0440\u043c\u0430\u0446\u0438\u0438 \u043f\u043e\u043c\u043e\u0433\u0438\u0442\u0435 \u0412\u0430\u0441\u0438\u043b\u0438\u044e \u043e\u043f\u0440\u0435\u0434\u0435\u043b\u0438\u0442\u044c \u043d\u0430\u0438\u043c\u0435\u043d\u044c\u0448\u0435\u0435 \u0432\u043e\u0437\u043c\u043e\u0436\u043d\u043e\u0435 \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e \u043a\u0430\u0440\u0442\u043e\u0447\u0435\u043a \u0432 \u043a\u0430\u0440\u0443\u0441\u0435\u043b\u0438.<\/p>\n<div class=\"spoiler\"><b class=\"spoiler_title\">\u0424\u043e\u0440\u043c\u0430\u0442\u044b \u0432\u0432\u043e\u0434\u0430\/\u0432\u044b\u0432\u043e\u0434\u0430 \u0438 \u043f\u0440\u0438\u043c\u0435\u0440\u044b<\/b><\/p>\n<div class=\"spoiler_text\">\n<h4>\u0424\u043e\u0440\u043c\u0430\u0442 \u0432\u0432\u043e\u0434\u0430<\/h4>\n<p>  \u0412 \u043f\u0435\u0440\u0432\u043e\u0439 \u0441\u0442\u0440\u043e\u043a\u0435 \u0437\u0430\u0434\u0430\u043d\u043e \u043e\u0434\u043d\u043e \u0446\u0435\u043b\u043e\u0435 \u0447\u0438\u0441\u043b\u043e n (1 \u2264 n \u2264 1000) \u2014 \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e \u0441\u0438\u043c\u0432\u043e\u043b\u043e\u0432, \u0432\u044b\u043f\u0438\u0441\u0430\u043d\u043d\u044b\u0445 \u0412\u0430\u0441\u0438\u043b\u0438\u0435\u043c.<\/p>\n<p>  \u0412\u0442\u043e\u0440\u0430\u044f \u0441\u0442\u0440\u043e\u043a\u0430 \u0441\u043e\u0434\u0435\u0440\u0436\u0438\u0442 \u0432\u044b\u043f\u0438\u0441\u0430\u043d\u043d\u0443\u044e \u0412\u0430\u0441\u0438\u043b\u0438\u0435\u043c \u043f\u043e\u0441\u043b\u0435\u0434\u043e\u0432\u0430\u0442\u0435\u043b\u044c\u043d\u043e\u0441\u0442\u044c. \u041e\u043d\u0430 \u0441\u043e\u0441\u0442\u043e\u0438\u0442 \u0438\u0437 n \u0441\u0438\u043c\u0432\u043e\u043b\u043e\u0432 \u2014 \u0441\u0442\u0440\u043e\u0447\u043d\u044b\u0445 \u0431\u0443\u043a\u0432 \u043b\u0430\u0442\u0438\u043d\u0441\u043a\u043e\u0433\u043e \u0430\u043b\u0444\u0430\u0432\u0438\u0442\u0430 \u0438 \u0437\u043d\u0430\u043a\u0430 #, \u043a\u043e\u0442\u043e\u0440\u044b\u0439 \u043e\u0431\u043e\u0437\u043d\u0430\u0447\u0430\u0435\u0442, \u0447\u0442\u043e \u0431\u0443\u043a\u0432\u0443 \u043d\u0430 \u044d\u0442\u043e\u0439 \u043f\u043e\u0437\u0438\u0446\u0438\u0438 \u043d\u0435\u0432\u043e\u0437\u043c\u043e\u0436\u043d\u043e \u0440\u0430\u0441\u043f\u043e\u0437\u043d\u0430\u0442\u044c.<\/p>\n<h4>\u0424\u043e\u0440\u043c\u0430\u0442 \u0432\u044b\u0432\u043e\u0434\u0430<\/h4>\n<p>  \u0412\u044b\u0432\u0435\u0434\u0438\u0442\u0435 \u043e\u0434\u043d\u043e \u0446\u0435\u043b\u043e\u0435 \u043f\u043e\u043b\u043e\u0436\u0438\u0442\u0435\u043b\u044c\u043d\u043e\u0435 \u0447\u0438\u0441\u043b\u043e\u00a0\u2014 \u043d\u0430\u0438\u043c\u0435\u043d\u044c\u0448\u0435\u0435 \u0432\u043e\u0437\u043c\u043e\u0436\u043d\u043e\u0435 \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e \u043a\u0430\u0440\u0442\u043e\u0447\u0435\u043a \u0432 \u043a\u0430\u0440\u0443\u0441\u0435\u043b\u0438.<\/p>\n<h4>\u041f\u0440\u0438\u043c\u0435\u0440 1<\/h4>\n<div class=\"scrollable-table\">\n<table>\n<tr>\n<td><b>\u0412\u0432\u043e\u0434<\/b><\/td>\n<td><b>\u0412\u044b\u0432\u043e\u0434<\/b><\/td>\n<\/tr>\n<tr>\n<td><code>5<br \/>  abcab<\/code><\/td>\n<td><code>3<\/code><\/td>\n<\/tr>\n<\/table>\n<\/div>\n<h4>\u041f\u0440\u0438\u043c\u0435\u0440 2<\/h4>\n<div class=\"scrollable-table\">\n<table>\n<tr>\n<td><b>\u0412\u0432\u043e\u0434<\/b><\/td>\n<td><b>\u0412\u044b\u0432\u043e\u0434<\/b><\/td>\n<\/tr>\n<tr>\n<td><code>7<br \/>  abbabba<\/code><\/td>\n<td><code>3<\/code><\/td>\n<\/tr>\n<\/table>\n<\/div>\n<h4>\u041f\u0440\u0438\u043c\u0435\u0440 3<\/h4>\n<div class=\"scrollable-table\">\n<table>\n<tr>\n<td><b>\u0412\u0432\u043e\u0434<\/b><\/td>\n<td><b>\u0412\u044b\u0432\u043e\u0434<\/b><\/td>\n<\/tr>\n<tr>\n<td><code>5<br \/>  ab#ba<\/code><\/td>\n<td><code>2<\/code><\/td>\n<\/tr>\n<\/table>\n<\/div>\n<h4>\u041f\u0440\u0438\u043c\u0435\u0440 4<\/h4>\n<div class=\"scrollable-table\">\n<table>\n<tr>\n<td><b>\u0412\u0432\u043e\u0434<\/b><\/td>\n<td><b>\u0412\u044b\u0432\u043e\u0434<\/b><\/td>\n<\/tr>\n<tr>\n<td><code>6<br \/>  ######<\/code><\/td>\n<td><code>1<\/code><\/td>\n<\/tr>\n<\/table>\n<\/div>\n<h4>\u041f\u0440\u0438\u043c\u0435\u0447\u0430\u043d\u0438\u044f<\/h4>\n<p>  \u0412 \u043f\u0435\u0440\u0432\u043e\u043c \u043f\u0440\u0438\u043c\u0435\u0440\u0435 \u0432\u0441\u0435 \u0431\u0443\u043a\u0432\u044b \u0443\u0434\u0430\u043b\u043e\u0441\u044c \u0440\u0430\u0441\u043f\u043e\u0437\u043d\u0430\u0442\u044c, \u043c\u0438\u043d\u0438\u043c\u0430\u043b\u044c\u043d\u0430\u044f \u043a\u0430\u0440\u0443\u0441\u0435\u043b\u044c \u043c\u043e\u0433\u043b\u0430 \u0441\u043e\u0441\u0442\u043e\u044f\u0442\u044c \u0438\u0437 3 \u043a\u0430\u0440\u0442\u043e\u0447\u0435\u043a\u00a0\u2014 abc.<\/p>\n<p>  \u0412\u043e \u0432\u0442\u043e\u0440\u043e\u043c \u043f\u0440\u0438\u043c\u0435\u0440\u0435 \u0432\u0441\u0435 \u0431\u0443\u043a\u0432\u044b \u0443\u0434\u0430\u043b\u043e\u0441\u044c \u0440\u0430\u0441\u043f\u043e\u0437\u043d\u0430\u0442\u044c, \u043c\u0438\u043d\u0438\u043c\u0430\u043b\u044c\u043d\u0430\u044f \u043a\u0430\u0440\u0443\u0441\u0435\u043b\u044c \u043c\u043e\u0433\u043b\u0430 \u0441\u043e\u0441\u0442\u043e\u044f\u0442\u044c \u0438\u0437 3 \u043a\u0430\u0440\u0442\u043e\u0447\u0435\u043a\u00a0\u2014 abb. \u041e\u0431\u0440\u0430\u0442\u0438\u0442\u0435 \u0432\u043d\u0438\u043c\u0430\u043d\u0438\u0435, \u0447\u0442\u043e \u0432\u0442\u043e\u0440\u0430\u044f \u0438 \u0442\u0440\u0435\u0442\u044c\u044f \u043a\u0430\u0440\u0442\u043e\u0447\u043a\u0438 \u0432 \u044d\u0442\u043e\u0439 \u043a\u0430\u0440\u0443\u0441\u0435\u043b\u0438 \u043e\u0434\u0438\u043d\u0430\u043a\u043e\u0432\u044b\u0435.<\/p>\n<p>  \u0412 \u0442\u0440\u0435\u0442\u044c\u0435\u043c \u043f\u0440\u0438\u043c\u0435\u0440\u0435 \u043d\u0430\u0438\u043c\u0435\u043d\u044c\u0448\u0430\u044f \u0432\u043e\u0437\u043c\u043e\u0436\u043d\u0430\u044f \u0434\u043b\u0438\u043d\u0430 \u043a\u0430\u0440\u0443\u0441\u0435\u043b\u0438 \u043f\u043e\u043b\u0443\u0447\u0430\u0435\u0442\u0441\u044f, \u0435\u0441\u043b\u0438 \u043f\u0440\u0435\u0434\u043f\u043e\u043b\u043e\u0436\u0438\u0442\u044c, \u0447\u0442\u043e \u043d\u0430 \u0442\u0440\u0435\u0442\u044c\u0435\u0439 \u043f\u043e\u0437\u0438\u0446\u0438\u0438 \u043d\u0430\u0445\u043e\u0434\u0438\u043b\u0441\u044f \u0441\u0438\u043c\u0432\u043e\u043b a. \u0422\u043e\u0433\u0434\u0430 \u0438\u0441\u0445\u043e\u0434\u043d\u0430\u044f \u0441\u0442\u0440\u043e\u043a\u0430\u00a0\u2014 ababa, \u043c\u0438\u043d\u0438\u043c\u0430\u043b\u044c\u043d\u0430\u044f \u043a\u0430\u0440\u0443\u0441\u0435\u043b\u044c \u0441\u043e\u0441\u0442\u043e\u0438\u0442 \u0438\u0437 2 \u043a\u0430\u0440\u0442\u043e\u0447\u0435\u043a\u00a0\u2014 ab.<\/p>\n<p>  \u0412 \u0447\u0435\u0442\u0432\u0451\u0440\u0442\u043e\u043c \u043f\u0440\u0438\u043c\u0435\u0440\u0435 \u0438\u0441\u0445\u043e\u0434\u043d\u0430\u044f \u0441\u0442\u0440\u043e\u043a\u0430 \u043c\u043e\u0433\u043b\u0430 \u0431\u044b\u0442\u044c \u043b\u044e\u0431\u043e\u0439, \u043d\u0430\u043f\u0440\u0438\u043c\u0435\u0440 ffffff. \u0422\u043e\u0433\u0434\u0430 \u043a\u0430\u0440\u0443\u0441\u0435\u043b\u044c \u043c\u043e\u0433\u043b\u0430 \u0441\u043e\u0441\u0442\u043e\u044f\u0442\u044c \u0438\u0437 \u043e\u0434\u043d\u043e\u0439 \u043a\u0430\u0440\u0442\u043e\u0447\u043a\u0438\u00a0\u2014 f.<\/p><\/div>\n<\/div>\n<p>  <\/p>\n<h4>\u0421\u0438\u0441\u0442\u0435\u043c\u0430 \u043e\u0446\u0435\u043d\u043a\u0438<\/h4>\n<p>  \u0422\u043e\u043b\u044c\u043a\u043e \u043f\u0440\u0438 \u043f\u0440\u043e\u0445\u043e\u0436\u0434\u0435\u043d\u0438\u0438 \u0432\u0441\u0435\u0445 \u0442\u0435\u0441\u0442\u043e\u0432 \u0437\u0430 \u0437\u0430\u0434\u0430\u0447\u0443 \u043c\u043e\u0436\u043d\u043e \u043f\u043e\u043b\u0443\u0447\u0438\u0442\u044c <b>50 \u0431\u0430\u043b\u043b\u043e\u0432<\/b>.<\/p>\n<p>  \u0412 \u0442\u0435\u0441\u0442\u0438\u0440\u0443\u044e\u0449\u0435\u0439 \u0441\u0438\u0441\u0442\u0435\u043c\u0435 \u0442\u0435\u0441\u0442\u044b 1\u20134 \u2014 \u043f\u0440\u0438\u043c\u0435\u0440\u044b \u0438\u0437 \u0443\u0441\u043b\u043e\u0432\u0438\u044f.<\/p>\n<h4>\u0420\u0435\u0448\u0435\u043d\u0438\u0435<\/h4>\n<p>  \u0414\u043e\u0441\u0442\u0430\u0442\u043e\u0447\u043d\u043e \u0431\u044b\u043b\u043e \u043f\u0435\u0440\u0435\u0431\u0440\u0430\u0442\u044c \u0432\u043e\u0437\u043c\u043e\u0436\u043d\u0443\u044e \u0434\u043b\u0438\u043d\u0443 \u043a\u0430\u0440\u0443\u0441\u0435\u043b\u0438 \u043e\u0442 1 \u0434\u043e n \u0438 \u0434\u043b\u044f \u043a\u0430\u0436\u0434\u043e\u0439 \u0444\u0438\u043a\u0441\u0438\u0440\u043e\u0432\u0430\u043d\u043d\u043e\u0439 \u0434\u043b\u0438\u043d\u044b \u043f\u0440\u043e\u0432\u0435\u0440\u0438\u0442\u044c, \u043c\u043e\u0433\u043b\u0430 \u043b\u0438 \u043e\u043d\u0430 \u0431\u044b\u0442\u044c \u0442\u0430\u043a\u043e\u0432\u043e\u0439. \u041f\u0440\u0438 \u044d\u0442\u043e\u043c \u043f\u043e\u043d\u044f\u0442\u043d\u043e, \u0447\u0442\u043e \u043e\u0442\u0432\u0435\u0442 \u0432\u0441\u0435\u0433\u0434\u0430 \u0441\u0443\u0449\u0435\u0441\u0442\u0432\u0443\u0435\u0442, \u043f\u043e\u0441\u043a\u043e\u043b\u044c\u043a\u0443 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0435 n \u0433\u0430\u0440\u0430\u043d\u0442\u0438\u0440\u043e\u0432\u0430\u043d\u043d\u043e \u044f\u0432\u043b\u044f\u0435\u0442\u0441\u044f \u0432\u043e\u0437\u043c\u043e\u0436\u043d\u044b\u043c \u043e\u0442\u0432\u0435\u0442\u043e\u043c. \u0414\u043b\u044f \u0444\u0438\u043a\u0441\u0438\u0440\u043e\u0432\u0430\u043d\u043d\u043e\u0439 \u0434\u043b\u0438\u043d\u044b \u043a\u0430\u0440\u0443\u0441\u0435\u043b\u0438 p \u0434\u043e\u0441\u0442\u0430\u0442\u043e\u0447\u043d\u043e \u043f\u0440\u043e\u0432\u0435\u0440\u0438\u0442\u044c, \u0447\u0442\u043e \u0432 \u043f\u0435\u0440\u0435\u0434\u0430\u043d\u043d\u043e\u0439 \u0441\u0442\u0440\u043e\u043a\u0435 \u0434\u043b\u044f \u0432\u0441\u0435\u0445 i \u043e\u0442 0 \u0434\u043e (p \u2013 1) \u043d\u0430 \u0432\u0441\u0435\u0445 \u043f\u043e\u0437\u0438\u0446\u0438\u044f\u0445 i, i + p, i + 2p \u0438 \u0442. \u0434. \u043d\u0430\u0445\u043e\u0434\u044f\u0442\u0441\u044f \u043e\u0434\u0438\u043d\u0430\u043a\u043e\u0432\u044b\u0435 \u0441\u0438\u043c\u0432\u043e\u043b\u044b \u0438\u043b\u0438 #. \u0415\u0441\u043b\u0438 \u0445\u043e\u0442\u044f \u0431\u044b \u0434\u043b\u044f \u043a\u0430\u043a\u043e\u0433\u043e-\u0442\u043e i \u0432\u0441\u0442\u0440\u0435\u0447\u0430\u0435\u0442\u0441\u044f 2 \u0440\u0430\u0437\u043b\u0438\u0447\u043d\u044b\u0445 \u0441\u0438\u043c\u0432\u043e\u043b\u0430 \u0438\u0437 \u0434\u0438\u0430\u043f\u0430\u0437\u043e\u043d\u0430 \u043e\u0442 a \u0434\u043e z, \u0442\u043e \u043a\u0430\u0440\u0443\u0441\u0435\u043b\u044c \u043d\u0435 \u043c\u043e\u0436\u0435\u0442 \u0431\u044b\u0442\u044c \u0434\u043b\u0438\u043d\u044b p. \u041f\u043e\u0441\u043a\u043e\u043b\u044c\u043a\u0443 \u0432 \u0445\u0443\u0434\u0448\u0435\u043c \u0441\u043b\u0443\u0447\u0430\u0435 \u0434\u043b\u044f \u043a\u0430\u0436\u0434\u043e\u0433\u043e p \u043d\u0443\u0436\u043d\u043e \u043f\u0440\u043e\u0431\u0435\u0436\u0430\u0442\u044c\u0441\u044f \u043f\u043e \u0432\u0441\u0435\u043c \u0441\u0438\u043c\u0432\u043e\u043b\u0430\u043c \u0441\u0442\u0440\u043e\u043a\u0438 \u043e\u0434\u0438\u043d \u0440\u0430\u0437, \u0441\u043b\u043e\u0436\u043d\u043e\u0441\u0442\u044c \u0442\u0430\u043a\u043e\u0433\u043e \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0430 \u2014 O(n<sup>2<\/sup>).<\/p>\n<pre><code class=\"python\">def check_character(char, curchar):     return curchar is None or char == \"#\" or curchar == char  def need_to_assign_curchar(char, curchar):     return curchar is None and char != \"#\"   n = int(input()) s = input().strip() for p in range(1, n + 1):     is_ok = True     for i in range(0, p):         curchar = None         for j in range(i, n, p):             if not check_character(s[j], curchar):                 is_ok = False                 break             if need_to_assign_curchar(s[j], curchar):                 curchar = s[j]         if not is_ok:             break     if is_ok:         print(p)         break<\/code><\/pre>\n<p>  <\/p>\n<h2>\u04102. \u0412\u043e\u0441\u0441\u0442\u0430\u043d\u043e\u0432\u0438 \u0434\u043b\u0438\u043d\u0443 \u043a\u0430\u0440\u0443\u0441\u0435\u043b\u0438<\/h2>\n<p>  <\/p>\n<h4>\u0423\u0441\u043b\u043e\u0432\u0438\u0435<\/h4>\n<div class=\"scrollable-table\">\n<table>\n<tr>\n<td>\u041e\u0433\u0440\u0430\u043d\u0438\u0447\u0435\u043d\u0438\u0435 \u0432\u0440\u0435\u043c\u0435\u043d\u0438<\/td>\n<td>1 \u0441<\/td>\n<\/tr>\n<tr>\n<td>\u041e\u0433\u0440\u0430\u043d\u0438\u0447\u0435\u043d\u0438\u0435 \u043f\u0430\u043c\u044f\u0442\u0438<\/td>\n<td>256 \u041c\u0411<\/td>\n<\/tr>\n<tr>\n<td>\u0412\u0432\u043e\u0434<\/td>\n<td>\u0441\u0442\u0430\u043d\u0434\u0430\u0440\u0442\u043d\u044b\u0439 \u0432\u0432\u043e\u0434 \u0438\u043b\u0438 input.txt<\/td>\n<\/tr>\n<tr>\n<td>\u0412\u044b\u0432\u043e\u0434<\/td>\n<td>\u0441\u0442\u0430\u043d\u0434\u0430\u0440\u0442\u043d\u044b\u0439 \u0432\u044b\u0432\u043e\u0434 \u0438\u043b\u0438 output.txt<\/td>\n<\/tr>\n<\/table>\n<\/div>\n<p>\u0420\u0435\u043a\u043e\u043c\u0435\u043d\u0434\u0430\u0442\u0435\u043b\u044c\u043d\u0430\u044f \u0441\u0438\u0441\u0442\u0435\u043c\u0430 \u0434\u043e\u043b\u0436\u043d\u0430 \u044d\u0444\u0444\u0435\u043a\u0442\u0438\u0432\u043d\u043e \u043e\u043f\u0440\u0435\u0434\u0435\u043b\u044f\u0442\u044c \u0438\u043d\u0442\u0435\u0440\u0435\u0441\u044b \u043b\u044e\u0434\u0435\u0439. \u0418 \u043f\u043e\u043c\u0438\u043c\u043e \u043c\u0435\u0442\u043e\u0434\u043e\u0432 \u043c\u0430\u0448\u0438\u043d\u043d\u043e\u0433\u043e \u043e\u0431\u0443\u0447\u0435\u043d\u0438\u044f, \u0434\u043b\u044f \u0432\u044b\u043f\u043e\u043b\u043d\u0435\u043d\u0438\u044f \u044d\u0442\u043e\u0439 \u0437\u0430\u0434\u0430\u0447\u0438 \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u044e\u0442\u0441\u044f \u0441\u043f\u0435\u0446\u0438\u0430\u043b\u044c\u043d\u044b\u0435 \u0438\u043d\u0442\u0435\u0440\u0444\u0435\u0439\u0441\u043d\u044b\u0435 \u0440\u0435\u0448\u0435\u043d\u0438\u044f, \u043a\u043e\u0442\u043e\u0440\u044b\u0435 \u044f\u0432\u043d\u044b\u043c \u043e\u0431\u0440\u0430\u0437\u043e\u043c \u0441\u043f\u0440\u0430\u0448\u0438\u0432\u0430\u044e\u0442 \u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u0442\u0435\u043b\u044f, \u0447\u0442\u043e \u0435\u043c\u0443 \u0438\u043d\u0442\u0435\u0440\u0435\u0441\u043d\u043e. \u041e\u0434\u043d\u0438\u043c \u0438\u0437 \u0442\u0430\u043a\u0438\u0445 \u0440\u0435\u0448\u0435\u043d\u0438\u0439 \u044f\u0432\u043b\u044f\u0435\u0442\u0441\u044f \u043a\u0430\u0440\u0443\u0441\u0435\u043b\u044c.<\/p>\n<p>  \u041a\u0430\u0440\u0443\u0441\u0435\u043b\u044c \u2014 \u044d\u0442\u043e \u0433\u043e\u0440\u0438\u0437\u043e\u043d\u0442\u0430\u043b\u044c\u043d\u0430\u044f \u043b\u0435\u043d\u0442\u0430 \u0438\u0437 \u043a\u0430\u0440\u0442\u043e\u0447\u0435\u043a, \u043a\u0430\u0436\u0434\u0430\u044f \u0438\u0437 \u043a\u043e\u0442\u043e\u0440\u044b\u0445 \u043f\u0440\u0435\u0434\u043b\u0430\u0433\u0430\u0435\u0442 \u043f\u043e\u0434\u043f\u0438\u0441\u0430\u0442\u044c\u0441\u044f \u043d\u0430 \u043a\u043e\u043d\u043a\u0440\u0435\u0442\u043d\u044b\u0439 \u0438\u0441\u0442\u043e\u0447\u043d\u0438\u043a \u0438\u043b\u0438 \u0442\u0435\u043c\u0443. \u041e\u0434\u043d\u0430 \u0438 \u0442\u0430 \u0436\u0435 \u043a\u0430\u0440\u0442\u043e\u0447\u043a\u0430 \u043c\u043e\u0436\u0435\u0442 \u0432\u0441\u0442\u0440\u0435\u0447\u0430\u0442\u044c\u0441\u044f \u0432 \u043a\u0430\u0440\u0443\u0441\u0435\u043b\u0438 \u043d\u0435\u0441\u043a\u043e\u043b\u044c\u043a\u043e \u0440\u0430\u0437. \u041a\u0430\u0440\u0443\u0441\u0435\u043b\u044c \u043c\u043e\u0436\u043d\u043e \u043f\u0440\u043e\u043a\u0440\u0443\u0447\u0438\u0432\u0430\u0442\u044c \u0441\u043b\u0435\u0432\u0430 \u043d\u0430\u043f\u0440\u0430\u0432\u043e, \u043f\u0440\u0438 \u044d\u0442\u043e\u043c \u043f\u043e\u0441\u043b\u0435 \u043f\u043e\u0441\u043b\u0435\u0434\u043d\u0435\u0439 \u043a\u0430\u0440\u0442\u043e\u0447\u043a\u0438 \u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u0442\u0435\u043b\u044c \u0441\u043d\u043e\u0432\u0430 \u0432\u0438\u0434\u0438\u0442 \u043f\u0435\u0440\u0432\u0443\u044e. \u0414\u043b\u044f \u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u0442\u0435\u043b\u044f \u043f\u0435\u0440\u0435\u0445\u043e\u0434 \u043e\u0442 \u043f\u043e\u0441\u043b\u0435\u0434\u043d\u0435\u0439 \u043a\u0430\u0440\u0442\u043e\u0447\u043a\u0438 \u043a \u043f\u0435\u0440\u0432\u043e\u0439 \u043d\u0435\u0437\u0430\u043c\u0435\u0442\u0435\u043d, \u0441 \u0435\u0433\u043e \u0442\u043e\u0447\u043a\u0438 \u0437\u0440\u0435\u043d\u0438\u044f \u043b\u0435\u043d\u0442\u0430 \u0431\u0435\u0441\u043a\u043e\u043d\u0435\u0447\u043d\u0430.<\/p>\n<p>  \u0412 \u043a\u0430\u043a\u043e\u0439-\u0442\u043e \u043c\u043e\u043c\u0435\u043d\u0442 \u043b\u044e\u0431\u043e\u043f\u044b\u0442\u043d\u044b\u0439 \u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u0442\u0435\u043b\u044c \u0412\u0430\u0441\u0438\u043b\u0438\u0439 \u0437\u0430\u043c\u0435\u0442\u0438\u043b, \u0447\u0442\u043e \u043b\u0435\u043d\u0442\u0430 \u043d\u0430 \u0441\u0430\u043c\u043e\u043c \u0434\u0435\u043b\u0435 \u0437\u0430\u0446\u0438\u043a\u043b\u0435\u043d\u0430, \u0438 \u0440\u0435\u0448\u0438\u043b \u0432\u044b\u044f\u0441\u043d\u0438\u0442\u044c \u0438\u0441\u0442\u0438\u043d\u043d\u0443\u044e \u0434\u043b\u0438\u043d\u0443 \u043a\u0430\u0440\u0443\u0441\u0435\u043b\u0438. \u0414\u043b\u044f \u044d\u0442\u043e\u0433\u043e \u043e\u043d \u0441\u0442\u0430\u043b \u043f\u0440\u043e\u043a\u0440\u0443\u0447\u0438\u0432\u0430\u0442\u044c \u043b\u0435\u043d\u0442\u0443 \u0438 \u043f\u043e\u0441\u043b\u0435\u0434\u043e\u0432\u0430\u0442\u0435\u043b\u044c\u043d\u043e \u0432\u044b\u043f\u0438\u0441\u044b\u0432\u0430\u0442\u044c \u0432\u0441\u0442\u0440\u0435\u0447\u0430\u044e\u0449\u0438\u0435\u0441\u044f \u043a\u0430\u0440\u0442\u043e\u0447\u043a\u0438, \u0434\u043b\u044f \u043f\u0440\u043e\u0441\u0442\u043e\u0442\u044b \u043e\u0431\u043e\u0437\u043d\u0430\u0447\u0430\u044f \u043a\u0430\u0436\u0434\u0443\u044e \u043a\u0430\u0440\u0442\u043e\u0447\u043a\u0443 \u0441\u0442\u0440\u043e\u0447\u043d\u043e\u0439 \u043b\u0430\u0442\u0438\u043d\u0441\u043a\u043e\u0439 \u0431\u0443\u043a\u0432\u043e\u0439. \u0422\u0430\u043a \u0412\u0430\u0441\u0438\u043b\u0438\u0439 \u0432\u044b\u043f\u0438\u0441\u0430\u043b \u043f\u0435\u0440\u0432\u044b\u0435 n \u043a\u0430\u0440\u0442\u043e\u0447\u0435\u043a. \u0413\u0430\u0440\u0430\u043d\u0442\u0438\u0440\u0443\u0435\u0442\u0441\u044f, \u0447\u0442\u043e \u043e\u043d \u043f\u0440\u043e\u0441\u043c\u043e\u0442\u0440\u0435\u043b \u0432\u0441\u0435 \u043a\u0430\u0440\u0442\u043e\u0447\u043a\u0438 \u043a\u0430\u0440\u0443\u0441\u0435\u043b\u0438 \u0445\u043e\u0442\u044f \u0431\u044b \u043e\u0434\u0438\u043d \u0440\u0430\u0437. \u041f\u043e\u0441\u043a\u043e\u043b\u044c\u043a\u0443 \u0412\u0430\u0441\u0438\u043b\u0438\u0439 \u043e\u0442\u0432\u043b\u0435\u043a\u0430\u043b\u0441\u044f \u043d\u0430 \u0441\u043e\u0434\u0435\u0440\u0436\u0438\u043c\u043e\u0435 \u043a\u0430\u0440\u0442\u043e\u0447\u0435\u043a, \u043f\u0440\u0438 \u0432\u044b\u043f\u0438\u0441\u044b\u0432\u0430\u043d\u0438\u0438 \u043e\u043d \u043c\u043e\u0433 \u043f\u043e \u043e\u0448\u0438\u0431\u043a\u0435 \u0437\u0430\u043c\u0435\u043d\u044f\u0442\u044c \u043e\u0434\u043d\u0443 \u0431\u0443\u043a\u0432\u0443 \u043d\u0430 \u0434\u0440\u0443\u0433\u0443\u044e, \u043d\u043e \u0438\u0437\u0432\u0435\u0441\u0442\u043d\u043e, \u0447\u0442\u043e \u0432\u0441\u0435\u0433\u043e \u043e\u043d \u0441\u0434\u0435\u043b\u0430\u043b \u043d\u0435 \u0431\u043e\u043b\u0435\u0435 k \u043e\u0448\u0438\u0431\u043e\u043a.<\/p>\n<p>  \u0412\u0430\u043c \u0432 \u0440\u0443\u043a\u0438 \u043f\u043e\u043f\u0430\u043b\u0438 \u0437\u0430\u043f\u0438\u0441\u0438, \u0441\u0434\u0435\u043b\u0430\u043d\u043d\u044b\u0435 \u0412\u0430\u0441\u0438\u043b\u0438\u0435\u043c, \u0432\u044b \u0442\u0430\u043a\u0436\u0435 \u0437\u043d\u0430\u0435\u0442\u0435 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0435 k. \u041e\u043f\u0440\u0435\u0434\u0435\u043b\u0438\u0442\u0435, \u043a\u0430\u043a\u043e\u0435 \u043d\u0430\u0438\u043c\u0435\u043d\u044c\u0448\u0435\u0435 \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e \u043a\u0430\u0440\u0442\u043e\u0447\u0435\u043a \u043c\u043e\u0433\u043b\u043e \u0431\u044b\u0442\u044c \u0432 \u0435\u0433\u043e \u043a\u0430\u0440\u0443\u0441\u0435\u043b\u0438.<\/p>\n<div class=\"spoiler\"><b class=\"spoiler_title\">\u0424\u043e\u0440\u043c\u0430\u0442\u044b \u0432\u0432\u043e\u0434\u0430\/\u0432\u044b\u0432\u043e\u0434\u0430 \u0438 \u043f\u0440\u0438\u043c\u0435\u0440\u044b<\/b><\/p>\n<div class=\"spoiler_text\">\n<h4>\u0424\u043e\u0440\u043c\u0430\u0442 \u0432\u0432\u043e\u0434\u0430<\/h4>\n<p>  \u0412 \u043f\u0435\u0440\u0432\u043e\u0439 \u0441\u0442\u0440\u043e\u043a\u0435 \u0437\u0430\u0434\u0430\u043d\u044b \u0434\u0432\u0430 \u0446\u0435\u043b\u044b\u0445 \u0447\u0438\u0441\u043b\u0430: n (1 \u2264 n \u2264 500) \u2014 \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e \u0441\u0438\u043c\u0432\u043e\u043b\u043e\u0432, \u0432\u044b\u043f\u0438\u0441\u0430\u043d\u043d\u044b\u0445 \u0412\u0430\u0441\u0438\u043b\u0438\u0435\u043c, \u0438 k (0 \u2264 k \u2264 n) \u2014 \u043c\u0430\u043a\u0441\u0438\u043c\u0430\u043b\u044c\u043d\u043e\u0435 \u0447\u0438\u0441\u043b\u043e \u043e\u0448\u0438\u0431\u043e\u043a, \u043a\u043e\u0442\u043e\u0440\u043e\u0435 \u0434\u043e\u043f\u0443\u0441\u0442\u0438\u043b \u0412\u0430\u0441\u0438\u043b\u0438\u0439.<\/p>\n<p>  \u0412\u0442\u043e\u0440\u0430\u044f \u0441\u0442\u0440\u043e\u043a\u0430 \u0441\u043e\u0434\u0435\u0440\u0436\u0438\u0442 n \u0441\u0442\u0440\u043e\u0447\u043d\u044b\u0445 \u0431\u0443\u043a\u0432 \u043b\u0430\u0442\u0438\u043d\u0441\u043a\u043e\u0433\u043e \u0430\u043b\u0444\u0430\u0432\u0438\u0442\u0430\u00a0\u2014 \u0432\u044b\u043f\u0438\u0441\u0430\u043d\u043d\u0430\u044f \u0412\u0430\u0441\u0438\u043b\u0438\u0435\u043c \u043f\u043e\u0441\u043b\u0435\u0434\u043e\u0432\u0430\u0442\u0435\u043b\u044c\u043d\u043e\u0441\u0442\u044c.<\/p>\n<h4>\u0424\u043e\u0440\u043c\u0430\u0442 \u0432\u044b\u0432\u043e\u0434\u0430<\/h4>\n<p>  \u0412\u044b\u0432\u0435\u0434\u0438\u0442\u0435 \u043e\u0434\u043d\u043e \u0446\u0435\u043b\u043e\u0435 \u043f\u043e\u043b\u043e\u0436\u0438\u0442\u0435\u043b\u044c\u043d\u043e\u0435 \u0447\u0438\u0441\u043b\u043e\u00a0\u2014 \u043d\u0430\u0438\u043c\u0435\u043d\u044c\u0448\u0435\u0435 \u0432\u043e\u0437\u043c\u043e\u0436\u043d\u043e\u0435 \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e \u043a\u0430\u0440\u0442\u043e\u0447\u0435\u043a \u0432 \u043a\u0430\u0440\u0443\u0441\u0435\u043b\u0438.<\/p>\n<h4>\u041f\u0440\u0438\u043c\u0435\u0440 1<\/h4>\n<div class=\"scrollable-table\">\n<table>\n<tr>\n<td><b>\u0412\u0432\u043e\u0434<\/b><\/td>\n<td><b>\u0412\u044b\u0432\u043e\u0434<\/b><\/td>\n<\/tr>\n<tr>\n<td><code>5 0<br \/>  abcab<\/code><\/td>\n<td><code>3<\/code><\/td>\n<\/tr>\n<\/table>\n<\/div>\n<h4>\u041f\u0440\u0438\u043c\u0435\u0440 2<\/h4>\n<div class=\"scrollable-table\">\n<table>\n<tr>\n<td><b>\u0412\u0432\u043e\u0434<\/b><\/td>\n<td><b>\u0412\u044b\u0432\u043e\u0434<\/b><\/td>\n<\/tr>\n<tr>\n<td><code>5 1<br \/>  abcba<\/code><\/td>\n<td><code>2<\/code><\/td>\n<\/tr>\n<\/table>\n<\/div>\n<h4>\u041f\u0440\u0438\u043c\u0435\u0440 3<\/h4>\n<div class=\"scrollable-table\">\n<table>\n<tr>\n<td><b>\u0412\u0432\u043e\u0434<\/b><\/td>\n<td><b>\u0412\u044b\u0432\u043e\u0434<\/b><\/td>\n<\/tr>\n<tr>\n<td><code>7 1<br \/>  abbabba<\/code><\/td>\n<td><code>3<\/code><\/td>\n<\/tr>\n<\/table>\n<\/div>\n<h4>\u041f\u0440\u0438\u043c\u0435\u0440 4<\/h4>\n<div class=\"scrollable-table\">\n<table>\n<tr>\n<td><b>\u0412\u0432\u043e\u0434<\/b><\/td>\n<td><b>\u0412\u044b\u0432\u043e\u0434<\/b><\/td>\n<\/tr>\n<tr>\n<td><code>6 6<br \/>  abcabc<\/code><\/td>\n<td><code>1<\/code><\/td>\n<\/tr>\n<\/table>\n<\/div>\n<h4>\u041f\u0440\u0438\u043c\u0435\u0447\u0430\u043d\u0438\u044f<\/h4>\n<p>  \u0412 \u043f\u0435\u0440\u0432\u043e\u043c \u043f\u0440\u0438\u043c\u0435\u0440\u0435 k = 0, \u0438 \u043c\u044b \u0442\u043e\u0447\u043d\u043e \u0437\u043d\u0430\u0435\u043c, \u0447\u0442\u043e \u0412\u0430\u0441\u0438\u043b\u0438\u0439 \u043d\u0435 \u043e\u0448\u0438\u0431\u0430\u043b\u0441\u044f, \u043c\u0438\u043d\u0438\u043c\u0430\u043b\u044c\u043d\u0430\u044f \u043a\u0430\u0440\u0443\u0441\u0435\u043b\u044c \u043c\u043e\u0433\u043b\u0430 \u0441\u043e\u0441\u0442\u043e\u044f\u0442\u044c \u0438\u0437 3 \u043a\u0430\u0440\u0442\u043e\u0447\u0435\u043a\u00a0\u2014 abc.<\/p>\n<p>  \u0412\u043e \u0432\u0442\u043e\u0440\u043e\u043c \u043f\u0440\u0438\u043c\u0435\u0440\u0435 \u043d\u0430\u0438\u043c\u0435\u043d\u044c\u0448\u0430\u044f \u0432\u043e\u0437\u043c\u043e\u0436\u043d\u0430\u044f \u0434\u043b\u0438\u043d\u0430 \u043a\u0430\u0440\u0443\u0441\u0435\u043b\u0438 \u043f\u043e\u043b\u0443\u0447\u0430\u0435\u0442\u0441\u044f, \u0435\u0441\u043b\u0438 \u043f\u0440\u0435\u0434\u043f\u043e\u043b\u043e\u0436\u0438\u0442\u044c, \u0447\u0442\u043e \u0412\u0430\u0441\u0438\u043b\u0438\u0439 \u043f\u043e \u043e\u0448\u0438\u0431\u043a\u0435 \u0437\u0430\u043c\u0435\u043d\u0438\u043b \u0442\u0440\u0435\u0442\u044c\u044e \u0431\u0443\u043a\u0432\u0443 a \u043d\u0430 c. \u0422\u043e\u0433\u0434\u0430 \u043d\u0430\u0441\u0442\u043e\u044f\u0449\u0430\u044f \u0441\u0442\u0440\u043e\u043a\u0430\u00a0\u2014 ababa, \u043c\u0438\u043d\u0438\u043c\u0430\u043b\u044c\u043d\u0430\u044f \u043a\u0430\u0440\u0443\u0441\u0435\u043b\u044c \u0441\u043e\u0441\u0442\u043e\u0438\u0442 \u0438\u0437 2 \u043a\u0430\u0440\u0442\u043e\u0447\u0435\u043a\u00a0\u2014 ab.<\/p>\n<p>  \u0412 \u0442\u0440\u0435\u0442\u044c\u0435\u043c \u043f\u0440\u0438\u043c\u0435\u0440\u0435 \u0438\u0437\u0432\u0435\u0441\u0442\u043d\u043e, \u0447\u0442\u043e \u0412\u0430\u0441\u0438\u043b\u0438\u0439 \u043c\u043e\u0433 \u0441\u0434\u0435\u043b\u0430\u0442\u044c \u043e\u0434\u043d\u0443 \u043e\u0448\u0438\u0431\u043a\u0443. \u041e\u0434\u043d\u0430\u043a\u043e \u0440\u0430\u0437\u043c\u0435\u0440 \u043a\u0430\u0440\u0443\u0441\u0435\u043b\u0438 \u043c\u0438\u043d\u0438\u043c\u0430\u043b\u0435\u043d, \u0435\u0441\u043b\u0438 \u043f\u0440\u0435\u0434\u043f\u043e\u043b\u043e\u0436\u0438\u0442\u044c, \u0447\u0442\u043e \u043e\u043d \u043d\u0435 \u0434\u0435\u043b\u0430\u043b \u043e\u0448\u0438\u0431\u043e\u043a. \u041c\u0438\u043d\u0438\u043c\u0430\u043b\u044c\u043d\u0430\u044f \u043a\u0430\u0440\u0443\u0441\u0435\u043b\u044c \u0441\u043e\u0441\u0442\u043e\u0438\u0442 \u0438\u0437 3 \u043a\u0430\u0440\u0442\u043e\u0447\u0435\u043a\u00a0\u2014 abb. \u041e\u0431\u0440\u0430\u0442\u0438\u0442\u0435 \u0432\u043d\u0438\u043c\u0430\u043d\u0438\u0435, \u0447\u0442\u043e \u0432\u0442\u043e\u0440\u0430\u044f \u0438 \u0442\u0440\u0435\u0442\u044c\u044f \u043a\u0430\u0440\u0442\u043e\u0447\u043a\u0438 \u0432 \u044d\u0442\u043e\u0439 \u043a\u0430\u0440\u0443\u0441\u0435\u043b\u0438 \u043e\u0434\u0438\u043d\u0430\u043a\u043e\u0432\u044b\u0435.<\/p>\n<p>  \u0412 \u0447\u0435\u0442\u0432\u0451\u0440\u0442\u043e\u043c \u043f\u0440\u0438\u043c\u0435\u0440\u0435 \u043c\u044b \u043c\u043e\u0436\u0435\u043c \u0441\u043a\u0430\u0437\u0430\u0442\u044c, \u0447\u0442\u043e \u0412\u0430\u0441\u0438\u043b\u0438\u0439 \u043e\u0448\u0438\u0431\u0441\u044f \u043f\u0440\u0438 \u0432\u0432\u043e\u0434\u0435 \u0432\u0441\u0435\u0445 \u0431\u0443\u043a\u0432, \u0438 \u0438\u0441\u0445\u043e\u0434\u043d\u0430\u044f \u0441\u0442\u0440\u043e\u043a\u0430 \u043d\u0430 \u0441\u0430\u043c\u043e\u043c \u0434\u0435\u043b\u0435 \u043c\u043e\u0433\u043b\u0430 \u0431\u044b\u0442\u044c \u043b\u044e\u0431\u043e\u0439, \u043d\u0430\u043f\u0440\u0438\u043c\u0435\u0440 ffffff. \u0422\u043e\u0433\u0434\u0430 \u043a\u0430\u0440\u0443\u0441\u0435\u043b\u044c \u043c\u043e\u0433\u043b\u0430 \u0441\u043e\u0441\u0442\u043e\u044f\u0442\u044c \u0438\u0437 \u043e\u0434\u043d\u043e\u0439 \u043a\u0430\u0440\u0442\u043e\u0447\u043a\u0438\u00a0\u2014 f.<\/p><\/div>\n<\/div>\n<p>  <\/p>\n<h4>\u0421\u0438\u0441\u0442\u0435\u043c\u0430 \u043e\u0446\u0435\u043d\u043a\u0438<\/h4>\n<p>  \u0422\u043e\u043b\u044c\u043a\u043e \u043f\u0440\u0438 \u043f\u0440\u043e\u0445\u043e\u0436\u0434\u0435\u043d\u0438\u0438 \u0432\u0441\u0435\u0445 \u0442\u0435\u0441\u0442\u043e\u0432 \u0437\u0430 \u0437\u0430\u0434\u0430\u0447\u0443 \u043c\u043e\u0436\u043d\u043e \u043f\u043e\u043b\u0443\u0447\u0438\u0442\u044c <b>50 \u0431\u0430\u043b\u043b\u043e\u0432<\/b>.<\/p>\n<p>  \u0412 \u0442\u0435\u0441\u0442\u0438\u0440\u0443\u044e\u0449\u0435\u0439 \u0441\u0438\u0441\u0442\u0435\u043c\u0435 \u0442\u0435\u0441\u0442\u044b 1\u20134 \u2014 \u043f\u0440\u0438\u043c\u0435\u0440\u044b \u0438\u0437 \u0443\u0441\u043b\u043e\u0432\u0438\u044f.<\/p>\n<h4>\u0420\u0435\u0448\u0435\u043d\u0438\u0435<\/h4>\n<p>  \u0414\u043e\u0441\u0442\u0430\u0442\u043e\u0447\u043d\u043e \u0431\u044b\u043b\u043e \u043f\u0435\u0440\u0435\u0431\u0440\u0430\u0442\u044c \u0432\u043e\u0437\u043c\u043e\u0436\u043d\u0443\u044e \u0434\u043b\u0438\u043d\u0443 \u043a\u0430\u0440\u0443\u0441\u0435\u043b\u0438 \u043e\u0442 1 \u0434\u043e n \u0438 \u0434\u043b\u044f \u043a\u0430\u0436\u0434\u043e\u0439 \u0444\u0438\u043a\u0441\u0438\u0440\u043e\u0432\u0430\u043d\u043d\u043e\u0439 \u0434\u043b\u0438\u043d\u044b \u043f\u0440\u043e\u0432\u0435\u0440\u0438\u0442\u044c, \u043c\u043e\u0433\u043b\u0430 \u043b\u0438 \u043e\u043d\u0430 \u0431\u044b\u0442\u044c \u0442\u0430\u043a\u043e\u0432\u043e\u0439. \u041f\u0440\u0438 \u044d\u0442\u043e\u043c \u043f\u043e\u043d\u044f\u0442\u043d\u043e, \u0447\u0442\u043e \u043e\u0442\u0432\u0435\u0442 \u0432\u0441\u0435\u0433\u0434\u0430 \u0441\u0443\u0449\u0435\u0441\u0442\u0432\u0443\u0435\u0442, \u043f\u043e\u0441\u043a\u043e\u043b\u044c\u043a\u0443 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0435 n \u0433\u0430\u0440\u0430\u043d\u0442\u0438\u0440\u043e\u0432\u0430\u043d\u043d\u043e \u044f\u0432\u043b\u044f\u0435\u0442\u0441\u044f \u0432\u043e\u0437\u043c\u043e\u0436\u043d\u044b\u043c \u043e\u0442\u0432\u0435\u0442\u043e\u043c, \u043a\u0430\u043a\u0438\u043c \u0431\u044b \u043d\u0438 \u0431\u044b\u043b\u043e \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0435 k. \u0414\u043b\u044f \u0444\u0438\u043a\u0441\u0438\u0440\u043e\u0432\u0430\u043d\u043d\u043e\u0439 \u0434\u043b\u0438\u043d\u044b \u043a\u0430\u0440\u0443\u0441\u0435\u043b\u0438 p \u0434\u043e\u0441\u0442\u0430\u0442\u043e\u0447\u043d\u043e \u043f\u043e\u0441\u0447\u0438\u0442\u0430\u0442\u044c \u043d\u0435\u0437\u0430\u0432\u0438\u0441\u0438\u043c\u043e \u0434\u043b\u044f \u0432\u0441\u0435\u0445 i \u043e\u0442 0 \u0434\u043e (p \u2013 1), \u043a\u0430\u043a\u043e\u0435 \u043c\u0438\u043d\u0438\u043c\u0430\u043b\u044c\u043d\u043e\u0435 \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e \u043e\u0448\u0438\u0431\u043e\u043a \u0434\u043e\u043f\u0443\u0449\u0435\u043d\u043e \u043d\u0430 \u043f\u043e\u0437\u0438\u0446\u0438\u044f\u0445 i, i + p, i + 2p \u0438 \u0442. \u0434. \u042d\u0442\u043e \u0447\u0438\u0441\u043b\u043e \u043e\u0448\u0438\u0431\u043e\u043a \u043c\u0438\u043d\u0438\u043c\u0430\u043b\u044c\u043d\u043e, \u0435\u0441\u043b\u0438 \u043f\u0440\u0438\u043d\u044f\u0442\u044c \u0437\u0430 \u0438\u0441\u0442\u0438\u043d\u043d\u044b\u0439 \u0441\u0438\u043c\u0432\u043e\u043b \u0442\u043e\u0442, \u043a\u043e\u0442\u043e\u0440\u044b\u0439 \u0432\u0441\u0442\u0440\u0435\u0447\u0430\u0435\u0442\u0441\u044f \u043d\u0430 \u044d\u0442\u0438\u0445 \u043f\u043e\u0437\u0438\u0446\u0438\u044f\u0445 \u0447\u0430\u0449\u0435 \u0432\u0441\u0435\u0445. \u0422\u043e\u0433\u0434\u0430 \u0447\u0438\u0441\u043b\u043e \u043e\u0448\u0438\u0431\u043e\u043a \u0440\u0430\u0432\u043d\u043e \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u0443 \u043f\u043e\u0437\u0438\u0446\u0438\u0439, \u043d\u0430 \u043a\u043e\u0442\u043e\u0440\u044b\u0445 \u0441\u0442\u043e\u0438\u0442 \u0434\u0440\u0443\u0433\u0430\u044f \u0431\u0443\u043a\u0432\u0430. \u0415\u0441\u043b\u0438 \u0434\u043b\u044f \u043d\u0435\u043a\u043e\u0442\u043e\u0440\u043e\u0433\u043e p \u043e\u0431\u0449\u0435\u0435 \u0447\u0438\u0441\u043b\u043e \u043e\u0448\u0438\u0431\u043e\u043a \u043d\u0435 \u043f\u0440\u0435\u0432\u043e\u0441\u0445\u043e\u0434\u0438\u0442 k, \u0442\u043e \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0435 p \u044f\u0432\u043b\u044f\u0435\u0442\u0441\u044f \u0432\u043e\u0437\u043c\u043e\u0436\u043d\u044b\u043c \u043e\u0442\u0432\u0435\u0442\u043e\u043c. \u041f\u043e\u0441\u043a\u043e\u043b\u044c\u043a\u0443 \u0434\u043b\u044f \u043a\u0430\u0436\u0434\u043e\u0433\u043e p \u043d\u0443\u0436\u043d\u043e \u043f\u0440\u043e\u0431\u0435\u0436\u0430\u0442\u044c\u0441\u044f \u043f\u043e \u0432\u0441\u0435\u043c \u0441\u0438\u043c\u0432\u043e\u043b\u0430\u043c \u0441\u0442\u0440\u043e\u043a\u0438 \u043e\u0434\u0438\u043d \u0440\u0430\u0437, \u0441\u043b\u043e\u0436\u043d\u043e\u0441\u0442\u044c \u0442\u0430\u043a\u043e\u0433\u043e \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0430 \u2014 O(n<sup>2<\/sup>).<\/p>\n<pre><code class=\"python\">n, k = map(int, input().split()) s = input().strip()  for p in range(1, n + 1):     mistakes = 0     for i in range(0, p):         counts = [0] * 26         for j in range(i, n, p):             counts[ord(s[j]) - ord(\"a\")] += 1         mistakes += sum(counts) - max(counts)     if mistakes &lt;= k:         print(p)         break<\/code><\/pre>\n<p>  <\/p>\n<h2>B1. \u041e\u043f\u0442\u0438\u043c\u0430\u043b\u044c\u043d\u0430\u044f \u043b\u0435\u043d\u0442\u0430 \u0440\u0435\u043a\u043e\u043c\u0435\u043d\u0434\u0430\u0446\u0438\u0439<\/h2>\n<p>  <\/p>\n<h4>\u0423\u0441\u043b\u043e\u0432\u0438\u0435<\/h4>\n<div class=\"scrollable-table\">\n<table>\n<tr>\n<td><\/td>\n<td><b>\u0412\u0441\u0435 \u044f\u0437\u044b\u043a\u0438<\/b><\/td>\n<td><b>Oracle Java 8<\/b><\/td>\n<td><b>GNU c++17 7.3<\/b><\/td>\n<\/tr>\n<tr>\n<td>\u041e\u0433\u0440\u0430\u043d\u0438\u0447\u0435\u043d\u0438\u0435 \u0432\u0440\u0435\u043c\u0435\u043d\u0438<\/td>\n<td>5 \u0441<\/td>\n<td>3 \u0441<\/td>\n<td>1 \u0441<\/td>\n<\/tr>\n<tr>\n<td>\u041e\u0433\u0440\u0430\u043d\u0438\u0447\u0435\u043d\u0438\u0435 \u043f\u0430\u043c\u044f\u0442\u0438<\/td>\n<td colspan=\"3\">256 \u041c\u0411<\/td>\n<\/tr>\n<tr>\n<td>\u0412\u0432\u043e\u0434<\/td>\n<td colspan=\"3\">\u0441\u0442\u0430\u043d\u0434\u0430\u0440\u0442\u043d\u044b\u0439 \u0432\u0432\u043e\u0434 \u0438\u043b\u0438 input.txt<\/td>\n<\/tr>\n<tr>\n<td>\u0412\u044b\u0432\u043e\u0434<\/td>\n<td colspan=\"3\">\u0441\u0442\u0430\u043d\u0434\u0430\u0440\u0442\u043d\u044b\u0439 \u0432\u044b\u0432\u043e\u0434 \u0438\u043b\u0438 output.txt<\/td>\n<\/tr>\n<\/table>\n<\/div>\n<p>\u0424\u043e\u0440\u043c\u0438\u0440\u043e\u0432\u0430\u043d\u0438\u0435 \u043e\u0447\u0435\u0440\u0435\u0434\u043d\u043e\u0439 \u043f\u043e\u0440\u0446\u0438\u0438 \u043f\u0435\u0440\u0441\u043e\u043d\u0430\u043b\u044c\u043d\u043e\u0439 \u0432\u044b\u0434\u0430\u0447\u0438 \u0440\u0435\u043a\u043e\u043c\u0435\u043d\u0434\u0430\u0446\u0438\u0439 \u0434\u043b\u044f \u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u0442\u0435\u043b\u044f \u2014 \u043d\u0435\u043f\u0440\u043e\u0441\u0442\u0430\u044f \u0437\u0430\u0434\u0430\u0447\u0430. \u0420\u0430\u0441\u0441\u043c\u043e\u0442\u0440\u0438\u043c n \u043f\u0443\u0431\u043b\u0438\u043a\u0430\u0446\u0438\u0439, \u0432\u044b\u0431\u0440\u0430\u043d\u043d\u044b\u0445 \u0438\u0437 \u0440\u0435\u043a\u043e\u043c\u0435\u043d\u0434\u0430\u0442\u0435\u043b\u044c\u043d\u043e\u0439 \u0431\u0430\u0437\u044b \u043f\u043e \u0438\u0442\u043e\u0433\u0430\u043c \u043e\u0442\u0431\u043e\u0440\u0430 \u043a\u0430\u043d\u0434\u0438\u0434\u0430\u0442\u043e\u0432. \u041f\u0443\u0431\u043b\u0438\u043a\u0430\u0446\u0438\u044f \u043f\u043e\u0434 \u043d\u043e\u043c\u0435\u0440\u043e\u043c i \u0445\u0430\u0440\u0430\u043a\u0442\u0435\u0440\u0438\u0437\u0443\u0435\u0442\u0441\u044f \u043e\u0446\u0435\u043d\u043a\u043e\u0439 \u0440\u0435\u043b\u0435\u0432\u0430\u043d\u0442\u043d\u043e\u0441\u0442\u0438 s<sub>i<\/sub> \u0438 \u043d\u0430\u0431\u043e\u0440\u043e\u043c \u0438\u0437 k \u0431\u0438\u043d\u0430\u0440\u043d\u044b\u0445 \u0430\u0442\u0440\u0438\u0431\u0443\u0442\u043e\u0432 a<sub>i1<\/sub>, a<sub>i2<\/sub>, &#8230;, a<sub>ik<\/sub>. \u041a\u0430\u0436\u0434\u044b\u0439 \u0438\u0437 \u044d\u0442\u0438\u0445 \u0430\u0442\u0440\u0438\u0431\u0443\u0442\u043e\u0432 \u043e\u0442\u0432\u0435\u0447\u0430\u0435\u0442 \u043d\u0435\u043a\u043e\u0442\u043e\u0440\u043e\u043c\u0443 \u0441\u0432\u043e\u0439\u0441\u0442\u0432\u0443 \u043f\u0443\u0431\u043b\u0438\u043a\u0430\u0446\u0438\u0438, \u043a \u043f\u0440\u0438\u043c\u0435\u0440\u0443, \u043f\u043e\u0434\u043f\u0438\u0441\u0430\u043d \u043b\u0438 \u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u0442\u0435\u043b\u044c \u043d\u0430 \u0438\u0441\u0442\u043e\u0447\u043d\u0438\u043a \u044d\u0442\u043e\u0439 \u043f\u0443\u0431\u043b\u0438\u043a\u0430\u0446\u0438\u0438, \u0431\u044b\u043b\u0430 \u043b\u0438 \u043f\u0443\u0431\u043b\u0438\u043a\u0430\u0446\u0438\u044f \u0441\u043e\u0437\u0434\u0430\u043d\u0430 \u0437\u0430 \u043f\u043e\u0441\u043b\u0435\u0434\u043d\u0438\u0435 24 \u0447\u0430\u0441\u0430 \u0438 \u0442. \u0434. \u041f\u0443\u0431\u043b\u0438\u043a\u0430\u0446\u0438\u044f \u043c\u043e\u0436\u0435\u0442 \u043e\u0431\u043b\u0430\u0434\u0430\u0442\u044c \u0441\u0440\u0430\u0437\u0443 \u043d\u0435\u0441\u043a\u043e\u043b\u044c\u043a\u0438\u043c\u0438 \u0438\u0437 \u044d\u0442\u0438\u0445 \u0441\u0432\u043e\u0439\u0441\u0442\u0432 \u043e\u0434\u043d\u043e\u0432\u0440\u0435\u043c\u0435\u043d\u043d\u043e \u2014 \u0432 \u0442\u0430\u043a\u043e\u043c \u0441\u043b\u0443\u0447\u0430\u0435 \u0441\u043e\u043e\u0442\u0432\u0435\u0442\u0441\u0442\u0432\u0443\u044e\u0449\u0438\u0435 \u0430\u0442\u0440\u0438\u0431\u0443\u0442\u044b \u043f\u0440\u0438\u043d\u0438\u043c\u0430\u044e\u0442 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0435 1, \u0430 \u043c\u043e\u0436\u0435\u0442 \u0438 \u043d\u0435 \u043e\u0431\u043b\u0430\u0434\u0430\u0442\u044c \u043d\u0438 \u043e\u0434\u043d\u0438\u043c \u0438\u0437 \u043d\u0438\u0445 \u2014 \u0438 \u0442\u043e\u0433\u0434\u0430 \u0432\u0441\u0435 \u0435\u0451 \u0430\u0442\u0440\u0438\u0431\u0443\u0442\u044b \u0440\u0430\u0432\u043d\u044b 0.<\/p>\n<p>  \u0414\u043b\u044f \u0442\u043e\u0433\u043e \u0447\u0442\u043e\u0431\u044b \u043b\u0435\u043d\u0442\u0430 \u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u0442\u0435\u043b\u044f \u0431\u044b\u043b\u0430 \u0440\u0430\u0437\u043d\u043e\u043e\u0431\u0440\u0430\u0437\u043d\u043e\u0439, \u043d\u0435\u043e\u0431\u0445\u043e\u0434\u0438\u043c\u043e \u0432\u044b\u0431\u0440\u0430\u0442\u044c \u0441\u0440\u0435\u0434\u0438 n \u043a\u0430\u043d\u0434\u0438\u0434\u0430\u0442\u043e\u0432 m \u043f\u0443\u0431\u043b\u0438\u043a\u0430\u0446\u0438\u0439 \u0442\u0430\u043a, \u0447\u0442\u043e\u0431\u044b \u0441\u0440\u0435\u0434\u0438 \u043d\u0438\u0445 \u043e\u043a\u0430\u0437\u0430\u043b\u043e\u0441\u044c \u043d\u0435 \u043c\u0435\u043d\u0435\u0435 A<sub>1<\/sub> \u043f\u0443\u0431\u043b\u0438\u043a\u0430\u0446\u0438\u0439, \u043e\u0431\u043b\u0430\u0434\u0430\u044e\u0449\u0438\u0445 \u043f\u0435\u0440\u0432\u044b\u043c \u0441\u0432\u043e\u0439\u0441\u0442\u0432\u043e\u043c, \u043d\u0435 \u043c\u0435\u043d\u0435\u0435 A<sub>2<\/sub> \u043f\u0443\u0431\u043b\u0438\u043a\u0430\u0446\u0438\u0439, \u043e\u0431\u043b\u0430\u0434\u0430\u044e\u0449\u0438\u0445 \u0432\u0442\u043e\u0440\u044b\u043c \u0441\u0432\u043e\u0439\u0441\u0442\u0432\u043e\u043c, \u2026, A<sub>k<\/sub> \u043f\u0443\u0431\u043b\u0438\u043a\u0430\u0446\u0438\u0439, \u043e\u0431\u043b\u0430\u0434\u0430\u044e\u0449\u0438\u0445 \u0441\u0432\u043e\u0439\u0441\u0442\u0432\u043e\u043c \u043f\u043e\u0434 \u043d\u043e\u043c\u0435\u0440\u043e\u043c k. \u041d\u0430\u0439\u0434\u0438\u0442\u0435 \u043c\u0430\u043a\u0441\u0438\u043c\u0430\u043b\u044c\u043d\u043e \u0432\u043e\u0437\u043c\u043e\u0436\u043d\u0443\u044e \u0441\u0443\u043c\u043c\u0430\u0440\u043d\u0443\u044e \u043e\u0446\u0435\u043d\u043a\u0443 \u0440\u0435\u043b\u0435\u0432\u0430\u043d\u0442\u043d\u043e\u0441\u0442\u0438 m \u043f\u0443\u0431\u043b\u0438\u043a\u0430\u0446\u0438\u0439, \u0443\u0434\u043e\u0432\u043b\u0435\u0442\u0432\u043e\u0440\u044f\u044e\u0449\u0438\u0445 \u044d\u0442\u043e\u043c\u0443 \u0442\u0440\u0435\u0431\u043e\u0432\u0430\u043d\u0438\u044e, \u043b\u0438\u0431\u043e \u043e\u043f\u0440\u0435\u0434\u0435\u043b\u0438\u0442\u0435, \u0447\u0442\u043e \u0442\u0430\u043a\u043e\u0433\u043e \u043d\u0430\u0431\u043e\u0440\u0430 \u043f\u0443\u0431\u043b\u0438\u043a\u0430\u0446\u0438\u0439 \u043d\u0435 \u0441\u0443\u0449\u0435\u0441\u0442\u0432\u0443\u0435\u0442.<\/p>\n<div class=\"spoiler\"><b class=\"spoiler_title\">\u0424\u043e\u0440\u043c\u0430\u0442\u044b \u0432\u0432\u043e\u0434\u0430\/\u0432\u044b\u0432\u043e\u0434\u0430 \u0438 \u043f\u0440\u0438\u043c\u0435\u0440\u044b<\/b><\/p>\n<div class=\"spoiler_text\">\n<h4>\u0424\u043e\u0440\u043c\u0430\u0442 \u0432\u0432\u043e\u0434\u0430<\/h4>\n<p>  \u0412 \u043f\u0435\u0440\u0432\u043e\u0439 \u0441\u0442\u0440\u043e\u043a\u0435 \u0437\u0430\u0434\u0430\u043d\u044b \u0442\u0440\u0438 \u0446\u0435\u043b\u044b\u0445 \u0447\u0438\u0441\u043b\u0430\u00a0\u2014 n, m, k (1 \u2264 n \u2264 50, 1 \u2264 m \u2264 min(n, 9), 1 \u2264 k \u2264 5).<\/p>\n<p>  \u0412 \u0441\u043b\u0435\u0434\u0443\u044e\u0449\u0438\u0445 n \u0441\u0442\u0440\u043e\u043a\u0430\u0445 \u0437\u0430\u0434\u0430\u043d\u044b \u0445\u0430\u0440\u0430\u043a\u0442\u0435\u0440\u0438\u0441\u0442\u0438\u043a\u0438 \u043f\u0443\u0431\u043b\u0438\u043a\u0430\u0446\u0438\u0439. \u0414\u043b\u044f i-\u0439 \u043f\u0443\u0431\u043b\u0438\u043a\u0430\u0446\u0438\u0438 \u0437\u0430\u0434\u0430\u043d\u043e \u0446\u0435\u043b\u043e\u0435 \u0447\u0438\u0441\u043b\u043e s<sub>i<\/sub> (1 \u2264 s<sub>i<\/sub> \u2264 10<sup>9<\/sup>) \u2014 \u043e\u0446\u0435\u043d\u043a\u0430 \u0440\u0435\u043b\u0435\u0432\u0430\u043d\u0442\u043d\u043e\u0441\u0442\u0438 \u0434\u0430\u043d\u043d\u043e\u0439 \u043f\u0443\u0431\u043b\u0438\u043a\u0430\u0446\u0438\u0438, \u0438 \u0434\u0430\u043b\u0435\u0435 \u0447\u0435\u0440\u0435\u0437 \u043f\u0440\u043e\u0431\u0435\u043b \u0441\u0442\u0440\u043e\u043a\u0430 \u0438\u0437 k \u0441\u0438\u043c\u0432\u043e\u043b\u043e\u0432, \u043a\u0430\u0436\u0434\u044b\u0439 \u0438\u0437 \u043a\u043e\u0442\u043e\u0440\u044b\u0445 \u0440\u0430\u0432\u0435\u043d 0 \u0438\u043b\u0438 1\u00a0\u2014 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u044f \u043a\u0430\u0436\u0434\u043e\u0433\u043e \u0438\u0437 \u0430\u0442\u0440\u0438\u0431\u0443\u0442\u043e\u0432 \u0434\u0430\u043d\u043d\u043e\u0439 \u043f\u0443\u0431\u043b\u0438\u043a\u0430\u0446\u0438\u0438.<\/p>\n<p>  \u0412 \u043f\u043e\u0441\u043b\u0435\u0434\u043d\u0435\u0439 \u0441\u0442\u0440\u043e\u043a\u0435 \u0437\u0430\u0434\u0430\u043d\u044b k \u0446\u0435\u043b\u044b\u0445 \u0447\u0438\u0441\u0435\u043b, \u0440\u0430\u0437\u0434\u0435\u043b\u0451\u043d\u043d\u044b\u0445 \u043f\u0440\u043e\u0431\u0435\u043b\u0430\u043c\u0438\u00a0\u2014 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u044f A<sub>1<\/sub>, &#8230;, A<sub>k<\/sub> (0\u00a0\u2264\u00a0A<sub>i<\/sub>\u00a0\u2264\u00a0m), \u043e\u043f\u0440\u0435\u0434\u0435\u043b\u044f\u044e\u0449\u0438\u0435 \u0442\u0440\u0435\u0431\u043e\u0432\u0430\u043d\u0438\u044f \u043a \u0438\u0442\u043e\u0433\u043e\u0432\u043e\u043c\u0443 \u043d\u0430\u0431\u043e\u0440\u0443 \u0438\u0437 m \u043f\u0443\u0431\u043b\u0438\u043a\u0430\u0446\u0438\u0439. <\/p>\n<h4>\u0424\u043e\u0440\u043c\u0430\u0442 \u0432\u044b\u0432\u043e\u0434\u0430<\/h4>\n<p>  \u0415\u0441\u043b\u0438 \u043d\u0435 \u0441\u0443\u0449\u0435\u0441\u0442\u0432\u0443\u0435\u0442 \u043d\u0430\u0431\u043e\u0440\u0430 \u0438\u0437 m \u043f\u0443\u0431\u043b\u0438\u043a\u0430\u0446\u0438\u0439, \u0443\u0434\u043e\u0432\u043b\u0435\u0442\u0432\u043e\u0440\u044f\u044e\u0449\u0438\u0445 \u043e\u0433\u0440\u0430\u043d\u0438\u0447\u0435\u043d\u0438\u044f\u043c, \u0432\u044b\u0432\u0435\u0434\u0438\u0442\u0435 \u0447\u0438\u0441\u043b\u043e 0. \u0418\u043d\u0430\u0447\u0435 \u0432\u044b\u0432\u0435\u0434\u0438\u0442\u0435 \u043e\u0434\u043d\u043e \u0446\u0435\u043b\u043e\u0435 \u043f\u043e\u043b\u043e\u0436\u0438\u0442\u0435\u043b\u044c\u043d\u043e\u0435 \u0447\u0438\u0441\u043b\u043e\u00a0\u2014 \u043c\u0430\u043a\u0441\u0438\u043c\u0430\u043b\u044c\u043d\u043e \u0432\u043e\u0437\u043c\u043e\u0436\u043d\u0443\u044e \u0441\u0443\u043c\u043c\u0430\u0440\u043d\u0443\u044e \u043e\u0446\u0435\u043d\u043a\u0443 \u0440\u0435\u043b\u0435\u0432\u0430\u043d\u0442\u043d\u043e\u0441\u0442\u0438.<\/p>\n<h4>\u041f\u0440\u0438\u043c\u0435\u0440 1<\/h4>\n<div class=\"scrollable-table\">\n<table>\n<tr>\n<td><b>\u0412\u0432\u043e\u0434<\/b><\/td>\n<td><b>\u0412\u044b\u0432\u043e\u0434<\/b><\/td>\n<\/tr>\n<tr>\n<td><code>4 2 2<br \/>  8 00<br \/>  6 01<br \/>  5 10<br \/>  2 11<br \/>  1 1<\/code><\/td>\n<td><code>11<\/code><\/td>\n<\/tr>\n<\/table>\n<\/div>\n<h4>\u041f\u0440\u0438\u043c\u0435\u0440 2<\/h4>\n<div class=\"scrollable-table\">\n<table>\n<tr>\n<td><b>\u0412\u0432\u043e\u0434<\/b><\/td>\n<td><b>\u0412\u044b\u0432\u043e\u0434<\/b><\/td>\n<\/tr>\n<tr>\n<td><code>3 2 2<br \/>  3 01<br \/>  3 10<br \/>  3 10<br \/>  1 2<\/code><\/td>\n<td><code>0<\/code><\/td>\n<\/tr>\n<\/table>\n<\/div>\n<h4>\u041f\u0440\u0438\u043c\u0435\u0447\u0430\u043d\u0438\u044f<\/h4>\n<p>  \u0412 \u043f\u0435\u0440\u0432\u043e\u043c \u043f\u0440\u0438\u043c\u0435\u0440\u0435 \u043d\u0435\u043e\u0431\u0445\u043e\u0434\u0438\u043c\u043e \u0438\u0437 \u0447\u0435\u0442\u044b\u0440\u0451\u0445 \u043f\u0443\u0431\u043b\u0438\u043a\u0430\u0446\u0438\u0439 \u0441 \u0434\u0432\u0443\u043c\u044f \u0441\u0432\u043e\u0439\u0441\u0442\u0432\u0430\u043c\u0438 \u0432\u044b\u0431\u0440\u0430\u0442\u044c \u0434\u0432\u0435 \u0442\u0430\u043a, \u0447\u0442\u043e\u0431\u044b \u0431\u044b\u043b\u043e \u043d\u0435 \u043c\u0435\u043d\u0435\u0435 \u043e\u0434\u043d\u043e\u0439 \u043f\u0443\u0431\u043b\u0438\u043a\u0430\u0446\u0438\u0438, \u043e\u0431\u043b\u0430\u0434\u0430\u044e\u0449\u0435\u0439 \u043f\u0435\u0440\u0432\u044b\u043c \u0441\u0432\u043e\u0439\u0441\u0442\u0432\u043e\u043c, \u0438 \u043e\u0434\u043d\u043e\u0439, \u043e\u0431\u043b\u0430\u0434\u0430\u044e\u0449\u0435\u0439 \u0432\u0442\u043e\u0440\u044b\u043c \u0441\u0432\u043e\u0439\u0441\u0442\u0432\u043e\u043c. \u0421\u0430\u043c\u0443\u044e \u0431\u043e\u043b\u044c\u0448\u0443\u044e \u0441\u0443\u043c\u043c\u0443 \u0440\u0435\u043b\u0435\u0432\u0430\u043d\u0442\u043d\u043e\u0441\u0442\u0435\u0439 \u043c\u043e\u0436\u043d\u043e \u043f\u043e\u043b\u0443\u0447\u0438\u0442\u044c, \u0435\u0441\u043b\u0438 \u0432\u0437\u044f\u0442\u044c \u0432\u0442\u043e\u0440\u0443\u044e \u0438 \u0442\u0440\u0435\u0442\u044c\u044e \u043f\u0443\u0431\u043b\u0438\u043a\u0430\u0446\u0438\u0438, \u0445\u043e\u0442\u044f \u043f\u043e\u0434 \u043e\u0433\u0440\u0430\u043d\u0438\u0447\u0435\u043d\u0438\u044f \u0442\u0430\u043a\u0436\u0435 \u043f\u043e\u0434\u0445\u043e\u0434\u0438\u0442 \u043b\u044e\u0431\u043e\u0439 \u0432\u0430\u0440\u0438\u0430\u043d\u0442 \u0441 \u0447\u0435\u0442\u0432\u0451\u0440\u0442\u043e\u0439 \u043f\u0443\u0431\u043b\u0438\u043a\u0430\u0446\u0438\u0435\u0439.<\/p>\n<p>  \u0412\u043e \u0432\u0442\u043e\u0440\u043e\u043c \u043f\u0440\u0438\u043c\u0435\u0440\u0435 \u043d\u0435\u0432\u043e\u0437\u043c\u043e\u0436\u043d\u043e \u0432\u044b\u0431\u0440\u0430\u0442\u044c \u0434\u0432\u0435 \u043f\u0443\u0431\u043b\u0438\u043a\u0430\u0446\u0438\u0438 \u0442\u0430\u043a, \u0447\u0442\u043e\u0431\u044b \u043e\u0431\u0435 \u043e\u0431\u043b\u0430\u0434\u0430\u043b\u0438 \u0432\u0442\u043e\u0440\u044b\u043c \u0441\u0432\u043e\u0439\u0441\u0442\u0432\u043e\u043c, \u0438\u0431\u043e \u0438\u043c \u043e\u0431\u043b\u0430\u0434\u0430\u0435\u0442 \u0442\u043e\u043b\u044c\u043a\u043e \u043f\u0435\u0440\u0432\u0430\u044f \u043f\u0443\u0431\u043b\u0438\u043a\u0430\u0446\u0438\u044f.<\/p><\/div>\n<\/div>\n<p>  <\/p>\n<h4>\u0421\u0438\u0441\u0442\u0435\u043c\u0430 \u043e\u0446\u0435\u043d\u043a\u0438<\/h4>\n<p>  \u0422\u0435\u0441\u0442\u044b \u043a \u044d\u0442\u043e\u0439 \u0437\u0430\u0434\u0430\u0447\u0435 \u0441\u043e\u0441\u0442\u043e\u044f\u0442 \u0438\u0437 \u043f\u044f\u0442\u0438 \u0433\u0440\u0443\u043f\u043f. \u0411\u0430\u043b\u043b\u044b \u0437\u0430 \u043a\u0430\u0436\u0434\u0443\u044e \u0433\u0440\u0443\u043f\u043f\u0443 \u0441\u0442\u0430\u0432\u044f\u0442\u0441\u044f \u0442\u043e\u043b\u044c\u043a\u043e \u043f\u0440\u0438 \u043f\u0440\u043e\u0445\u043e\u0436\u0434\u0435\u043d\u0438\u0438 \u0432\u0441\u0435\u0445 \u0442\u0435\u0441\u0442\u043e\u0432 \u0433\u0440\u0443\u043f\u043f\u044b \u0438 \u0432\u0441\u0435\u0445 \u0442\u0435\u0441\u0442\u043e\u0432 <b>\u043f\u0440\u0435\u0434\u044b\u0434\u0443\u0449\u0438\u0445<\/b> \u0433\u0440\u0443\u043f\u043f. \u041f\u0440\u043e\u0445\u043e\u0436\u0434\u0435\u043d\u0438\u0435 \u0442\u0435\u0441\u0442\u043e\u0432 \u0438\u0437 \u0443\u0441\u043b\u043e\u0432\u0438\u044f \u043d\u0435\u043e\u0431\u0445\u043e\u0434\u0438\u043c\u043e \u0434\u043b\u044f \u043f\u043e\u043b\u0443\u0447\u0435\u043d\u0438\u044f \u0431\u0430\u043b\u043b\u043e\u0432 \u0437\u0430 \u0433\u0440\u0443\u043f\u043f\u044b \u043d\u0430\u0447\u0438\u043d\u0430\u044f \u0441\u043e \u0432\u0442\u043e\u0440\u043e\u0439. \u0412\u0441\u0435\u0433\u043e \u0437\u0430 \u0437\u0430\u0434\u0430\u0447\u0443 \u043c\u043e\u0436\u043d\u043e \u043f\u043e\u043b\u0443\u0447\u0438\u0442\u044c <b>100 \u0431\u0430\u043b\u043b\u043e\u0432<\/b>.<\/p>\n<p>  \u0412 \u0442\u0435\u0441\u0442\u0438\u0440\u0443\u044e\u0449\u0435\u0439 \u0441\u0438\u0441\u0442\u0435\u043c\u0435 \u0442\u0435\u0441\u0442\u044b 1\u20132 \u2014 \u043f\u0440\u0438\u043c\u0435\u0440\u044b \u0438\u0437 \u0443\u0441\u043b\u043e\u0432\u0438\u044f.<\/p>\n<p>  1. <b>(10 \u0431\u0430\u043b\u043b\u043e\u0432)<\/b> \u0442\u0435\u0441\u0442\u044b 3\u201310: k = 1, m \u2264 3, s<sub>i<\/sub> \u2264 1000, \u043d\u0435 \u0442\u0440\u0435\u0431\u0443\u0435\u0442\u0441\u044f \u043f\u0440\u043e\u0445\u043e\u0436\u0434\u0435\u043d\u0438\u0435 \u0442\u0435\u0441\u0442\u043e\u0432 \u0438\u0437 \u0443\u0441\u043b\u043e\u0432\u0438\u044f<br \/>  2. <b>(20 \u0431\u0430\u043b\u043b\u043e\u0432)<\/b> \u0442\u0435\u0441\u0442\u044b 11\u201320: k \u2264 2, m \u2264 3<br \/>  3. <b>(20 \u0431\u0430\u043b\u043b\u043e\u0432)<\/b> \u0442\u0435\u0441\u0442\u044b 21\u201329: k \u2264 2<br \/>  4. <b>(20 \u0431\u0430\u043b\u043b\u043e\u0432)<\/b> \u0442\u0435\u0441\u0442\u044b 30\u201337: k \u2264 3<br \/>  5. <b>(30 \u0431\u0430\u043b\u043b\u043e\u0432)<\/b> \u0442\u0435\u0441\u0442\u044b 38\u201347: \u043d\u0435\u0442 \u0434\u043e\u043f\u043e\u043b\u043d\u0438\u0442\u0435\u043b\u044c\u043d\u044b\u0445 \u043e\u0433\u0440\u0430\u043d\u0438\u0447\u0435\u043d\u0438\u0439<\/p>\n<h4>\u0420\u0435\u0448\u0435\u043d\u0438\u0435<\/h4>\n<p>  \u0415\u0441\u0442\u044c n \u043f\u0443\u0431\u043b\u0438\u043a\u0430\u0446\u0438\u0439, \u0443 \u043a\u0430\u0436\u0434\u043e\u0439 \u0435\u0441\u0442\u044c \u0441\u043a\u043e\u0440 \u0438 k \u0431\u0443\u043b\u0435\u0432\u044b\u0445 \u0444\u043b\u0430\u0436\u043a\u043e\u0432, \u0442\u0440\u0435\u0431\u0443\u0435\u0442\u0441\u044f \u0432\u044b\u0431\u0440\u0430\u0442\u044c m \u043a\u0430\u0440\u0442\u043e\u0447\u0435\u043a, \u0442\u0430\u043a\u0438\u0445 \u0447\u0442\u043e \u0441\u0443\u043c\u043c\u0430 \u0440\u0435\u043b\u0435\u0432\u0430\u043d\u0442\u043d\u043e\u0441\u0442\u0435\u0439 \u043c\u0430\u043a\u0441\u0438\u043c\u0430\u043b\u044c\u043d\u0430 \u0438 \u0432\u044b\u043f\u043e\u043b\u043d\u0435\u043d\u043e k \u0442\u0440\u0435\u0431\u043e\u0432\u0430\u043d\u0438\u0439 \u0432\u0438\u0434\u0430 \u00ab\u0441\u0440\u0435\u0434\u0438 \u0432\u044b\u0431\u0440\u0430\u043d\u043d\u044b\u0445 m \u043f\u0443\u0431\u043b\u0438\u043a\u0430\u0446\u0438\u0439 \u0434\u043e\u043b\u0436\u043d\u043e \u0431\u044b\u0442\u044c \u2265 A<sub>i<\/sub> \u043a\u0430\u0440\u0442\u043e\u0447\u0435\u043a \u0441 i-\u044b\u043c \u0444\u043b\u0430\u0436\u043a\u043e\u043c\u00bb, \u043b\u0438\u0431\u043e \u043e\u043f\u0440\u0435\u0434\u0435\u043b\u0438\u0442\u044c, \u0447\u0442\u043e \u0442\u0430\u043a\u043e\u0433\u043e \u043d\u0430\u0431\u043e\u0440\u0430 \u043f\u0443\u0431\u043b\u0438\u043a\u0430\u0446\u0438\u0439 \u043d\u0435 \u0441\u0443\u0449\u0435\u0441\u0442\u0432\u0443\u0435\u0442.<\/p>\n<p>  <b>\u0420\u0435\u0448\u0435\u043d\u0438\u0435 \u043d\u0430 10 \u0431\u0430\u043b\u043b\u043e\u0432<\/b>: \u0435\u0441\u043b\u0438 \u0435\u0441\u0442\u044c \u0440\u043e\u0432\u043d\u043e \u043e\u0434\u0438\u043d \u0444\u043b\u0430\u0436\u043e\u043a, \u0434\u043e\u0441\u0442\u0430\u0442\u043e\u0447\u043d\u043e \u0432\u0437\u044f\u0442\u044c A<sub>1<\/sub> \u043f\u0443\u0431\u043b\u0438\u043a\u0430\u0446\u0438\u0439 \u0441 \u044d\u0442\u0438\u043c \u0444\u043b\u0430\u0436\u043a\u043e\u043c, \u0438\u043c\u0435\u044e\u0449\u0438\u0445 \u043d\u0430\u0438\u0431\u043e\u043b\u044c\u0448\u0443\u044e \u0440\u0435\u043b\u0435\u0432\u0430\u043d\u0442\u043d\u043e\u0441\u0442\u044c (\u0435\u0441\u043b\u0438 \u0442\u0430\u043a\u0438\u0445 \u043a\u0430\u0440\u0442\u043e\u0447\u0435\u043a \u043c\u0435\u043d\u044c\u0448\u0435, \u0447\u0435\u043c A<sub>1<\/sub>, \u0442\u043e \u0438\u0441\u043a\u043e\u043c\u043e\u0433\u043e \u043d\u0430\u0431\u043e\u0440\u0430 \u043d\u0435 \u0441\u0443\u0449\u0435\u0441\u0442\u0432\u0443\u0435\u0442), \u0430 \u043e\u0441\u0442\u0430\u043b\u044c\u043d\u044b\u0435 (m \u2013 A<sub>1<\/sub>) \u0434\u043e\u0431\u0440\u0430\u0442\u044c \u043e\u0441\u0442\u0430\u0432\u0448\u0438\u043c\u0438\u0441\u044f \u043a\u0430\u0440\u0442\u043e\u0447\u043a\u0430\u043c\u0438 \u0441 \u043d\u0430\u0438\u043b\u0443\u0447\u0448\u0435\u0439 \u0440\u0435\u043b\u0435\u0432\u0430\u043d\u0442\u043d\u043e\u0441\u0442\u044c\u044e.<\/p>\n<p>  <b>\u0420\u0435\u0448\u0435\u043d\u0438\u0435 \u043d\u0430 30 \u0431\u0430\u043b\u043b\u043e\u0432<\/b>: \u0435\u0441\u043b\u0438 m \u043d\u0435 \u043f\u0440\u0435\u0432\u043e\u0441\u0445\u043e\u0434\u0438\u0442 3, \u0442\u043e \u043c\u043e\u0436\u043d\u043e \u043d\u0430\u0439\u0442\u0438 \u043e\u0442\u0432\u0435\u0442 \u043f\u043e\u043b\u043d\u044b\u043c \u043f\u0435\u0440\u0435\u0431\u043e\u0440\u043e\u043c \u0432\u0441\u0435\u0432\u043e\u0437\u043c\u043e\u0436\u043d\u044b\u0445 O(n<sup>3<\/sup>) \u0442\u0440\u043e\u0435\u043a \u043a\u0430\u0440\u0442\u043e\u0447\u0435\u043a, \u0432\u044b\u0431\u0440\u0430\u0442\u044c \u043d\u0430\u0438\u043b\u0443\u0447\u0448\u0438\u0439 \u043f\u043e \u0441\u0443\u043c\u043c\u0430\u0440\u043d\u043e\u0439 \u0440\u0435\u043b\u0435\u0432\u0430\u043d\u0442\u043d\u043e\u0441\u0442\u0438 \u0432\u0430\u0440\u0438\u0430\u043d\u0442, \u0443\u0434\u043e\u0432\u043b\u0435\u0442\u0432\u043e\u0440\u044f\u044e\u0449\u0438\u0439 \u043e\u0433\u0440\u0430\u043d\u0438\u0447\u0435\u043d\u0438\u044f\u043c.<\/p>\n<p>  <b>\u0420\u0435\u0448\u0435\u043d\u0438\u0435 \u043d\u0430 70 \u0431\u0430\u043b\u043b\u043e\u0432<\/b> (\u043d\u0430 50 \u0431\u0430\u043b\u043b\u043e\u0432 \u0432\u0441\u0451 \u0442\u043e \u0436\u0435 \u0441\u0430\u043c\u043e\u0435, \u0442\u043e\u043b\u044c\u043a\u043e \u043f\u0440\u043e\u0449\u0435 \u0440\u0435\u0430\u043b\u0438\u0437\u043e\u0432\u0430\u0442\u044c): \u0435\u0441\u043b\u0438 \u0435\u0441\u0442\u044c \u043d\u0435 \u0431\u043e\u043b\u0435\u0435 3 \u0444\u043b\u0430\u0436\u043a\u043e\u0432, \u0442\u043e \u043c\u043e\u0436\u043d\u043e \u0440\u0430\u0437\u0431\u0438\u0442\u044c \u0432\u0441\u0435 \u043f\u0443\u0431\u043b\u0438\u043a\u0430\u0446\u0438\u0438 \u043d\u0430 8 \u043d\u0435\u043f\u0435\u0440\u0435\u0441\u0435\u043a\u0430\u044e\u0449\u0438\u0445\u0441\u044f \u0433\u0440\u0443\u043f\u043f \u043f\u043e \u043d\u0430\u0431\u043e\u0440\u0443 \u0444\u043b\u0430\u0436\u043a\u043e\u0432, \u043a\u043e\u0442\u043e\u0440\u044b\u043c\u0438 \u043e\u043d\u0438 \u043e\u0431\u043b\u0430\u0434\u0430\u044e\u0442: 000, 001, 010, 011, 100, 101, 110, 111. \u041f\u0443\u0431\u043b\u0438\u043a\u0430\u0446\u0438\u0438 \u0432 \u043a\u0430\u0436\u0434\u043e\u0439 \u0433\u0440\u0443\u043f\u043f\u0435 \u043d\u0443\u0436\u043d\u043e \u043e\u0442\u0441\u043e\u0440\u0442\u0438\u0440\u043e\u0432\u0430\u0442\u044c \u043f\u043e \u0443\u0431\u044b\u0432\u0430\u043d\u0438\u044e \u0440\u0435\u043b\u0435\u0432\u0430\u043d\u0442\u043d\u043e\u0441\u0442\u0438. \u0414\u0430\u043b\u0435\u0435 \u043c\u043e\u0436\u043d\u043e \u0437\u0430 O(m<sup>4<\/sup>) \u043f\u0435\u0440\u0435\u0431\u0440\u0430\u0442\u044c, \u0441\u043a\u043e\u043b\u044c\u043a\u043e \u043b\u0443\u0447\u0448\u0438\u0445 \u043f\u0443\u0431\u043b\u0438\u043a\u0430\u0446\u0438\u0439 \u043c\u044b \u0431\u0435\u0440\u0451\u043c \u0438\u0437 \u0433\u0440\u0443\u043f\u043f 111, 011, 110 \u0438 101. \u0418\u0437 \u043a\u0430\u0436\u0434\u043e\u0439 \u0431\u0435\u0440\u0451\u043c \u043e\u0442 0 \u0434\u043e m \u043f\u0443\u0431\u043b\u0438\u043a\u0430\u0446\u0438\u0439, \u0432 \u0441\u0443\u043c\u043c\u0435 \u043d\u0435 \u0431\u043e\u043b\u0435\u0435 m. \u041f\u043e\u0441\u043b\u0435 \u044d\u0442\u043e\u0433\u043e \u0441\u0442\u0430\u043d\u043e\u0432\u0438\u0442\u0441\u044f \u044f\u0441\u043d\u043e, \u0441\u043a\u043e\u043b\u044c\u043a\u043e \u043f\u0443\u0431\u043b\u0438\u043a\u0430\u0446\u0438\u0439 \u043d\u0435\u043e\u0431\u0445\u043e\u0434\u0438\u043c\u043e \u0434\u043e\u0431\u0440\u0430\u0442\u044c \u0438\u0437 \u0433\u0440\u0443\u043f\u043f 100, 010 \u0438 001, \u0447\u0442\u043e\u0431\u044b \u0442\u0440\u0435\u0431\u043e\u0432\u0430\u043d\u0438\u044f \u0443\u0434\u043e\u0432\u043b\u0435\u0442\u0432\u043e\u0440\u044f\u043b\u0438\u0441\u044c. \u041e\u0441\u0442\u0430\u0451\u0442\u0441\u044f \u0434\u043e\u0431\u0440\u0430\u0442\u044c \u0434\u043e m \u043e\u0441\u0442\u0430\u0432\u0448\u0438\u043c\u0438\u0441\u044f \u043a\u0430\u0440\u0442\u043e\u0447\u043a\u0430\u043c\u0438 \u0441 \u043d\u0430\u0438\u043b\u0443\u0447\u0448\u0435\u0439 \u0440\u0435\u043b\u0435\u0432\u0430\u043d\u0442\u043d\u043e\u0441\u0442\u044c\u044e.<\/p>\n<p>  <b>\u041f\u043e\u043b\u043d\u043e\u0435 \u0440\u0435\u0448\u0435\u043d\u0438\u0435<\/b>: \u0440\u0430\u0441\u0441\u043c\u043e\u0442\u0440\u0438\u043c \u0444\u0443\u043d\u043a\u0446\u0438\u044e \u0434\u0438\u043d\u0430\u043c\u0438\u0447\u0435\u0441\u043a\u043e\u0433\u043e \u043f\u0440\u043e\u0433\u0440\u0430\u043c\u043c\u0438\u0440\u043e\u0432\u0430\u043d\u0438\u044f dp[i][a]&#8230;[z]. \u042d\u0442\u043e \u043c\u0430\u043a\u0441\u0438\u043c\u0430\u043b\u044c\u043d\u0430\u044f \u0441\u0443\u043c\u043c\u0430\u0440\u043d\u0430\u044f \u043e\u0446\u0435\u043d\u043a\u0430 \u0440\u0435\u043b\u0435\u0432\u0430\u043d\u0442\u043d\u043e\u0441\u0442\u0438, \u043a\u043e\u0442\u043e\u0440\u0443\u044e \u043c\u043e\u0436\u043d\u043e \u043f\u043e\u043b\u0443\u0447\u0438\u0442\u044c, \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u0432 \u0440\u043e\u0432\u043d\u043e i \u043f\u0443\u0431\u043b\u0438\u043a\u0430\u0446\u0438\u0439, \u0447\u0442\u043e\u0431\u044b \u0431\u044b\u043b\u043e \u0440\u043e\u0432\u043d\u043e a \u043f\u0443\u0431\u043b\u0438\u043a\u0430\u0446\u0438\u0439 \u0441 \u0444\u043b\u0430\u0436\u043a\u043e\u043c A, &#8230;, z \u043f\u0443\u0431\u043b\u0438\u043a\u0430\u0446\u0438\u0439 \u0441 \u0444\u043b\u0430\u0436\u043a\u043e\u043c Z. \u0422\u043e\u0433\u0434\u0430 \u0438\u0441\u0445\u043e\u0434\u043d\u043e dp[0][0]&#8230;[0] = 0, \u0430 \u0434\u043b\u044f \u0432\u0441\u0435\u0445 \u043e\u0441\u0442\u0430\u043b\u044c\u043d\u044b\u0445 \u043d\u0430\u0431\u043e\u0440\u043e\u0432 \u043f\u0430\u0440\u0430\u043c\u0435\u0442\u0440\u043e\u0432 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0435 \u043f\u043e\u043b\u043e\u0436\u0438\u043c \u0440\u0430\u0432\u043d\u044b\u043c -1, \u0447\u0442\u043e\u0431\u044b \u0432 \u0434\u0430\u043b\u044c\u043d\u0435\u0439\u0448\u0435\u043c \u043c\u0430\u043a\u0441\u0438\u043c\u0438\u0437\u0438\u0440\u043e\u0432\u0430\u0442\u044c \u044d\u0442\u043e \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0435. \u0414\u0430\u043b\u0435\u0435 \u0431\u0443\u0434\u0435\u043c \u00ab\u0432\u0432\u043e\u0434\u0438\u0442\u044c \u0432 \u0438\u0433\u0440\u0443\u00bb \u043a\u0430\u0440\u0442\u043e\u0447\u043a\u0438 \u043f\u043e \u043e\u0434\u043d\u043e\u0439 \u0438 \u0441 \u043f\u043e\u043c\u043e\u0449\u044c\u044e \u043a\u0430\u0436\u0434\u043e\u0439 \u043a\u0430\u0440\u0442\u043e\u0447\u043a\u0438 \u0443\u043b\u0443\u0447\u0448\u0430\u0442\u044c \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u044f \u044d\u0442\u043e\u0439 \u0444\u0443\u043d\u043a\u0446\u0438\u0438: \u0434\u043b\u044f \u043a\u0430\u0436\u0434\u043e\u0433\u043e \u0441\u043e\u0441\u0442\u043e\u044f\u043d\u0438\u044f \u0434\u0438\u043d\u0430\u043c\u0438\u043a\u0438 (i, a, b, &#8230;, z) \u0441 \u043f\u043e\u043c\u043e\u0449\u044c\u044e j-\u0439 \u043f\u0443\u0431\u043b\u0438\u043a\u0430\u0446\u0438\u0438 \u0441 \u0444\u043b\u0430\u0436\u043a\u0430\u043c\u0438 (a<sub>j<\/sub>, b<sub>j<\/sub>, &#8230;, z<sub>j<\/sub>) \u043c\u043e\u0436\u043d\u043e \u043f\u043e\u043f\u0440\u043e\u0431\u043e\u0432\u0430\u0442\u044c \u0441\u043e\u0432\u0435\u0440\u0448\u0438\u0442\u044c \u043f\u0435\u0440\u0435\u0445\u043e\u0434 \u0432 \u0441\u043e\u0441\u0442\u043e\u044f\u043d\u0438\u0435 (i + 1, a + a<sub>j<\/sub>, b + b<sub>j<\/sub>, &#8230;, z + z<sub>j<\/sub>) \u0438 \u043f\u0440\u043e\u0432\u0435\u0440\u0438\u0442\u044c, \u043d\u0435 \u0443\u043b\u0443\u0447\u0448\u0438\u0442\u0441\u044f \u043b\u0438 \u0440\u0435\u0437\u0443\u043b\u044c\u0442\u0430\u0442 \u0432 \u044d\u0442\u043e\u043c \u0441\u043e\u0441\u0442\u043e\u044f\u043d\u0438\u0438. \u0412\u0430\u0436\u043d\u043e: \u043f\u0440\u0438 \u043f\u0435\u0440\u0435\u0445\u043e\u0434\u0435 \u043d\u0430\u0441 \u043d\u0435 \u0438\u043d\u0442\u0435\u0440\u0435\u0441\u0443\u044e\u0442 \u0441\u043e\u0441\u0442\u043e\u044f\u043d\u0438\u044f, \u0433\u0434\u0435 i \u2265 m, \u043f\u043e\u044d\u0442\u043e\u043c\u0443 \u0432\u0441\u0435\u0433\u043e \u0441\u043e\u0441\u0442\u043e\u044f\u043d\u0438\u0439 \u0443 \u0442\u0430\u043a\u043e\u0439 \u0434\u0438\u043d\u0430\u043c\u0438\u043a\u0438 \u043d\u0435 \u0431\u043e\u043b\u0435\u0435 m<sup>k + 1<\/sup>, \u0438 \u0438\u0442\u043e\u0433\u043e\u0432\u0430\u044f \u0430\u0441\u0438\u043c\u043f\u0442\u043e\u0442\u0438\u043a\u0430 \u2014 O(nm<sup>k + 1<\/sup>). \u041a\u043e\u0433\u0434\u0430 \u043f\u043e\u0441\u0447\u0438\u0442\u0430\u043d\u044b \u0441\u043e\u0441\u0442\u043e\u044f\u043d\u0438\u044f \u0434\u0438\u043d\u0430\u043c\u0438\u043a\u0438, \u043e\u0442\u0432\u0435\u0442\u043e\u043c \u044f\u0432\u043b\u044f\u0435\u0442\u0441\u044f \u0441\u043e\u0441\u0442\u043e\u044f\u043d\u0438\u0435, \u043a\u043e\u0442\u043e\u0440\u043e\u0435 \u0443\u0434\u043e\u0432\u043b\u0435\u0442\u0432\u043e\u0440\u044f\u0435\u0442 \u043e\u0433\u0440\u0430\u043d\u0438\u0447\u0435\u043d\u0438\u044f\u043c \u0438 \u0434\u0430\u0451\u0442 \u043d\u0430\u0438\u0431\u043e\u043b\u044c\u0448\u0443\u044e \u0441\u0443\u043c\u043c\u0430\u0440\u043d\u0443\u044e \u043e\u0446\u0435\u043d\u043a\u0443 \u0440\u0435\u043b\u0435\u0432\u0430\u043d\u0442\u043d\u043e\u0441\u0442\u0438.<\/p>\n<p>  \u0421 \u0442\u043e\u0447\u043a\u0438 \u0437\u0440\u0435\u043d\u0438\u044f \u0440\u0435\u0430\u043b\u0438\u0437\u0430\u0446\u0438\u0438 \u0434\u043b\u044f \u0443\u0441\u043a\u043e\u0440\u0435\u043d\u0438\u044f \u0440\u0430\u0431\u043e\u0442\u044b \u043f\u0440\u043e\u0433\u0440\u0430\u043c\u043c\u044b \u043f\u043e\u043b\u0435\u0437\u043d\u043e \u0445\u0440\u0430\u043d\u0438\u0442\u044c \u0441\u043e\u0441\u0442\u043e\u044f\u043d\u0438\u0435 \u0434\u0438\u043d\u0430\u043c\u0438\u0447\u0435\u0441\u043a\u043e\u0433\u043e \u043f\u0440\u043e\u0433\u0440\u0430\u043c\u043c\u0438\u0440\u043e\u0432\u0430\u043d\u0438\u044f \u0438 \u0444\u043b\u0430\u0436\u043a\u0438 \u043a\u0430\u0436\u0434\u043e\u0439 \u0438\u0437 \u043f\u0443\u0431\u043b\u0438\u043a\u0430\u0446\u0438\u0439 \u0432 \u0443\u043f\u0430\u043a\u043e\u0432\u0430\u043d\u043d\u043e\u043c \u0432\u0438\u0434\u0435 \u0432 \u043e\u0434\u043d\u043e\u043c \u0446\u0435\u043b\u043e\u043c \u0447\u0438\u0441\u043b\u0435 (\u0441\u043c. \u043a\u043e\u0434), \u0430 \u043d\u0435 \u0432 \u0441\u043f\u0438\u0441\u043a\u0435 \u0438\u043b\u0438 \u043a\u043e\u0440\u0442\u0435\u0436\u0435. \u0422\u0430\u043a\u043e\u0435 \u0440\u0435\u0448\u0435\u043d\u0438\u0435 \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u0435\u0442 \u043c\u0435\u043d\u044c\u0448\u0435 \u043f\u0430\u043c\u044f\u0442\u0438 \u0438 \u043f\u043e\u0437\u0432\u043e\u043b\u044f\u0435\u0442 \u044d\u0444\u0444\u0435\u043a\u0442\u0438\u0432\u043d\u043e \u043f\u0440\u043e\u0438\u0437\u0432\u043e\u0434\u0438\u0442\u044c \u0430\u043f\u0434\u0435\u0439\u0442\u044b \u0441\u043e\u0441\u0442\u043e\u044f\u043d\u0438\u0439 \u0434\u0438\u043d\u0430\u043c\u0438\u043a\u0438.<\/p>\n<p>  \u041a\u043e\u0434 \u043f\u043e\u043b\u043d\u043e\u0433\u043e \u0440\u0435\u0448\u0435\u043d\u0438\u044f:<\/p>\n<pre><code class=\"python\">def pack_state(num_items, counts):     result = 0     for count in counts:         result = (result &lt;&lt; 8) + count     return (result &lt;&lt; 8) + num_items   def get_num_items(state):     return state &amp; 255   def get_flags_counts(state, num_flags):     flags_counts = [0] * num_flags     state &gt;&gt;= 8     for i in range(num_flags):         flags_counts[num_flags - i - 1] = state &amp; 255         state &gt;&gt;= 8     return flags_counts   n, m, k = map(int, input().split()) scores, attributes = [], [] for i in range(n):     score, flags = input().split()     scores.append(int(score))     attributes.append(list(map(int, flags))) limits = list(map(int, input().split()))  dp = {0 : 0} for i in range(n):     score = scores[i]     state_delta = pack_state(1, attributes[i])     dp_temp = {}     for state, value in dp.items():         if get_num_items(state) &gt;= m:             continue         new_state = state + state_delta         if value + score &gt; dp.get(new_state, -1):             dp_temp[new_state] = value + score     dp.update(dp_temp)  best_score = 0 for state, value in dp.items():     if get_num_items(state) != m:         continue      flags_counts = get_flags_counts(state, k)     satisfied_bounds = True     for i in range(k):         if flags_counts[i] &lt; limits[i]:             satisfied_bounds = False             break      if not satisfied_bounds:         continue      if value &gt; best_score:         best_score = value  print(best_score)<\/code><\/pre>\n<p>  <\/p>\n<h2>B2. \u041f\u0440\u0438\u0431\u043b\u0438\u0436\u0435\u043d\u0438\u0435 \u0444\u0443\u043d\u043a\u0446\u0438\u0438<\/h2>\n<p>  <\/p>\n<h4>\u0423\u0441\u043b\u043e\u0432\u0438\u0435<\/h4>\n<div class=\"scrollable-table\">\n<table>\n<tr>\n<td>\u041e\u0433\u0440\u0430\u043d\u0438\u0447\u0435\u043d\u0438\u0435 \u0432\u0440\u0435\u043c\u0435\u043d\u0438<\/td>\n<td>2 \u0441<\/td>\n<\/tr>\n<tr>\n<td>\u041e\u0433\u0440\u0430\u043d\u0438\u0447\u0435\u043d\u0438\u0435 \u043f\u0430\u043c\u044f\u0442\u0438<\/td>\n<td>256 \u041c\u0411<\/td>\n<\/tr>\n<tr>\n<td>\u0412\u0432\u043e\u0434<\/td>\n<td>\u0441\u0442\u0430\u043d\u0434\u0430\u0440\u0442\u043d\u044b\u0439 \u0432\u0432\u043e\u0434 \u0438\u043b\u0438 input.txt<\/td>\n<\/tr>\n<tr>\n<td>\u0412\u044b\u0432\u043e\u0434<\/td>\n<td>\u0441\u0442\u0430\u043d\u0434\u0430\u0440\u0442\u043d\u044b\u0439 \u0432\u044b\u0432\u043e\u0434 \u0438\u043b\u0438 output.txt<\/td>\n<\/tr>\n<\/table>\n<\/div>\n<p>\u0414\u043b\u044f \u043e\u0446\u0435\u043d\u043a\u0438 \u0441\u0442\u0435\u043f\u0435\u043d\u0438 \u0440\u0435\u043b\u0435\u0432\u0430\u043d\u0442\u043d\u043e\u0441\u0442\u0438 \u0434\u043e\u043a\u0443\u043c\u0435\u043d\u0442\u043e\u0432 \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u044e\u0442\u0441\u044f \u0440\u0430\u0437\u043b\u0438\u0447\u043d\u044b\u0435 \u043c\u0435\u0442\u043e\u0434\u044b \u043c\u0430\u0448\u0438\u043d\u043d\u043e\u0433\u043e \u043e\u0431\u0443\u0447\u0435\u043d\u0438\u044f\u00a0\u2014 \u043d\u0430\u043f\u0440\u0438\u043c\u0435\u0440, \u0440\u0435\u0448\u0430\u044e\u0449\u0438\u0435 \u0434\u0435\u0440\u0435\u0432\u044c\u044f. k-\u0438\u0447\u043d\u043e\u0435 \u0440\u0435\u0448\u0430\u044e\u0449\u0435\u0435 \u0434\u0435\u0440\u0435\u0432\u043e \u0438\u043c\u0435\u0435\u0442 \u0432 \u043a\u0430\u0436\u0434\u043e\u043c \u0443\u0437\u043b\u0435 \u0440\u0435\u0448\u0430\u044e\u0449\u0435\u0435 \u043f\u0440\u0430\u0432\u0438\u043b\u043e, \u043a\u043e\u0442\u043e\u0440\u043e\u0435 \u0440\u0430\u0437\u0434\u0435\u043b\u044f\u0435\u0442 \u043e\u0431\u044a\u0435\u043a\u0442\u044b \u043d\u0430 k \u043a\u043b\u0430\u0441\u0441\u043e\u0432 \u043f\u043e \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u044f\u043c \u043d\u0435\u043a\u043e\u0442\u043e\u0440\u043e\u0433\u043e \u043f\u0440\u0438\u0437\u043d\u0430\u043a\u0430. \u041d\u0430 \u043f\u0440\u0430\u043a\u0442\u0438\u043a\u0435 \u043e\u0431\u044b\u0447\u043d\u043e \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u044e\u0442\u0441\u044f \u0434\u0432\u043e\u0438\u0447\u043d\u044b\u0435 \u0440\u0435\u0448\u0430\u044e\u0449\u0438\u0435 \u0434\u0435\u0440\u0435\u0432\u044c\u044f. \u0420\u0430\u0441\u0441\u043c\u043e\u0442\u0440\u0438\u043c \u0443\u043f\u0440\u043e\u0449\u0451\u043d\u043d\u0443\u044e \u0432\u0435\u0440\u0441\u0438\u044e \u0437\u0430\u0434\u0430\u0447\u0438 \u043e\u043f\u0442\u0438\u043c\u0438\u0437\u0430\u0446\u0438\u0438, \u043a\u043e\u0442\u043e\u0440\u0443\u044e \u043d\u0435\u043e\u0431\u0445\u043e\u0434\u0438\u043c\u043e \u0440\u0435\u0448\u0430\u0442\u044c \u0432 \u043a\u0430\u0436\u0434\u043e\u043c \u0443\u0437\u043b\u0435 k-\u0438\u0447\u043d\u043e\u0433\u043e \u0440\u0435\u0448\u0430\u044e\u0449\u0435\u0433\u043e \u0434\u0435\u0440\u0435\u0432\u0430.<\/p>\n<p>  \u041f\u0443\u0441\u0442\u044c \u0434\u0438\u0441\u043a\u0440\u0435\u0442\u043d\u0430\u044f \u0444\u0443\u043d\u043a\u0446\u0438\u044f f \u043e\u043f\u0440\u0435\u0434\u0435\u043b\u0435\u043d\u0430 \u0432 \u0442\u043e\u0447\u043a\u0430\u0445 i = 1, 2, &#8230;, n. \u041d\u0435\u043e\u0431\u0445\u043e\u0434\u0438\u043c\u043e \u043d\u0430\u0439\u0442\u0438 \u043a\u0443\u0441\u043e\u0447\u043d\u043e-\u043f\u043e\u0441\u0442\u043e\u044f\u043d\u043d\u0443\u044e \u0444\u0443\u043d\u043a\u0446\u0438\u044e g, \u0441\u043e\u0441\u0442\u043e\u044f\u0449\u0443\u044e \u043d\u0435 \u0431\u043e\u043b\u0435\u0435 \u0447\u0435\u043c \u0438\u0437 k \u0443\u0447\u0430\u0441\u0442\u043a\u043e\u0432 \u043f\u043e\u0441\u0442\u043e\u044f\u043d\u0441\u0442\u0432\u0430, \u0442\u0430\u043a\u0443\u044e \u0447\u0442\u043e \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0435 SSE\u00a0=\u00a0<math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/e0e\/4ef\/8fd\/e0e4ef8fd6788c4c97136e24de4f5da5.svg\" alt=\"$\\sum_{i=1}^n$\" data-tex=\"inline\"><\/math>(g(i) \u2013 f(i))<sup>2<\/sup> \u043c\u0438\u043d\u0438\u043c\u0430\u043b\u044c\u043d\u043e.<\/p>\n<div class=\"spoiler\"><b class=\"spoiler_title\">\u0424\u043e\u0440\u043c\u0430\u0442\u044b \u0432\u0432\u043e\u0434\u0430\/\u0432\u044b\u0432\u043e\u0434\u0430 \u0438 \u043f\u0440\u0438\u043c\u0435\u0440\u044b<\/b><\/p>\n<div class=\"spoiler_text\">\n<h4>\u0424\u043e\u0440\u043c\u0430\u0442 \u0432\u0432\u043e\u0434\u0430<\/h4>\n<p>  \u0412 \u043f\u0435\u0440\u0432\u043e\u0439 \u0441\u0442\u0440\u043e\u043a\u0435 \u0437\u0430\u0434\u0430\u043d\u044b \u0434\u0432\u0430 \u0446\u0435\u043b\u044b\u0445 \u0447\u0438\u0441\u043b\u0430 n \u0438 k (1 \u2264 n \u2264 300, 1 \u2264 k \u2264 min(n, 10)).<\/p>\n<p>  \u0412\u043e \u0432\u0442\u043e\u0440\u043e\u0439 \u0441\u0442\u0440\u043e\u043a\u0435 \u0437\u0430\u0434\u0430\u043d\u043e n \u0446\u0435\u043b\u044b\u0445 \u0447\u0438\u0441\u0435\u043b f(1), f(2), &#8230;, f(n) \u2014 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u044f \u043f\u0440\u0438\u0431\u043b\u0438\u0436\u0430\u0435\u043c\u043e\u0439 \u0444\u0443\u043d\u043a\u0446\u0438\u0438 \u0432 \u0442\u043e\u0447\u043a\u0430\u0445 1, 2, &#8230;, n (\u201310<sup>6<\/sup> \u2264 f(i) \u2264 10<sup>6<\/sup>).<\/p>\n<h4>\u0424\u043e\u0440\u043c\u0430\u0442 \u0432\u044b\u0432\u043e\u0434\u0430<\/h4>\n<p>  \u0412\u044b\u0432\u0435\u0434\u0438\u0442\u0435 \u0435\u0434\u0438\u043d\u0441\u0442\u0432\u0435\u043d\u043d\u043e\u0435 \u0447\u0438\u0441\u043b\u043e\u00a0\u2014 \u043c\u0438\u043d\u0438\u043c\u0430\u043b\u044c\u043d\u043e\u0435 \u0432\u043e\u0437\u043c\u043e\u0436\u043d\u043e\u0435 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0435 SSE. \u041e\u0442\u0432\u0435\u0442 \u0441\u0447\u0438\u0442\u0430\u0435\u0442\u0441\u044f \u043f\u0440\u0430\u0432\u0438\u043b\u044c\u043d\u044b\u043c, \u0435\u0441\u043b\u0438 \u0430\u0431\u0441\u043e\u043b\u044e\u0442\u043d\u0430\u044f \u0438\u043b\u0438 \u043e\u0442\u043d\u043e\u0441\u0438\u0442\u0435\u043b\u044c\u043d\u0430\u044f \u043f\u043e\u0433\u0440\u0435\u0448\u043d\u043e\u0441\u0442\u044c \u043d\u0435 \u043f\u0440\u0435\u0432\u043e\u0441\u0445\u043e\u0434\u0438\u0442 10<sup>\u20136<\/sup>.<\/p>\n<h4>\u041f\u0440\u0438\u043c\u0435\u0440 1<\/h4>\n<div class=\"scrollable-table\">\n<table>\n<tr>\n<td><b>\u0412\u0432\u043e\u0434<\/b><\/td>\n<td><b>\u0412\u044b\u0432\u043e\u0434<\/b><\/td>\n<\/tr>\n<tr>\n<td><code>3 1<br \/>  1 2 3<\/code><\/td>\n<td><code>2.000000<\/code><\/td>\n<\/tr>\n<\/table>\n<\/div>\n<h4>\u041f\u0440\u0438\u043c\u0435\u0440 2<\/h4>\n<div class=\"scrollable-table\">\n<table>\n<tr>\n<td><b>\u0412\u0432\u043e\u0434<\/b><\/td>\n<td><b>\u0412\u044b\u0432\u043e\u0434<\/b><\/td>\n<\/tr>\n<tr>\n<td><code>3 2<br \/>  1 2 3<\/code><\/td>\n<td><code>0.500000<\/code><\/td>\n<\/tr>\n<\/table>\n<\/div>\n<h4>\u041f\u0440\u0438\u043c\u0435\u0440 3<\/h4>\n<div class=\"scrollable-table\">\n<table>\n<tr>\n<td><b>\u0412\u0432\u043e\u0434<\/b><\/td>\n<td><b>\u0412\u044b\u0432\u043e\u0434<\/b><\/td>\n<\/tr>\n<tr>\n<td><code>5 2<br \/>  2 1 5 3 4<\/code><\/td>\n<td><code>2.500000<\/code><\/td>\n<\/tr>\n<\/table>\n<\/div>\n<h4>\u041f\u0440\u0438\u043c\u0435\u0447\u0430\u043d\u0438\u044f<\/h4>\n<p>  \u0412 \u043f\u0435\u0440\u0432\u043e\u043c \u043f\u0440\u0438\u043c\u0435\u0440\u0435 \u043e\u043f\u0442\u0438\u043c\u0430\u043b\u044c\u043d\u0430\u044f \u0444\u0443\u043d\u043a\u0446\u0438\u044f g \u2014 \u043a\u043e\u043d\u0441\u0442\u0430\u043d\u0442\u0430 g(i) = 2. <br \/>  SSE\u00a0=\u00a0(2\u00a0\u2013\u00a01)<sup>2<\/sup>\u00a0+\u00a0(2\u00a0\u2013\u00a02)<sup>2<\/sup>\u00a0+\u00a0(2\u00a0\u2013\u00a03)<sup>2<\/sup>\u00a0=\u00a02. <\/p>\n<p>  \u0412\u043e \u0432\u0442\u043e\u0440\u043e\u043c \u043f\u0440\u0438\u043c\u0435\u0440\u0435 \u0435\u0441\u0442\u044c 2 \u0432\u0430\u0440\u0438\u0430\u043d\u0442\u0430. \u041b\u0438\u0431\u043e g(1) = 1 \u0438 g(2) = g(3) = 2.5, \u043b\u0438\u0431\u043e g(1) = g(2) = 1.5 \u0438 <br \/>  g(3) = 3. \u0412 \u043b\u044e\u0431\u043e\u043c \u0441\u043b\u0443\u0447\u0430\u0435 SSE = 0.5.<\/p>\n<p>  \u0412 \u0442\u0440\u0435\u0442\u044c\u0435\u043c \u043f\u0440\u0438\u043c\u0435\u0440\u0435 \u043e\u043f\u0442\u0438\u043c\u0430\u043b\u044c\u043d\u043e\u0435 \u043f\u0440\u0438\u0431\u043b\u0438\u0436\u0435\u043d\u0438\u0435 \u0444\u0443\u043d\u043a\u0446\u0438\u0438 f \u0441 \u043f\u043e\u043c\u043e\u0449\u044c\u044e \u0434\u0432\u0443\u0445 \u0443\u0447\u0430\u0441\u0442\u043a\u043e\u0432 \u043f\u043e\u0441\u0442\u043e\u044f\u043d\u0441\u0442\u0432\u0430 \u0438\u0437\u043e\u0431\u0440\u0430\u0436\u0435\u043d\u043e \u043d\u0438\u0436\u0435: g(1) = g(2) = 1.5 \u0438 g(3) = g(4) = g(5) = 4. <br \/>  SSE = (1.5 + 2)<sup>2<\/sup> + (1.5 \u2013 1)<sup>2<\/sup> + (4 \u2013 5)<sup>2<\/sup> + (4 \u2013 3)<sup>2<\/sup> + (4 \u2013 4)<sup>2<\/sup> = 2.5.<\/p>\n<p>  <img decoding=\"async\" src=\"https:\/\/habrastorage.org\/webt\/qo\/kn\/v1\/qoknv1ew42eyvuzbszfckfhybkq.jpeg\"><\/div>\n<\/div>\n<p>  <\/p>\n<h4>\u0421\u0438\u0441\u0442\u0435\u043c\u0430 \u043e\u0446\u0435\u043d\u043a\u0438<\/h4>\n<p>  \u0422\u0435\u0441\u0442\u044b \u043a \u044d\u0442\u043e\u0439 \u0437\u0430\u0434\u0430\u0447\u0435 \u0441\u043e\u0441\u0442\u043e\u044f\u0442 \u0438\u0437 \u043f\u044f\u0442\u0438 \u0433\u0440\u0443\u043f\u043f. \u0411\u0430\u043b\u043b\u044b \u0437\u0430 \u043a\u0430\u0436\u0434\u0443\u044e \u0433\u0440\u0443\u043f\u043f\u0443 \u0441\u0442\u0430\u0432\u044f\u0442\u0441\u044f \u0442\u043e\u043b\u044c\u043a\u043e \u043f\u0440\u0438 \u043f\u0440\u043e\u0445\u043e\u0436\u0434\u0435\u043d\u0438\u0438 \u0432\u0441\u0435\u0445 \u0442\u0435\u0441\u0442\u043e\u0432 \u0433\u0440\u0443\u043f\u043f\u044b \u0438 \u0432\u0441\u0435\u0445 \u0442\u0435\u0441\u0442\u043e\u0432 <b>\u043f\u0440\u0435\u0434\u044b\u0434\u0443\u0449\u0438\u0445<\/b> \u0433\u0440\u0443\u043f\u043f. \u041f\u0440\u043e\u0445\u043e\u0436\u0434\u0435\u043d\u0438\u0435 \u0442\u0435\u0441\u0442\u043e\u0432 \u0438\u0437 \u0443\u0441\u043b\u043e\u0432\u0438\u044f \u043d\u0435\u043e\u0431\u0445\u043e\u0434\u0438\u043c\u043e \u0434\u043b\u044f \u043f\u043e\u043b\u0443\u0447\u0435\u043d\u0438\u044f \u0431\u0430\u043b\u043b\u043e\u0432 \u0437\u0430 \u0433\u0440\u0443\u043f\u043f\u044b \u043d\u0430\u0447\u0438\u043d\u0430\u044f \u0441\u043e \u0432\u0442\u043e\u0440\u043e\u0439. \u0412\u0441\u0435\u0433\u043e \u0437\u0430 \u0437\u0430\u0434\u0430\u0447\u0443 \u043c\u043e\u0436\u043d\u043e \u043f\u043e\u043b\u0443\u0447\u0438\u0442\u044c <b>100 \u0431\u0430\u043b\u043b\u043e\u0432<\/b>.<\/p>\n<p>  \u0412 \u0442\u0435\u0441\u0442\u0438\u0440\u0443\u044e\u0449\u0435\u0439 \u0441\u0438\u0441\u0442\u0435\u043c\u0435 \u0442\u0435\u0441\u0442\u044b 1\u20133 \u2014 \u043f\u0440\u0438\u043c\u0435\u0440\u044b \u0438\u0437 \u0443\u0441\u043b\u043e\u0432\u0438\u044f.<\/p>\n<p>  1. <b>(10 \u0431\u0430\u043b\u043b\u043e\u0432)<\/b> \u0442\u0435\u0441\u0442\u044b 4\u201322: k = 1, \u043d\u0435 \u0442\u0440\u0435\u0431\u0443\u0435\u0442\u0441\u044f \u043f\u0440\u043e\u0445\u043e\u0436\u0434\u0435\u043d\u0438\u0435 \u0442\u0435\u0441\u0442\u043e\u0432 \u0438\u0437 \u0443\u0441\u043b\u043e\u0432\u0438\u044f<br \/>  2. <b>(20 \u0431\u0430\u043b\u043b\u043e\u0432)<\/b> \u0442\u0435\u0441\u0442\u044b 23\u201328: k \u2264 2<br \/>  3. <b>(20 \u0431\u0430\u043b\u043b\u043e\u0432)<\/b> \u0442\u0435\u0441\u0442\u044b 29\u201334: k \u2264 3<br \/>  4. <b>(20 \u0431\u0430\u043b\u043b\u043e\u0432)<\/b> \u0442\u0435\u0441\u0442\u044b 35\u201340: k \u2264 4<br \/>  5. <b>(30 \u0431\u0430\u043b\u043b\u043e\u0432)<\/b> \u0442\u0435\u0441\u0442\u044b 41\u201346: \u043d\u0435\u0442 \u0434\u043e\u043f\u043e\u043b\u043d\u0438\u0442\u0435\u043b\u044c\u043d\u044b\u0445 \u043e\u0433\u0440\u0430\u043d\u0438\u0447\u0435\u043d\u0438\u0439<\/p>\n<h4>\u0420\u0435\u0448\u0435\u043d\u0438\u0435<\/h4>\n<p>  \u041a\u0430\u043a \u0438\u0437\u0432\u0435\u0441\u0442\u043d\u043e, \u043a\u043e\u043d\u0441\u0442\u0430\u043d\u0442\u0430, \u043a\u043e\u0442\u043e\u0440\u0430\u044f \u043c\u0438\u043d\u0438\u043c\u0438\u0437\u0438\u0440\u0443\u0435\u0442 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0435 SSE \u0434\u043b\u044f \u043d\u0430\u0431\u043e\u0440\u0430 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0439 f<sub>1<\/sub>, f<sub>2<\/sub>, &#8230;, f<sub>n<\/sub>, \u2014 \u044d\u0442\u043e \u0441\u0440\u0435\u0434\u043d\u0435\u0435 \u043f\u0435\u0440\u0435\u0447\u0438\u0441\u043b\u0435\u043d\u043d\u044b\u0445 \u0437\u0434\u0435\u0441\u044c \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0439. \u041f\u0440\u0438 \u044d\u0442\u043e\u043c, \u043a\u0430\u043a \u043d\u0435\u0442\u0440\u0443\u0434\u043d\u043e \u0443\u0431\u0435\u0434\u0438\u0442\u044c\u0441\u044f \u043f\u0443\u0442\u0451\u043c \u043f\u0440\u043e\u0441\u0442\u044b\u0445 \u0432\u044b\u043a\u043b\u0430\u0434\u043e\u043a, \u0441\u0430\u043c\u043e \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0435 SSE = <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/042\/e1e\/5fe\/042e1e5fe9980523483be6348048b9cd.svg\" alt=\"$\u0441\u0443\u043c\u043c\u0430\\ \u043a\u0432\u0430\u0434\u0440\u0430\u0442\u043e\u0432\\ \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0439\\ \u2013 \\frac{\u043a\u0432\u0430\u0434\u0440\u0430\u0442\\ \u0441\u0443\u043c\u043c\u044b\\ \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0439}{n}$\" data-tex=\"inline\"><\/math>.<\/p>\n<p>  <b>\u0420\u0435\u0448\u0435\u043d\u0438\u0435 \u043d\u0430 10 \u0431\u0430\u043b\u043b\u043e\u0432<\/b>: \u043f\u0440\u043e\u0441\u0442\u043e \u0441\u0447\u0438\u0442\u0430\u0435\u043c \u0441\u0440\u0435\u0434\u043d\u0435\u0435 \u0432\u0441\u0435\u0445 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0439 \u0444\u0443\u043d\u043a\u0446\u0438\u0438 \u0438 SSE \u0437\u0430 O(n).<\/p>\n<p>  <b>\u0420\u0435\u0448\u0435\u043d\u0438\u0435 \u043d\u0430 30 \u0431\u0430\u043b\u043b\u043e\u0432<\/b>: \u043f\u0435\u0440\u0435\u0431\u0438\u0440\u0430\u0435\u043c \u043f\u043e\u0441\u043b\u0435\u0434\u043d\u044e\u044e \u0442\u043e\u0447\u043a\u0443, \u043e\u0442\u043d\u043e\u0441\u044f\u0449\u0443\u044e\u0441\u044f \u043a \u043f\u0435\u0440\u0432\u043e\u043c\u0443 \u0443\u0447\u0430\u0441\u0442\u043a\u0443 \u043f\u043e\u0441\u0442\u043e\u044f\u043d\u0441\u0442\u0432\u0430 \u0438\u0437 \u0434\u0432\u0443\u0445, \u0434\u043b\u044f \u0444\u0438\u043a\u0441\u0438\u0440\u043e\u0432\u0430\u043d\u043d\u043e\u0433\u043e \u0440\u0430\u0437\u0431\u0438\u0435\u043d\u0438\u044f \u0432\u044b\u0447\u0438\u0441\u043b\u044f\u0435\u043c SSE \u0438 \u0432\u044b\u0431\u0438\u0440\u0430\u0435\u043c \u043e\u043f\u0442\u0438\u043c\u0430\u043b\u044c\u043d\u043e\u0435. \u041a\u0440\u043e\u043c\u0435 \u0442\u043e\u0433\u043e, \u0432\u0430\u0436\u043d\u043e \u043d\u0435 \u0437\u0430\u0431\u044b\u0442\u044c \u0440\u0430\u0437\u043e\u0431\u0440\u0430\u0442\u044c \u043a\u0435\u0439\u0441, \u043a\u043e\u0433\u0434\u0430 \u0443\u0447\u0430\u0441\u0442\u043e\u043a \u043f\u043e\u0441\u0442\u043e\u044f\u043d\u0441\u0442\u0432\u0430 \u0442\u043e\u043b\u044c\u043a\u043e \u043e\u0434\u0438\u043d. \u0421\u043b\u043e\u0436\u043d\u043e\u0441\u0442\u044c \u2014 O(n<sup>2<\/sup>).<\/p>\n<p>  <b>\u0420\u0435\u0448\u0435\u043d\u0438\u0435 \u043d\u0430 50 \u0431\u0430\u043b\u043b\u043e\u0432<\/b>: \u043f\u0435\u0440\u0435\u0431\u0438\u0440\u0430\u0435\u043c \u0433\u0440\u0430\u043d\u0438\u0446\u044b \u0440\u0430\u0437\u0431\u0438\u0435\u043d\u0438\u044f \u043d\u0430 \u0443\u0447\u0430\u0441\u0442\u043a\u0438 \u043f\u043e\u0441\u0442\u043e\u044f\u043d\u0441\u0442\u0432\u0430 \u0437\u0430 O(n<sup>2<\/sup>), \u0434\u043b\u044f \u0444\u0438\u043a\u0441\u0438\u0440\u043e\u0432\u0430\u043d\u043d\u043e\u0433\u043e \u0440\u0430\u0437\u0431\u0438\u0435\u043d\u0438\u044f \u043d\u0430 3 \u043e\u0442\u0440\u0435\u0437\u043a\u0430 \u0432\u044b\u0447\u0438\u0441\u043b\u044f\u0435\u043c SSE \u0438 \u0432\u044b\u0431\u0438\u0440\u0430\u0435\u043c \u043e\u043f\u0442\u0438\u043c\u0430\u043b\u044c\u043d\u043e\u0435. \u0421\u043b\u043e\u0436\u043d\u043e\u0441\u0442\u044c \u2014 O(n<sup>3<\/sup>).<\/p>\n<p>  <b>\u0420\u0435\u0448\u0435\u043d\u0438\u0435 \u043d\u0430 70 \u0431\u0430\u043b\u043b\u043e\u0432<\/b>: \u043f\u0440\u0435\u0434\u043f\u043e\u0434\u0441\u0447\u0438\u0442\u044b\u0432\u0430\u0435\u043c \u0441\u0443\u043c\u043c\u044b \u0438 \u0441\u0443\u043c\u043c\u044b \u043a\u0432\u0430\u0434\u0440\u0430\u0442\u043e\u0432 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0439 f<sub>i<\/sub> \u043d\u0430 \u043f\u0440\u0435\u0444\u0438\u043a\u0441\u0430\u0445, \u044d\u0442\u043e \u043f\u043e\u0437\u0432\u043e\u043b\u0438\u0442 \u0431\u044b\u0441\u0442\u0440\u043e \u0441\u0447\u0438\u0442\u0430\u0442\u044c \u0441\u0440\u0435\u0434\u043d\u0435\u0435 \u0438 SSE \u043d\u0430 \u043b\u044e\u0431\u043e\u043c \u043e\u0442\u0440\u0435\u0437\u043a\u0435. \u041f\u0435\u0440\u0435\u0431\u0438\u0440\u0430\u0435\u043c \u0433\u0440\u0430\u043d\u0438\u0446\u044b \u0440\u0430\u0437\u0431\u0438\u0435\u043d\u0438\u044f \u043d\u0430 4 \u0443\u0447\u0430\u0441\u0442\u043a\u0430 \u043f\u043e\u0441\u0442\u043e\u044f\u043d\u0441\u0442\u0432\u0430 \u0437\u0430 O(n<sup>3<\/sup>), \u0441 \u043f\u043e\u043c\u043e\u0449\u044c\u044e \u043f\u0440\u0435\u0434\u043f\u043e\u0434\u0441\u0447\u0438\u0442\u0430\u043d\u043d\u044b\u0445 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0439 \u043d\u0430 \u043f\u0440\u0435\u0444\u0438\u043a\u0441\u0430\u0445 \u0437\u0430 O(1) \u0432\u044b\u0447\u0438\u0441\u043b\u044f\u0435\u043c SSE. \u0421\u043b\u043e\u0436\u043d\u043e\u0441\u0442\u044c \u2014 O(n<sup>3<\/sup>).<\/p>\n<p>  <b>\u041f\u043e\u043b\u043d\u043e\u0435 \u0440\u0435\u0448\u0435\u043d\u0438\u0435<\/b>: \u0440\u0430\u0441\u0441\u043c\u043e\u0442\u0440\u0438\u043c \u0444\u0443\u043d\u043a\u0446\u0438\u044e \u0434\u0438\u043d\u0430\u043c\u0438\u0447\u0435\u0441\u043a\u043e\u0433\u043e \u043f\u0440\u043e\u0433\u0440\u0430\u043c\u043c\u0438\u0440\u043e\u0432\u0430\u043d\u0438\u044f dp[s][i]. \u042d\u0442\u043e \u043d\u0430\u0438\u043c\u0435\u043d\u044c\u0448\u0435\u0435 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0435 SSE, \u0435\u0441\u043b\u0438 \u043f\u0440\u0438\u0431\u043b\u0438\u0436\u0430\u0442\u044c \u043f\u0435\u0440\u0432\u044b\u0435 i \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0439 \u0441 \u043f\u043e\u043c\u043e\u0449\u044c\u044e s \u043e\u0442\u0440\u0435\u0437\u043a\u043e\u0432. \u0422\u043e\u0433\u0434\u0430 <br \/>  dp[0][0] = 0, \u0430 \u0434\u043b\u044f \u0432\u0441\u0435\u0445 \u043e\u0441\u0442\u0430\u043b\u044c\u043d\u044b\u0445 \u043d\u0430\u0431\u043e\u0440\u043e\u0432 \u043f\u0430\u0440\u0430\u043c\u0435\u0442\u0440\u043e\u0432 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0435 \u043f\u043e\u043b\u043e\u0436\u0438\u043c \u0440\u0430\u0432\u043d\u044b\u043c \u0431\u0435\u0441\u043a\u043e\u043d\u0435\u0447\u043d\u043e\u0441\u0442\u0438, \u0447\u0442\u043e\u0431\u044b \u0432 \u0434\u0430\u043b\u044c\u043d\u0435\u0439\u0448\u0435\u043c \u043c\u0438\u043d\u0438\u043c\u0438\u0437\u0438\u0440\u043e\u0432\u0430\u0442\u044c \u044d\u0442\u043e \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0435. \u0411\u0443\u0434\u0435\u043c \u0440\u0435\u0448\u0430\u0442\u044c \u0437\u0430\u0434\u0430\u0447\u0443, \u043f\u043e\u0441\u0442\u0435\u043f\u0435\u043d\u043d\u043e \u0443\u0432\u0435\u043b\u0438\u0447\u0438\u0432\u0430\u044f \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0435 s. \u041a\u0430\u043a \u0432\u044b\u0447\u0438\u0441\u043b\u0438\u0442\u044c dp[s][i], \u0435\u0441\u043b\u0438 \u0443\u0436\u0435 \u043f\u043e\u0441\u0447\u0438\u0442\u0430\u043d\u044b \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u044f \u0434\u0438\u043d\u0430\u043c\u0438\u043a\u0438 \u0434\u043b\u044f \u0432\u0441\u0435\u0445 \u043c\u0435\u043d\u044c\u0448\u0438\u0445 s? \u0414\u043e\u0441\u0442\u0430\u0442\u043e\u0447\u043d\u043e \u043e\u0431\u043e\u0437\u043d\u0430\u0447\u0438\u0442\u044c \u0437\u0430 t \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e \u043f\u0435\u0440\u0432\u044b\u0445 \u0442\u043e\u0447\u0435\u043a, \u043f\u043e\u043a\u0440\u044b\u0442\u044b\u0445 \u043f\u0440\u0435\u0434\u044b\u0434\u0443\u0449\u0438\u043c\u0438 (s \u2013 1) \u043e\u0442\u0440\u0435\u0437\u043a\u0430\u043c\u0438, \u0438 \u043f\u0435\u0440\u0435\u0431\u0440\u0430\u0442\u044c \u0432\u0441\u0435 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u044f t, \u0430 \u043e\u0441\u0442\u0430\u043b\u044c\u043d\u044b\u0435 (i \u2013 t) \u0442\u043e\u0447\u0435\u043a \u043f\u0440\u0438\u0431\u043b\u0438\u0437\u0438\u0442\u044c \u0441 \u043f\u043e\u043c\u043e\u0449\u044c\u044e \u043e\u0441\u0442\u0430\u0432\u0448\u0435\u0433\u043e\u0441\u044f \u043e\u0442\u0440\u0435\u0437\u043a\u0430. \u041d\u0443\u0436\u043d\u043e \u0432\u044b\u0431\u0440\u0430\u0442\u044c \u043d\u0430\u0438\u043b\u0443\u0447\u0448\u0435\u0435 \u043f\u043e \u0438\u0442\u043e\u0433\u043e\u0432\u043e\u043c\u0443 SSE \u043d\u0430 i \u0442\u043e\u0447\u043a\u0430\u0445 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0435 t. \u0415\u0441\u043b\u0438 \u043f\u0440\u0435\u0434\u043f\u043e\u0434\u0441\u0447\u0438\u0442\u0430\u0442\u044c \u0441\u0443\u043c\u043c\u044b \u0438 \u0441\u0443\u043c\u043c\u044b \u043a\u0432\u0430\u0434\u0440\u0430\u0442\u043e\u0432 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0439 f<sub>i<\/sub> \u043d\u0430 \u043f\u0440\u0435\u0444\u0438\u043a\u0441\u0430\u0445, \u0442\u043e \u044d\u0442\u043e \u043f\u0440\u0438\u0431\u043b\u0438\u0436\u0435\u043d\u0438\u0435 \u0431\u0443\u0434\u0435\u0442 \u043f\u0440\u043e\u0438\u0437\u0432\u043e\u0434\u0438\u0442\u044c\u0441\u044f \u0437\u0430 O(1), \u0438 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0435 dp[s][i] \u0443\u0434\u0430\u0441\u0442\u0441\u044f \u0432\u044b\u0447\u0438\u0441\u043b\u0438\u0442\u044c \u0437\u0430 O(n). \u0418\u0442\u043e\u0433\u043e\u0432\u044b\u043c \u043e\u0442\u0432\u0435\u0442\u043e\u043c \u0431\u0443\u0434\u0435\u0442 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0435 dp[k][n]. \u0418\u0442\u043e\u0433\u043e\u0432\u0430\u044f \u0441\u043b\u043e\u0436\u043d\u043e\u0441\u0442\u044c \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0430 \u2014 O(kn<sup>2<\/sup>).<\/p>\n<p>  \u041a\u043e\u0434 \u043f\u043e\u043b\u043d\u043e\u0433\u043e \u0440\u0435\u0448\u0435\u043d\u0438\u044f:<\/p>\n<pre><code class=\"python\">n, k = map(int, input().split()) f = list(map(float, input().split()))  prefix_sum = [0.0] * (n + 1) prefix_sum_sqr = [0.0] * (n + 1) for i in range(1, n + 1):     prefix_sum[i] = prefix_sum[i - 1] + f[i - 1]     prefix_sum_sqr[i] = prefix_sum_sqr[i - 1] + f[i - 1] ** 2  def get_best_sse(l, r):     num = r - l + 1     s_sqr = (prefix_sum[r] - prefix_sum[l - 1]) ** 2     ss = prefix_sum_sqr[r] - prefix_sum_sqr[l - 1]     return ss - s_sqr \/ num  dp_curr = [1e100] * (n + 1) dp_prev = [1e100] * (n + 1) dp_prev[0] = 0.0 for num_segments in range(1, k + 1):     dp_curr[num_segments] = 0.0     for num_covered in range(num_segments + 1, n + 1):         dp_curr[num_covered] = 1e100         for num_covered_previously in range(num_segments - 1, num_covered):             dp_curr[num_covered] = min(dp_curr[num_covered], dp_prev[num_covered_previously] + get_best_sse(num_covered_previously + 1, num_covered))     dp_curr, dp_prev = dp_prev, dp_curr  print(dp_prev[n])<\/code><\/pre>\n<p>  <\/p>\n<h2>C. \u041f\u0440\u0435\u0434\u0441\u043a\u0430\u0437\u0430\u043d\u0438\u0435 \u043a\u043b\u0438\u043a\u043e\u0432 \u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u0442\u0435\u043b\u044f<\/h2>\n<p>  <\/p>\n<h4>\u0423\u0441\u043b\u043e\u0432\u0438\u0435<\/h4>\n<p>  \u041e\u0434\u043d\u0438\u043c \u0438\u0437 \u0432\u0430\u0436\u043d\u0435\u0439\u0448\u0438\u0445 \u0441\u0438\u0433\u043d\u0430\u043b\u043e\u0432 \u0434\u043b\u044f \u0440\u0435\u043a\u043e\u043c\u0435\u043d\u0434\u0430\u0442\u0435\u043b\u044c\u043d\u043e\u0439 \u0441\u0438\u0441\u0442\u0435\u043c\u044b \u044f\u0432\u043b\u044f\u0435\u0442\u0441\u044f \u043f\u043e\u0432\u0435\u0434\u0435\u043d\u0438\u0435 \u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u0442\u0435\u043b\u044f. \u0422\u0430\u043a\u0438\u0445 \u0434\u0430\u043d\u043d\u044b\u0445 \u0437\u0430\u0447\u0430\u0441\u0442\u0443\u044e \u0434\u043e\u0441\u0442\u0430\u0442\u043e\u0447\u043d\u043e, \u0447\u0442\u043e\u0431\u044b \u043f\u043e\u0441\u0442\u0440\u043e\u0438\u0442\u044c \u0431\u0435\u0439\u0437\u043b\u0430\u0439\u043d \u043f\u0440\u0438\u0435\u043c\u043b\u0435\u043c\u043e\u0433\u043e \u043a\u0430\u0447\u0435\u0441\u0442\u0432\u0430.<\/p>\n<p>  \u0412 \u044d\u0442\u043e\u043c \u0437\u0430\u0434\u0430\u043d\u0438\u0438 \u0432\u0430\u043c \u043d\u0443\u0436\u043d\u043e \u043f\u043e\u0441\u0442\u0440\u043e\u0438\u0442\u044c \u0440\u0435\u043a\u043e\u043c\u0435\u043d\u0434\u0430\u0442\u0435\u043b\u044c\u043d\u0443\u044e \u0441\u0438\u0441\u0442\u0435\u043c\u0443 \u043d\u0430 \u043e\u0441\u043d\u043e\u0432\u0435 \u0434\u0430\u043d\u043d\u044b\u0445 \u043e \u0434\u0435\u0439\u0441\u0442\u0432\u0438\u044f\u0445 \u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u0442\u0435\u043b\u0435\u0439 \u0432 \u043f\u0435\u0440\u0441\u043e\u043d\u0430\u043b\u044c\u043d\u043e\u0439 \u043b\u0435\u043d\u0442\u0435 \u0440\u0435\u043a\u043e\u043c\u0435\u043d\u0434\u0430\u0446\u0438\u0439 \u042f\u043d\u0434\u0435\u043a\u0441.\u0414\u0437\u0435\u043d\u0430.<\/p>\n<p>  \u0412\u0430\u043c \u0434\u043e\u0441\u0442\u0443\u043f\u043d\u044b 2 \u0434\u0430\u0442\u0430\u0441\u0435\u0442\u0430: \u0442\u0440\u0435\u043d\u0438\u0440\u043e\u0432\u043e\u0447\u043d\u044b\u0439 (train.csv) \u0438 \u0442\u0435\u0441\u0442\u043e\u0432\u044b\u0439 (test.csv). \u041a\u0430\u0436\u0434\u0430\u044f \u0441\u0442\u0440\u043e\u043a\u0430 \u0432 \u0434\u0430\u0442\u0430\u0441\u0435\u0442\u0430\u0445 \u0441\u043e\u043e\u0442\u0432\u0435\u0442\u0441\u0442\u0432\u0443\u0435\u0442 \u0432\u0437\u0430\u0438\u043c\u043e\u0434\u0435\u0439\u0441\u0442\u0432\u0438\u044e \u043d\u0435\u043a\u043e\u0442\u043e\u0440\u043e\u0433\u043e \u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u0442\u0435\u043b\u044f \u0441 \u043d\u0435\u043a\u043e\u0442\u043e\u0440\u044b\u043c \u0434\u043e\u043a\u0443\u043c\u0435\u043d\u0442\u043e\u043c, \u043f\u043e\u043a\u0430\u0437\u0430\u043d\u043d\u044b\u043c \u0435\u043c\u0443 \u0432 \u043b\u0435\u043d\u0442\u0435 \u0440\u0435\u043a\u043e\u043c\u0435\u043d\u0434\u0430\u0446\u0438\u0439. \u0414\u0430\u0442\u0430\u0441\u0435\u0442\u044b \u0441\u043e\u0434\u0435\u0440\u0436\u0430\u0442 \u0441\u043b\u0435\u0434\u0443\u044e\u0449\u0438\u0435 \u043a\u043e\u043b\u043e\u043d\u043a\u0438:<\/p>\n<p>  \u2014 sample_id \u2014 \u0447\u0438\u0441\u043b\u043e\u0432\u043e\u0439 id \u0432\u0437\u0430\u0438\u043c\u043e\u0434\u0435\u0439\u0441\u0442\u0432\u0438\u044f,<br \/>  \u2014 item \u2014 \u0447\u0438\u0441\u043b\u043e\u0432\u043e\u0439 id \u043f\u043e\u043a\u0430\u0437\u0430\u043d\u043d\u043e\u0433\u043e \u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u0442\u0435\u043b\u044e \u0434\u043e\u043a\u0443\u043c\u0435\u043d\u0442\u0430,<br \/>  \u2014 publisher \u2014 \u0447\u0438\u0441\u043b\u043e\u0432\u043e\u0439 id \u0430\u0432\u0442\u043e\u0440\u0430 \u0434\u043e\u043a\u0443\u043c\u0435\u043d\u0442\u0430,<br \/>  \u2014 user \u2014 \u0447\u0438\u0441\u043b\u043e\u0432\u043e\u0439 id \u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u0442\u0435\u043b\u044f,<br \/>  topic_i, weight_i \u2014 \u0447\u0438\u0441\u043b\u043e\u0432\u043e\u0439 id i-\u043e\u0439 \u0442\u0435\u043c\u044b \u0434\u043e\u043a\u0443\u043c\u0435\u043d\u0442\u0430 \u0438 \u0441\u0442\u0435\u043f\u0435\u043d\u044c \u043f\u0440\u0438\u043d\u0430\u0434\u043b\u0435\u0436\u043d\u043e\u0441\u0442\u0438 \u0434\u043e\u043a\u0443\u043c\u0435\u043d\u0442\u0430 \u0434\u0430\u043d\u043d\u043e\u0439 \u0442\u0435\u043c\u0435 (\u0446\u0435\u043b\u043e\u0435 \u0447\u0438\u0441\u043b\u043e \u043e\u0442 0 \u0434\u043e 100) (i = 0, 1, 2, 3, 4),<br \/>  \u2014 target \u2014 \u0444\u0430\u043a\u0442 \u043a\u043b\u0438\u043a\u0430 \u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u0442\u0435\u043b\u044f \u043d\u0430 \u0434\u043e\u043a\u0443\u043c\u0435\u043d\u0442 (1 \u2014 \u0431\u044b\u043b \u043a\u043b\u0438\u043a, 0 \u2014 \u0431\u044b\u043b \u043f\u043e\u043a\u0430\u0437 \u0431\u0435\u0437 \u043a\u043b\u0438\u043a\u0430). \u042d\u0442\u043e\u0442 \u0441\u0442\u043e\u043b\u0431\u0435\u0446 \u043f\u0440\u0438\u0441\u0443\u0442\u0441\u0442\u0432\u0443\u0435\u0442 \u0442\u043e\u043b\u044c\u043a\u043e \u0432 \u0442\u0440\u0435\u043d\u0438\u0440\u043e\u0432\u043e\u0447\u043d\u043e\u043c \u0434\u0430\u0442\u0430\u0441\u0435\u0442\u0435.<\/p>\n<p>  \u041d\u0435\u043e\u0431\u0445\u043e\u0434\u0438\u043c\u043e \u043f\u043e\u0441\u0442\u0440\u043e\u0438\u0442\u044c \u043c\u043e\u0434\u0435\u043b\u044c \u0434\u043b\u044f \u043f\u0440\u0435\u0434\u0441\u043a\u0430\u0437\u0430\u043d\u0438\u044f \u043a\u043b\u0438\u043a\u043e\u0432 \u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u0442\u0435\u043b\u044f \u0438 \u043f\u0440\u0438\u043c\u0435\u043d\u0438\u0442\u044c \u0435\u0451 \u043a \u0442\u0435\u0441\u0442\u043e\u0432\u043e\u043c\u0443 \u0434\u0430\u0442\u0430\u0441\u0435\u0442\u0443.<\/p>\n<p>  \u0413\u0430\u0440\u0430\u043d\u0442\u0438\u0440\u0443\u0435\u0442\u0441\u044f, \u0447\u0442\u043e \u0432\u0441\u0435 \u0432\u0441\u0442\u0440\u0435\u0447\u0430\u044e\u0449\u0438\u0435\u0441\u044f \u0432 \u0442\u0435\u0441\u0442\u043e\u0432\u043e\u043c \u0434\u0430\u0442\u0430\u0441\u0435\u0442\u0435 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u044f \u0441\u0442\u043e\u043b\u0431\u0446\u043e\u0432 item, publisher, user, topic \u0432\u0441\u0442\u0440\u0435\u0447\u0430\u044e\u0442\u0441\u044f \u0438 \u0432 \u0442\u0440\u0435\u043d\u0438\u0440\u043e\u0432\u043e\u0447\u043d\u043e\u043c \u0434\u0430\u0442\u0430\u0441\u0435\u0442\u0435.<\/p>\n<p>  \u0412 \u043a\u0430\u0447\u0435\u0441\u0442\u0432\u0435 \u0440\u0435\u0448\u0435\u043d\u0438\u044f \u043d\u0443\u0436\u043d\u043e \u043e\u0442\u043f\u0440\u0430\u0432\u0438\u0442\u044c csv-\u0444\u0430\u0439\u043b, \u0441\u043e\u0441\u0442\u043e\u044f\u0449\u0438\u0439 \u0438\u0437 \u0434\u0432\u0443\u0445 \u043a\u043e\u043b\u043e\u043d\u043e\u043a: sample_id \u0438 target, \u0433\u0434\u0435 sample_id \u2014 id \u0441\u0442\u0440\u043e\u043a\u0438 \u0438\u0437 \u0442\u0435\u0441\u0442\u043e\u0432\u043e\u0433\u043e \u0434\u0430\u0442\u0430\u0441\u0435\u0442\u0430, \u0430 target \u2014 \u043f\u0440\u0435\u0434\u0441\u043a\u0430\u0437\u0430\u043d\u043d\u0430\u044f \u0432\u0435\u0440\u043e\u044f\u0442\u043d\u043e\u0441\u0442\u044c \u043a\u043b\u0438\u043a\u0430. \u041a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e \u0441\u0442\u0440\u043e\u043a \u0432 \u044d\u0442\u043e\u043c \u0444\u0430\u0439\u043b\u0435 \u0434\u043e\u043b\u0436\u043d\u043e \u0441\u043e\u0432\u043f\u0430\u0434\u0430\u0442\u044c \u0441 \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e\u043c \u0441\u0442\u0440\u043e\u043a \u0432 test.csv. \u0421\u0442\u0440\u043e\u043a\u0438 \u0432 \u0444\u0430\u0439\u043b\u0435 \u0441 \u0440\u0435\u0448\u0435\u043d\u0438\u0435\u043c \u0434\u043e\u043b\u0436\u043d\u044b \u0431\u044b\u0442\u044c \u043e\u0442\u0441\u043e\u0440\u0442\u0438\u0440\u043e\u0432\u0430\u043d\u044b \u043f\u043e \u0432\u043e\u0437\u0440\u0430\u0441\u0442\u0430\u043d\u0438\u044e \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0439 \u043a\u043e\u043b\u043e\u043d\u043a\u0438 sample_id (\u0432 \u0442\u043e\u043c \u0436\u0435 \u043f\u043e\u0440\u044f\u0434\u043a\u0435, \u0447\u0442\u043e \u0438 \u0432 test.csv). \u0412\u0441\u0435 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u044f \u0432\u0435\u0440\u043e\u044f\u0442\u043d\u043e\u0441\u0442\u0435\u0439 \u0432 \u043a\u043e\u043b\u043e\u043d\u043a\u0435 target \u0434\u043e\u043b\u0436\u043d\u044b \u0431\u044b\u0442\u044c \u0432\u0435\u0449\u0435\u0441\u0442\u0432\u0435\u043d\u043d\u044b\u043c\u0438 \u0447\u0438\u0441\u043b\u0430\u043c\u0438 \u043e\u0442 0 \u0434\u043e 1.<\/p>\n<p>  \u0414\u043b\u044f \u043e\u0446\u0435\u043d\u043a\u0438 \u043a\u0430\u0447\u0435\u0441\u0442\u0432\u0430 \u043e\u0442\u043f\u0440\u0430\u0432\u043b\u0435\u043d\u043d\u043e\u0433\u043e \u0440\u0435\u0448\u0435\u043d\u0438\u044f \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u0435\u0442\u0441\u044f \u043c\u0435\u0442\u0440\u0438\u043a\u0430 logloss.<\/p>\n<p>  \u0417\u0430 \u044d\u0442\u0443 \u0437\u0430\u0434\u0430\u0447\u0443 \u043c\u043e\u0436\u043d\u043e \u043f\u043e\u043b\u0443\u0447\u0438\u0442\u044c \u043c\u0430\u043a\u0441\u0438\u043c\u0443\u043c 150 \u0431\u0430\u043b\u043b\u043e\u0432. \u0414\u043b\u044f \u043a\u043e\u043d\u0432\u0435\u0440\u0442\u0430\u0446\u0438\u0438 \u043c\u0435\u0442\u0440\u0438\u043a\u0438 logloss \u0432 \u0431\u0430\u043b\u043b\u044b \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u0435\u0442\u0441\u044f \u0441\u043b\u0435\u0434\u0443\u044e\u0449\u0430\u044f \u0444\u0443\u043d\u043a\u0446\u0438\u044f:  <\/p>\n<p><math>$$display$$\\begin{equation*} score = \u00a0\\begin{cases} \u00a0\u00a0\u00a00 &amp;\\text{, logloss &gt; 0.5}\\\\ \u00a0\u00a0\u00a0min(150,(200 * (0.5 &#8212; logloss))^2) &amp;\\text{, logloss \u2264 0.5} \u00a0\\end{cases} \\end{equation*}$$display$$<\/math><\/p>\n<p>\u041f\u0440\u0438 \u043e\u0442\u043f\u0440\u0430\u0432\u043a\u0435 \u0440\u0435\u0448\u0435\u043d\u0438\u044f logloss \u0432\u044b\u0447\u0438\u0441\u043b\u044f\u0435\u0442\u0441\u044f \u0441\u0440\u0430\u0437\u0443 \u043d\u0430 \u0432\u0441\u0451\u043c \u0442\u0435\u0441\u0442\u043e\u0432\u043e\u043c \u0434\u0430\u0442\u0430\u0441\u0435\u0442\u0435 \u0438 \u043a\u043e\u043d\u0432\u0435\u0440\u0442\u0438\u0440\u0443\u0435\u0442\u0441\u044f \u0432 \u0438\u0442\u043e\u0433\u043e\u0432\u044b\u0439 \u0431\u0430\u043b\u043b \u0437\u0430 \u043f\u043e\u0441\u044b\u043b\u043a\u0443. \u0411\u0430\u043b\u043b\u044b \u0441\u0447\u0438\u0442\u0430\u044e\u0442\u0441\u044f \u0441 \u0442\u043e\u0447\u043d\u043e\u0441\u0442\u044c\u044e \u0434\u043e 2 \u0437\u043d\u0430\u043a\u043e\u0432 \u043f\u043e\u0441\u043b\u0435 \u0437\u0430\u043f\u044f\u0442\u043e\u0439, logloss \u0440\u0435\u0448\u0435\u043d\u0438\u044f \u043f\u043e\u043a\u0430\u0437\u044b\u0432\u0430\u0435\u0442\u0441\u044f \u0441 \u0442\u043e\u0447\u043d\u043e\u0441\u0442\u044c\u044e \u0434\u043e 4 \u0437\u043d\u0430\u043a\u043e\u0432 \u043f\u043e\u0441\u043b\u0435 \u0437\u0430\u043f\u044f\u0442\u043e\u0439.<\/p>\n<div class=\"spoiler\"><b class=\"spoiler_title\">\u0424\u043e\u0440\u043c\u0430\u0442\u044b \u0432\u0432\u043e\u0434\u0430\/\u0432\u044b\u0432\u043e\u0434\u0430 \u0438 \u043f\u0440\u0438\u043c\u0435\u0447\u0430\u043d\u0438\u044f<\/b><\/p>\n<div class=\"spoiler_text\">\n<h4>\u0424\u043e\u0440\u043c\u0430\u0442 \u0432\u0432\u043e\u0434\u0430<\/h4>\n<p>  \u0424\u0440\u0430\u0433\u043c\u0435\u043d\u0442 train.csv:  <\/p>\n<div class=\"scrollable-table\">\n<table>\n<tr>\n<td><code>sample_id,item,publisher,user,topic_0,topic_1,topic_2,topic_3,topic_4,weight_0,weight_1,weight_2,weight_3,weight_4,target <br \/>  0,531,147,2925,411,477,618,249,460,27,18,9,8,7,0 <br \/>  1,1574,260,2981,212,287,382,302,51,27,11,2,1,0,0 <br \/>  2,940,394,1230,145,150,212,170,174,7,6,6,5,5,0 <br \/>  3,52,520,2597,201,283,618,249,617,35,33,30,11,9,1 <br \/>  4,766,55,1680,362,150,477,305,388,51,15,13,10,9,1 <br \/>  ...<\/code><\/td>\n<\/tr>\n<\/table>\n<\/div>\n<p>\u0424\u0440\u0430\u0433\u043c\u0435\u043d\u0442 test.csv:  <\/p>\n<div class=\"scrollable-table\">\n<table>\n<tr>\n<td><code>sample_id,item,publisher,user,topic_0,topic_1,topic_2,topic_3,topic_4,weight_0,weight_1,weight_2,weight_3,weight_4 <br \/>  1009109,1716,349,1053,362,397,430,287,431,54,54,51,26,13 <br \/>  1009110,1707,202,254,150,73,356,212,482,29,7,5,5,4 <br \/>  1009111,1592,520,1524,397,287,356,330,281,95,46,6,5,3 <br \/>  1009112,1541,82,2994,397,287,102,323,356,93,77,25,7,4 <br \/>  1009113,52,520,936,201,283,618,249,617,35,33,30,11,9 <br \/>  ...<\/code><\/td>\n<\/tr>\n<\/table>\n<\/div>\n<h4>\u0424\u043e\u0440\u043c\u0430\u0442 \u0432\u044b\u0432\u043e\u0434\u0430<\/h4>\n<p>  \u0424\u0440\u0430\u0433\u043c\u0435\u043d\u0442 \u0432\u043e\u0437\u043c\u043e\u0436\u043d\u043e\u0433\u043e \u0444\u0430\u0439\u043b\u0430 \u0441 \u0440\u0435\u0448\u0435\u043d\u0438\u0435\u043c:  <\/p>\n<div class=\"scrollable-table\">\n<table>\n<tr>\n<td><code>sample_id,target <br \/>  1009109,0.2449 <br \/>  1009110,0.7809 <br \/>  1009111,0.1317 <br \/>  1009112,0.9552 <br \/>  1009113,0.6703 <br \/>  ...<\/code><\/td>\n<\/tr>\n<\/table>\n<\/div>\n<h4>\u041f\u0440\u0438\u043c\u0435\u0447\u0430\u043d\u0438\u044f<\/h4>\n<p>  \u0414\u0430\u0442\u0430\u0441\u0435\u0442\u044b \u043c\u043e\u0436\u043d\u043e \u0441\u043a\u0430\u0447\u0430\u0442\u044c \u043f\u043e \u0441\u0441\u044b\u043b\u043a\u0435: <a href=\"https:\/\/yadi.sk\/d\/pVna8ejcnQZK_A\">yadi.sk\/d\/pVna8ejcnQZK_A<\/a>. \u0422\u0430\u043c \u0436\u0435 \u0432\u044b \u0441\u043c\u043e\u0436\u0435\u0442\u0435 \u043d\u0430\u0439\u0442\u0438 \u0431\u0435\u0439\u0437\u043b\u0430\u0439\u043d, \u043a\u043e\u0442\u043e\u0440\u044b\u0439 \u043f\u043e\u043c\u043e\u0436\u0435\u0442 \u043f\u0440\u0438\u0441\u0442\u0443\u043f\u0438\u0442\u044c \u043a \u0437\u0430\u0434\u0430\u0447\u0435.<\/p>\n<p>  \u0414\u043b\u044f \u043f\u043e\u0434\u0441\u0447\u0435\u0442\u0430 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u044f \u043c\u0435\u0442\u0440\u0438\u043a\u0438 logloss \u043d\u0430 \u043e\u0434\u043d\u043e\u043c \u043e\u0431\u044a\u0435\u043a\u0442\u0435 \u0442\u0435\u0441\u0442\u043e\u0432\u043e\u0433\u043e \u0434\u0430\u0442\u0430\u0441\u0435\u0442\u0430 \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u0435\u0442\u0441\u044f \u0441\u043b\u0435\u0434\u0443\u044e\u0449\u0430\u044f \u0444\u0443\u043d\u043a\u0446\u0438\u044f:<\/p>\n<p>  <code>EPS = 1e-4 <\/p>\n<p>  <b>def<\/b> logloss(y_true, y_pred): <br \/>  \u00a0\u00a0\u00a0\u00a0<b>if abs<\/b>(y_pred - 1) &lt; EPS: <br \/>  \u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0y_pred = 1 - EPS <br \/>  \u00a0\u00a0\u00a0\u00a0<b>if abs<\/b>(y_pred) &lt; EPS: <br \/>  \u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0y_pred = EPS <br \/>  \u00a0\u00a0\u00a0\u00a0<b>return<\/b> -y_true \u2217 log(y_pred) - (1 - y_true) \u2217 log(1 - y_pred)<\/code><\/p>\n<p>  \u0418\u0442\u043e\u0433\u043e\u0432\u044b\u0439 logloss \u0437\u0430 \u043f\u043e\u0441\u044b\u043b\u043a\u0443 \u0432\u044b\u0447\u0438\u0441\u043b\u044f\u0435\u0442\u0441\u044f \u043a\u0430\u043a \u0441\u0440\u0435\u0434\u043d\u0435\u0435 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0435 logloss \u043f\u043e \u0432\u0441\u0435\u043c \u043e\u0431\u044a\u0435\u043a\u0442\u0430\u043c \u0442\u0435\u0441\u0442\u043e\u0432\u043e\u0433\u043e \u0434\u0430\u0442\u0430\u0441\u0435\u0442\u0430.<\/p>\n<p>  \u0414\u043b\u044f \u043f\u043e\u0434\u0441\u0447\u0435\u0442\u0430 \u0431\u0430\u043b\u043b\u043e\u0432 \u043f\u043e logloss \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u0435\u0442\u0441\u044f \u0441\u043b\u0435\u0434\u0443\u044e\u0449\u0430\u044f \u0444\u0443\u043d\u043a\u0446\u0438\u044f:<\/p>\n<p>  <code><b>def<\/b> score(logloss):<br \/>  \u00a0\u00a0\u00a0\u00a0<b>if<\/b> logloss &gt; 0.5:<br \/>  \u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0<b>return<\/b> 0.0 <br \/>  \u00a0\u00a0\u00a0\u00a0<b>return<\/b> min(150, (200 \u2217 (0.5 - logloss)) \u2217\u2217 2)<\/code><\/div>\n<\/div>\n<p>  <\/p>\n<h4>\u0420\u0435\u0448\u0435\u043d\u0438\u0435<\/h4>\n<p>  \u041d\u0443\u0436\u043d\u043e \u043f\u0440\u0435\u0434\u0441\u043a\u0430\u0437\u0430\u0442\u044c, \u043f\u043e\u043d\u0440\u0430\u0432\u0438\u0442\u0441\u044f \u043b\u0438 \u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u0442\u0435\u043b\u044e \u043f\u0443\u0431\u043b\u0438\u043a\u0430\u0446\u0438\u044f. \u0415\u0441\u0442\u044c \u0440\u0430\u0437\u043d\u044b\u0435 \u0441\u043f\u043e\u0441\u043e\u0431\u044b \u0440\u0435\u0448\u0438\u0442\u044c \u0437\u0430\u0434\u0430\u0447\u0443. \u041d\u0430\u0434\u043e \u0443\u0447\u0438\u0442\u044b\u0432\u0430\u0442\u044c, \u0447\u0442\u043e \u0432\u0441\u0435 \u0441\u0443\u0449\u043d\u043e\u0441\u0442\u0438 (\u0434\u043e\u043a\u0443\u043c\u0435\u043d\u0442\u044b, \u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u0442\u0435\u043b\u0438, \u0438\u0441\u0442\u043e\u0447\u043d\u0438\u043a\u0438, \u0442\u0435\u043c\u044b) \u043e\u0434\u0438\u043d\u0430\u043a\u043e\u0432\u044b\u0435 \u043a\u0430\u043a \u0432 \u0442\u0440\u0435\u043d\u0438\u0440\u043e\u0432\u043e\u0447\u043d\u043e\u043c, \u0442\u0430\u043a \u0438 \u0432 \u0442\u0435\u0441\u0442\u043e\u0432\u043e\u043c \u0434\u0430\u0442\u0430\u0441\u0435\u0442\u0435 \u2014 \u0442\u043e \u0435\u0441\u0442\u044c \u043d\u0435\u0442 \u043f\u0440\u043e\u0431\u043b\u0435\u043c \u0441 \u0442\u0435\u043c, \u0447\u0442\u043e \u043e \u043a\u0430\u043a\u0438\u0445-\u0442\u043e \u0434\u043e\u043a\u0443\u043c\u0435\u043d\u0442\u0430\u0445 \u0438\u0437 \u0442\u0435\u0441\u0442\u043e\u0432\u043e\u0433\u043e \u0434\u0430\u0442\u0430\u0441\u0435\u0442\u0430 \u043c\u044b \u043d\u0435 \u0437\u043d\u0430\u0435\u043c, \u043a\u0430\u043a \u0441 \u043d\u0438\u043c\u0438 \u0432\u0437\u0430\u0438\u043c\u043e\u0434\u0435\u0439\u0441\u0442\u0432\u0443\u044e\u0442 \u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u0442\u0435\u043b\u0438. <\/p>\n<p>  \u041c\u044b \u043e\u043f\u0438\u0448\u0435\u043c \u043d\u0435\u043a\u043e\u0442\u043e\u0440\u044b\u0435 \u043f\u043e\u0434\u0445\u043e\u0434\u044b \u0443\u0447\u0430\u0441\u0442\u043d\u0438\u043a\u043e\u0432, \u043d\u0430\u0431\u0440\u0430\u0432\u0448\u0438\u0445 100 \u0438 \u0431\u043e\u043b\u0435\u0435 \u0431\u0430\u043b\u043b\u043e\u0432 (\u0438\u0437 150). <\/p>\n<p>  \u0421\u0430\u043c\u044b\u0439 \u043f\u0440\u043e\u0441\u0442\u043e\u0439 \u0441\u043f\u043e\u0441\u043e\u0431 \u2014 \u0437\u0430\u0433\u0440\u0443\u0437\u0438\u0442\u044c \u0434\u0430\u0442\u0430\u0441\u0435\u0442 \u0432 CatBoost \u0438 \u0430\u043a\u043a\u0443\u0440\u0430\u0442\u043d\u043e \u043f\u043e\u0434\u043e\u0431\u0440\u0430\u0442\u044c \u0433\u0438\u043f\u0435\u0440\u043f\u0430\u0440\u0430\u043c\u0435\u0442\u0440\u044b. \u041f\u043e\u0441\u043a\u043e\u043b\u044c\u043a\u0443 CatBoost \u0443\u043c\u0435\u0435\u0442 \u0445\u043e\u0440\u043e\u0448\u043e \u043e\u0431\u0440\u0430\u0431\u0430\u0442\u044b\u0432\u0430\u0442\u044c \u043a\u0430\u0442\u0435\u0433\u043e\u0440\u0438\u0430\u043b\u044c\u043d\u044b\u0435 \u043f\u0440\u0438\u0437\u043d\u0430\u043a\u0438 (\u043a\u043e\u0442\u043e\u0440\u044b\u0445 \u0431\u044b\u043b\u043e \u0431\u043e\u043b\u044c\u0448\u0438\u043d\u0441\u0442\u0432\u043e \u0432 \u0438\u0441\u0445\u043e\u0434\u043d\u043e\u043c \u0434\u0430\u0442\u0430\u0441\u0435\u0442\u0435), \u0434\u0430\u0436\u0435 \u0442\u0430\u043a\u043e\u0435 \u043f\u0440\u043e\u0441\u0442\u043e\u0435 \u0440\u0435\u0448\u0435\u043d\u0438\u0435 \u0434\u0430\u0432\u0430\u043b\u043e \u0445\u043e\u0440\u043e\u0448\u0438\u0439 \u0440\u0435\u0437\u0443\u043b\u044c\u0442\u0430\u0442. \u0427\u0442\u043e\u0431\u044b \u043f\u043e\u0432\u044b\u0441\u0438\u0442\u044c \u043a\u0430\u0447\u0435\u0441\u0442\u0432\u043e \u0440\u0430\u0431\u043e\u0442\u044b \u043c\u0435\u0442\u043e\u0434\u0430, \u043c\u043e\u0436\u043d\u043e \u0431\u044b\u043b\u043e \u0441\u0433\u0435\u043d\u0435\u0440\u0438\u0440\u043e\u0432\u0430\u0442\u044c \u0431\u043e\u043b\u044c\u0448\u0435 \u043f\u0440\u0438\u0437\u043d\u0430\u043a\u043e\u0432. \u041a \u043f\u0440\u0438\u043c\u0435\u0440\u0443, \u0441\u0434\u0435\u043b\u0430\u0442\u044c \u0440\u0430\u0437\u043d\u044b\u0435 \u043f\u0440\u0438\u0437\u043d\u0430\u043a\u0438-\u0441\u0447\u0451\u0442\u0447\u0438\u043a\u0438: \u043a\u043b\u0438\u043a\u0430\u0431\u0435\u043b\u044c\u043d\u043e\u0441\u0442\u044c \u0434\u043e\u043a\u0443\u043c\u0435\u043d\u0442\u0430 <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/2b5\/df3\/a7e\/2b5df3a7e99e00d2056f18b9f651809b.svg\" alt=\"$(\\frac{\u0447\u0438\u0441\u043b\u043e\\ \u043a\u043b\u0438\u043a\u043e\u0432\\ \u043d\u0430\\ \u0434\u043e\u043a\u0443\u043c\u0435\u043d\u0442}{\u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e\\ \u043f\u043e\u043a\u0430\u0437\u043e\u0432})$\" data-tex=\"inline\"><\/math>, \u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u0442\u0435\u043b\u044f, \u0438\u0441\u0442\u043e\u0447\u043d\u0438\u043a\u0430, \u0442\u0435\u043c, \u043a\u0430\u043a\u0438\u0435-\u0442\u043e \u043f\u0430\u0440\u043d\u044b\u0435 \u0432\u0437\u0430\u0438\u043c\u043e\u0434\u0435\u0439\u0441\u0442\u0432\u0438\u044f (\u043a\u0430\u043a \u0447\u0430\u0441\u0442\u043e \u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u0442\u0435\u043b\u044c \u043a\u043b\u0438\u043a\u0430\u0435\u0442 \u043d\u0430 \u0442\u0435\u043c\u044b \u0441\u0442\u0430\u0442\u044c\u0438).<\/p>\n<p>  \u0425\u043e\u0440\u043e\u0448\u0438\u0439 \u0440\u0435\u0437\u0443\u043b\u044c\u0442\u0430\u0442 \u043c\u043e\u0436\u043d\u043e \u0431\u044b\u043b\u043e \u043f\u043e\u043b\u0443\u0447\u0438\u0442\u044c \u0438 \u0441 \u043f\u043e\u043c\u043e\u0449\u044c\u044e \u043a\u043e\u043b\u043b\u0430\u0431\u043e\u0440\u0430\u0442\u0438\u0432\u043d\u044b\u0445 \u043c\u0435\u0442\u043e\u0434\u043e\u0432. \u041d\u0430\u043f\u0440\u0438\u043c\u0435\u0440, \u043c\u043e\u0436\u043d\u043e \u0431\u044b\u043b\u043e \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u0442\u044c \u0440\u0430\u0437\u043b\u043e\u0436\u0435\u043d\u0438\u0435 \u043c\u0430\u0442\u0440\u0438\u0446\u044b \u0434\u043e\u043a\u0443\u043c\u0435\u043d\u0442-\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u0442\u0435\u043b\u044c \u0438\u043b\u0438 \u043c\u0435\u0442\u043e\u0434\u044b, \u043a\u043e\u0442\u043e\u0440\u044b\u0435 \u0443\u0447\u0438\u0442\u044b\u0432\u0430\u044e\u0442 \u0434\u0440\u0443\u0433\u0438\u0435 \u0434\u043e\u0441\u0442\u0443\u043f\u043d\u044b\u0435 \u0434\u0430\u043d\u043d\u044b\u0435: FM (Factorization Machines) \u0438 FFM (Field-aware Factorization Machines).<\/p>\n<hr>\n<p>  \u0415\u0441\u043b\u0438 \u0432\u044b \u043f\u043b\u0430\u043d\u0438\u0440\u0443\u0435\u0442\u0435 \u0443\u0447\u0430\u0441\u0442\u0432\u043e\u0432\u0430\u0442\u044c \u0432 \u0441\u043e\u0440\u0435\u0432\u043d\u043e\u0432\u0430\u043d\u0438\u044f\u0445 \u043f\u043e \u043c\u0430\u0448\u0438\u043d\u043d\u043e\u043c\u0443 \u043e\u0431\u0443\u0447\u0435\u043d\u0438\u044e, \u043f\u043e\u0441\u043c\u043e\u0442\u0440\u0438\u0442\u0435 <a href=\"https:\/\/habr.com\/ru\/company\/yandex\/blog\/461273\/\">\u0440\u0430\u0437\u0431\u043e\u0440<\/a> ML-\u0442\u0440\u0435\u043a\u0430 \u043f\u0435\u0440\u0432\u043e\u0433\u043e \u0447\u0435\u043c\u043f\u0438\u043e\u043d\u0430\u0442\u0430.<\/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\/ru\/company\/yandex\/blog\/477452\/\"> https:\/\/habr.com\/ru\/company\/yandex\/blog\/477452\/<\/a><\/p>\n","protected":false},"excerpt":{"rendered":"\n<div class=\"post__text post__text-html js-mediator-article\" id=\"post-content-body\" data-io-article-url=\"https:\/\/habr.com\/ru\/company\/yandex\/blog\/477452\/\"><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/webt\/ri\/tp\/iv\/ritpivveq5sfetymakd2icpummo.jpeg\" width=\"340\" align=\"right\">\u0412 \u043e\u043a\u0442\u044f\u0431\u0440\u0435 \u0441\u043e\u0441\u0442\u043e\u044f\u043b\u0441\u044f \u0432\u0442\u043e\u0440\u043e\u0439 \u0447\u0435\u043c\u043f\u0438\u043e\u043d\u0430\u0442 \u043f\u043e \u043f\u0440\u043e\u0433\u0440\u0430\u043c\u043c\u0438\u0440\u043e\u0432\u0430\u043d\u0438\u044e. \u041c\u044b \u043f\u043e\u043b\u0443\u0447\u0438\u043b\u0438 12 500 \u0437\u0430\u044f\u0432\u043e\u043a, \u0431\u043e\u043b\u0435\u0435 6000 \u0447\u0435\u043b\u043e\u0432\u0435\u043a \u043f\u043e\u043f\u0440\u043e\u0431\u043e\u0432\u0430\u043b\u0438 \u0441\u0432\u043e\u0438 \u0441\u0438\u043b\u044b \u0432 \u0441\u043e\u0440\u0435\u0432\u043d\u043e\u0432\u0430\u043d\u0438\u044f\u0445. \u0412 \u044d\u0442\u043e\u0442 \u0440\u0430\u0437 \u0443\u0447\u0430\u0441\u0442\u043d\u0438\u043a\u0438 \u043c\u043e\u0433\u043b\u0438 \u0432\u044b\u0431\u0440\u0430\u0442\u044c \u043e\u0434\u0438\u043d \u0438\u0437 \u0441\u043b\u0435\u0434\u0443\u044e\u0449\u0438\u0445 \u0442\u0440\u0435\u043a\u043e\u0432: \u0431\u044d\u043a\u0435\u043d\u0434, \u0444\u0440\u043e\u043d\u0442\u0435\u043d\u0434, \u043c\u043e\u0431\u0438\u043b\u044c\u043d\u0443\u044e \u0440\u0430\u0437\u0440\u0430\u0431\u043e\u0442\u043a\u0443 \u0438 \u043c\u0430\u0448\u0438\u043d\u043d\u043e\u0435 \u043e\u0431\u0443\u0447\u0435\u043d\u0438\u0435. \u0412 \u043a\u0430\u0436\u0434\u043e\u043c \u0442\u0440\u0435\u043a\u0435 \u0442\u0440\u0435\u0431\u043e\u0432\u0430\u043b\u043e\u0441\u044c \u043f\u0440\u043e\u0439\u0442\u0438 \u043a\u0432\u0430\u043b\u0438\u0444\u0438\u043a\u0430\u0446\u0438\u043e\u043d\u043d\u044b\u0439 \u044d\u0442\u0430\u043f \u0438 \u0444\u0438\u043d\u0430\u043b.<\/p>\n<p>  \u041f\u043e \u0442\u0440\u0430\u0434\u0438\u0446\u0438\u0438 \u043c\u044b \u043e\u043f\u0443\u0431\u043b\u0438\u043a\u0443\u0435\u043c \u0440\u0430\u0437\u0431\u043e\u0440\u044b \u0442\u0440\u0435\u043a\u043e\u0432 \u043d\u0430 \u0425\u0430\u0431\u0440\u0435. \u041d\u0430\u0447\u043d\u0451\u043c \u0441 \u0437\u0430\u0434\u0430\u0447 \u043a\u0432\u0430\u043b\u0438\u0444\u0438\u043a\u0430\u0446\u0438\u043e\u043d\u043d\u043e\u0433\u043e \u044d\u0442\u0430\u043f\u0430 \u043f\u043e \u043c\u0430\u0448\u0438\u043d\u043d\u043e\u043c\u0443 \u043e\u0431\u0443\u0447\u0435\u043d\u0438\u044e. \u041a\u043e\u043c\u0430\u043d\u0434\u0430 \u043f\u043e\u0434\u0433\u043e\u0442\u043e\u0432\u0438\u043b\u0430 \u043f\u044f\u0442\u044c \u0442\u0430\u043a\u0438\u0445 \u0437\u0430\u0434\u0430\u0447, \u0438\u0437 \u043a\u043e\u0442\u043e\u0440\u044b\u0445 \u0441\u043e\u0441\u0442\u0430\u0432\u0438\u043b\u0430 \u0434\u0432\u0430 \u0432\u0430\u0440\u0438\u0430\u043d\u0442\u0430 \u043f\u043e \u0442\u0440\u0438 \u0437\u0430\u0434\u0430\u0447\u0438: \u0432 \u043f\u0435\u0440\u0432\u043e\u043c \u0432\u0430\u0440\u0438\u0430\u043d\u0442\u0435 \u0431\u044b\u043b\u0438 \u0437\u0430\u0434\u0430\u0447\u0438 A1, B1 \u0438 C, \u0432\u043e \u0432\u0442\u043e\u0440\u043e\u043c \u2014 A2, B2 \u0438 C. \u0412\u0430\u0440\u0438\u0430\u043d\u0442\u044b \u0441\u043b\u0443\u0447\u0430\u0439\u043d\u043e \u0440\u0430\u0441\u043f\u0440\u0435\u0434\u0435\u043b\u044f\u043b\u0438\u0441\u044c \u043c\u0435\u0436\u0434\u0443 \u0443\u0447\u0430\u0441\u0442\u043d\u0438\u043a\u0430\u043c\u0438. \u0410\u0432\u0442\u043e\u0440 \u0437\u0430\u0434\u0430\u0447\u0438 C \u2014 \u043d\u0430\u0448 \u0440\u0430\u0437\u0440\u0430\u0431\u043e\u0442\u0447\u0438\u043a \u041f\u0430\u0432\u0435\u043b \u041f\u0430\u0440\u0445\u043e\u043c\u0435\u043d\u043a\u043e, \u043e\u0441\u0442\u0430\u043b\u044c\u043d\u044b\u0435 \u0437\u0430\u0434\u0430\u0447\u0438 \u0441\u043e\u0441\u0442\u0430\u0432\u0438\u043b \u0435\u0433\u043e \u043a\u043e\u043b\u043b\u0435\u0433\u0430 \u041d\u0438\u043a\u0438\u0442\u0430 \u0421\u0435\u043d\u0434\u0435\u0440\u043e\u0432\u0438\u0447. <\/p>\n<p>  \u0417\u0430 \u043f\u0435\u0440\u0432\u0443\u044e \u043f\u0440\u043e\u0441\u0442\u0443\u044e \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0438\u0447\u0435\u0441\u043a\u0443\u044e \u0437\u0430\u0434\u0430\u0447\u0443 (A1\/A2) \u0443\u0447\u0430\u0441\u0442\u043d\u0438\u043a\u0438 \u043c\u043e\u0433\u043b\u0438 \u043f\u043e\u043b\u0443\u0447\u0438\u0442\u044c 50 \u0431\u0430\u043b\u043b\u043e\u0432, \u043f\u0440\u0430\u0432\u0438\u043b\u044c\u043d\u043e \u0440\u0435\u0430\u043b\u0438\u0437\u043e\u0432\u0430\u0432 \u043f\u0435\u0440\u0435\u0431\u043e\u0440 \u043f\u043e \u043e\u0442\u0432\u0435\u0442\u0443. \u0417\u0430 \u0432\u0442\u043e\u0440\u0443\u044e \u0437\u0430\u0434\u0430\u0447\u0443 (B1\/B2) \u043c\u044b \u0434\u0430\u0432\u0430\u043b\u0438 \u043e\u0442 10 \u0434\u043e 100 \u0431\u0430\u043b\u043b\u043e\u0432 \u2014 \u0432 \u0437\u0430\u0432\u0438\u0441\u0438\u043c\u043e\u0441\u0442\u0438 \u043e\u0442 \u044d\u0444\u0444\u0435\u043a\u0442\u0438\u0432\u043d\u043e\u0441\u0442\u0438 \u0440\u0435\u0448\u0435\u043d\u0438\u044f. \u0427\u0442\u043e\u0431\u044b \u043f\u043e\u043b\u0443\u0447\u0438\u0442\u044c 100 \u0431\u0430\u043b\u043b\u043e\u0432, \u0442\u0440\u0435\u0431\u043e\u0432\u0430\u043b\u043e\u0441\u044c \u0440\u0435\u0430\u043b\u0438\u0437\u043e\u0432\u0430\u0442\u044c \u043c\u0435\u0442\u043e\u0434 \u0434\u0438\u043d\u0430\u043c\u0438\u0447\u0435\u0441\u043a\u043e\u0433\u043e \u043f\u0440\u043e\u0433\u0440\u0430\u043c\u043c\u0438\u0440\u043e\u0432\u0430\u043d\u0438\u044f. \u0422\u0440\u0435\u0442\u044c\u044f \u0437\u0430\u0434\u0430\u0447\u0430 \u0431\u044b\u043b\u0430 \u043f\u043e\u0441\u0432\u044f\u0449\u0435\u043d\u0430 \u043f\u043e\u0441\u0442\u0440\u043e\u0435\u043d\u0438\u044e \u043a\u043b\u0438\u043a\u043e\u0432\u043e\u0439 \u043c\u043e\u0434\u0435\u043b\u0438 \u043f\u043e \u043f\u0440\u0435\u0434\u043e\u0441\u0442\u0430\u0432\u043b\u0435\u043d\u043d\u044b\u043c \u043e\u0431\u0443\u0447\u0430\u044e\u0449\u0438\u043c \u0434\u0430\u043d\u043d\u044b\u043c. \u0412 \u043d\u0435\u0439 \u0442\u0440\u0435\u0431\u043e\u0432\u0430\u043b\u043e\u0441\u044c \u043f\u0440\u0438\u043c\u0435\u043d\u0438\u0442\u044c \u043c\u0435\u0442\u043e\u0434\u044b \u0440\u0430\u0431\u043e\u0442\u044b \u0441 \u043a\u0430\u0442\u0435\u0433\u043e\u0440\u0438\u0430\u043b\u044c\u043d\u044b\u043c\u0438 \u043f\u0440\u0438\u0437\u043d\u0430\u043a\u0430\u043c\u0438 \u0438 \u0432\u043e\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u0442\u044c\u0441\u044f \u043d\u0435\u043b\u0438\u043d\u0435\u0439\u043d\u043e\u0439 \u043c\u043e\u0434\u0435\u043b\u044c\u044e \u043e\u0431\u0443\u0447\u0435\u043d\u0438\u044f (\u043d\u0430\u043f\u0440\u0438\u043c\u0435\u0440, \u0433\u0440\u0430\u0434\u0438\u0435\u043d\u0442\u043d\u044b\u043c \u0431\u0443\u0441\u0442\u0438\u043d\u0433\u043e\u043c). \u0417\u0430 \u0437\u0430\u0434\u0430\u0447\u0443 \u043c\u043e\u0436\u043d\u043e \u0431\u044b\u043b\u043e \u043f\u043e\u043b\u0443\u0447\u0438\u0442\u044c \u0434\u043e 150 \u0431\u0430\u043b\u043b\u043e\u0432 \u2014 \u0432 \u0437\u0430\u0432\u0438\u0441\u0438\u043c\u043e\u0441\u0442\u0438 \u043e\u0442 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u044f \u0444\u0443\u043d\u043a\u0446\u0438\u0438 \u043f\u043e\u0442\u0435\u0440\u044c \u043d\u0430 \u0442\u0435\u0441\u0442\u043e\u0432\u043e\u0439 \u0432\u044b\u0431\u043e\u0440\u043a\u0435.  <\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[],"tags":[],"class_list":["post-295204","post","type-post","status-publish","format-standard","hentry"],"_links":{"self":[{"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=\/wp\/v2\/posts\/295204","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=295204"}],"version-history":[{"count":0,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=\/wp\/v2\/posts\/295204\/revisions"}],"wp:attachment":[{"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=295204"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=295204"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=295204"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}