{"id":292525,"date":"2019-07-25T09:02:11","date_gmt":"2019-07-25T09:02:11","guid":{"rendered":"http:\/\/savepearlharbor.com\/?p=292525"},"modified":"-0001-11-30T00:00:00","modified_gmt":"-0001-11-29T21:00:00","slug":"","status":"publish","type":"post","link":"https:\/\/savepearlharbor.com\/?p=292525","title":{"rendered":"\u0416\u0430\u0434\u043d\u044b\u0439 \u043f\u043e\u0434\u0445\u043e\u0434 \u0438 \u0438\u0433\u0440\u043e\u0432\u044b\u0435 \u0430\u0432\u0442\u043e\u043c\u0430\u0442\u044b. \u0420\u0430\u0437\u0431\u043e\u0440 \u0437\u0430\u0434\u0430\u0447 ML-\u0442\u0440\u0435\u043a\u0430 \u0447\u0435\u043c\u043f\u0438\u043e\u043d\u0430\u0442\u0430 \u043f\u043e \u043f\u0440\u043e\u0433\u0440\u0430\u043c\u043c\u0438\u0440\u043e\u0432\u0430\u043d\u0438\u044e"},"content":{"rendered":"\n<div class=\"post__text post__text-html js-mediator-article\"><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/webt\/sd\/i7\/yd\/sdi7ydyv5yabtpudjamnnmm2dge.jpeg\"><\/p>\n<p>  \u041c\u044b \u043f\u0440\u043e\u0434\u043e\u043b\u0436\u0430\u0435\u043c \u043f\u0443\u0431\u043b\u0438\u043a\u043e\u0432\u0430\u0442\u044c \u0440\u0430\u0437\u0431\u043e\u0440\u044b \u0437\u0430\u0434\u0430\u0447, \u043a\u043e\u0442\u043e\u0440\u044b\u0435 \u043f\u0440\u0435\u0434\u043b\u0430\u0433\u0430\u043b\u0438\u0441\u044c \u043d\u0430 \u043d\u0435\u0434\u0430\u0432\u043d\u0435\u043c \u0447\u0435\u043c\u043f\u0438\u043e\u043d\u0430\u0442\u0435. \u041d\u0430 \u043e\u0447\u0435\u0440\u0435\u0434\u0438 \u2014 \u0437\u0430\u0434\u0430\u0447\u0438, \u0432\u0437\u044f\u0442\u044b\u0435 \u0438\u0437 \u043a\u0432\u0430\u043b\u0438\u0444\u0438\u043a\u0430\u0446\u0438\u043e\u043d\u043d\u043e\u0433\u043e \u0440\u0430\u0443\u043d\u0434\u0430 \u0434\u043b\u044f \u0441\u043f\u0435\u0446\u0438\u0430\u043b\u0438\u0441\u0442\u043e\u0432 \u043f\u043e \u043c\u0430\u0448\u0438\u043d\u043d\u043e\u043c\u0443 \u043e\u0431\u0443\u0447\u0435\u043d\u0438\u044e. \u042d\u0442\u043e \u0442\u0440\u0435\u0442\u0438\u0439 \u0442\u0440\u0435\u043a \u0438\u0437 \u0447\u0435\u0442\u044b\u0440\u0451\u0445 (\u0431\u044d\u043a\u0435\u043d\u0434, \u0444\u0440\u043e\u043d\u0442\u0435\u043d\u0434, ML, \u0430\u043d\u0430\u043b\u0438\u0442\u0438\u043a\u0430). \u0423\u0447\u0430\u0441\u0442\u043d\u0438\u043a\u0430\u043c \u043d\u0443\u0436\u043d\u043e \u0431\u044b\u043b\u043e \u0441\u0434\u0435\u043b\u0430\u0442\u044c \u043c\u043e\u0434\u0435\u043b\u044c \u0438\u0441\u043f\u0440\u0430\u0432\u043b\u0435\u043d\u0438\u044f \u043e\u043f\u0435\u0447\u0430\u0442\u043e\u043a \u0432 \u0442\u0435\u043a\u0441\u0442\u0430\u0445, \u043f\u0440\u0435\u0434\u043b\u043e\u0436\u0438\u0442\u044c \u0441\u0442\u0440\u0430\u0442\u0435\u0433\u0438\u044e \u0438\u0433\u0440\u044b \u043d\u0430 \u0438\u0433\u0440\u043e\u0432\u044b\u0445 \u0430\u0432\u0442\u043e\u043c\u0430\u0442\u0430\u0445, \u0434\u043e\u0432\u0435\u0441\u0442\u0438 \u0434\u043e \u0443\u043c\u0430 \u0441\u0438\u0441\u0442\u0435\u043c\u0443 \u0440\u0435\u043a\u043e\u043c\u0435\u043d\u0434\u0430\u0446\u0438\u0439 \u043a\u043e\u043d\u0442\u0435\u043d\u0442\u0430 \u0438 \u0441\u043e\u0441\u0442\u0430\u0432\u0438\u0442\u044c \u0435\u0449\u0451 \u043d\u0435\u0441\u043a\u043e\u043b\u044c\u043a\u043e \u043f\u0440\u043e\u0433\u0440\u0430\u043c\u043c.<\/p>\n<p>  <a name=\"habracut\"><\/a><\/p>\n<h2>A. \u041e\u043f\u0435\u0447\u0430\u0442\u043a\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><\/td>\n<td><b>\u0412\u0441\u0435 \u044f\u0437\u044b\u043a\u0438<\/b><\/td>\n<td><b>python2.7+numpy<\/b><\/td>\n<td><b>python3.5+numpy<\/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>1 \u0441<\/td>\n<td>5 \u0441<\/td>\n<td>5 \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>64 \u041c\u0411<\/td>\n<td>256 \u041c\u0411<\/td>\n<td>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>(\u044d\u043f\u0438\u0433\u0440\u0430\u0444)(\u0441 \u043e\u0434\u043d\u043e\u0433\u043e \u0444\u043e\u0440\u0443\u043c\u0430)<br \/>  \u2014 \u041a\u0442\u043e \u0441\u043e\u0447\u0438\u043d\u0438\u043b \u044d\u0442\u0443 \u0447\u0443\u0448\u044c? <br \/>  \u2014 \u0410\u0441\u0442\u0440\u043e\u0444\u0438\u0437\u0438\u043a\u0438. \u041e\u043d\u0438 \u0442\u043e\u0436\u0435 \u043b\u044e\u0434\u0438. <br \/>  \u2014 \u0412\u044b 10 \u043e\u0448\u0438\u0431\u043e\u043a \u0432 \u0441\u043b\u043e\u0432\u0435 \u00ab\u0436\u0443\u0440\u043d\u0430\u043b\u0438\u0441\u0442\u044b\u00bb \u0441\u0434\u0435\u043b\u0430\u043b\u0438. <\/p>\n<p>  \u041c\u043d\u043e\u0433\u0438\u0435 \u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u0442\u0435\u043b\u0438 \u0434\u0435\u043b\u0430\u044e\u0442 \u043e\u0448\u0438\u0431\u043a\u0438 \u043f\u0440\u0438 \u043d\u0430\u0431\u043e\u0440\u0435, \u043d\u0435\u043a\u043e\u0442\u043e\u0440\u044b\u0435 \u2014 \u0438\u0437-\u0437\u0430 \u043f\u043e\u043f\u0430\u0434\u0430\u043d\u0438\u0439 \u043c\u0438\u043c\u043e \u043a\u043b\u0430\u0432\u0438\u0448, \u043d\u0435\u043a\u043e\u0442\u043e\u0440\u044b\u0435 \u2014 \u0438\u0437-\u0437\u0430 \u0441\u0432\u043e\u0435\u0439 \u043d\u0435\u0433\u0440\u0430\u043c\u043e\u0442\u043d\u043e\u0441\u0442\u0438. \u041c\u044b \u0445\u043e\u0442\u0438\u043c \u043f\u0440\u043e\u0432\u0435\u0440\u0438\u0442\u044c, \u043c\u043e\u0433 \u043b\u0438 \u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u0442\u0435\u043b\u044c \u043d\u0430 \u0441\u0430\u043c\u043e\u043c \u0434\u0435\u043b\u0435 \u0438\u043c\u0435\u0442\u044c \u0432 \u0432\u0438\u0434\u0443 \u043d\u0435\u043a\u043e\u0442\u043e\u0440\u043e\u0435 \u0434\u0440\u0443\u0433\u043e\u0435 \u0441\u043b\u043e\u0432\u043e, \u0447\u0435\u043c \u0442\u043e, \u043a\u043e\u0442\u043e\u0440\u043e\u0435 \u043e\u043d \u043d\u0430\u0431\u0440\u0430\u043b.<\/p>\n<p>  \u0411\u043e\u043b\u0435\u0435 \u0444\u043e\u0440\u043c\u0430\u043b\u044c\u043d\u043e, \u043f\u0440\u0435\u0434\u043f\u043e\u043b\u043e\u0436\u0438\u043c, \u0447\u0442\u043e \u0438\u043c\u0435\u0435\u0442 \u043c\u0435\u0441\u0442\u043e \u0441\u043b\u0435\u0434\u0443\u044e\u0449\u0430\u044f \u043c\u043e\u0434\u0435\u043b\u044c \u043e\u0448\u0438\u0431\u043e\u043a: \u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u0442\u0435\u043b\u044c \u043d\u0430\u0447\u0438\u043d\u0430\u0435\u0442 \u0441 \u043d\u0435\u043a\u043e\u0442\u043e\u0440\u043e\u0433\u043e \u0441\u043b\u043e\u0432\u0430, \u043a\u043e\u0442\u043e\u0440\u043e\u0435 \u043e\u043d \u0445\u043e\u0447\u0435\u0442 \u043d\u0430\u043f\u0438\u0441\u0430\u0442\u044c, \u0438 \u0434\u0430\u043b\u044c\u0448\u0435 \u043f\u043e\u0441\u043b\u0435\u0434\u043e\u0432\u0430\u0442\u0435\u043b\u044c\u043d\u043e \u0434\u0435\u043b\u0430\u0435\u0442 \u0432 \u043d\u0451\u043c \u043d\u0435\u043a\u043e\u0442\u043e\u0440\u043e\u0435 \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e \u043e\u0448\u0438\u0431\u043e\u043a. \u041a\u0430\u0436\u0434\u0430\u044f \u043e\u0448\u0438\u0431\u043a\u0430 \u043f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u043b\u044f\u0435\u0442 \u0441\u043e\u0431\u043e\u0439 \u0437\u0430\u043c\u0435\u043d\u0443 \u043d\u0435\u043a\u043e\u0442\u043e\u0440\u043e\u0439 \u043f\u043e\u0434\u0441\u0442\u0440\u043e\u043a\u0438 \u0441\u043b\u043e\u0432\u0430 \u043d\u0430 \u0434\u0440\u0443\u0433\u0443\u044e \u043f\u043e\u0434\u0441\u0442\u0440\u043e\u043a\u0443. \u041e\u0434\u043d\u0430 \u043e\u0448\u0438\u0431\u043a\u0430 \u0441\u043e\u043e\u0442\u0432\u0435\u0442\u0441\u0442\u0432\u0443\u0435\u0442 \u0437\u0430\u043c\u0435\u043d\u0435 \u0442\u043e\u043b\u044c\u043a\u043e \u0432 \u043e\u0434\u043d\u043e\u0439 \u043f\u043e\u0437\u0438\u0446\u0438\u0438 (\u0442\u043e \u0435\u0441\u0442\u044c \u0435\u0441\u043b\u0438 \u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u0442\u0435\u043b\u044c \u0437\u0430\u0445\u043e\u0447\u0435\u0442 \u0441\u0434\u0435\u043b\u0430\u0442\u044c \u0435\u0434\u0438\u043d\u0441\u0442\u0432\u0435\u043d\u043d\u0443\u044e \u043e\u0448\u0438\u0431\u043a\u0443 \u043f\u043e \u043f\u0440\u0430\u0432\u0438\u043b\u0443 \u00ababc\u00bb\u2192\u00abcba\u00bb, \u0442\u043e \u0438\u0437 \u0441\u0442\u0440\u043e\u043a\u0438 \u00ababcabc\u00bb \u043e\u043d \u043c\u043e\u0436\u0435\u0442 \u043f\u043e\u043b\u0443\u0447\u0438\u0442\u044c \u043b\u0438\u0431\u043e \u00abcbaabc\u00bb, \u043b\u0438\u0431\u043e \u00ababccba\u00bb). \u041f\u043e\u0441\u043b\u0435 \u043a\u0430\u0436\u0434\u043e\u0439 \u043e\u0448\u0438\u0431\u043a\u0438 \u043f\u0440\u043e\u0446\u0435\u0441\u0441 \u043f\u043e\u0432\u0442\u043e\u0440\u044f\u0435\u0442\u0441\u044f. \u041e\u0434\u043d\u043e \u0438 \u0442\u043e \u0436\u0435 \u043f\u0440\u0430\u0432\u0438\u043b\u043e \u043c\u043e\u0433\u043b\u043e \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u0442\u044c\u0441\u044f \u043d\u0435\u0441\u043a\u043e\u043b\u044c\u043a\u043e \u0440\u0430\u0437 \u0432 \u0440\u0430\u0437\u043b\u0438\u0447\u043d\u044b\u0445 \u0448\u0430\u0433\u0430\u0445 (\u0442\u0430\u043a, \u0432 \u0432\u044b\u0448\u0435\u043f\u0440\u0438\u0432\u0435\u0434\u0451\u043d\u043d\u043e\u043c \u043f\u0440\u0438\u043c\u0435\u0440\u0435 \u0437\u0430 \u0434\u0432\u0430 \u0448\u0430\u0433\u0430 \u043c\u043e\u0433\u043b\u043e \u043f\u043e\u043b\u0443\u0447\u0438\u0442\u044c\u0441\u044f \u00abcbacba\u00bb).<\/p>\n<p>  \u0422\u0440\u0435\u0431\u0443\u0435\u0442\u0441\u044f \u043e\u043f\u0440\u0435\u0434\u0435\u043b\u0438\u0442\u044c, \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 \u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u0442\u0435\u043b\u044c \u043c\u043e\u0433 \u0441\u043e\u0432\u0435\u0440\u0448\u0438\u0442\u044c, \u0435\u0441\u043b\u0438 \u043e\u043d \u0438\u043c\u0435\u043b \u0432 \u0432\u0438\u0434\u0443 \u043e\u0434\u043d\u043e \u0437\u0430\u0434\u0430\u043d\u043d\u043e\u0435 \u0441\u043b\u043e\u0432\u043e, \u0430 \u043d\u0430\u043f\u0438\u0441\u0430\u043b \u0434\u0440\u0443\u0433\u043e\u0435.<\/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<\/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 \u0441\u043e\u0434\u0435\u0440\u0436\u0438\u0442\u0441\u044f \u0441\u043b\u043e\u0432\u043e, \u043a\u043e\u0442\u043e\u0440\u043e\u0435, \u043f\u043e \u043d\u0430\u0448\u0435\u043c\u0443 \u043f\u0440\u0435\u0434\u043f\u043e\u043b\u043e\u0436\u0435\u043d\u0438\u044e, \u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u0442\u0435\u043b\u044c \u0438\u043c\u0435\u043b \u0432 \u0432\u0438\u0434\u0443 (\u043e\u043d\u043e \u0441\u043e\u0441\u0442\u043e\u0438\u0442 \u0438\u0437 \u0431\u0443\u043a\u0432 \u043b\u0430\u0442\u0438\u043d\u0441\u043a\u043e\u0433\u043e \u0430\u043b\u0444\u0430\u0432\u0438\u0442\u0430 \u0432 \u043d\u0438\u0436\u043d\u0435\u043c \u0440\u0435\u0433\u0438\u0441\u0442\u0440\u0435, \u0434\u043b\u0438\u043d\u0430 \u043d\u0435 \u043f\u0440\u0435\u0432\u044b\u0448\u0430\u0435\u0442 20).<\/p>\n<p>  \u0412\u043e \u0432\u0442\u043e\u0440\u043e\u0439 \u0441\u0442\u0440\u043e\u043a\u0435 \u0441\u043e\u0434\u0435\u0440\u0436\u0438\u0442\u0441\u044f \u0441\u043b\u043e\u0432\u043e, \u043a\u043e\u0442\u043e\u0440\u043e\u0435 \u043e\u043d \u043d\u0430 \u0441\u0430\u043c\u043e\u043c \u0434\u0435\u043b\u0435 \u043d\u0430\u043f\u0438\u0441\u0430\u043b (\u043e\u043d\u043e \u0442\u0430\u043a\u0436\u0435 \u0441\u043e\u0441\u0442\u043e\u0438\u0442 \u0438\u0437 \u0431\u0443\u043a\u0432 \u043b\u0430\u0442\u0438\u043d\u0441\u043a\u043e\u0433\u043e \u0430\u043b\u0444\u0430\u0432\u0438\u0442\u0430 \u0432 \u043d\u0438\u0436\u043d\u0435\u043c \u0440\u0435\u0433\u0438\u0441\u0442\u0440\u0435, \u0434\u043b\u0438\u043d\u0430 \u043d\u0435 \u043f\u0440\u0435\u0432\u044b\u0448\u0430\u0435\u0442 20).<\/p>\n<p>  \u0412 \u0442\u0440\u0435\u0442\u044c\u0435\u0439 \u0441\u0442\u0440\u043e\u043a\u0435 \u0441\u043e\u0434\u0435\u0440\u0436\u0438\u0442\u0441\u044f \u0435\u0434\u0438\u043d\u0441\u0442\u0432\u0435\u043d\u043d\u043e\u0435 \u0447\u0438\u0441\u043b\u043e N (N &lt; 50) \u2014 \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e \u0437\u0430\u043c\u0435\u043d, \u043e\u043f\u0438\u0441\u044b\u0432\u0430\u044e\u0449\u0438\u0445 \u0440\u0430\u0437\u043b\u0438\u0447\u043d\u044b\u0435 \u043e\u0448\u0438\u0431\u043a\u0438.<\/p>\n<p>  \u0412 \u0441\u043b\u0435\u0434\u0443\u044e\u0449\u0438\u0445 N \u0441\u0442\u0440\u043e\u043a\u0430\u0445 \u0441\u043e\u0434\u0435\u0440\u0436\u0430\u0442\u0441\u044f \u0432\u043e\u0437\u043c\u043e\u0436\u043d\u044b\u0435 \u0437\u0430\u043c\u0435\u043d\u044b \u0432 \u0444\u043e\u0440\u043c\u0430\u0442\u0435 &amp;lt\u00ab\u043f\u0440\u0430\u0432\u0438\u043b\u044c\u043d\u0430\u044f\u00bb \u043f\u043e\u0441\u043b\u0435\u0434\u043e\u0432\u0430\u0442\u0435\u043b\u044c\u043d\u043e\u0441\u0442\u044c \u0431\u0443\u043a\u0432&amp;gt&lt;\u043f\u0440\u043e\u0431\u0435\u043b&gt;&lt;\u00ab\u043e\u0448\u0438\u0431\u043e\u0447\u043d\u0430\u044f\u00bb \u043f\u043e\u0441\u043b\u0435\u0434\u043e\u0432\u0430\u0442\u0435\u043b\u044c\u043d\u043e\u0441\u0442\u044c \u0431\u0443\u043a\u0432&gt;. \u041f\u043e\u0441\u043b\u0435\u0434\u043e\u0432\u0430\u0442\u0435\u043b\u044c\u043d\u043e\u0441\u0442\u0438 \u0438\u043c\u0435\u044e\u0442 \u0434\u043b\u0438\u043d\u0443 \u043d\u0435 \u0431\u043e\u043b\u0435\u0435 6 \u0441\u0438\u043c\u0432\u043e\u043b\u043e\u0432.<\/p>\n<h4>\u0424\u043e\u0440\u043c\u0430\u0442 \u0432\u044b\u0432\u043e\u0434\u0430<\/h4>\n<p>  \u0422\u0440\u0435\u0431\u0443\u0435\u0442\u0441\u044f \u0432\u044b\u0432\u0435\u0441\u0442\u0438 \u043e\u0434\u043d\u043e \u0447\u0438\u0441\u043b\u043e \u2014 \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, \u043a\u043e\u0442\u043e\u0440\u043e\u0435 \u043c\u043e\u0433 \u0441\u043e\u0432\u0435\u0440\u0448\u0438\u0442\u044c \u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u0442\u0435\u043b\u044c. \u0415\u0441\u043b\u0438 \u044d\u0442\u043e \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e \u043f\u0440\u0435\u0432\u044b\u0448\u0430\u0435\u0442 4 \u0438\u043b\u0438 \u0436\u0435 \u0438\u0437 \u043e\u0434\u043d\u043e\u0433\u043e \u0441\u043b\u043e\u0432\u0430 \u043d\u0435\u0432\u043e\u0437\u043c\u043e\u0436\u043d\u043e \u043f\u043e\u043b\u0443\u0447\u0438\u0442\u044c \u0434\u0440\u0443\u0433\u043e\u0435, \u0441\u043b\u0435\u0434\u0443\u0435\u0442 \u0432\u044b\u0432\u0435\u0441\u0442\u0438 \u20131.<\/p>\n<h4>\u041f\u0440\u0438\u043c\u0435\u0440<\/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>mlax<br \/>  drum<br \/>  50<br \/>  l r<br \/>  mlax gtwt<br \/>  m d<br \/>  mlax ujoc<br \/>  ml pq<br \/>  m f<br \/>  ml bf<br \/>  mlax aruq<br \/>  mlax nqdd<br \/>  mlax fglm<br \/>  mlax bfit<br \/>  mlax mziq<br \/>  mla hlb<br \/>  a u<br \/>  mlax vmpa<br \/>  m w<br \/>  a w<br \/>  ax ok<br \/>  mla kqf<br \/>  m e<br \/>  x x<br \/>  ml if<br \/>  ml gk<br \/>  l e<br \/>  mla xrh<br \/>  m j<br \/>  a c<br \/>  a b<br \/>  m q<br \/>  ax fr<br \/>  ml sb<br \/>  mlax gxxx<br \/>  x m<br \/>  mlax hczx<br \/>  l q<br \/>  la sv<br \/>  l g<br \/>  ax eh<br \/>  lax mjh<br \/>  la ec<br \/>  la pv<br \/>  ml iq<br \/>  a q<br \/>  lax jrs<br \/>  la qn<br \/>  lax bjo<br \/>  l o<br \/>  a z<br \/>  l n<br \/>  a c<\/code><\/td>\n<td><code>4<\/code><\/td>\n<\/tr>\n<\/table>\n<\/div>\n<\/div>\n<\/div>\n<p>  <\/p>\n<h4>\u0420\u0435\u0448\u0435\u043d\u0438\u0435<\/h4>\n<p>  \u041f\u043e\u043f\u0440\u043e\u0431\u0443\u0435\u043c \u0441\u0433\u0435\u043d\u0435\u0440\u0438\u0440\u043e\u0432\u0430\u0442\u044c \u0438\u0437 \u043f\u0440\u0430\u0432\u0438\u043b\u044c\u043d\u043e\u0433\u043e \u043d\u0430\u043f\u0438\u0441\u0430\u043d\u0438\u044f \u0432\u0441\u0435 \u0432\u043e\u0437\u043c\u043e\u0436\u043d\u044b\u0435 \u0441\u043b\u043e\u0432\u0430 \u043d\u0435 \u0431\u043e\u043b\u0435\u0435 \u0447\u0435\u043c \u0441 4 \u043e\u0448\u0438\u0431\u043a\u0430\u043c\u0438. \u0418\u0445 \u0432 \u0445\u0443\u0434\u0448\u0435\u043c \u0441\u043b\u0443\u0447\u0430\u0435 \u043c\u043e\u0436\u0435\u0442 \u0431\u044b\u0442\u044c O((L\ufe52N)<sup>4<\/sup>). \u0412 \u043e\u0433\u0440\u0430\u043d\u0438\u0447\u0435\u043d\u0438\u044f\u0445 \u0437\u0430\u0434\u0430\u0447\u0438 \u044d\u0442\u043e \u0434\u043e\u0432\u043e\u043b\u044c\u043d\u043e \u0431\u043e\u043b\u044c\u0448\u043e\u0435 \u0447\u0438\u0441\u043b\u043e, \u043f\u043e\u044d\u0442\u043e\u043c\u0443 \u043d\u0443\u0436\u043d\u043e \u043f\u0440\u0438\u0434\u0443\u043c\u0430\u0442\u044c, \u043a\u0430\u043a \u0443\u043c\u0435\u043d\u044c\u0448\u0438\u0442\u044c \u0441\u043b\u043e\u0436\u043d\u043e\u0441\u0442\u044c. \u041c\u043e\u0436\u043d\u043e \u0432\u043c\u0435\u0441\u0442\u043e \u044d\u0442\u043e\u0433\u043e \u0432\u043e\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u0442\u044c\u0441\u044f \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u043e\u043c meet-in-the-middle: \u0441\u0433\u0435\u043d\u0435\u0440\u0438\u0440\u043e\u0432\u0430\u0442\u044c \u0441\u043b\u043e\u0432\u0430 \u043d\u0435 \u0431\u043e\u043b\u0435\u0435 \u0447\u0435\u043c c 2 \u043e\u0448\u0438\u0431\u043a\u0430\u043c\u0438, \u0430 \u0442\u0430\u043a\u0436\u0435 \u0441\u043b\u043e\u0432\u0430, \u0438\u0437 \u043a\u043e\u0442\u043e\u0440\u044b\u0445 \u043c\u043e\u0436\u043d\u043e \u043f\u043e\u043b\u0443\u0447\u0438\u0442\u044c \u043d\u0430\u043f\u0438\u0441\u0430\u043d\u043d\u043e\u0435 \u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u0442\u0435\u043b\u0435\u043c \u0441\u043b\u043e\u0432\u043e, \u0441\u0434\u0435\u043b\u0430\u0432 \u043d\u0435 \u0431\u043e\u043b\u0435\u0435 2 \u043e\u0448\u0438\u0431\u043e\u043a. \u0417\u0430\u043c\u0435\u0442\u0438\u043c, \u0447\u0442\u043e \u0440\u0430\u0437\u043c\u0435\u0440 \u043a\u0430\u0436\u0434\u043e\u0433\u043e \u0438\u0437 \u044d\u0442\u0438\u0445 \u043c\u043d\u043e\u0436\u0435\u0441\u0442\u0432 \u043d\u0435 \u0431\u0443\u0434\u0435\u0442 \u043f\u0440\u0435\u0432\u044b\u0448\u0430\u0442\u044c 10<sup>6<\/sup>. \u0415\u0441\u043b\u0438 \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e \u0441\u0434\u0435\u043b\u0430\u043d\u043d\u044b\u0445 \u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u0442\u0435\u043b\u0435\u043c \u043e\u0448\u0438\u0431\u043e\u043a \u043d\u0435 \u043f\u0440\u0435\u0432\u043e\u0441\u0445\u043e\u0434\u0438\u0442 4, \u0442\u043e \u044d\u0442\u0438 \u043c\u043d\u043e\u0436\u0435\u0441\u0442\u0432\u0430 \u0431\u0443\u0434\u0443\u0442 \u043f\u0435\u0440\u0435\u0441\u0435\u043a\u0430\u0442\u044c\u0441\u044f. \u0410\u043d\u0430\u043b\u043e\u0433\u0438\u0447\u043d\u043e \u043c\u043e\u0436\u043d\u043e \u043f\u0440\u043e\u0432\u0435\u0440\u0438\u0442\u044c, \u0447\u0442\u043e \u0447\u0438\u0441\u043b\u043e \u043e\u0448\u0438\u0431\u043e\u043a \u043d\u0435 \u043f\u0440\u0435\u0432\u043e\u0441\u0445\u043e\u0434\u0438\u0442 3, 2 \u0438 1.<\/p>\n<pre><code class=\"cpp\">struct FromTo { \tstd::string from; \tstd::string to; };  std::pair&lt;size_t, std::string&gt; applyRule(const std::string&amp; word, const FromTo &amp;fromTo, int pos) {\t\t \twhile(true) { \t\tint from = word.find(fromTo.from, pos); \t\tif (from == std::string::npos) { \t\t\treturn {std::string::npos, {}}; \t\t} \t\tint to = from + fromTo.from.size(); \t\tauto cpy = word; \t\tfor (int i = from; i &lt; to; i++) { \t\t\tcpy[i] = fromTo.to[i - from]; \t\t} \t\treturn {from, std::move(cpy)}; \t} }  void inverseRules(std::vector&lt;FromTo&gt; &amp;rules) { \tfor (auto&amp; rule: rules) { \t\tstd::swap(rule.from, rule.to); \t} }  int solve(std::string&amp; wordOrig, std::string&amp; wordMissprinted, std::vector&lt;FromTo&gt;&amp; replaces) { \tstd::unordered_map&lt;std::string, int&gt; mapping; \tstd::unordered_map&lt;int, std::string&gt; mappingInverse; \t \tmapping.emplace(wordOrig, 0); \tmappingInverse.emplace(0, wordOrig);  \tmapping.emplace(wordMissprinted, 1); \tmappingInverse.emplace(1, wordMissprinted);  \tstd::unordered_map&lt;int, std::unordered_set&lt;int&gt;&gt; edges;  \tauto buildGraph = [&amp;edges, &amp;mapping, &amp;mappingInverse](int startId, const std::vector&lt;FromTo&gt;&amp; replaces, bool dir) { \t\tstd::unordered_set&lt;int&gt; mappingLayer0;\t \t\tmappingLayer0 = {startId};  \t\tfor (int i = 0; i &lt; 2; i++) { \t\t\tstd::unordered_set&lt;int&gt; mappingLayer1;\t\t\t \t\t\tfor (const auto&amp; v: mappingLayer0) { \t\t\t\tauto&amp; word = mappingInverse.at(v); \t\t\t\tfor (auto&amp; fromTo: replaces) {\t\t\t \t\t\t\t\tsize_t from = 0; \t\t\t\t\twhile (true) { \t\t\t\t\t\tauto [tmp, wordCpy] = applyRule(word, fromTo, from);\t\t\t\t\t\t \t\t\t\t\t\tif (tmp == std::string::npos) { \t\t\t\t\t\t\tbreak; \t\t\t\t\t\t} \t\t\t\t\t\tfrom = tmp + 1;\t\t\t\t\t \t\t\t\t\t\t{ \t\t\t\t\t\t\tint w = mapping.size(); \t\t\t\t\t\t\tmapping.emplace(wordCpy, w); \t\t\t\t\t\t\tw = mapping.at(wordCpy); \t\t\t\t\t\t\tmappingInverse.emplace(w, std::move(wordCpy)); \t\t\t\t\t\t\tif (dir) { \t\t\t\t\t\t\t\tedges[v].emplace(w); \t\t\t\t\t\t\t} else { \t\t\t\t\t\t\t\tedges[w].emplace(v); \t\t\t\t\t\t\t} \t\t\t\t\t\t\tmappingLayer1.emplace(w); \t\t\t\t\t\t} \t\t\t\t\t} \t\t\t\t} \t\t\t} \t\t\tmappingLayer0 = std::move(mappingLayer1); \t\t} \t};  \tbuildGraph(0, replaces, true); \tinverseRules(replaces); \tbuildGraph(1, replaces, false);  \t{ \t\tstd::queue&lt;std::pair&lt;int, int&gt;&gt; q; \t\tq.emplace(0, 0); \t\tstd::vector&lt;bool&gt; mask(mapping.size(), false); \t\tint level{0};  \t\twhile (q.size()) { \t\t\tauto [w, level] = q.front(); \t\t\tq.pop(); \t\t\tif (mask[w]) { \t\t\t\tcontinue; \t\t\t} \t\t\tmask[w] = true;  \t\t\tif (mappingInverse.at(w) == wordMissprinted) { \t\t\t\treturn level; \t\t\t}  \t\t\tfor (auto&amp; v: edges[w]) { \t\t\t\tq.emplace(v, level + 1); \t\t\t} \t\t} \t}  \treturn -1; }<\/code><\/pre>\n<p>  <\/p>\n<h2>B. \u041c\u043d\u043e\u0433\u043e\u0440\u0443\u043a\u0438\u0439 \u0431\u0430\u043d\u0434\u0438\u0442<\/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>64 \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<\/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<\/td>\n<\/tr>\n<\/table>\n<\/div>\n<p>\u042d\u0442\u043e \u0438\u043d\u0442\u0435\u0440\u0430\u043a\u0442\u0438\u0432\u043d\u0430\u044f \u0437\u0430\u0434\u0430\u0447\u0430.<\/p>\n<p>  \u0412\u044b \u0441\u0430\u043c\u0438 \u043d\u0435 \u0437\u043d\u0430\u0435\u0442\u0435 \u043a\u0430\u043a \u0442\u0430\u043a \u0432\u044b\u0448\u043b\u043e, \u043d\u043e \u0432\u044b \u043e\u0431\u043d\u0430\u0440\u0443\u0436\u0438\u043b\u0438 \u0441\u0435\u0431\u044f \u0432 \u0437\u0430\u043b\u0435 \u0441 \u0438\u0433\u0440\u043e\u0432\u044b\u043c\u0438 \u0430\u0432\u0442\u043e\u043c\u0430\u0442\u0430\u043c\u0438 \u0441 \u0446\u0435\u043b\u044b\u043c \u043c\u0435\u0448\u043a\u043e\u043c \u0436\u0435\u0442\u043e\u043d\u043e\u0432. \u041a \u0441\u043e\u0436\u0430\u043b\u0435\u043d\u0438\u044e, \u0432 \u043a\u0430\u0441\u0441\u0435 \u0436\u0435\u0442\u043e\u043d\u044b \u043d\u0430\u0437\u0430\u0434 \u043f\u0440\u0438\u043d\u0438\u043c\u0430\u0442\u044c \u043e\u0442\u043a\u0430\u0437\u044b\u0432\u0430\u044e\u0442\u0441\u044f, \u0438 \u0432\u044b \u0440\u0435\u0448\u0438\u043b\u0438 \u0438\u0441\u043f\u044b\u0442\u0430\u0442\u044c \u0441\u0432\u043e\u044e \u0443\u0434\u0430\u0447\u0443. \u0412 \u0437\u0430\u043b\u0435 \u0435\u0441\u0442\u044c \u043c\u043d\u043e\u0433\u043e \u0430\u0432\u0442\u043e\u043c\u0430\u0442\u043e\u0432, \u0432 \u043a\u043e\u0442\u043e\u0440\u044b\u0435 \u0432\u044b \u043c\u043e\u0436\u0435\u0442\u0435 \u0438\u0433\u0440\u0430\u0442\u044c. \u0414\u043b\u044f \u043e\u0434\u043d\u043e\u0439 \u0438\u0433\u0440\u044b \u0441 \u0430\u0432\u0442\u043e\u043c\u0430\u0442\u043e\u043c \u0432\u044b \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u0435\u0442\u0435 \u043e\u0434\u0438\u043d \u0436\u0435\u0442\u043e\u043d. \u0412 \u0441\u043b\u0443\u0447\u0430\u0435 \u0432\u044b\u0438\u0433\u0440\u044b\u0448\u0430 \u0430\u0432\u0442\u043e\u043c\u0430\u0442 \u0434\u0430\u0451\u0442 \u0432\u0430\u043c \u043e\u0434\u0438\u043d \u0434\u043e\u043b\u043b\u0430\u0440, \u0432 \u0441\u043b\u0443\u0447\u0430\u0435 \u043f\u0440\u043e\u0438\u0433\u0440\u044b\u0448\u0430 \u2014 \u043d\u0438\u0447\u0435\u0433\u043e. \u0423 \u043a\u0430\u0436\u0434\u043e\u0433\u043e \u0430\u0432\u0442\u043e\u043c\u0430\u0442\u0430 \u0435\u0441\u0442\u044c \u0444\u0438\u043a\u0441\u0438\u0440\u043e\u0432\u0430\u043d\u043d\u0430\u044f \u0432\u0435\u0440\u043e\u044f\u0442\u043d\u043e\u0441\u0442\u044c \u0432\u044b\u0438\u0433\u0440\u044b\u0448\u0430 (\u043a\u043e\u0442\u043e\u0440\u0443\u044e \u0432\u044b \u043d\u0435 \u0437\u043d\u0430\u0435\u0442\u0435), \u043d\u043e \u0443 \u0440\u0430\u0437\u043d\u044b\u0445 \u0430\u0432\u0442\u043e\u043c\u0430\u0442\u043e\u0432 \u043e\u043d\u0430 \u0440\u0430\u0437\u043d\u0430\u044f. \u0418\u0437\u0443\u0447\u0438\u0432 \u0441\u0430\u0439\u0442 \u043f\u0440\u043e\u0438\u0437\u0432\u043e\u0434\u0438\u0442\u0435\u043b\u044f \u044d\u0442\u0438\u0445 \u0430\u0432\u0442\u043e\u043c\u0430\u0442\u043e\u0432, \u0432\u044b \u0432\u044b\u044f\u0441\u043d\u0438\u043b\u0438, \u0447\u0442\u043e \u0432\u0435\u0440\u043e\u044f\u0442\u043d\u043e\u0441\u0442\u044c \u0432\u044b\u0438\u0433\u0440\u044b\u0448\u0430 \u0443 \u043a\u0430\u0436\u0434\u043e\u0433\u043e \u0430\u0432\u0442\u043e\u043c\u0430\u0442\u0430 \u0432\u044b\u0431\u0438\u0440\u0430\u0435\u0442\u0441\u044f \u0441\u043b\u0443\u0447\u0430\u0439\u043d\u043e \u043d\u0430 \u044d\u0442\u0430\u043f\u0435 \u0438\u0437\u0433\u043e\u0442\u043e\u0432\u043b\u0435\u043d\u0438\u044f \u0438\u0437 <a href=\"https:\/\/ru.wikipedia.org\/wiki\/%D0%91%D0%B5%D1%82%D0%B0-%D1%80%D0%B0%D1%81%D0%BF%D1%80%D0%B5%D0%B4%D0%B5%D0%BB%D0%B5%D0%BD%D0%B8%D0%B5\">\u0431\u0435\u0442\u0430-\u0440\u0430\u0441\u043f\u0440\u0435\u0434\u0435\u043b\u0435\u043d\u0438\u044f<\/a> \u0441 \u043e\u043f\u0440\u0435\u0434\u0435\u043b\u0451\u043d\u043d\u044b\u043c\u0438 \u043f\u0430\u0440\u0430\u043c\u0435\u0442\u0440\u0430\u043c\u0438.<\/p>\n<p>  \u0412\u0430\u043c \u0445\u043e\u0447\u0435\u0442\u0441\u044f \u043c\u0430\u043a\u0441\u0438\u043c\u0438\u0437\u0438\u0440\u043e\u0432\u0430\u0442\u044c \u0441\u0432\u043e\u0439 \u043e\u0436\u0438\u0434\u0430\u0435\u043c\u044b\u0439 \u0432\u044b\u0438\u0433\u0440\u044b\u0448.<\/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<\/b><\/p>\n<div class=\"spoiler_text\">\n<h4>\u0424\u043e\u0440\u043c\u0430\u0442 \u0432\u0432\u043e\u0434\u0430<\/h4>\n<p>  \u041e\u0434\u043d\u043e \u0438\u0441\u043f\u043e\u043b\u043d\u0435\u043d\u0438\u0435 \u043c\u043e\u0436\u0435\u0442 \u0441\u043e\u0441\u0442\u043e\u044f\u0442\u044c \u0438\u0437 \u043d\u0435\u0441\u043a\u043e\u043b\u044c\u043a\u0438\u0445 \u0442\u0435\u0441\u0442\u043e\u0432.<\/p>\n<p>  \u041a\u0430\u0436\u0434\u044b\u0439 \u0442\u0435\u0441\u0442 \u043d\u0430\u0447\u0438\u043d\u0430\u0435\u0442\u0441\u044f \u0441 \u0442\u043e\u0433\u043e, \u0447\u0442\u043e \u0432\u0430\u0448\u0435\u0439 \u043f\u0440\u043e\u0433\u0440\u0430\u043c\u043c\u0435 \u0432 \u043e\u0434\u043d\u043e\u0439 \u0441\u0442\u0440\u043e\u043a\u0435 \u043f\u043e\u0434\u0430\u044e\u0442\u0441\u044f \u0434\u0432\u0430 \u0446\u0435\u043b\u044b\u0445 \u0447\u0438\u0441\u043b\u0430, \u0440\u0430\u0437\u0434\u0435\u043b\u0451\u043d\u043d\u044b\u0435 \u043f\u0440\u043e\u0431\u0435\u043b\u043e\u043c: \u0447\u0438\u0441\u043b\u043e N \u2014 \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e \u0436\u0435\u0442\u043e\u043d\u043e\u0432 \u0432 \u0432\u0430\u0448\u0435\u043c \u043c\u0435\u0448\u043a\u0435, \u0438 M \u2014 \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e \u0430\u0432\u0442\u043e\u043c\u0430\u0442\u043e\u0432 \u0432 \u0437\u0430\u043b\u0435 (N \u2264 10<sup>4<\/sup>, M \u2264 min(N, 100)). \u0412 \u0441\u043b\u0435\u0434\u0443\u044e\u0449\u0435\u0439 \u0441\u0442\u0440\u043e\u043a\u0435 \u0441\u043e\u0434\u0435\u0440\u0436\u0430\u0442\u0441\u044f \u0434\u0432\u0430 \u0432\u0435\u0449\u0435\u0441\u0442\u0432\u0435\u043d\u043d\u044b\u0445 \u0447\u0438\u0441\u043b\u0430 \u03b1 \u0438 \u03b2 (1 \u2264 \u03b1, \u03b2 \u2264 10) \u2014 \u043f\u0430\u0440\u0430\u043c\u0435\u0442\u0440\u044b \u0431\u0435\u0442\u0430-\u0440\u0430\u0441\u043f\u0440\u0435\u0434\u0435\u043b\u0435\u043d\u0438\u044f \u0432\u0435\u0440\u043e\u044f\u0442\u043d\u043e\u0441\u0442\u0438 \u0432\u044b\u0438\u0433\u0440\u044b\u0448\u0430.<\/p>\n<p>  \u041f\u0440\u043e\u0442\u043e\u043a\u043e\u043b \u043e\u0431\u0449\u0435\u043d\u0438\u044f \u0441 \u043f\u0440\u043e\u0432\u0435\u0440\u044f\u044e\u0449\u0435\u0439 \u0441\u0438\u0441\u0442\u0435\u043c\u043e\u0439 \u0442\u0430\u043a\u043e\u0439: \u0432\u044b \u0434\u0435\u043b\u0430\u0435\u0442\u0435 \u0440\u043e\u0432\u043d\u043e N \u0437\u0430\u043f\u0440\u043e\u0441\u043e\u0432. \u041d\u0430 \u043a\u0430\u0436\u0434\u044b\u0439 \u0437\u0430\u043f\u0440\u043e\u0441 \u0432\u044b\u0432\u0435\u0434\u0438\u0442\u0435 \u0432 \u043e\u0442\u0434\u0435\u043b\u044c\u043d\u0443\u044e \u0441\u0442\u0440\u043e\u043a\u0443 \u043d\u043e\u043c\u0435\u0440 \u0430\u0432\u0442\u043e\u043c\u0430\u0442\u0430, \u0432 \u043a\u043e\u0442\u043e\u0440\u044b\u0439 \u0432\u044b \u0431\u0443\u0434\u0435\u0442\u0435 \u0438\u0433\u0440\u0430\u0442\u044c (\u043e\u0442 1 \u0434\u043e M \u0432\u043a\u043b\u044e\u0447\u0438\u0442\u0435\u043b\u044c\u043d\u043e). \u0412 \u043a\u0430\u0447\u0435\u0441\u0442\u0432\u0435 \u043e\u0442\u0432\u0435\u0442\u0430 \u0432 \u043e\u0442\u0434\u0435\u043b\u044c\u043d\u043e\u0439 \u0441\u0442\u0440\u043e\u043a\u0435 \u0431\u0443\u0434\u0435\u0442 \u0441\u0442\u043e\u044f\u0442\u044c \u043b\u0438\u0431\u043e \u00ab0\u00bb, \u043b\u0438\u0431\u043e \u00ab1\u00bb, \u043e\u0437\u043d\u0430\u0447\u0430\u044e\u0449\u0438\u0435 \u0441\u043e\u043e\u0442\u0432\u0435\u0442\u0441\u0442\u0432\u0435\u043d\u043d\u043e \u043f\u0440\u043e\u0438\u0433\u0440\u044b\u0448 \u0438 \u0432\u044b\u0438\u0433\u0440\u044b\u0448 \u0432 \u0438\u0433\u0440\u0435 \u0441 \u0437\u0430\u043f\u0440\u043e\u0448\u0435\u043d\u043d\u044b\u043c \u0430\u0432\u0442\u043e\u043c\u0430\u0442\u043e\u043c.<\/p>\n<p>  \u041f\u043e\u0441\u043b\u0435 \u043f\u043e\u0441\u043b\u0435\u0434\u043d\u0435\u0433\u043e \u0442\u0435\u0441\u0442\u0430 \u0432\u043c\u0435\u0441\u0442\u043e \u0447\u0438\u0441\u0435\u043b N \u0438 M \u0431\u0443\u0434\u0443\u0442 \u0441\u0442\u043e\u044f\u0442\u044c \u0434\u0432\u0430 \u043d\u0443\u043b\u044f.<\/p>\n<h4>\u0424\u043e\u0440\u043c\u0430\u0442 \u0432\u044b\u0432\u043e\u0434\u0430<\/h4>\n<p>  \u0417\u0430\u0434\u0430\u0447\u0430 \u0431\u0443\u0434\u0435\u0442 \u0441\u0447\u0438\u0442\u0430\u0442\u044c\u0441\u044f \u0441\u0434\u0430\u043d\u043d\u043e\u0439, \u0435\u0441\u043b\u0438 \u0432\u0430\u0448\u0435 \u0440\u0435\u0448\u0435\u043d\u0438\u0435 \u043d\u0435 \u0441\u0438\u043b\u044c\u043d\u043e \u0445\u0443\u0436\u0435 \u0440\u0435\u0448\u0435\u043d\u0438\u044f \u0436\u044e\u0440\u0438. \u0415\u0441\u043b\u0438 \u0432\u0430\u0448\u0435 \u0440\u0435\u0448\u0435\u043d\u0438\u0435 \u0431\u0443\u0434\u0435\u0442 \u0437\u043d\u0430\u0447\u0438\u0442\u0435\u043b\u044c\u043d\u043e \u0445\u0443\u0436\u0435 \u0440\u0435\u0448\u0435\u043d\u0438\u044f \u0436\u044e\u0440\u0438, \u0432\u044b \u043f\u043e\u043b\u0443\u0447\u0438\u0442\u0435 \u0432\u0435\u0440\u0434\u0438\u043a\u0442 \u00ab\u043d\u0435\u043f\u0440\u0430\u0432\u0438\u043b\u044c\u043d\u044b\u0439 \u043e\u0442\u0432\u0435\u0442\u00bb.<\/p>\n<p>  \u0413\u0430\u0440\u0430\u043d\u0442\u0438\u0440\u0443\u0435\u0442\u0441\u044f, \u0447\u0442\u043e \u0435\u0441\u043b\u0438 \u0432\u0430\u0448\u0435 \u0440\u0435\u0448\u0435\u043d\u0438\u0435 \u043d\u0435 \u0445\u0443\u0436\u0435, \u0447\u0435\u043c \u0440\u0435\u0448\u0435\u043d\u0438\u0435 \u0436\u044e\u0440\u0438, \u0442\u043e \u0432\u0435\u0440\u043e\u044f\u0442\u043d\u043e\u0441\u0442\u044c \u043f\u043e\u043b\u0443\u0447\u0438\u0442\u044c \u0432\u0435\u0440\u0434\u0438\u043a\u0442 \u00ab\u043d\u0435\u043f\u0440\u0430\u0432\u0438\u043b\u044c\u043d\u044b\u0439 \u043e\u0442\u0432\u0435\u0442\u00bb \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\u0447\u0430\u043d\u0438\u044f<\/h4>\n<p>  \u041f\u0440\u0438\u043c\u0435\u0440 \u0432\u0437\u0430\u0438\u043c\u043e\u0434\u0435\u0439\u0441\u0442\u0432\u0438\u044f:<\/p>\n<pre><code class=\"cpp\">____________________ \u00a0\u00a0stdin\u00a0\u00a0\u00a0\u00a0\u00a0stdout ____________________ ____________________ \u00a0\u00a0\u00a05 2\t \u00a0\u00a0\u00a02 2\t \u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a02 \u00a0\u00a0\u00a0\u00a01\t \u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a01 \u00a0\u00a0\u00a0\u00a00\t \u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a01 \u00a0\u00a0\u00a0\u00a01\t \u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a02 \u00a0\u00a0\u00a0\u00a01 \u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a02 \u00a0\u00a0\u00a0\u00a01<\/code><\/pre>\n<\/div>\n<\/div>\n<p>  <\/p>\n<h4>\u0420\u0435\u0448\u0435\u043d\u0438\u0435<\/h4>\n<p>  \u042d\u0442\u0430 \u0437\u0430\u0434\u0430\u0447\u0430 \u0434\u043e\u0441\u0442\u0430\u0442\u043e\u0447\u043d\u043e \u0438\u0437\u0432\u0435\u0441\u0442\u043d\u0430, \u0435\u0451 \u043c\u043e\u0436\u043d\u043e \u0431\u044b\u043b\u043e \u0440\u0435\u0448\u0430\u0442\u044c \u043f\u043e-\u0440\u0430\u0437\u043d\u043e\u043c\u0443. \u041e\u0441\u043d\u043e\u0432\u043d\u043e\u0435 \u0440\u0435\u0448\u0435\u043d\u0438\u0435 \u0436\u044e\u0440\u0438 \u0440\u0435\u0430\u043b\u0438\u0437\u043e\u0432\u044b\u0432\u0430\u043b\u043e \u0441\u0442\u0440\u0430\u0442\u0435\u0433\u0438\u044e <a href=\"https:\/\/en.wikipedia.org\/wiki\/Thompson_sampling\">Thompson sampling<\/a>, \u043d\u043e \u043f\u043e\u0441\u043a\u043e\u043b\u044c\u043a\u0443 \u0447\u0438\u0441\u043b\u043e \u0448\u0430\u0433\u043e\u0432 \u0431\u044b\u043b\u043e \u0438\u0437\u0432\u0435\u0441\u0442\u043d\u043e \u0432 \u043d\u0430\u0447\u0430\u043b\u0435 \u0440\u0430\u0431\u043e\u0442\u044b \u043f\u0440\u043e\u0433\u0440\u0430\u043c\u043c\u044b, \u0441\u0443\u0449\u0435\u0441\u0442\u0432\u0443\u044e\u0442 \u0438 \u0431\u043e\u043b\u0435\u0435 \u043e\u043f\u0442\u0438\u043c\u0430\u043b\u044c\u043d\u044b\u0435 \u0441\u0442\u0440\u0430\u0442\u0435\u0433\u0438\u0438 (\u043d\u0430\u043f\u0440\u0438\u043c\u0435\u0440, UCB1). \u0411\u043e\u043b\u0435\u0435 \u0442\u043e\u0433\u043e, \u043c\u043e\u0436\u043d\u043e \u0431\u044b\u043b\u043e \u0434\u0430\u0436\u0435 \u043e\u0431\u043e\u0439\u0442\u0438\u0441\u044c epsilon-greedy-\u0441\u0442\u0440\u0430\u0442\u0435\u0433\u0438\u0435\u0439: \u0441 \u043d\u0435\u043a\u043e\u0442\u043e\u0440\u043e\u0439 \u0432\u0435\u0440\u043e\u044f\u0442\u043d\u043e\u0441\u0442\u044c\u044e \u03b5 \u0438\u0433\u0440\u0430\u0442\u044c \u0432 \u0441\u043b\u0443\u0447\u0430\u0439\u043d\u044b\u0439 \u0430\u0432\u0442\u043e\u043c\u0430\u0442 \u0438 \u0441 \u0432\u0435\u0440\u043e\u044f\u0442\u043d\u043e\u0441\u0442\u044c\u044e (1 \u2013 \u03b5) \u0438\u0433\u0440\u0430\u0442\u044c \u0432 \u0430\u0432\u0442\u043e\u043c\u0430\u0442, \u0443 \u043a\u043e\u0442\u043e\u0440\u043e\u0433\u043e \u0441\u0442\u0430\u0442\u0438\u0441\u0442\u0438\u043a\u0430 \u043f\u043e\u0431\u0435\u0434 \u043b\u0443\u0447\u0448\u0435 \u0432\u0441\u0435\u0433\u043e.<\/p>\n<pre><code class=\"python\">class SolverFromStdIn(object):     def __init__(self):         self.regrets = [0.]         self.total_win = [0.]         self.moves = []   class ThompsonSampling(SolverFromStdIn):     def __init__(self, bandits_total, init_a=1, init_b=1):         \"\"\"         init_a (int): initial value of a in Beta(a, b).         init_b (int): initial value of b in Beta(a, b).         \"\"\"          SolverFromStdIn.__init__(self)         self.n = bandits_total          self.alpha = init_a         self.beta = init_b          self._as = [init_a] * self.n # [random.betavariate(self.alpha, self.beta) for _ in range(self.n)]         self._bs = [init_b] * self.n # [random.betavariate(self.alpha, self.beta) for _ in range(self.n)]         self.last_move = -1         random.seed(int(time.time()))      def move(self):         samples = [random.betavariate(self._as[x], self._bs[x]) for x in range(self.n)]         self.last_move = max(range(self.n), key=lambda x: samples[x])          self.moves.append(self.last_move)         return self.last_move      def set_reward(self, reward):         i = self.last_move         r = reward          self._as[i] += r         self._bs[i] += (1 - r)                  return i, r  while True:     n, m = map(int, sys.stdin.readline().split())      if n == 0 and m == 0:         break              alpha, beta = map(float, sys.stdin.readline().split())     solver = ThompsonSampling(m)      for _ in range(n):         print &gt;&gt; sys.stdout, solver.move() + 1         sys.stdout.flush()         reward = int(sys.stdin.readline())         solver.set_reward(reward)<\/code><\/pre>\n<p>  <\/p>\n<h2>C. \u0412\u044b\u0440\u0430\u0432\u043d\u0438\u0432\u0430\u043d\u0438\u0435 \u043f\u0440\u0435\u0434\u043b\u043e\u0436\u0435\u043d\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>\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>64 \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>\u041e\u0434\u043d\u0430 \u0438\u0437 \u0432\u0430\u0436\u043d\u0435\u0439\u0448\u0438\u0445 \u0437\u0430\u0434\u0430\u0447 \u0434\u043b\u044f \u043e\u0431\u0443\u0447\u0435\u043d\u0438\u044f \u0445\u043e\u0440\u043e\u0448\u0435\u0439 \u043c\u043e\u0434\u0435\u043b\u0438 \u043c\u0430\u0448\u0438\u043d\u043d\u043e\u0433\u043e \u043f\u0435\u0440\u0435\u0432\u043e\u0434\u0430 \u2014 \u0445\u043e\u0440\u043e\u0448\u0438\u0439 \u043a\u043e\u0440\u043f\u0443\u0441 \u043f\u0430\u0440\u0430\u043b\u043b\u0435\u043b\u044c\u043d\u044b\u0445 \u043f\u0440\u0435\u0434\u043b\u043e\u0436\u0435\u043d\u0438\u0439. \u041e\u0431\u044b\u0447\u043d\u043e \u0438\u0441\u0442\u043e\u0447\u043d\u0438\u043a\u043e\u043c \u0434\u043b\u044f \u043f\u0430\u0440\u0430\u043b\u043b\u0435\u043b\u044c\u043d\u044b\u0445 \u043f\u0440\u0435\u0434\u043b\u043e\u0436\u0435\u043d\u0438\u0439 \u044f\u0432\u043b\u044f\u044e\u0442\u0441\u044f \u043f\u0430\u0440\u0430\u043b\u043b\u0435\u043b\u044c\u043d\u044b\u0435 \u0434\u043e\u043a\u0443\u043c\u0435\u043d\u0442\u044b. \u041e\u043a\u0430\u0437\u044b\u0432\u0430\u0435\u0442\u0441\u044f, \u0447\u0430\u0441\u0442\u043e \u0434\u043b\u044f \u0442\u043e\u0433\u043e, \u0447\u0442\u043e\u0431\u044b \u043f\u043e\u0441\u0442\u0440\u043e\u0438\u0442\u044c \u043d\u0435\u043a\u043e\u0442\u043e\u0440\u044b\u0439 \u043a\u043e\u0440\u043f\u0443\u0441 \u043f\u0430\u0440\u0430\u043b\u043b\u0435\u043b\u044c\u043d\u044b\u0445 \u043f\u0440\u0435\u0434\u043b\u043e\u0436\u0435\u043d\u0438\u0439, \u043d\u0435 \u043d\u0443\u0436\u043d\u043e \u0437\u043d\u0430\u0442\u044c \u043d\u0438\u0447\u0435\u0433\u043e, \u043a\u0440\u043e\u043c\u0435 \u0438\u0445 \u0434\u043b\u0438\u043d. \u0412 \u0447\u0430\u0441\u0442\u043d\u043e\u0441\u0442\u0438, \u043c\u043e\u0436\u043d\u043e \u0437\u0430\u043c\u0435\u0442\u0438\u0442\u044c, \u0447\u0442\u043e \u0447\u0435\u043c \u0434\u043b\u0438\u043d\u0435\u0435 \u043f\u0440\u0435\u0434\u043b\u043e\u0436\u0435\u043d\u0438\u0435 \u043d\u0430 \u0438\u0441\u0445\u043e\u0434\u043d\u043e\u043c \u044f\u0437\u044b\u043a\u0435, \u0442\u0435\u043c \u0434\u043b\u0438\u043d\u0435\u0435, \u0441\u043a\u043e\u0440\u0435\u0435 \u0432\u0441\u0435\u0433\u043e, \u0431\u0443\u0434\u0435\u0442 \u0435\u0433\u043e \u043f\u0435\u0440\u0435\u0432\u043e\u0434. \u041d\u0435\u043a\u043e\u0442\u043e\u0440\u0430\u044f \u0441\u043b\u043e\u0436\u043d\u043e\u0441\u0442\u044c \u0441\u043e\u0441\u0442\u043e\u0438\u0442 \u0432 \u0442\u043e\u043c, \u0447\u0442\u043e \u043f\u0440\u0438 \u043f\u0435\u0440\u0435\u0432\u043e\u0434\u0435 \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e \u043f\u0440\u0435\u0434\u043b\u043e\u0436\u0435\u043d\u0438\u0439 \u0432 \u0442\u0435\u043a\u0441\u0442\u0435 \u043c\u043e\u0436\u0435\u0442 \u043f\u043e\u043c\u0435\u043d\u044f\u0442\u044c\u0441\u044f: \u0438\u043d\u043e\u0433\u0434\u0430 \u0434\u0432\u0430 \u0441\u043e\u0441\u0435\u0434\u043d\u0438\u0445 \u043f\u0440\u0435\u0434\u043b\u043e\u0436\u0435\u043d\u0438\u044f \u043f\u0440\u0438 \u043f\u0435\u0440\u0435\u0432\u043e\u0434\u0435 \u043c\u043e\u0433\u0443\u0442 \u0431\u044b\u0442\u044c \u043e\u0431\u044a\u0435\u0434\u0438\u043d\u0435\u043d\u044b \u0432 \u043e\u0434\u043d\u043e, \u0438\u043b\u0438 \u043d\u0430\u043e\u0431\u043e\u0440\u043e\u0442 \u2014 \u043e\u0434\u043d\u043e \u043f\u0440\u0435\u0434\u043b\u043e\u0436\u0435\u043d\u0438\u0435 \u043c\u043e\u0433\u043b\u043e \u0431\u044b\u0442\u044c \u0440\u0430\u0437\u0434\u0435\u043b\u0435\u043d\u043e \u043d\u0430 \u0434\u0432\u0430. \u0412 \u043e\u0442\u0434\u0435\u043b\u044c\u043d\u044b\u0445 \u0440\u0435\u0434\u043a\u0438\u0445 \u0441\u043b\u0443\u0447\u0430\u044f\u0445 \u043f\u0440\u0435\u0434\u043b\u043e\u0436\u0435\u043d\u0438\u044f \u043c\u043e\u0433\u0443\u0442 \u0446\u0435\u043b\u0438\u043a\u043e\u043c \u043f\u0440\u043e\u043f\u0443\u0441\u043a\u0430\u0442\u044c\u0441\u044f \u0432 \u043f\u0435\u0440\u0435\u0432\u043e\u0434\u0435, \u0438\u043b\u0438 \u0432 \u043f\u0435\u0440\u0435\u0432\u043e\u0434\u0435 \u043c\u043e\u0436\u0435\u0442 \u043f\u043e\u044f\u0432\u0438\u0442\u044c\u0441\u044f \u043f\u0440\u0435\u0434\u043b\u043e\u0436\u0435\u043d\u0438\u0435, \u043a\u043e\u0442\u043e\u0440\u043e\u0433\u043e \u043d\u0435 \u0431\u044b\u043b\u043e \u0432 \u043e\u0440\u0438\u0433\u0438\u043d\u0430\u043b\u0435.<\/p>\n<p>  \u0411\u043e\u043b\u0435\u0435 \u0444\u043e\u0440\u043c\u0430\u043b\u044c\u043d\u043e, \u043f\u0440\u0435\u0434\u043f\u043e\u043b\u043e\u0436\u0438\u043c, \u0447\u0442\u043e \u0432\u0435\u0440\u043d\u0430 \u0441\u043b\u0435\u0434\u0443\u044e\u0449\u0430\u044f \u0433\u0435\u043d\u0435\u0440\u0430\u0442\u0438\u0432\u043d\u0430\u044f \u043c\u043e\u0434\u0435\u043b\u044c \u0434\u043b\u044f \u043f\u0430\u0440\u0430\u043b\u043b\u0435\u043b\u044c\u043d\u044b\u0445 \u043a\u043e\u0440\u043f\u0443\u0441\u043e\u0432. \u041d\u0430 \u043a\u0430\u0436\u0434\u043e\u043c \u0448\u0430\u0433\u0435 \u043c\u044b \u0441\u043e\u0432\u0435\u0440\u0448\u0430\u0435\u043c \u043e\u0434\u043d\u043e \u0438\u0437 \u0441\u043b\u0435\u0434\u0443\u044e\u0449\u0438\u0445 \u0434\u0435\u0439\u0441\u0442\u0432\u0438\u0439:<\/p>\n<p>  <b>1. <i>\u041e\u0441\u0442\u0430\u043d\u043e\u0432\u043a\u0430<\/i><\/b><\/p>\n<p>  \u0421 \u0432\u0435\u0440\u043e\u044f\u0442\u043d\u043e\u0441\u0442\u044c\u044e p<sub>h<\/sub> \u0433\u0435\u043d\u0435\u0440\u0430\u0446\u0438\u044f \u043a\u043e\u0440\u043f\u0443\u0441\u043e\u0432 \u0437\u0430\u043a\u0430\u043d\u0447\u0438\u0432\u0430\u0435\u0442\u0441\u044f.<\/p>\n<p>  <b>2. [1-0] <i>\u041f\u0440\u043e\u043f\u0443\u0441\u043a \u043f\u0440\u0435\u0434\u043b\u043e\u0436\u0435\u043d\u0438\u044f<\/i><\/b><\/p>\n<p>  \u0421 \u0432\u0435\u0440\u043e\u044f\u0442\u043d\u043e\u0441\u0442\u044c\u044e p<sub>d<\/sub> \u043f\u0440\u0438\u043f\u0438\u0441\u044b\u0432\u0430\u0435\u043c \u0432 \u043e\u0440\u0438\u0433\u0438\u043d\u0430\u043b\u044c\u043d\u044b\u0439 \u0442\u0435\u043a\u0441\u0442 \u043e\u0434\u043d\u043e \u043f\u0440\u0435\u0434\u043b\u043e\u0436\u0435\u043d\u0438\u0435. \u0412 \u043f\u0435\u0440\u0435\u0432\u043e\u0434 \u043d\u0435 \u043f\u0440\u0438\u043f\u0438\u0441\u044b\u0432\u0430\u0435\u043c \u043d\u0438\u0447\u0435\u0433\u043e. \u0414\u043b\u0438\u043d\u0430 \u043f\u0440\u0435\u0434\u043b\u043e\u0436\u0435\u043d\u0438\u044f \u043d\u0430 \u044f\u0437\u044b\u043a\u0435 \u043e\u0440\u0438\u0433\u0438\u043d\u0430\u043b\u0430 L \u2265 1 \u0432\u044b\u0431\u0438\u0440\u0430\u0435\u0442\u0441\u044f \u0438\u0437 \u0434\u0438\u0441\u043a\u0440\u0435\u0442\u043d\u043e\u0433\u043e \u0440\u0430\u0441\u043f\u0440\u0435\u0434\u0435\u043b\u0435\u043d\u0438\u044f:<\/p>\n<p>  <img decoding=\"async\" src=\"https:\/\/habrastorage.org\/webt\/bm\/pe\/t_\/bmpet_y_ksvwgbohazpgctekbks.png\" width=\"350\">.<\/p>\n<p>  \u0417\u0434\u0435\u0441\u044c <i>\u03bc<sub>s<\/sub><\/i>, <i>\u03c3<sub>s<\/sub><\/i> \u2014 \u043f\u0430\u0440\u0430\u043c\u0435\u0442\u0440\u044b \u0440\u0430\u0441\u043f\u0440\u0435\u0434\u0435\u043b\u0435\u043d\u0438\u044f, \u0430 <i>\u03b1<sub>s<\/sub><\/i> \u2014 \u043d\u043e\u0440\u043c\u0438\u0440\u043e\u0432\u043e\u0447\u043d\u044b\u0439 \u043a\u043e\u044d\u0444\u0444\u0438\u0446\u0438\u0435\u043d\u0442, \u0432\u044b\u0431\u0438\u0440\u0430\u0435\u043c\u044b\u0439 \u0442\u0430\u043a, \u0447\u0442\u043e\u0431\u044b <img decoding=\"async\" src=\"https:\/\/habrastorage.org\/webt\/fm\/ae\/ns\/fmaensnvy1nauvywiluibhryr6s.png\" width=\"100\">.<\/p>\n<p>  <b>3. [0-1] <i>\u0412\u0441\u0442\u0430\u0432\u043a\u0430 \u043f\u0440\u0435\u0434\u043b\u043e\u0436\u0435\u043d\u0438\u044f<\/i><\/b><\/p>\n<p>  \u0421 \u0432\u0435\u0440\u043e\u044f\u0442\u043d\u043e\u0441\u0442\u044c\u044e p<sub>i<\/sub> \u043f\u0440\u0438\u043f\u0438\u0441\u044b\u0432\u0430\u0435\u043c \u0432 \u043f\u0435\u0440\u0435\u0432\u043e\u0434 \u043e\u0434\u043d\u043e \u043f\u0440\u0435\u0434\u043b\u043e\u0436\u0435\u043d\u0438\u0435. \u0412 \u043e\u0440\u0438\u0433\u0438\u043d\u0430\u043b \u043d\u0435 \u043f\u0440\u0438\u043f\u0438\u0441\u044b\u0432\u0430\u0435\u043c \u043d\u0438\u0447\u0435\u0433\u043e. \u0414\u043b\u0438\u043d\u0430 \u043f\u0440\u0435\u0434\u043b\u043e\u0436\u0435\u043d\u0438\u044f \u043d\u0430 \u044f\u0437\u044b\u043a\u0435 \u043f\u0435\u0440\u0435\u0432\u043e\u0434\u0430 L \u2265 1 \u0432\u044b\u0431\u0438\u0440\u0430\u0435\u0442\u0441\u044f \u0438\u0437 \u0434\u0438\u0441\u043a\u0440\u0435\u0442\u043d\u043e\u0433\u043e \u0440\u0430\u0441\u043f\u0440\u0435\u0434\u0435\u043b\u0435\u043d\u0438\u044f:<\/p>\n<p>  <img decoding=\"async\" src=\"https:\/\/habrastorage.org\/webt\/yl\/yn\/kr\/ylynkr3cs_t7dpedebtzqj3uryk.png\" width=\"350\">.<\/p>\n<p>  \u0417\u0434\u0435\u0441\u044c <i>\u03bc<sub>t<\/sub><\/i>, <i>\u03c3<sub>t<\/sub><\/i> \u2014 \u043f\u0430\u0440\u0430\u043c\u0435\u0442\u0440\u044b \u0440\u0430\u0441\u043f\u0440\u0435\u0434\u0435\u043b\u0435\u043d\u0438\u044f, \u0430 <i>\u03b1<sub>t<\/sub><\/i> \u2014 \u043d\u043e\u0440\u043c\u0438\u0440\u043e\u0432\u043e\u0447\u043d\u044b\u0439 \u043a\u043e\u044d\u0444\u0444\u0438\u0446\u0438\u0435\u043d\u0442, \u0432\u044b\u0431\u0438\u0440\u0430\u0435\u043c\u044b\u0439 \u0442\u0430\u043a, \u0447\u0442\u043e\u0431\u044b <img decoding=\"async\" src=\"https:\/\/habrastorage.org\/webt\/bq\/-k\/p3\/bq-kp37k-c-k5fpq9jrz4r8rkvy.png\" width=\"100\">.<\/p>\n<p>  <b>4. <i>\u041f\u0435\u0440\u0435\u0432\u043e\u0434<\/i><\/b><\/p>\n<p>  \u0421 \u0432\u0435\u0440\u043e\u044f\u0442\u043d\u043e\u0441\u0442\u044c\u044e (1 \u2013 p<sub>d<\/sub> \u2013 p<sub>i<\/sub> \u2013 p<sub>h<\/sub>) \u0431\u0435\u0440\u0451\u043c \u0434\u043b\u0438\u043d\u0443 \u043f\u0440\u0435\u0434\u043b\u043e\u0436\u0435\u043d\u0438\u044f \u043d\u0430 \u044f\u0437\u044b\u043a\u0435 \u043e\u0440\u0438\u0433\u0438\u043d\u0430\u043b\u0430 L<sub>s<\/sub> \u2265 1 \u0438\u0437 \u0440\u0430\u0441\u043f\u0440\u0435\u0434\u0435\u043b\u0435\u043d\u0438\u044f p<sub>s<\/sub> (\u0441 \u043e\u043a\u0440\u0443\u0433\u043b\u0435\u043d\u0438\u0435\u043c \u0432\u0432\u0435\u0440\u0445). \u0414\u0430\u043b\u0435\u0435 \u0433\u0435\u043d\u0435\u0440\u0438\u0440\u0443\u0435\u043c \u0434\u043b\u0438\u043d\u0443 \u043f\u0440\u0435\u0434\u043b\u043e\u0436\u0435\u043d\u0438\u044f \u043d\u0430 \u044f\u0437\u044b\u043a\u0435 \u043f\u0435\u0440\u0435\u0432\u043e\u0434\u0430 L<sub>t<\/sub> \u2265 1 \u0438\u0437 \u0443\u0441\u043b\u043e\u0432\u043d\u043e\u0433\u043e \u0434\u0438\u0441\u043a\u0440\u0435\u0442\u043d\u043e\u0433\u043e \u0440\u0430\u0441\u043f\u0440\u0435\u0434\u0435\u043b\u0435\u043d\u0438\u044f:<\/p>\n<p>  <img decoding=\"async\" src=\"https:\/\/habrastorage.org\/webt\/ae\/b6\/mx\/aeb6mx4cols1jplbs-di9emhxf8.png\" width=\"500\">.<\/p>\n<p>  \u0417\u0434\u0435\u0441\u044c <i>\u03b1<sub>st<\/sub><\/i> \u2014 \u043d\u043e\u0440\u043c\u0438\u0440\u043e\u0432\u043e\u0447\u043d\u044b\u0439 \u043a\u043e\u044d\u0444\u0444\u0438\u0446\u0438\u0435\u043d\u0442, \u0430 \u043e\u0441\u0442\u0430\u043b\u044c\u043d\u044b\u0435 \u043f\u0430\u0440\u0430\u043c\u0435\u0442\u0440\u044b \u043e\u043f\u0438\u0441\u0430\u043d\u044b \u0432 \u043f\u0440\u0435\u0434\u044b\u0434\u0443\u0449\u0438\u0445 \u043f\u0443\u043d\u043a\u0442\u0430\u0445.<\/p>\n<p>  \u0414\u0430\u043b\u0435\u0435 \u043f\u0440\u043e\u0438\u0441\u0445\u043e\u0434\u0438\u0442 \u0435\u0449\u0451 \u043e\u0434\u0438\u043d \u0448\u0430\u0433:<\/p>\n<p>  1. [2-1] \u0421 \u0432\u0435\u0440\u043e\u044f\u0442\u043d\u043e\u0441\u0442\u044c\u044e p<sub>split s<\/sub> \u0441\u0433\u0435\u043d\u0435\u0440\u0438\u0440\u043e\u0432\u0430\u043d\u043d\u043e\u0435 \u043f\u0440\u0435\u0434\u043b\u043e\u0436\u0435\u043d\u0438\u0435 \u043d\u0430 \u044f\u0437\u044b\u043a\u0435 \u043e\u0440\u0438\u0433\u0438\u043d\u0430\u043b\u0430 \u0440\u0430\u0441\u043f\u0430\u0434\u0430\u0435\u0442\u0441\u044f \u043d\u0430 \u0434\u0432\u0430 \u043d\u0435\u043f\u0443\u0441\u0442\u044b\u0445, \u0442\u0430\u043a, \u0447\u0442\u043e\u0431\u044b \u0441\u0443\u043c\u043c\u0430\u0440\u043d\u043e\u0435 \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e \u0441\u043b\u043e\u0432 <b><i>\u0443\u0432\u0435\u043b\u0438\u0447\u0438\u043b\u043e\u0441\u044c \u0440\u043e\u0432\u043d\u043e \u043d\u0430 \u043e\u0434\u0438\u043d<\/i><\/b>. \u0412\u0435\u0440\u043e\u044f\u0442\u043d\u043e\u0441\u0442\u044c \u0442\u043e\u0433\u043e, \u0447\u0442\u043e \u043f\u0440\u0435\u0434\u043b\u043e\u0436\u0435\u043d\u0438\u0435 \u0434\u043b\u0438\u043d\u044b L<sub>s<\/sub> \u0440\u0430\u0441\u043f\u0430\u0434\u0451\u0442\u0441\u044f \u043d\u0430 \u0447\u0430\u0441\u0442\u0438 \u0434\u043b\u0438\u043d\u043e\u0439 L<sub>1<\/sub> \u0438 L<sub>2<\/sub> (\u0442\u043e \u0435\u0441\u0442\u044c L<sub>1<\/sub> + L<sub>2<\/sub> = L<sub>s<\/sub> + 1), \u043f\u0440\u043e\u043f\u043e\u0440\u0446\u0438\u043e\u043d\u0430\u043b\u044c\u043d\u0430 P<sub>s<\/sub>(L<sub>1<\/sub>) \u22c5 P<sub>s<\/sub>(L<sub>2<\/sub>).<\/p>\n<p>  2. [1-2] \u0421 \u0432\u0435\u0440\u043e\u044f\u0442\u043d\u043e\u0441\u0442\u044c\u044e p<sub>split t<\/sub> \u0441\u0433\u0435\u043d\u0435\u0440\u0438\u0440\u043e\u0432\u0430\u043d\u043d\u043e\u0435 \u043f\u0440\u0435\u0434\u043b\u043e\u0436\u0435\u043d\u0438\u0435 \u043d\u0430 \u044f\u0437\u044b\u043a\u0435 \u043f\u0435\u0440\u0435\u0432\u043e\u0434\u0430 \u0440\u0430\u0441\u043f\u0430\u0434\u0430\u0435\u0442\u0441\u044f \u043d\u0430 \u0434\u0432\u0430 \u043d\u0435\u043f\u0443\u0441\u0442\u044b\u0445, \u0442\u0430\u043a, \u0447\u0442\u043e\u0431\u044b \u0441\u0443\u043c\u043c\u0430\u0440\u043d\u043e\u0435 \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e \u0441\u043b\u043e\u0432 \u0443\u0432\u0435\u043b\u0438\u0447\u0438\u043b\u043e\u0441\u044c \u0440\u043e\u0432\u043d\u043e \u043d\u0430 \u043e\u0434\u0438\u043d. \u0412\u0435\u0440\u043e\u044f\u0442\u043d\u043e\u0441\u0442\u044c \u0442\u043e\u0433\u043e, \u0447\u0442\u043e \u043f\u0440\u0435\u0434\u043b\u043e\u0436\u0435\u043d\u0438\u0435 \u0434\u043b\u0438\u043d\u044b L<sub>t<\/sub> \u0440\u0430\u0441\u043f\u0430\u0434\u0451\u0442\u0441\u044f \u043d\u0430 \u0447\u0430\u0441\u0442\u0438 \u0434\u043b\u0438\u043d\u043e\u0439 L1 \u0438 L2 (\u0442\u043e \u0435\u0441\u0442\u044c L<sub>1<\/sub> + L<sub>2<\/sub> = L<sub>t<\/sub> + 1), \u043f\u0440\u043e\u043f\u043e\u0440\u0446\u0438\u043e\u043d\u0430\u043b\u044c\u043d\u0430 P<sub>t<\/sub>(L<sub>1<\/sub>) \u22c5 P<sub>t<\/sub>(L<sub>2<\/sub>).<\/p>\n<p>  3. 3. [1-1] \u0421 \u0432\u0435\u0440\u043e\u044f\u0442\u043d\u043e\u0441\u0442\u044c\u044e (1 \u2013 p<sub>split s<\/sub> \u2013 p<sub>split t<\/sub>) \u043d\u0438 \u043e\u0434\u043d\u043e \u0438\u0437 \u043f\u0430\u0440\u044b \u0441\u0433\u0435\u043d\u0435\u0440\u0438\u0440\u043e\u0432\u0430\u043d\u043d\u044b\u0445 \u043f\u0440\u0435\u0434\u043b\u043e\u0436\u0435\u043d\u0438\u0439 \u043d\u0435 \u0440\u0430\u0441\u043f\u0430\u0434\u0451\u0442\u0441\u044f.<\/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, \u043f\u0440\u0438\u043c\u0435\u0440\u044b \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>  \u0412 \u043f\u0435\u0440\u0432\u043e\u0439 \u0441\u0442\u0440\u043e\u043a\u0435 \u0444\u0430\u0439\u043b\u0430 \u0437\u0430\u043f\u0438\u0441\u0430\u043d\u044b \u043f\u0430\u0440\u0430\u043c\u0435\u0442\u0440\u044b \u0440\u0430\u0441\u043f\u0440\u0435\u0434\u0435\u043b\u0435\u043d\u0438\u0439: p<sub>h<\/sub>, p<sub>d<\/sub>, p<sub>i<\/sub>, p<sub>split s<\/sub>, p<sub>split t<\/sub>, \u03bc<sub>s<\/sub>, \u03c3<sub>s<\/sub>, \u03bc<sub>t<\/sub>, \u03c3<sub>t<\/sub>. 0,1 \u2264 \u03c3<sub>s<\/sub> &lt; \u03c3<sub>t<\/sub> \u2264 3. 0 \u2264 \u03bc<sub>s<\/sub>, \u03bc<sub>t<\/sub> \u2264 5.<\/p>\n<p>  \u0412 \u0441\u043b\u0435\u0434\u0443\u044e\u0449\u0435\u0439 \u0441\u0442\u0440\u043e\u043a\u0435 \u0441\u0442\u043e\u044f\u0442 \u0447\u0438\u0441\u043b\u0430 N<sub>s<\/sub> \u0438 N<sub>t<\/sub> \u2014 \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e \u043f\u0440\u0435\u0434\u043b\u043e\u0436\u0435\u043d\u0438\u0439 \u0432 \u043a\u043e\u0440\u043f\u0443\u0441\u0435 \u043d\u0430 \u044f\u0437\u044b\u043a\u0435 \u043e\u0440\u0438\u0433\u0438\u043d\u0430\u043b\u0430 \u0438 \u043d\u0430 \u044f\u0437\u044b\u043a\u0435 \u043f\u0435\u0440\u0435\u0432\u043e\u0434\u0430 \u0441\u043e\u043e\u0442\u0432\u0435\u0442\u0441\u0442\u0432\u0435\u043d\u043d\u043e (1 \u2264 N<sub>s<\/sub>, N<sub>t<\/sub> \u2264 1000).<\/p>\n<p>  \u0412 \u0441\u043b\u0435\u0434\u0443\u044e\u0449\u0435\u0439 \u0441\u0442\u0440\u043e\u043a\u0435 \u043d\u0430\u0445\u043e\u0434\u044f\u0442\u0441\u044f N<sub>s<\/sub> \u0446\u0435\u043b\u044b\u0445 \u0447\u0438\u0441\u0435\u043b \u2014 \u0434\u043b\u0438\u043d\u044b \u043f\u0440\u0435\u0434\u043b\u043e\u0436\u0435\u043d\u0438\u0439 \u043d\u0430 \u044f\u0437\u044b\u043a\u0435 \u043e\u0440\u0438\u0433\u0438\u043d\u0430\u043b\u0430. \u0412 \u0441\u043b\u0435\u0434\u0443\u044e\u0449\u0435\u0439 \u0441\u0442\u0440\u043e\u043a\u0435 \u043d\u0430\u0445\u043e\u0434\u044f\u0442\u0441\u044f N<sub>t<\/sub> \u0446\u0435\u043b\u044b\u0445 \u0447\u0438\u0441\u0435\u043b \u2014 \u0434\u043b\u0438\u043d\u044b \u043f\u0440\u0435\u0434\u043b\u043e\u0436\u0435\u043d\u0438\u0439 \u043d\u0430 \u044f\u0437\u044b\u043a\u0435 \u043f\u0435\u0440\u0435\u0432\u043e\u0434\u0430.<\/p>\n<p>  \u0412 \u0441\u043b\u0435\u0434\u0443\u044e\u0449\u0435\u0439 \u0441\u0442\u0440\u043e\u043a\u0435 \u043d\u0430\u0445\u043e\u0434\u044f\u0442\u0441\u044f \u0434\u0432\u0430 \u0447\u0438\u0441\u043b\u0430: j \u0438 k (1 \u2264 j \u2264 N<sub>s<\/sub>, 1 \u2264 k \u2264 N<sub>t<\/sub>).<\/p>\n<h4>\u0424\u043e\u0440\u043c\u0430\u0442 \u0432\u044b\u0432\u043e\u0434\u0430<\/h4>\n<p>  \u0422\u0440\u0435\u0431\u0443\u0435\u0442\u0441\u044f \u0432\u044b\u0432\u0435\u0441\u0442\u0438 \u0432\u0435\u0440\u043e\u044f\u0442\u043d\u043e\u0441\u0442\u044c \u0442\u043e\u0433\u043e, \u0447\u0442\u043e \u043f\u0440\u0435\u0434\u043b\u043e\u0436\u0435\u043d\u0438\u044f \u0441 \u0438\u043d\u0434\u0435\u043a\u0441\u0430\u043c\u0438 j \u0438 k \u0432 \u0442\u0435\u043a\u0441\u0442\u0430\u0445 \u0441\u043e\u043e\u0442\u0432\u0435\u0442\u0441\u0442\u0432\u0435\u043d\u043d\u043e \u044f\u0432\u043b\u044f\u044e\u0442\u0441\u044f \u043f\u0430\u0440\u0430\u043b\u043b\u0435\u043b\u044c\u043d\u044b\u043c\u0438 (\u0442\u043e \u0435\u0441\u0442\u044c \u0447\u0442\u043e \u043e\u043d\u0438 \u0441\u0433\u0435\u043d\u0435\u0440\u0438\u0440\u043e\u0432\u0430\u043d\u044b \u043d\u0430 \u043e\u0434\u043d\u043e\u043c \u0448\u0430\u0433\u0435 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0430 \u0438 \u043d\u0438 \u043e\u0434\u043d\u043e \u0438\u0437 \u043d\u0438\u0445 \u043d\u0435 \u044f\u0432\u043b\u044f\u0435\u0442\u0441\u044f \u0440\u0435\u0437\u0443\u043b\u044c\u0442\u0430\u0442\u043e\u043c \u0440\u0430\u0441\u043f\u0430\u0434\u0430).<\/p>\n<p>  \u0412\u0430\u0448 \u043e\u0442\u0432\u0435\u0442 \u0431\u0443\u0434\u0435\u0442 \u043f\u0440\u0438\u043d\u044f\u0442, \u0435\u0441\u043b\u0438 \u0430\u0431\u0441\u043e\u043b\u044e\u0442\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>\u20134<\/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>0.05 0.08 0.07 0.15 0.1 1 0.3 3 0.5<br \/>  1 1<br \/>  4<br \/>  20<br \/>  1 1<\/code><\/td>\n<td><code>0.975037457809<\/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>0.1 0.2 0.3 0.25 0.3 1 0.3 3 0.5<br \/>  2 1<br \/>  3 4<br \/>  20<br \/>  2 1<\/code><\/td>\n<td><code>0.247705779810<\/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>0.2 0.2 0.2 0.3 0.3 3 0.3 1 1<br \/>  5 3<br \/>  16 35 24 19 23<br \/>  5 6 7<br \/>  2 1<\/code><\/td>\n<td><code>0.200961101684<\/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 \u0438\u0441\u0445\u043e\u0434\u043d\u0443\u044e \u043f\u043e\u0441\u043b\u0435\u0434\u043e\u0432\u0430\u0442\u0435\u043b\u044c\u043d\u043e\u0441\u0442\u044c \u0447\u0438\u0441\u0435\u043b \u043c\u043e\u0436\u043d\u043e \u043f\u043e\u043b\u0443\u0447\u0438\u0442\u044c \u0442\u0440\u0435\u043c\u044f \u0441\u043f\u043e\u0441\u043e\u0431\u0430\u043c\u0438:<\/p>\n<p>  \u2022 \u0421\u043d\u0430\u0447\u0430\u043b\u0430 \u0441 \u0432\u0435\u0440\u043e\u044f\u0442\u043d\u043e\u0441\u0442\u044c\u044e p<sub>d<\/sub> \u0434\u043e\u043f\u0438\u0441\u0430\u0442\u044c \u043e\u0434\u043d\u043e \u043f\u0440\u0435\u0434\u043b\u043e\u0436\u0435\u043d\u0438\u0435 \u0432 \u043e\u0440\u0438\u0433\u0438\u043d\u0430\u043b\u044c\u043d\u044b\u0439 \u0442\u0435\u043a\u0441\u0442, \u0437\u0430\u0442\u0435\u043c \u0441 \u0432\u0435\u0440\u043e\u044f\u0442\u043d\u043e\u0441\u0442\u044c\u044e p<sub>i<\/sub> \u0434\u043e\u043f\u0438\u0441\u0430\u0442\u044c \u043e\u0434\u043d\u043e \u043f\u0440\u0435\u0434\u043b\u043e\u0436\u0435\u043d\u0438\u0435 \u0432 \u043f\u0435\u0440\u0435\u0432\u043e\u0434, \u043f\u043e\u0442\u043e\u043c \u0441 \u0432\u0435\u0440\u043e\u044f\u0442\u043d\u043e\u0441\u0442\u044c\u044e p<sub>h<\/sub> \u0437\u0430\u043a\u043e\u043d\u0447\u0438\u0442\u044c \u0433\u0435\u043d\u0435\u0440\u0430\u0446\u0438\u044e.<\/p>\n<p>  \u0412\u0435\u0440\u043e\u044f\u0442\u043d\u043e\u0441\u0442\u044c \u044d\u0442\u043e\u0433\u043e \u0441\u043e\u0431\u044b\u0442\u0438\u044f \u0440\u0430\u0432\u043d\u0430 P<sub>1<\/sub> = p<sub>d<\/sub> * P<sub>s<\/sub>(4) * p<sub>i<\/sub> * P<sub>t<\/sub>(20) * p<sub>h<\/sub>.<\/p>\n<p>  \u2022 \u0421\u043d\u0430\u0447\u0430\u043b\u0430 \u0441 \u0432\u0435\u0440\u043e\u044f\u0442\u043d\u043e\u0441\u0442\u044c\u044e p<sub>d<\/sub> \u0434\u043e\u043f\u0438\u0441\u0430\u0442\u044c \u043e\u0434\u043d\u043e \u043f\u0440\u0435\u0434\u043b\u043e\u0436\u0435\u043d\u0438\u0435 \u0432 \u043e\u0440\u0438\u0433\u0438\u043d\u0430\u043b\u044c\u043d\u044b\u0439 \u0442\u0435\u043a\u0441\u0442, \u0437\u0430\u0442\u0435\u043c \u0441 \u0432\u0435\u0440\u043e\u044f\u0442\u043d\u043e\u0441\u0442\u044c\u044e p<sub>i<\/sub> \u0434\u043e\u043f\u0438\u0441\u0430\u0442\u044c \u043e\u0434\u043d\u043e \u043f\u0440\u0435\u0434\u043b\u043e\u0436\u0435\u043d\u0438\u0435 \u0432 \u043f\u0435\u0440\u0435\u0432\u043e\u0434, \u043f\u043e\u0442\u043e\u043c \u0441 \u0432\u0435\u0440\u043e\u044f\u0442\u043d\u043e\u0441\u0442\u044c\u044e p<sub>h<\/sub> \u0437\u0430\u043a\u043e\u043d\u0447\u0438\u0442\u044c \u0433\u0435\u043d\u0435\u0440\u0430\u0446\u0438\u044e.<\/p>\n<p>  \u0412\u0435\u0440\u043e\u044f\u0442\u043d\u043e\u0441\u0442\u044c \u044d\u0442\u043e\u0433\u043e \u0441\u043e\u0431\u044b\u0442\u0438\u044f \u0440\u0430\u0432\u043d\u0430 P<sub>2<\/sub> = p<sub>i<\/sub> * P<sub>t<\/sub>(20) * p<sub>d<\/sub> * P<sub>s<\/sub>(4) * p<sub>h<\/sub>.<\/p>\n<p>  \u2022 C \u0432\u0435\u0440\u043e\u044f\u0442\u043d\u043e\u0441\u0442\u044c\u044e (1 \u2013 p<sub>h<\/sub> \u2013 p<sub>d<\/sub> \u2013 p<sub>i<\/sub>) \u0441\u0433\u0435\u043d\u0435\u0440\u0438\u0440\u043e\u0432\u0430\u0442\u044c \u0434\u0432\u0430 \u043f\u0440\u0435\u0434\u043b\u043e\u0436\u0435\u043d\u0438\u044f, \u0437\u0430\u0442\u0435\u043c \u0441 \u0432\u0435\u0440\u043e\u044f\u0442\u043d\u043e\u0441\u0442\u044c\u044e (1 \u2013 p<sub>split s<\/sub> \u2013 p<sub>split t<\/sub>) \u043e\u0441\u0442\u0430\u0432\u0438\u0442\u044c \u0432\u0441\u0451 \u043a\u0430\u043a \u0435\u0441\u0442\u044c (\u0442\u043e \u0435\u0441\u0442\u044c \u043d\u0435 \u0440\u0430\u0437\u0431\u0438\u0432\u0430\u0442\u044c \u043d\u0430 \u0434\u0432\u0430 \u043f\u0440\u0435\u0434\u043b\u043e\u0436\u0435\u043d\u0438\u044f \u043d\u0438 \u043e\u0440\u0438\u0433\u0438\u043d\u0430\u043b, \u043d\u0438 \u043f\u0435\u0440\u0435\u0432\u043e\u0434) \u0438 \u043f\u043e\u0441\u043b\u0435 \u044d\u0442\u043e\u0433\u043e \u0441 \u0432\u0435\u0440\u043e\u044f\u0442\u043d\u043e\u0441\u0442\u044c\u044e p<sub>h<\/sub> \u0437\u0430\u043a\u043e\u043d\u0447\u0438\u0442\u044c \u0433\u0435\u043d\u0435\u0440\u0430\u0446\u0438\u044e.<\/p>\n<p>  \u0412\u0435\u0440\u043e\u044f\u0442\u043d\u043e\u0441\u0442\u044c \u044d\u0442\u043e\u0433\u043e \u0441\u043e\u0431\u044b\u0442\u0438\u044f \u0440\u0430\u0432\u043d\u0430 <br \/>  <img decoding=\"async\" src=\"https:\/\/habrastorage.org\/webt\/xw\/ka\/ys\/xwkayskmtg4g3tkt9pb3n-ieyoa.png\" width=\"550\">.<\/p>\n<p>  \u0412 \u0438\u0442\u043e\u0433\u0435 \u043e\u0442\u0432\u0435\u0442 \u0440\u0430\u0441\u0441\u0447\u0438\u0442\u044b\u0432\u0430\u0435\u0442\u0441\u044f \u043a\u0430\u043a <img decoding=\"async\" src=\"https:\/\/habrastorage.org\/webt\/zm\/tw\/xk\/zmtwxkdjhhctfrcbiqsc0tur6g0.png\" width=\"100\">.<\/div>\n<\/div>\n<p>  <\/p>\n<h4>\u0420\u0435\u0448\u0435\u043d\u0438\u0435<\/h4>\n<p>  \u0417\u0430\u0434\u0430\u0447\u0430 \u044f\u0432\u043b\u044f\u0435\u0442\u0441\u044f \u0447\u0430\u0441\u0442\u043d\u044b\u043c \u0441\u043b\u0443\u0447\u0430\u0435\u043c \u0432\u044b\u0440\u0430\u0432\u043d\u0438\u0432\u0430\u043d\u0438\u044f \u0441 \u043f\u043e\u043c\u043e\u0449\u044c\u044e \u0441\u043a\u0440\u044b\u0442\u044b\u0445 \u043c\u0430\u0440\u043a\u043e\u0432\u0441\u043a\u0438\u0445 \u043c\u043e\u0434\u0435\u043b\u0435\u0439 (HMM alignment). \u041e\u0441\u043d\u043e\u0432\u043d\u0430\u044f \u0438\u0434\u0435\u044f \u0441\u043e\u0441\u0442\u043e\u0438\u0442 \u0432 \u0442\u043e\u043c, \u0447\u0442\u043e \u043c\u043e\u0436\u043d\u043e \u0432\u044b\u0447\u0438\u0441\u043b\u0438\u0442\u044c \u0432\u0435\u0440\u043e\u044f\u0442\u043d\u043e\u0441\u0442\u044c \u0433\u0435\u043d\u0435\u0440\u0430\u0446\u0438\u0438 \u043a\u043e\u043d\u043a\u0440\u0435\u0442\u043d\u043e\u0439 \u043f\u0430\u0440\u044b \u0434\u043e\u043a\u0443\u043c\u0435\u043d\u0442\u043e\u0432 \u0441 \u043f\u043e\u043c\u043e\u0449\u044c\u044e \u044d\u0442\u043e\u0439 \u043c\u043e\u0434\u0435\u043b\u0438 \u0438 <a href=\"https:\/\/en.wikipedia.org\/wiki\/Forward_algorithm\">\u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0430 forward<\/a>: \u0432 \u0434\u0430\u043d\u043d\u043e\u043c \u0441\u043b\u0443\u0447\u0430\u0435 \u0441\u043e\u0441\u0442\u043e\u044f\u043d\u0438\u0435\u043c \u044f\u0432\u043b\u044f\u0435\u0442\u0441\u044f \u043f\u0430\u0440\u0430 \u043f\u0440\u0435\u0444\u0438\u043a\u0441\u043e\u0432 \u0434\u043e\u043a\u0443\u043c\u0435\u043d\u0442\u043e\u0432. \u0421\u043e\u043e\u0442\u0432\u0435\u0442\u0441\u0442\u0432\u0435\u043d\u043d\u043e, \u0442\u0440\u0435\u0431\u0443\u0435\u043c\u0443\u044e \u0432\u0435\u0440\u043e\u044f\u0442\u043d\u043e\u0441\u0442\u044c \u0432\u044b\u0440\u0430\u0432\u043d\u0438\u0432\u0430\u043d\u0438\u044f \u043a\u043e\u043d\u043a\u0440\u0435\u0442\u043d\u043e\u0439 \u043f\u0430\u0440\u044b \u043f\u0430\u0440\u0430\u043b\u043b\u0435\u043b\u044c\u043d\u044b\u0445 \u043f\u0440\u0435\u0434\u043b\u043e\u0436\u0435\u043d\u0438\u0439 \u043c\u043e\u0436\u043d\u043e \u0432\u044b\u0447\u0438\u0441\u043b\u0438\u0442\u044c \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u043e\u043c <a href=\"https:\/\/en.wikipedia.org\/wiki\/Forward%E2%80%93backward_algorithm\">forward-backward<\/a>.<\/p>\n<div class=\"spoiler\"><b class=\"spoiler_title\">\u041a\u043e\u0434<\/b><\/p>\n<div class=\"spoiler_text\">\n<pre><code class=\"cpp\">#include &lt;iostream&gt; #include &lt;iomanip&gt; #include &lt;cmath&gt; #include &lt;vector&gt;  double p_h, p_d, p_i, p_tr, p_ss, p_st, mu_s, sigma_s, mu_t, sigma_t;  double lognorm_cdf(double x, double mu, double sigma) {     if (x &lt; 1e-9)         return 0.0;     double res = std::log(x) - mu;     res \/= std::sqrt(2.0) * sigma;     res = 0.5 * (1 + std::erf(res));     return res; }  double length_probability(int l, double mu, double sigma) {     return lognorm_cdf(l, mu, sigma) - lognorm_cdf(l - 1, mu, sigma); }  double translation_probability(int ls, int lt) {     double res = length_probability(ls, mu_s, sigma_s);     double mu = mu_t - mu_s + std::log(ls);     double sigma = std::sqrt(sigma_t * sigma_t - sigma_s * sigma_s);     res *= length_probability(lt, mu, sigma);     return res; }  double split_probability(int l1, int l2, double mu, double sigma) {     int l_sum = l1 + l2;     double total_prob = 0.0;     for (int i = 1; i &lt; l_sum; ++i) {         total_prob += length_probability(i, mu, sigma) * length_probability(l_sum - i, mu, sigma);     }     return length_probability(l1, mu, sigma) * length_probability(l2, mu, sigma) \/ total_prob; }  double log_prob10(int ls) {     return std::log(p_d * length_probability(ls, mu_s, sigma_s)); }  double log_prob01(int lt) {     return std::log(p_i * length_probability(lt, mu_t, sigma_t)); }  double log_prob11(int ls, int lt) {     return std::log(p_tr * (1 - p_ss - p_st) * translation_probability(ls, lt)); }  double log_prob21(int ls1, int ls2, int lt) {     return std::log(p_tr * p_ss * split_probability(ls1, ls2, mu_s, sigma_s) * translation_probability(ls1 + ls2 - 1, lt)); }  double log_prob12(int ls, int lt1, int lt2) {     return std::log(p_tr * p_st * split_probability(lt1, lt2, mu_t, sigma_t) * translation_probability(ls, lt1 + lt2 - 1)); }  double logsum(double v1, double v2) {     double res = std::max(v1, v2);     v1 -= res;     v2 -= res;     v1 = std::min(v1, v2);     if (v1 &lt; -30) {         return res;     }     return res + std::log(std::exp(v1) + 1.0); }  double loginc(double* to, double from) {     *to = logsum(*to, from); }  constexpr double INF = 1e25;  int main(void) {     using std::cin;     using std::cout;     cin &gt;&gt; p_h &gt;&gt; p_d &gt;&gt; p_i &gt;&gt; p_ss &gt;&gt; p_st &gt;&gt; mu_s &gt;&gt; sigma_s &gt;&gt; mu_t &gt;&gt; sigma_t;     p_tr = 1.0 - p_h - p_d - p_i;     int Ns, Nt;     cin &gt;&gt; Ns &gt;&gt; Nt;      using std::vector;     vector&lt;int&gt; ls(Ns), lt(Nt);     for (int i = 0; i &lt; Ns; ++i)         cin &gt;&gt; ls[i];     for (int i = 0; i &lt; Nt; ++i)         cin &gt;&gt; lt[i];      vector&lt; vector&lt; double&gt; &gt; fwd(Ns + 1, vector&lt;double&gt;(Nt + 1, -INF)), bwd = fwd;     fwd[0][0] = 0;     bwd[Ns][Nt] = 0;     for (int i = 0; i &lt;= Ns; ++i) {         for (int j = 0; j &lt;= Nt; ++j) {             if (i &gt;= 1) {                 loginc(&amp;fwd[i][j], fwd[i - 1][j] + log_prob10(ls[i - 1]));                 loginc(&amp;bwd[Ns - i][Nt - j], bwd[Ns - i + 1][Nt - j] + log_prob10(ls[Ns - i]));             }             if (j &gt;= 1) {                 loginc(&amp;fwd[i][j], fwd[i][j - 1] + log_prob01(lt[j - 1]));                 loginc(&amp;bwd[Ns - i][Nt - j], bwd[Ns - i][Nt - j + 1] + log_prob01(lt[Nt - j]));             }             if (i &gt;= 1 &amp;&amp; j &gt;= 1) {                 loginc(&amp;fwd[i][j], fwd[i - 1][j - 1] + log_prob11(ls[i - 1], lt[j - 1]));                 loginc(&amp;bwd[Ns - i][Nt - j], bwd[Ns - i + 1][Nt - j + 1] + log_prob11(ls[Ns - i], lt[Nt - j]));             }             if (i &gt;= 2 &amp;&amp; j &gt;= 1) {                 loginc(&amp;fwd[i][j], fwd[i - 2][j - 1] + log_prob21(ls[i - 1], ls[i - 2], lt[j - 1]));                 loginc(&amp;bwd[Ns - i][Nt - j], bwd[Ns - i + 2][Nt - j + 1] + log_prob21(ls[Ns - i], ls[Ns - i + 1], lt[Nt - j]));             }             if (i &gt;= 1 &amp;&amp; j &gt;= 2) {                 loginc(&amp;fwd[i][j], fwd[i - 1][j - 2] + log_prob12(ls[i - 1], lt[j - 1], lt[j - 2]));                 loginc(&amp;bwd[Ns - i][Nt - j], bwd[Ns - i + 1][Nt - j + 2] + log_prob12(ls[Ns - i], lt[Nt - j], lt[Nt - j + 1]));             }         }     }     int j, k;     cin &gt;&gt; j &gt;&gt; k;     double rlog = fwd[j - 1][k - 1] + bwd[j][k] + log_prob11(ls[j - 1], lt[k - 1]) - bwd[0][0];     cout &lt;&lt; std::fixed &lt;&lt; std::setprecision(12) &lt;&lt; std::exp(rlog) &lt;&lt; std::endl; }<\/code><\/pre>\n<\/div>\n<\/div>\n<p>  <\/p>\n<h2>D. \u041b\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>\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>64 \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\u0430\u0441\u0441\u043c\u043e\u0442\u0440\u0438\u043c \u043b\u0435\u043d\u0442\u0443 \u0440\u0435\u043a\u043e\u043c\u0435\u043d\u0434\u0430\u0446\u0438\u0439 \u0440\u0430\u0437\u043d\u043e\u0440\u043e\u0434\u043d\u043e\u0433\u043e \u043a\u043e\u043d\u0442\u0435\u043d\u0442\u0430. \u0412 \u043d\u0435\u0439 \u0441\u043c\u0435\u0448\u0430\u043d\u044b \u043e\u0431\u044a\u0435\u043a\u0442\u044b \u0440\u0430\u0437\u043d\u043e\u0433\u043e \u0442\u0438\u043f\u0430 (\u043a\u0430\u0440\u0442\u0438\u043d\u043a\u0438, \u0432\u0438\u0434\u0435\u043e, \u043d\u043e\u0432\u043e\u0441\u0442\u0438 \u0438 \u0442. \u0434.). \u042d\u0442\u0438 \u043e\u0431\u044a\u0435\u043a\u0442\u044b \u043e\u0431\u044b\u0447\u043d\u043e \u0443\u043f\u043e\u0440\u044f\u0434\u043e\u0447\u0438\u0432\u0430\u044e\u0442\u0441\u044f \u043f\u043e \u0440\u0435\u043b\u0435\u0432\u0430\u043d\u0442\u043d\u043e\u0441\u0442\u0438 \u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u0442\u0435\u043b\u044e: \u0447\u0435\u043c \u0440\u0435\u043b\u0435\u0432\u0430\u043d\u0442\u043d\u0435\u0435 (\u0438\u043d\u0442\u0435\u0440\u0435\u0441\u043d\u0435\u0435) \u043e\u0431\u044a\u0435\u043a\u0442 \u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u0442\u0435\u043b\u044e, \u0442\u0435\u043c \u043e\u043d \u0431\u043b\u0438\u0436\u0435 \u043a \u043d\u0430\u0447\u0430\u043b\u0443 \u0441\u043f\u0438\u0441\u043a\u0430 \u0440\u0435\u043a\u043e\u043c\u0435\u043d\u0434\u0430\u0446\u0438\u0439. \u041e\u0434\u043d\u0430\u043a\u043e \u043f\u0440\u0438 \u0442\u0430\u043a\u043e\u043c \u0443\u043f\u043e\u0440\u044f\u0434\u043e\u0447\u0438\u0432\u0430\u043d\u0438\u0438 \u0447\u0430\u0441\u0442\u043e \u0432\u043e\u0437\u043d\u0438\u043a\u0430\u044e\u0442 \u0441\u0438\u0442\u0443\u0430\u0446\u0438\u0438, \u0432 \u043a\u043e\u0442\u043e\u0440\u044b\u0445 \u0432 \u0441\u043f\u0438\u0441\u043a\u0435 \u0440\u0435\u043a\u043e\u043c\u0435\u043d\u0434\u0430\u0446\u0438\u0439 \u0432\u0441\u0442\u0440\u0435\u0447\u0430\u044e\u0442\u0441\u044f \u043d\u0435\u0441\u043a\u043e\u043b\u044c\u043a\u043e \u043e\u0431\u044a\u0435\u043a\u0442\u043e\u0432 \u043f\u043e\u0434\u0440\u044f\u0434 \u043e\u0434\u043d\u043e\u0433\u043e \u0442\u0438\u043f\u0430. \u042d\u0442\u043e \u0441\u0438\u043b\u044c\u043d\u043e \u0443\u0445\u0443\u0434\u0448\u0430\u0435\u0442 \u0432\u043d\u0435\u0448\u043d\u0435\u0435 \u0440\u0430\u0437\u043d\u043e\u043e\u0431\u0440\u0430\u0437\u0438\u0435 \u043d\u0430\u0448\u0438\u0445 \u0440\u0435\u043a\u043e\u043c\u0435\u043d\u0434\u0430\u0446\u0438\u0439 \u0438 \u043f\u043e\u044d\u0442\u043e\u043c\u0443 \u043d\u0435 \u043d\u0440\u0430\u0432\u0438\u0442\u0441\u044f \u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u0442\u0435\u043b\u044f\u043c. \u041d\u0435\u043e\u0431\u0445\u043e\u0434\u0438\u043c\u043e \u0440\u0435\u0430\u043b\u0438\u0437\u043e\u0432\u0430\u0442\u044c \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c, \u043a\u043e\u0442\u043e\u0440\u044b\u0439 \u043f\u043e \u0441\u043f\u0438\u0441\u043a\u0443 \u0440\u0435\u043a\u043e\u043c\u0435\u043d\u0434\u0430\u0446\u0438\u0439 \u0441\u043e\u0441\u0442\u0430\u0432\u0438\u0442 \u043d\u043e\u0432\u044b\u0439 \u0441\u043f\u0438\u0441\u043e\u043a, \u043a\u043e\u0442\u043e\u0440\u044b\u0439 \u0431\u0443\u0434\u0435\u0442 \u043b\u0438\u0448\u0435\u043d \u044d\u0442\u043e\u0439 \u043f\u0440\u043e\u0431\u043b\u0435\u043c\u044b \u0438 \u0431\u0443\u0434\u0435\u0442 \u043d\u0430\u0438\u0431\u043e\u043b\u0435\u0435 \u0440\u0435\u043b\u0435\u0432\u0430\u043d\u0442\u043d\u044b\u043c.<\/p>\n<p>  \u041f\u0443\u0441\u0442\u044c \u0437\u0430\u0434\u0430\u043d \u0438\u0441\u0445\u043e\u0434\u043d\u044b\u0439 \u0441\u043f\u0438\u0441\u043e\u043a \u0440\u0435\u043a\u043e\u043c\u0435\u043d\u0434\u0430\u0446\u0438\u0439 a = [a<sub>0<\/sub>, a<sub>1<\/sub>,\u2026, a<sub>n \u2212 1<\/sub>] \u0434\u043b\u0438\u043d\u044b n &gt; 0. \u041e\u0431\u044a\u0435\u043a\u0442 \u043f\u043e\u0434 \u043d\u043e\u043c\u0435\u0440\u043e\u043c i \u0438\u043c\u0435\u0435\u0442 \u0442\u0438\u043f \u0441 \u043d\u043e\u043c\u0435\u0440\u043e\u043c b<sub>i<\/sub> \u2208 {0,\u2026, m \u2212 1}. \u041a\u0440\u043e\u043c\u0435 \u0442\u043e\u0433\u043e, \u043e\u0431\u044a\u0435\u043a\u0442 \u043f\u043e\u0434 \u043d\u043e\u043c\u0435\u0440 i \u0438\u043c\u0435\u0435\u0442 \u0440\u0435\u043b\u0435\u0432\u0430\u043d\u0442\u043d\u043e\u0441\u0442\u044c r(a<sub>i<\/sub>) = 2<sub>\u2212i<\/sub>. \u0420\u0430\u0441\u0441\u043c\u043e\u0442\u0440\u0438\u043c \u0441\u043f\u0438\u0441\u043e\u043a, \u043a\u043e\u0442\u043e\u0440\u044b\u0439 \u043f\u043e\u043b\u0443\u0447\u0430\u0435\u0442\u0441\u044f \u0438\u0437 \u0438\u0441\u0445\u043e\u0434\u043d\u043e\u0433\u043e \u0432\u044b\u0431\u043e\u0440\u043e\u043c \u043f\u043e\u0434\u043c\u043d\u043e\u0436\u0435\u0441\u0442\u0432\u0430 \u043e\u0431\u044a\u0435\u043a\u0442\u043e\u0432 \u0438 \u0438\u0445 \u043f\u0435\u0440\u0435\u0441\u0442\u0430\u043d\u043e\u0432\u043a\u043e\u0439: x = [a<sub>i<sub>0<\/sub><\/sub>, a<sub>i<sub>1<\/sub><\/sub>,\u2026,a<sub>i<sub>k\u22121<\/sub><\/sub>] \u0434\u043b\u0438\u043d\u044b k (0 \u2264 k \u2264 n). \u0421\u043f\u0438\u0441\u043e\u043a \u043d\u0430\u0437\u044b\u0432\u0430\u0435\u0442\u0441\u044f \u0434\u043e\u043f\u0443\u0441\u0442\u0438\u043c\u044b\u043c, \u0435\u0441\u043b\u0438 \u043d\u0438\u043a\u0430\u043a\u0438\u0435 \u0434\u0432\u0430 \u043f\u043e\u0434\u0440\u044f\u0434 \u0438\u0434\u0443\u0449\u0438\u0445 \u043e\u0431\u044a\u0435\u043a\u0442\u0430 \u0432 \u043d\u0451\u043c \u043d\u0435 \u0441\u043e\u0432\u043f\u0430\u0434\u0430\u044e\u0442 \u043f\u043e \u0442\u0438\u043f\u0443, \u0442. \u0435. b<sub>i<sub>j<\/sub><\/sub> \u2260 b<sub>i<sub>j + 1<\/sub><\/sub> \u0434\u043b\u044f \u0432\u0441\u0435\u0445 j = 0,\u2026, k\u22122. \u0420\u0435\u043b\u0435\u0432\u0430\u043d\u0442\u043d\u043e\u0441\u0442\u044c \u0441\u043f\u0438\u0441\u043a\u0430 \u0432\u044b\u0447\u0438\u0441\u043b\u044f\u0435\u0442\u0441\u044f \u043f\u043e \u0444\u043e\u0440\u043c\u0443\u043b\u0435 <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/85a\/ace\/7d0\/85aace7d094a726238fde37c4dcd85cf.svg\" alt=\"$\\sum_{j=0}^{k-1} 2_{-j}r(a_{i_j})$\" data-tex=\"inline\"><\/math>. \u0412\u0430\u043c \u043d\u0443\u0436\u043d\u043e \u043d\u0430\u0439\u0442\u0438 \u043c\u0430\u043a\u0441\u0438\u043c\u0430\u043b\u044c\u043d\u044b\u0439 \u043f\u043e \u0440\u0435\u043b\u0435\u0432\u0430\u043d\u0442\u043d\u043e\u0441\u0442\u0438 \u0441\u043f\u0438\u0441\u043e\u043a \u0441\u0440\u0435\u0434\u0438 \u0432\u0441\u0435\u0445 \u0434\u043e\u043f\u0443\u0441\u0442\u0438\u043c\u044b\u0445.<\/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>  \u041d\u0430 \u043f\u0435\u0440\u0432\u043e\u0439 \u0441\u0442\u0440\u043e\u043a\u0435 \u0447\u0435\u0440\u0435\u0437 \u043f\u0440\u043e\u0431\u0435\u043b \u0437\u0430\u043f\u0438\u0441\u0430\u043d\u044b \u0447\u0438\u0441\u043b\u0430 n \u0438 m (1 \u2264 n \u2264 100000, 1 \u2264 m \u2264 n). \u041d\u0430 \u0441\u043b\u0435\u0434\u0443\u044e\u0449\u0438\u0445 n \u0441\u0442\u0440\u043e\u043a\u0430\u0445 \u0437\u0430\u043f\u0438\u0441\u0430\u043d\u044b \u0447\u0438\u0441\u043b\u0430 b<sub>i<\/sub> \u0434\u043b\u044f i = 0,\u2026, n \u2212 1 (0 \u2264 b<sub>i<\/sub> \u2264 m \u2212 1).<\/p>\n<h4>\u0424\u043e\u0440\u043c\u0430\u0442 \u0432\u044b\u0432\u043e\u0434\u0430<\/h4>\n<p>  \u0412\u044b\u043f\u0438\u0448\u0438\u0442\u0435 \u0447\u0435\u0440\u0435\u0437 \u043f\u0440\u043e\u0431\u0435\u043b \u043d\u043e\u043c\u0435\u0440\u0430 \u043e\u0431\u044a\u0435\u043a\u0442\u043e\u0432 \u0438\u0442\u043e\u0433\u043e\u0432\u043e\u0433\u043e \u0441\u043f\u0438\u0441\u043a\u0430: i<sub>0<\/sub>, i<sub>1<\/sub>,\u2026, i<sub>k\u22121<\/sub>.<\/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>1 1<br \/>  0<\/code><\/td>\n<td><code>0<\/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>2 2<br \/>  1<br \/>  1<\/code><\/td>\n<td><code>0<\/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>10 2<br \/>  1<br \/>  1<br \/>  1<br \/>  0<br \/>  0<br \/>  1<br \/>  0<br \/>  1<br \/>  1<br \/>  1<\/code><\/td>\n<td><code>0 3 1 4 2 6 5<\/code><\/td>\n<\/tr>\n<\/table>\n<\/div>\n<\/div>\n<\/div>\n<p>  <\/p>\n<h4>\u0420\u0435\u0448\u0435\u043d\u0438\u0435<\/h4>\n<p>  \u041f\u0443\u0442\u0435\u043c \u043d\u0435\u0441\u043b\u043e\u0436\u043d\u044b\u0445 \u043c\u0430\u0442\u0435\u043c\u0430\u0442\u0438\u0447\u0435\u0441\u043a\u0438\u0445 \u0432\u044b\u043a\u043b\u0430\u0434\u043e\u043a \u043c\u043e\u0436\u043d\u043e \u043f\u043e\u043a\u0430\u0437\u0430\u0442\u044c, \u0447\u0442\u043e \u0437\u0430\u0434\u0430\u0447\u0430 \u043c\u043e\u0436\u0435\u0442 \u0431\u044b\u0442\u044c \u0440\u0435\u0448\u0435\u043d\u0430 \u00ab\u0436\u0430\u0434\u043d\u044b\u043c\u00bb \u043f\u043e\u0434\u0445\u043e\u0434\u043e\u043c, \u0442. \u0435. \u0432 \u043e\u043f\u0442\u0438\u043c\u0430\u043b\u044c\u043d\u043e\u043c \u0441\u043f\u0438\u0441\u043a\u0435 \u0440\u0435\u043a\u043e\u043c\u0435\u043d\u0434\u0430\u0446\u0438\u0439 \u043d\u0430 \u043a\u0430\u0436\u0434\u043e\u0439 \u043f\u043e\u0437\u0438\u0446\u0438\u0438 \u0441\u0442\u043e\u0438\u0442 \u0441\u0430\u043c\u044b\u0439 \u0440\u0435\u043b\u0435\u0432\u0430\u043d\u0442\u043d\u044b\u0439 \u043e\u0431\u044a\u0435\u043a\u0442 \u0438\u0437 \u0432\u0441\u0435\u0445, \u043a\u043e\u0442\u043e\u0440\u044b\u0435 \u0434\u043e\u043f\u0443\u0441\u0442\u0438\u043c\u044b \u043f\u0440\u0438 \u0442\u043e\u043c \u0436\u0435 \u043d\u0430\u0447\u0430\u043b\u0435 \u0441\u043f\u0438\u0441\u043a\u0430. \u0418\u043c\u043f\u043b\u0435\u043c\u0435\u043d\u0442\u0430\u0446\u0438\u044f \u044d\u0442\u043e\u0433\u043e \u043f\u043e\u0434\u0445\u043e\u0434\u0430 \u043f\u0440\u043e\u0441\u0442\u0430\u044f: \u0431\u0435\u0440\u0451\u043c \u043e\u0431\u044a\u0435\u043a\u0442\u044b \u043f\u043e\u0434\u0440\u044f\u0434 \u0438 \u0434\u043e\u0431\u0430\u0432\u043b\u044f\u0435\u043c \u0438\u0445 \u0432 \u043e\u0442\u0432\u0435\u0442, \u0435\u0441\u043b\u0438 \u044d\u0442\u043e \u0432\u043e\u0437\u043c\u043e\u0436\u043d\u043e. \u041a\u043e\u0433\u0434\u0430 \u0432\u0441\u0442\u0440\u0435\u0447\u0430\u0435\u0442\u0441\u044f \u043d\u0435\u0434\u043e\u043f\u0443\u0441\u0442\u0438\u043c\u044b\u0439 \u043e\u0431\u044a\u0435\u043a\u0442 (\u0442\u0438\u043f \u043a\u043e\u0442\u043e\u0440\u043e\u0433\u043e \u0441\u043e\u0432\u043f\u0430\u0434\u0430\u0435\u0442 \u0441 \u0442\u0438\u043f\u043e\u043c \u043f\u0440\u0435\u0434\u044b\u0434\u0443\u0449\u0435\u0433\u043e), \u0442\u043e \u043e\u0442\u043a\u043b\u0430\u0434\u044b\u0432\u0430\u0435\u043c \u0435\u0433\u043e \u0432 \u043e\u0442\u0434\u0435\u043b\u044c\u043d\u0443\u044e \u043e\u0447\u0435\u0440\u0435\u0434\u044c, \u0438\u0437 \u043a\u043e\u0442\u043e\u0440\u043e\u0439 \u0432\u0441\u0442\u0430\u0432\u043b\u044f\u0435\u043c \u0432 \u043e\u0442\u0432\u0435\u0442 \u043f\u0440\u0438 \u043f\u0435\u0440\u0432\u043e\u0439 \u0436\u0435 \u0432\u043e\u0437\u043c\u043e\u0436\u043d\u043e\u0441\u0442\u0438. \u0417\u0430\u043c\u0435\u0442\u0438\u043c, \u0447\u0442\u043e \u0432 \u043a\u0430\u0436\u0434\u044b\u0439 \u043c\u043e\u043c\u0435\u043d\u0442 \u0432\u0440\u0435\u043c\u0435\u043d\u0438 \u0443 \u0432\u0441\u0435\u0445 \u043e\u0431\u044a\u0435\u043a\u0442\u043e\u0432 \u0432 \u044d\u0442\u043e\u0439 \u043e\u0447\u0435\u0440\u0435\u0434\u0438 \u0431\u0443\u0434\u0435\u0442 \u0441\u043e\u0432\u043f\u0430\u0434\u0430\u044e\u0449\u0438\u0439 \u0442\u0438\u043f. \u0412 \u043a\u043e\u043d\u0446\u0435 \u0432 \u043e\u0447\u0435\u0440\u0435\u0434\u0438 \u043c\u043e\u0433\u0443\u0442 \u043e\u0441\u0442\u0430\u0442\u044c\u0441\u044f \u043d\u0435\u0441\u043a\u043e\u043b\u044c\u043a\u043e \u043e\u0431\u044a\u0435\u043a\u0442\u043e\u0432, \u043e\u043d\u0438 \u0443\u0436\u0435 \u043d\u0435 \u0432\u043e\u0439\u0434\u0443\u0442 \u0432 \u043e\u0442\u0432\u0435\u0442.<\/p>\n<pre><code class=\"cpp\"> std::vector&lt;int&gt; blend(int n, int m, const std::vector&lt;int&gt;&amp; types) {     std::vector&lt;int&gt; result;     std::queue&lt;int&gt; repeated;     for (int i = 0; i &lt; n; ++i) {         if (result.empty() || types[result.back()] != types[i]) {             result.push_back(i);             if (!repeated.empty() &amp;&amp; types[repeated.front()] != types[result.back()]) {                 result.push_back(repeated.front());                 repeated.pop();             }         } else {             repeated.push(i);         }     }     return result; }<\/code><\/pre>\n<p>  <\/p>\n<h2>D. \u041a\u043b\u0430\u0441\u0442\u0435\u0440\u0438\u0437\u0430\u0446\u0438\u044f \u0441\u0438\u043c\u0432\u043e\u043b\u044c\u043d\u044b\u0445 \u043f\u043e\u0441\u043b\u0435\u0434\u043e\u0432\u0430\u0442\u0435\u043b\u044c\u043d\u043e\u0441\u0442\u0435\u0439<\/h2>\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>python2.7+numpy<\/b><\/td>\n<td><b>python3.5+numpy<\/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>1 \u0441<\/td>\n<td>6 \u0441<\/td>\n<td>6 \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>64 \u041c\u0411<\/td>\n<td>64 \u041c\u0411<\/td>\n<td>64 \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>\u0418\u043c\u0435\u0435\u0442\u0441\u044f \u043a\u043e\u043d\u0435\u0447\u043d\u044b\u0439 \u0430\u043b\u0444\u0430\u0432\u0438\u0442 A = {a<sub>1<\/sub>, a<sub>2<\/sub>,\u2026, a<sub>K\u22121<\/sub>, a<sub>K<\/sub> = S}, a<sub>i<\/sub> \u2208 {a, b,\u2026, z}, S \u2014 \u043a\u043e\u043d\u0435\u0446 \u0441\u0442\u0440\u043e\u043a\u0438.<\/p>\n<p>  \u0420\u0430\u0441\u0441\u043c\u043e\u0442\u0440\u0438\u043c \u0441\u043b\u0435\u0434\u0443\u044e\u0449\u0438\u0439 \u0441\u043f\u043e\u0441\u043e\u0431 \u0433\u0435\u043d\u0435\u0440\u0430\u0446\u0438\u0438 \u0441\u043b\u0443\u0447\u0430\u0439\u043d\u044b\u0445 \u0441\u0442\u0440\u043e\u043a \u043d\u0430\u0434 \u0430\u043b\u0444\u0430\u0432\u0438\u0442\u043e\u043c A:<\/p>\n<p>  1. \u041f\u0435\u0440\u0432\u044b\u0439 \u0441\u0438\u043c\u0432\u043e\u043b x<sub>1<\/sub> \u2014 \u0441\u043b\u0443\u0447\u0430\u0439\u043d\u0430\u044f \u0432\u0435\u043b\u0438\u0447\u0438\u043d\u0430 \u0441 \u0440\u0430\u0441\u043f\u0440\u0435\u0434\u0435\u043b\u0435\u043d\u0438\u0435\u043c P(x<sub>1<\/sub> = a<sub>i<\/sub>) = q<sub>i<\/sub> (\u0438\u0437\u0432\u0435\u0441\u0442\u043d\u043e, \u0447\u0442\u043e q<sub>K<\/sub> = 0).<br \/>  2. \u041a\u0430\u0436\u0434\u044b\u0439 \u0441\u043b\u0435\u0434\u0443\u044e\u0449\u0438\u0439 \u0441\u0438\u043c\u0432\u043e\u043b \u0433\u0435\u043d\u0435\u0440\u0438\u0440\u0443\u0435\u0442\u0441\u044f \u043d\u0430 \u043e\u0441\u043d\u043e\u0432\u0435 \u043f\u0440\u0435\u0434\u044b\u0434\u0443\u0449\u0435\u0433\u043e \u0432 \u0441\u043e\u043e\u0442\u0432\u0435\u0442\u0441\u0442\u0432\u0438\u0438 \u0441 \u0443\u0441\u043b\u043e\u0432\u043d\u044b\u043c \u0440\u0430\u0441\u043f\u0440\u0435\u0434\u0435\u043b\u0435\u043d\u0438\u0435\u043c P(x<sub>i<\/sub> = a<sub>j<\/sub> || x<sub>i \u2013 1<\/sub> = a<sub>l<\/sub>) = p<sub>jl<\/sub>.<br \/>  3. \u0415\u0441\u043b\u0438 x<sub>i<\/sub> = S, \u0433\u0435\u043d\u0435\u0440\u0430\u0446\u0438\u044f \u043f\u0440\u0435\u043a\u0440\u0430\u0449\u0430\u0435\u0442\u0441\u044f \u0438 \u0440\u0435\u0437\u0443\u043b\u044c\u0442\u0430\u0442\u043e\u043c \u044f\u0432\u043b\u044f\u0435\u0442\u0441\u044f x<sub>1<\/sub>x<sub>2<\/sub>&#8230;x<sub>i\u22121<\/sub>.<\/p>\n<p>  \u0414\u0430\u0451\u0442\u0441\u044f \u043d\u0430\u0431\u043e\u0440 \u0441\u0442\u0440\u043e\u043a, \u0441\u0433\u0435\u043d\u0435\u0440\u0438\u0440\u043e\u0432\u0430\u043d\u043d\u044b\u0445 \u0438\u0437 \u0441\u043c\u0435\u0441\u0438 \u0434\u0432\u0443\u0445 \u043e\u043f\u0438\u0441\u0430\u043d\u043d\u044b\u0445 \u043c\u043e\u0434\u0435\u043b\u0435\u0439 \u0441 \u0440\u0430\u0437\u043b\u0438\u0447\u043d\u044b\u043c\u0438 \u043f\u0430\u0440\u0430\u043c\u0435\u0442\u0440\u0430\u043c\u0438. \u041d\u0435\u043e\u0431\u0445\u043e\u0434\u0438\u043c\u043e \u0434\u043b\u044f \u043a\u0430\u0436\u0434\u043e\u0439 \u0441\u0442\u0440\u043e\u043a\u0438 \u0434\u0430\u0442\u044c \u0438\u043d\u0434\u0435\u043a\u0441 \u0446\u0435\u043f\u0438, \u0438\u0437 \u043a\u043e\u0442\u043e\u0440\u043e\u0439 \u043e\u043d\u0430 \u0431\u044b\u043b\u0430 \u0441\u0433\u0435\u043d\u0435\u0440\u0438\u0440\u043e\u0432\u0430\u043d\u0430.<\/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, \u043f\u0440\u0438\u043c\u0435\u0440 \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>  \u0412 \u043f\u0435\u0440\u0432\u043e\u0439 \u0441\u0442\u0440\u043e\u043a\u0435 \u0437\u0430\u043f\u0438\u0441\u0430\u043d\u043e \u0434\u0432\u0430 \u0447\u0438\u0441\u043b\u0430 1000 \u2264 N \u2264 2000 \u0438 3 \u2264 K \u2264 27 \u2014 \u0447\u0438\u0441\u043b\u043e \u0441\u0442\u0440\u043e\u043a \u0438 \u0440\u0430\u0437\u043c\u0435\u0440 \u0430\u043b\u0444\u0430\u0432\u0438\u0442\u0430 \u0441\u043e\u043e\u0442\u0432\u0435\u0442\u0441\u0442\u0432\u0435\u043d\u043d\u043e.<\/p>\n<p>  \u0412\u043e \u0432\u0442\u043e\u0440\u043e\u0439 \u0441\u0442\u0440\u043e\u043a\u0435 \u0437\u0430\u043f\u0438\u0441\u0430\u043d\u0430 \u0441\u0442\u0440\u043e\u043a\u0430, \u0441\u043e\u0441\u0442\u043e\u044f\u0449\u0430\u044f \u0438\u0437 K\u22121 \u0440\u0430\u0437\u043b\u0438\u0447\u043d\u044b\u0445 \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, \u043e\u0431\u043e\u0437\u043d\u0430\u044e\u0449\u0430\u044f \u043f\u0435\u0440\u0432\u044b\u0435 K\u22121 \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u043e\u0432 \u0430\u043b\u0444\u0430\u0432\u0438\u0442\u0430.<\/p>\n<p>  \u041a\u0430\u0436\u0434\u0430\u044f \u0438\u0437 \u0441\u043b\u0435\u0434\u0443\u044e\u0449\u0438\u0445 N \u0441\u0442\u0440\u043e\u043a \u0441\u0433\u0435\u043d\u0435\u0440\u0438\u0440\u043e\u0432\u0430\u043d\u0430 \u043f\u043e \u043e\u043f\u0438\u0441\u0430\u043d\u043d\u043e\u043c\u0443 \u0432 \u0443\u0441\u043b\u043e\u0432\u0438\u0438 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0443.<\/p>\n<h4>\u0424\u043e\u0440\u043c\u0430\u0442 \u0432\u044b\u0432\u043e\u0434\u0430<\/h4>\n<p>  N \u0441\u0442\u0440\u043e\u043a, \u0432 i-\u0439 \u0441\u0442\u0440\u043e\u043a\u0435 \u0441\u043e\u0434\u0435\u0440\u0436\u0438\u0442\u0441\u044f \u043d\u043e\u043c\u0435\u0440 \u043a\u043b\u0430\u0441\u0442\u0435\u0440\u0430 (0\/1) \u0434\u043b\u044f \u043f\u043e\u0441\u043b\u0435\u0434\u043e\u0432\u0430\u0442\u0435\u043b\u044c\u043d\u043e\u0441\u0442\u0438 \u043d\u0430 i+1-\u0439 \u0441\u0442\u0440\u043e\u043a\u0435 \u0432\u0445\u043e\u0434\u043d\u043e\u0433\u043e \u0444\u0430\u0439\u043b\u0430. \u0421\u043e\u0432\u043f\u0430\u0434\u0435\u043d\u0438\u0435 \u0441 \u0438\u0441\u0442\u0438\u043d\u043d\u044b\u043c \u043e\u0442\u0432\u0435\u0442\u043e\u043c \u0434\u043e\u043b\u0436\u043d\u043e \u0431\u044b\u0442\u044c \u043d\u0435 \u043c\u0435\u043d\u0435\u0435 80%.<\/p>\n<h4>\u041f\u0440\u0438\u043c\u0435\u0440<\/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>100 3<br \/>  a<br \/>  a<br \/>  aa<br \/>  a<br \/>  aaa<br \/>  a<br \/>  aaaaaa<br \/>  aa<br \/>  a<br \/>  a<br \/>  a<br \/>  aaa<br \/>  a<br \/>  a<br \/>  aaa<br \/>  aa<br \/>  aaaa<br \/>  aaa<br \/>  a<br \/>  aaaaa<br \/>  aa<br \/>  a<br \/>  aaaa<br \/>  a<br \/>  a<br \/>  a<br \/>  a<br \/>  a<br \/>  a<br \/>  aa<br \/>  aaaa<br \/>  aaa<br \/>  a<br \/>  aa<br \/>  aaaa<br \/>  a<br \/>  a<br \/>  a<br \/>  a<br \/>  a<br \/>  a<br \/>  a<br \/>  a<br \/>  a<br \/>  a<br \/>  aa<br \/>  aaa<br \/>  aaa<br \/>  a<br \/>  a<br \/>  bbb<br \/>  bb<br \/>  bb<br \/>  bbbbbbb<br \/>  bb<br \/>  bbb<br \/>  b<br \/>  bbbbbbb<br \/>  bbbb<br \/>  bbb<br \/>  bb<br \/>  bbb<br \/>  bb<br \/>  bb<br \/>  bbb<br \/>  bbbbbb<br \/>  bbb<br \/>  b<br \/>  bbbbbb<br \/>  b<br \/>  bbbbb<br \/>  b<br \/>  b<br \/>  bb<br \/>  b<br \/>  bb<br \/>  bb<br \/>  b<br \/>  b<br \/>  b<br \/>  b<br \/>  bb<br \/>  bb<br \/>  bb<br \/>  b<br \/>  b<br \/>  b<br \/>  bb<br \/>  b<br \/>  bbb<br \/>  bb<br \/>  b<br \/>  bbbbbb<br \/>  b<br \/>  bb<br \/>  bb<br \/>  bb<br \/>  b<br \/>  bb<br \/>  bbb<\/code><\/td>\n<td><code>0<br \/>  0<br \/>  0<br \/>  0<br \/>  0<br \/>  0<br \/>  0<br \/>  0<br \/>  0<br \/>  0<br \/>  0<br \/>  0<br \/>  0<br \/>  0<br \/>  0<br \/>  0<br \/>  0<br \/>  0<br \/>  0<br \/>  0<br \/>  0<br \/>  0<br \/>  0<br \/>  0<br \/>  0<br \/>  0<br \/>  0<br \/>  0<br \/>  0<br \/>  0<br \/>  0<br \/>  0<br \/>  0<br \/>  0<br \/>  0<br \/>  0<br \/>  0<br \/>  0<br \/>  0<br \/>  0<br \/>  0<br \/>  0<br \/>  0<br \/>  0<br \/>  0<br \/>  0<br \/>  0<br \/>  0<br \/>  0<br \/>  0<br \/>  1<br \/>  1<br \/>  1<br \/>  1<br \/>  1<br \/>  1<br \/>  1<br \/>  1<br \/>  1<br \/>  1<br \/>  1<br \/>  1<br \/>  1<br \/>  1<br \/>  1<br \/>  1<br \/>  1<br \/>  1<br \/>  1<br \/>  1<br \/>  1<br \/>  1<br \/>  1<br \/>  1<br \/>  1<br \/>  1<br \/>  1<br \/>  1<br \/>  1<br \/>  1<br \/>  1<br \/>  1<br \/>  1<br \/>  1<br \/>  1<br \/>  1<br \/>  1<br \/>  1<br \/>  1<br \/>  1<br \/>  1<br \/>  1<br \/>  1<br \/>  1<br \/>  1<br \/>  1<br \/>  1<br \/>  1<br \/>  1<br \/>  1<\/code><\/td>\n<\/tr>\n<\/table>\n<\/div>\n<h4>\u041f\u0440\u0438\u043c\u0435\u0447\u0430\u043d\u0438\u044f<\/h4>\n<p>  \u0417\u0430\u043c\u0435\u0447\u0430\u043d\u0438\u0435 \u043a \u0442\u0435\u0441\u0442\u0443 \u0438\u0437 \u0443\u0441\u043b\u043e\u0432\u0438\u044f: \u0432 \u043d\u0451\u043c \u043f\u0435\u0440\u0432\u044b\u0435 50 \u0441\u0442\u0440\u043e\u043a \u0441\u0433\u0435\u043d\u0435\u0440\u0438\u0440\u043e\u0432\u0430\u043d\u044b \u0438\u0437 \u0440\u0430\u0441\u043f\u0440\u0435\u0434\u0435\u043b\u0435\u043d\u0438\u044f <br \/>  P(x<sub>i<\/sub> = a | x<sub>i\u22121<\/sub> = a) = 0.5, P(x<sub>i<\/sub> = S | x<sub>i\u22121<\/sub> = a) = 0.5, P(x<sub>1<\/sub> = a) = 1; \u0432\u0442\u043e\u0440\u044b\u0435 50 \u2014 \u0438\u0437 \u0440\u0430\u0441\u043f\u0440\u0435\u0434\u0435\u043b\u0435\u043d\u0438\u044f <br \/>  P(x<sub>i<\/sub> = b | x<sub>i\u22121<\/sub> = b) = 0.5, P(x<sub>i<\/sub> = S | x<sub>i\u22121<\/sub> = b) = 0.5, P(x<sub>1<\/sub> = b) = 1.<\/div>\n<\/div>\n<p>  <\/p>\n<h4>\u0420\u0435\u0448\u0435\u043d\u0438\u0435<\/h4>\n<p>  \u0417\u0430\u0434\u0430\u0447\u0430 \u0440\u0435\u0448\u0430\u0435\u0442\u0441\u044f \u0441 \u043f\u043e\u043c\u043e\u0449\u044c\u044e <a href=\"http:\/\/www.machinelearning.ru\/wiki\/index.php?title=EM-%D0%B0%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC\">EM-\u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0430<\/a>: \u043f\u0440\u0435\u0434\u043f\u043e\u043b\u0430\u0433\u0430\u0435\u0442\u0441\u044f, \u0447\u0442\u043e \u043f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u043b\u0435\u043d\u043d\u0430\u044f \u0432\u044b\u0431\u043e\u0440\u043a\u0430 \u0441\u0433\u0435\u043d\u0435\u0440\u0438\u0440\u043e\u0432\u0430\u043d\u0430 \u0438\u0437 \u0441\u043c\u0435\u0441\u0438 \u0434\u0432\u0443\u0445 \u043c\u0430\u0440\u043a\u043e\u0432\u0441\u043a\u0438\u0445 \u0446\u0435\u043f\u0435\u0439, \u043f\u0430\u0440\u0430\u043c\u0435\u0442\u0440\u044b \u043a\u043e\u0442\u043e\u0440\u044b\u0445 \u0432\u043e\u0441\u0441\u0442\u0430\u043d\u0430\u0432\u043b\u0438\u0432\u0430\u044e\u0442\u0441\u044f \u0432 \u043f\u0440\u043e\u0446\u0435\u0441\u0441\u0435 \u0438\u0442\u0435\u0440\u0430\u0446\u0438\u0439. \u041e\u0433\u0440\u0430\u043d\u0438\u0447\u0435\u043d\u0438\u0435 \u0432 80% \u043f\u0440\u0430\u0432\u0438\u043b\u044c\u043d\u044b\u0445 \u043e\u0442\u0432\u0435\u0442\u043e\u0432 \u0441\u0434\u0435\u043b\u0430\u043d\u043e, \u0447\u0442\u043e\u0431\u044b \u043d\u0430 \u043f\u0440\u0430\u0432\u0438\u043b\u044c\u043d\u043e\u0441\u0442\u044c \u0440\u0435\u0448\u0435\u043d\u0438\u044f \u043d\u0435 \u0432\u043b\u0438\u044f\u043b\u0438 \u043f\u0440\u0438\u043c\u0435\u0440\u044b, \u0443 \u043a\u043e\u0442\u043e\u0440\u044b\u0445 \u0432\u044b\u0441\u043e\u043a\u0430\u044f \u0432\u0435\u0440\u043e\u044f\u0442\u043d\u043e\u0441\u0442\u044c \u0432 \u043e\u0431\u0435\u0438\u0445 \u0446\u0435\u043f\u044f\u0445. \u042d\u0442\u0438 \u043f\u0440\u0438\u043c\u0435\u0440\u044b, \u0442\u0430\u043a\u0438\u043c \u043e\u0431\u0440\u0430\u0437\u043e\u043c, \u043f\u0440\u0438 \u043f\u0440\u0430\u0432\u0438\u043b\u044c\u043d\u043e\u043c \u0432\u043e\u0441\u0441\u0442\u0430\u043d\u043e\u0432\u043b\u0435\u043d\u0438\u0438 \u043c\u043e\u0433\u0443\u0442 \u0431\u044b\u0442\u044c \u043e\u0442\u043d\u0435\u0441\u0435\u043d\u044b \u043a \u0446\u0435\u043f\u0438, \u043d\u0435\u0432\u0435\u0440\u043d\u043e\u0439 \u0441 \u0442\u043e\u0447\u043a\u0438 \u0437\u0440\u0435\u043d\u0438\u044f \u0441\u0433\u0435\u043d\u0435\u0440\u0438\u0440\u043e\u0432\u0430\u043d\u043d\u043e\u0433\u043e \u043e\u0442\u0432\u0435\u0442\u0430.<\/p>\n<pre><code class=\"python\">import random import math   EPS = 1e-9   def empty_row(size):     return [0] * size   def empty_matrix(rows, cols):     return [empty_row(cols) for _ in range(rows)]   def normalized_row(row):     row_sum = sum(row) + EPS     return [x \/ row_sum for x in row]   def normalized_matrix(mtx):     return [normalized_row(r) for r in mtx]   def restore_params(alphabet, string_samples):     n_tokens = len(alphabet)     n_samples = len(string_samples)     samples = [tuple([alphabet.index(token) for token in s] + [n_tokens - 1, n_tokens - 1]) for s in string_samples]     probs = [random.random() for _ in range(n_samples)]      for _ in range(200):         old_probs = [x for x in probs]          # probs fixed            p0, A = empty_row(n_tokens), empty_matrix(n_tokens, n_tokens)         q0, B = empty_row(n_tokens), empty_matrix(n_tokens, n_tokens)         for prob, sample in zip(probs, samples):             p0[sample[0]] += prob             q0[sample[0]] += 1 - prob             for t1, t2 in zip(sample[:-1], sample[1:]):                 A[t1][t2] += prob                 B[t1][t2] += 1 - prob          A, p0 = normalized_matrix(A), normalized_row(p0)         B, q0 = normalized_matrix(B), normalized_row(q0)                  trans_log_diff = [             [math.log(b + EPS) - math.log(a + EPS) for b, a in zip(B_r, A_r)]             for B_r, A_r in zip(B, A)         ]                # A, p0, B, q0 fixed         probs = empty_row(n_samples)         for i, sample in enumerate(samples):             value = math.log(q0[sample[0]] + EPS) - math.log(p0[sample[0]] + EPS)             for t1, t2 in zip(sample[:-1], sample[1:]):                 value += trans_log_diff[t1][t2]             probs[i] = 1.0 \/ (1.0 + math.exp(value))                  if max(abs(x - y) for x, y in zip(probs, old_probs)) &lt; 1e-9:             break          return [int(x &gt; 0.5) for x in probs]   def main():     N, K = list(map(int, input().split()))     string_samples = []     alphabet = list(input().strip()) + ['']     for _ in range(N):         string_samples.append(input().rstrip())     result = restore_params(alphabet, string_samples)     for r in result:         print(r)   if __name__ == '__main__':     main()<\/code><\/pre>\n<p>  <\/p>\n<hr>\n<p>  \u0412\u043e\u0442 \u0440\u0430\u0437\u0431\u043e\u0440\u044b \u0437\u0430\u0434\u0430\u0447 \u043f\u043e <a href=\"https:\/\/habr.com\/ru\/company\/yandex\/blog\/457262\/\">\u0431\u044d\u043a\u0435\u043d\u0434\u0443<\/a> \u0438 <a href=\"https:\/\/habr.com\/ru\/company\/yandex\/blog\/460139\/\">\u0444\u0440\u043e\u043d\u0442\u0435\u043d\u0434\u0443<\/a>.<\/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\/461273\/\"> https:\/\/habr.com\/ru\/company\/yandex\/blog\/461273\/<\/a><\/p>\n","protected":false},"excerpt":{"rendered":"\n<div class=\"post__text post__text-html js-mediator-article\"><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/webt\/sd\/i7\/yd\/sdi7ydyv5yabtpudjamnnmm2dge.jpeg\"><\/p>\n<p>  \u041c\u044b \u043f\u0440\u043e\u0434\u043e\u043b\u0436\u0430\u0435\u043c \u043f\u0443\u0431\u043b\u0438\u043a\u043e\u0432\u0430\u0442\u044c \u0440\u0430\u0437\u0431\u043e\u0440\u044b \u0437\u0430\u0434\u0430\u0447, \u043a\u043e\u0442\u043e\u0440\u044b\u0435 \u043f\u0440\u0435\u0434\u043b\u0430\u0433\u0430\u043b\u0438\u0441\u044c \u043d\u0430 \u043d\u0435\u0434\u0430\u0432\u043d\u0435\u043c \u0447\u0435\u043c\u043f\u0438\u043e\u043d\u0430\u0442\u0435. \u041d\u0430 \u043e\u0447\u0435\u0440\u0435\u0434\u0438 \u2014 \u0437\u0430\u0434\u0430\u0447\u0438, \u0432\u0437\u044f\u0442\u044b\u0435 \u0438\u0437 \u043a\u0432\u0430\u043b\u0438\u0444\u0438\u043a\u0430\u0446\u0438\u043e\u043d\u043d\u043e\u0433\u043e \u0440\u0430\u0443\u043d\u0434\u0430 \u0434\u043b\u044f \u0441\u043f\u0435\u0446\u0438\u0430\u043b\u0438\u0441\u0442\u043e\u0432 \u043f\u043e \u043c\u0430\u0448\u0438\u043d\u043d\u043e\u043c\u0443 \u043e\u0431\u0443\u0447\u0435\u043d\u0438\u044e. \u042d\u0442\u043e \u0442\u0440\u0435\u0442\u0438\u0439 \u0442\u0440\u0435\u043a \u0438\u0437 \u0447\u0435\u0442\u044b\u0440\u0451\u0445 (\u0431\u044d\u043a\u0435\u043d\u0434, \u0444\u0440\u043e\u043d\u0442\u0435\u043d\u0434, ML, \u0430\u043d\u0430\u043b\u0438\u0442\u0438\u043a\u0430). \u0423\u0447\u0430\u0441\u0442\u043d\u0438\u043a\u0430\u043c \u043d\u0443\u0436\u043d\u043e \u0431\u044b\u043b\u043e \u0441\u0434\u0435\u043b\u0430\u0442\u044c \u043c\u043e\u0434\u0435\u043b\u044c \u0438\u0441\u043f\u0440\u0430\u0432\u043b\u0435\u043d\u0438\u044f \u043e\u043f\u0435\u0447\u0430\u0442\u043e\u043a \u0432 \u0442\u0435\u043a\u0441\u0442\u0430\u0445, \u043f\u0440\u0435\u0434\u043b\u043e\u0436\u0438\u0442\u044c \u0441\u0442\u0440\u0430\u0442\u0435\u0433\u0438\u044e \u0438\u0433\u0440\u044b \u043d\u0430 \u0438\u0433\u0440\u043e\u0432\u044b\u0445 \u0430\u0432\u0442\u043e\u043c\u0430\u0442\u0430\u0445, \u0434\u043e\u0432\u0435\u0441\u0442\u0438 \u0434\u043e \u0443\u043c\u0430 \u0441\u0438\u0441\u0442\u0435\u043c\u0443 \u0440\u0435\u043a\u043e\u043c\u0435\u043d\u0434\u0430\u0446\u0438\u0439 \u043a\u043e\u043d\u0442\u0435\u043d\u0442\u0430 \u0438 \u0441\u043e\u0441\u0442\u0430\u0432\u0438\u0442\u044c \u0435\u0449\u0451 \u043d\u0435\u0441\u043a\u043e\u043b\u044c\u043a\u043e \u043f\u0440\u043e\u0433\u0440\u0430\u043c\u043c.<\/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-292525","post","type-post","status-publish","format-standard","hentry"],"_links":{"self":[{"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=\/wp\/v2\/posts\/292525","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=292525"}],"version-history":[{"count":0,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=\/wp\/v2\/posts\/292525\/revisions"}],"wp:attachment":[{"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=292525"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=292525"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=292525"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}