{"id":269776,"date":"2015-12-07T15:28:02","date_gmt":"2015-12-07T12:28:02","guid":{"rendered":"http:\/\/savepearlharbor.com\/?p=269776"},"modified":"-0001-11-30T00:00:00","modified_gmt":"-0001-11-29T21:00:00","slug":"","status":"publish","type":"post","link":"https:\/\/savepearlharbor.com\/?p=269776","title":{"rendered":"\u0412\u043f\u0435\u0440\u0435\u0434, \u043d\u0430 \u043f\u043e\u0438\u0441\u043a\u0438 \u043f\u0430\u043b\u0438\u043d\u0434\u0440\u043e\u043c\u043e\u0432 2"},"content":{"rendered":"<p>       \u041d\u0435 \u0442\u0430\u043a \u0434\u0430\u0432\u043d\u043e \u043f\u0440\u043e\u0447\u0438\u0442\u0430\u043b \u043d\u0430 \u0445\u0430\u0431\u0440\u0435 <a href=\"http:\/\/habrahabr.ru\/post\/270325\/\">\u0441\u0442\u0430\u0442\u044c\u044e<\/a>  <a href=\"http:\/\/habrahabr.ru\/users\/grey_wolfs\/\" class=\"user_link\">grey_wolfs<\/a> \u043e \u0440\u0435\u0448\u0435\u043d\u0438\u0438 \u0438 \u043e\u043f\u0442\u0438\u043c\u0438\u0437\u0430\u0446\u0438\u0438 \u043b\u044e\u0431\u043e\u043f\u044b\u0442\u043d\u043e\u0439 \u043a\u043e\u043d\u043a\u0443\u0440\u0441\u043d\u043e\u0439 \u0437\u0430\u0434\u0430\u0447\u043a\u0438 \u0441 \u0432\u0435\u0441\u044c\u043c\u0430 \u043b\u0430\u043a\u043e\u043d\u0438\u0447\u043d\u044b\u043c \u043e\u043f\u0440\u0435\u0434\u0435\u043b\u0435\u043d\u0438\u0435\u043c:<\/p>\n<blockquote><p>\u00abThe decimal number 585 is 1001001001 in binary. It is palindromic in both bases. Find n-th palindromic number\u00bb. \u0418\u043b\u0438, \u043f\u043e-\u0440\u0443\u0441\u0441\u043a\u0438: \u00ab\u0414\u0435\u0441\u044f\u0442\u0438\u0447\u043d\u043e\u0435 \u0447\u0438\u0441\u043b\u043e 585 \u0432 \u0434\u0432\u043e\u0438\u0447\u043d\u043e\u0439 \u0441\u0438\u0441\u0442\u0435\u043c\u0435 \u0441\u0447\u0438\u0441\u043b\u0435\u043d\u0438\u044f \u0432\u044b\u0433\u043b\u044f\u0434\u0438\u0442 \u043a\u0430\u043a 1001001001. \u041e\u043d\u043e \u044f\u0432\u043b\u044f\u0435\u0442\u0441\u044f \u043f\u0430\u043b\u0438\u043d\u0434\u0440\u043e\u043c\u043e\u043c \u0432 \u043e\u0431\u0435\u0438\u0445 \u0441\u0438\u0441\u0442\u0435\u043c\u0430\u0445 \u0441\u0447\u0438\u0441\u043b\u0435\u043d\u0438\u044f. \u041d\u0430\u0439\u0434\u0438\u0442\u0435 n-\u0439 \u043f\u043e\u0434\u043e\u0431\u043d\u044b\u0439 \u043f\u0430\u043b\u0438\u043d\u0434\u0440\u043e\u043c\u00bb.<\/p><\/blockquote>\n<p>  <a name=\"habracut\"><\/a><br \/>  \u0410\u0432\u0442\u043e\u0440 \u043d\u0430\u0447\u0430\u043b \u0441\u0432\u043e\u0439 \u0443\u0432\u043b\u0435\u043a\u0430\u0442\u0435\u043b\u044c\u043d\u044b\u0439 \u0440\u0430\u0441\u0441\u043a\u0430\u0437 \u0441 \u0441\u0430\u043c\u043e\u0433\u043e \u0442\u0440\u0438\u0432\u0438\u0430\u043b\u044c\u043d\u043e\u0433\u043e \u0440\u0435\u0448\u0435\u043d\u0438\u044f \u043f\u0435\u0440\u0435\u0431\u043e\u0440\u043e\u043c \u0438 \u043f\u0440\u043e\u0432\u0435\u0440\u043a\u043e\u0439 \u0432\u0441\u0435\u0445 \u0447\u0438\u0441\u0435\u043b \u043e\u0442 <b>1<\/b> \u0434\u043e <b>N<\/b> \u0438 \u0432\u044b\u0447\u0438\u0441\u043b\u0438\u0442\u0435\u043b\u044c\u043d\u043e\u0439 \u0441\u043b\u043e\u0436\u043d\u043e\u0441\u0442\u044c\u044e <b>O(N * log(N))<\/b>, \u0433\u0434\u0435 <b>N<\/b> \u2014 \u043c\u0430\u043a\u0441\u0438\u043c\u0430\u043b\u044c\u043d\u043e\u0435 \u043f\u0440\u043e\u0432\u0435\u0440\u044f\u0435\u043c\u043e\u0435 \u0447\u0438\u0441\u043b\u043e. \u041c\u043d\u043e\u0436\u0438\u0442\u0435\u043b\u044c <b>log(N)<\/b> \u043d\u0435\u043e\u0431\u0445\u043e\u0434\u0438\u043c, \u0442.\u043a. \u0434\u043b\u044f \u043a\u0430\u0436\u0434\u043e\u0433\u043e \u043f\u0440\u043e\u0432\u0435\u0440\u044f\u0435\u043c\u043e\u0433\u043e \u0447\u0438\u0441\u043b\u0430 \u0441\u043e\u0432\u0435\u0440\u0448\u0430\u0435\u0442\u0441\u044f \u043d\u0435\u0441\u043a\u043e\u043b\u044c\u043a\u043e \u0434\u0435\u0439\u0441\u0442\u0432\u0438\u0439, \u0437\u0430\u0432\u0438\u0441\u044f\u0449\u0438\u0445 \u043e\u0442 \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u0430 \u0435\u0433\u043e \u0440\u0430\u0437\u0440\u044f\u0434\u043e\u0432.<\/p>\n<p>  \u041f\u0435\u0440\u0432\u0430\u044f \u0436\u0435 \u0440\u0430\u0431\u043e\u0447\u0430\u044f \u043e\u043f\u0442\u0438\u043c\u0438\u0437\u0430\u0446\u0438\u044f, \u0430 \u0438\u043c\u0435\u043d\u043d\u043e \u0437\u0430\u043c\u0435\u043d\u0430 \u043f\u0435\u0440\u0435\u0431\u043e\u0440\u0430 \u0432\u0441\u0435\u0445 \u0447\u0438\u0441\u0435\u043b \u043d\u0430 \u043f\u0435\u0440\u0435\u0431\u043e\u0440 \u0442\u043e\u043b\u044c\u043a\u043e \u0434\u0435\u0441\u044f\u0442\u0438\u0447\u043d\u044b\u0445 \u043f\u0430\u043b\u0438\u043d\u0434\u0440\u043e\u043c\u043e\u0432, \u043a\u0430\u0440\u0434\u0438\u043d\u0430\u043b\u044c\u043d\u043e \u0443\u043b\u0443\u0447\u0448\u0438\u043b\u0430 \u0432\u044b\u0447\u0438\u0441\u043b\u0438\u0442\u0435\u043b\u044c\u043d\u0443\u044e \u0441\u043b\u043e\u0436\u043d\u043e\u0441\u0442\u044c \u0434\u043e <b>O(N<sup>1\/2<\/sup> * log(N))<\/b>, \u0442. \u043a. \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e \u043f\u0440\u043e\u0432\u0435\u0440\u044f\u0435\u043c\u044b\u0445 \u0447\u0438\u0441\u0435\u043b \u0443\u043c\u0435\u043d\u044c\u0448\u0438\u043b\u043e\u0441\u044c \u0434\u043e <b>O(N<sup>1\/2<\/sup>)<\/b>. \u0418 \u043d\u0435\u0441\u043c\u043e\u0442\u0440\u044f \u043d\u0430 \u043d\u0435\u043a\u043e\u0442\u043e\u0440\u044b\u0435 \u043f\u043e\u0442\u0435\u0440\u0438 \u0438\u0437-\u0437\u0430 \u0443\u0441\u043b\u043e\u0436\u043d\u0435\u043d\u0438\u044f \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0430, \u043d\u0430 \u0434\u043e\u0441\u0442\u0430\u0442\u043e\u0447\u043d\u043e \u0431\u043e\u043b\u044c\u0448\u0438\u0445 <b>N<\/b> \u0432\u0440\u0435\u043c\u044f \u0432\u044b\u043f\u043e\u043b\u043d\u0435\u043d\u0438\u044f \u043f\u0440\u0435\u0434\u0441\u043a\u0430\u0437\u0443\u0435\u043c\u043e \u0443\u043b\u0443\u0447\u0448\u0438\u043b\u043e\u0441\u044c \u043d\u0430 \u043f\u043e\u0440\u044f\u0434\u043a\u0438.<\/p>\n<p>  \u0421\u0434\u0435\u043b\u0430\u0432 \u0435\u0449\u0435 \u043d\u0435\u0441\u043a\u043e\u043b\u044c\u043a\u043e \u043d\u0435\u0431\u043e\u043b\u044c\u0448\u0438\u0445 \u043e\u043f\u0442\u0438\u043c\u0438\u0437\u0430\u0446\u0438\u0439, \u0430\u0432\u0442\u043e\u0440 \u0443\u043b\u0443\u0447\u0448\u0438\u043b \u0432\u0440\u0435\u043c\u044f \u0432\u044b\u043f\u043e\u043b\u043d\u0435\u043d\u0438\u044f \u0435\u0449\u0435 \u0432 <b>3<\/b> \u0440\u0430\u0437\u0430, \u0438 \u043d\u0430 \u044d\u0442\u043e\u043c \u043d\u0435\u043f\u043b\u043e\u0445\u043e\u043c \u0440\u0435\u0437\u0443\u043b\u044c\u0442\u0430\u0442\u0435 \u0440\u0435\u0448\u0438\u043b \u043e\u0441\u0442\u0430\u043d\u043e\u0432\u0438\u0442\u044c\u0441\u044f.<\/p>\n<p>  \u0415\u0449\u0435 \u043d\u0435 \u0434\u043e\u0447\u0438\u0442\u0430\u0432 \u0434\u043e \u043a\u043e\u043d\u0446\u0430, \u044f \u043f\u043e\u0434\u0443\u043c\u0430\u043b \u043e \u0442\u043e\u043c, \u0447\u0442\u043e \u043f\u0440\u0438 \u0442\u043e\u0439 \u0436\u0435 \u0432\u044b\u0447\u0438\u0441\u043b\u0438\u0442\u0435\u043b\u044c\u043d\u043e\u0439 \u0441\u043b\u043e\u0436\u043d\u043e\u0441\u0442\u0438 <b>O(N<sup>1\/2<\/sup> * log(N))<\/b> \u043d\u0430\u0432\u0435\u0440\u043d\u044f\u043a\u0430 \u0431\u0443\u0434\u0435\u0442 \u0433\u043e\u0440\u0430\u0437\u0434\u043e \u0431\u044b\u0441\u0442\u0440\u0435\u0435 \u0440\u0430\u0431\u043e\u0442\u0430\u0442\u044c \u043d\u0435 \u0441\u043e \u0441\u0442\u0440\u043e\u043a\u0430\u043c\u0438, \u0430 \u043d\u0430\u043f\u0440\u044f\u043c\u0443\u044e \u0441 \u0447\u0438\u0441\u043b\u0430\u043c\u0438. \u0422\u043e \u0435\u0441\u0442\u044c \u0441\u0433\u0435\u043d\u0435\u0440\u0438\u0440\u043e\u0432\u0430\u0442\u044c \u043f\u043e\u0441\u043b\u0435\u0434\u043e\u0432\u0430\u0442\u0435\u043b\u044c\u043d\u043e\u0441\u0442\u044c \u043f\u0430\u043b\u0438\u043d\u0434\u0440\u043e\u043c\u043e\u0432, \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u044f \u043d\u0435 \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u0438 \u0441\u043e \u0441\u0442\u0440\u043e\u043a\u0430\u043c\u0438, \u0430 \u0430\u0440\u0438\u0444\u043c\u0435\u0442\u0438\u0447\u0435\u0441\u043a\u0438\u0435 \u0434\u0435\u0439\u0441\u0442\u0432\u0438\u044f.<\/p>\n<p>  \u0418 \u044d\u0442\u043e \u043e\u043a\u0430\u0437\u0430\u043b\u043e\u0441\u044c \u0441\u043e\u0432\u0441\u0435\u043c \u043d\u0435 \u0441\u043b\u043e\u0436\u043d\u043e, \u0432\u0435\u0434\u044c \u043f\u043e\u0441\u043b\u0435\u0434\u043e\u0432\u0430\u0442\u0435\u043b\u044c\u043d\u043e\u0441\u0442\u044c \u0447\u0438\u0441\u0435\u043b-\u043f\u0430\u043b\u0438\u043d\u0434\u0440\u043e\u043c\u043e\u0432 \u043e\u0434\u0438\u043d\u0430\u043a\u043e\u0432\u043e\u0439 \u0434\u043b\u0438\u043d\u044b \u043d\u0430\u043f\u043e\u043c\u0438\u043d\u0430\u0435\u0442 \u0430\u0440\u0438\u0444\u043c\u0435\u0442\u0438\u0447\u0435\u0441\u043a\u0443\u044e \u043f\u0440\u043e\u0433\u0440\u0435\u0441\u0441\u0438\u044e \u0441 \u043f\u043e\u0441\u0442\u043e\u044f\u043d\u043d\u044b\u043c \u0448\u0430\u0433\u043e\u043c, \u043a\u043e\u0442\u043e\u0440\u0443\u044e \u043d\u0430\u0434\u043e \u043a\u043e\u0440\u0440\u0435\u043a\u0442\u0438\u0440\u043e\u0432\u0430\u0442\u044c \u043a\u0430\u0436\u0434\u044b\u0435 <b>BASE<\/b>, <b>BASE<sup>2<\/sup><\/b>, <b>BASE<sup>3<\/sup><\/b>,\u2026 \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u043e\u0432.<\/p>\n<p>  \u041d\u0430\u043f\u0440\u0438\u043c\u0435\u0440, \u0434\u043b\u044f \u0434\u0435\u0441\u044f\u0442\u0438\u0447\u043d\u044b\u0445 \u043f\u0430\u043b\u0438\u043d\u0434\u0440\u043e\u043c\u043e\u0432 \u0448\u0438\u0440\u0438\u043d\u043e\u0439 <b>5<\/b> \u043e\u0441\u043d\u043e\u0432\u043d\u043e\u0439 \u0448\u0430\u0433 \u0431\u0443\u0434\u0435\u0442 \u0440\u0430\u0432\u043d <b>+100<\/b>:<\/p>\n<p>  <b><code> 10001, 10101, 10201, 10301, 10401, 10501, 10601, 10701, 10801, 10901, 11001 <\/code><\/b><\/p>\n<p>  \u041f\u043e\u0441\u043b\u0435\u0434\u043d\u0438\u0439 \u044d\u043b\u0435\u043c\u0435\u043d\u0442 \u043f\u043e\u0441\u043b\u0435\u0434\u043e\u0432\u0430\u0442\u0435\u043b\u044c\u043d\u043e\u0441\u0442\u0438 \u043d\u0435 \u044f\u0432\u043b\u044f\u0435\u0442\u0441\u044f \u043f\u0430\u043b\u0438\u043d\u0434\u0440\u043e\u043c\u043e\u043c \u0438 \u0442\u0440\u0435\u0431\u0443\u0435\u0442 \u043a\u043e\u0440\u0440\u0435\u043a\u0446\u0438\u0438 <b>+10<\/b>, \u0434\u043e <b><code>11011<\/code><\/b><\/p>\n<p>  <b><code> 11011, 11111, 11211, 11311, 11411, 11511, 11611, 11711, 11811, 11911, 12011 <\/code><\/b><\/p>\n<p>  \u041f\u043e\u0441\u043b\u0435\u0434\u043d\u0438\u0439 \u044d\u043b\u0435\u043c\u0435\u043d\u0442 \u044d\u043b\u0435\u043c\u0435\u043d\u0442 \u043f\u043e\u0441\u043b\u0435\u0434\u043e\u0432\u0430\u0442\u0435\u043b\u044c\u043d\u043e\u0441\u0442\u0438 \u043e\u043f\u044f\u0442\u044c \u0442\u0440\u0435\u0431\u0443\u0435\u0442 \u043a\u043e\u0440\u0440\u0435\u043a\u0446\u0438\u0438 <b>+10<\/b>, \u0434\u043e <b><code>12021<\/code><\/b><\/p>\n<p>  \u0422\u0430\u043a \u0434\u043e\u0445\u043e\u0434\u0438\u043c \u0442\u043e <b>99<\/b>-\u0433\u043e \u0438 <b>100<\/b>-\u0433\u043e \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u043e\u0432: <b><code>19991, 20091<\/code><\/b><\/p>\n<p>  \u041d\u0435\u043e\u0431\u0445\u043e\u0434\u0438\u043c\u0430\u044f \u043a\u043e\u0440\u0440\u0435\u043a\u0446\u0438\u044f \u0434\u043b\u044f <b>100<\/b>-\u0433\u043e \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u0430 <b>+10-99<\/b> =<b> -89<\/b>, \u0432 \u0440\u0435\u0437\u0443\u043b\u044c\u0442\u0430\u0442\u0435, \u043f\u043e\u043b\u0443\u0447\u0430\u0435\u043c <b><code>20002<\/code><\/b> \u0438 \u043f\u0440\u043e\u0434\u043e\u043b\u0436\u0430\u0435\u043c \u0434\u043e \u0442\u0435\u0445 \u043f\u043e\u0440, \u043f\u043e\u043a\u0430 \u043d\u0435 \u0434\u043e\u0439\u0434\u0435\u043c \u0434\u043e <b><code>99999<\/code><\/b>.<\/p>\n<p>  \u0422\u0430\u043a \u043a\u0430\u043a \u0430\u0440\u0438\u0444\u043c\u0435\u0442\u0438\u0447\u0435\u0441\u043a\u0430\u044f \u0433\u0435\u043d\u0435\u0440\u0430\u0446\u0438\u044f \u043f\u0430\u043b\u0438\u043d\u0434\u0440\u043e\u043c\u043e\u0432 \u0441\u0442\u0430\u043b\u0430 \u043e\u0447\u0435\u043d\u044c \u0431\u044b\u0441\u0442\u0440\u043e\u0439 (\u0432 \u0441\u0440\u0435\u0434\u043d\u0435\u043c \u0432\u0441\u0435\u0433\u043e \u043d\u0435\u0441\u043a\u043e\u043b\u044c\u043a\u043e \u043a\u043e\u043c\u043c\u0430\u043d\u0434 \u0430\u0441\u0441\u0435\u043c\u0431\u043b\u0435\u0440\u0430), \u044f \u0440\u0435\u0448\u0438\u043b, \u0447\u0442\u043e \u0433\u0435\u043d\u0435\u0440\u0430\u0446\u0438\u044f \u043f\u0430\u043b\u0438\u043d\u0434\u0440\u043e\u043c\u043e\u0432 \u0432 \u043e\u0434\u043d\u043e\u043c \u043e\u0441\u043d\u043e\u0432\u0430\u043d\u0438\u0438 + \u043f\u0440\u043e\u0432\u0435\u0440\u043a\u0430 \u043d\u0430 \u043f\u0430\u043b\u0438\u043d\u0434\u0440\u043e\u043c \u0432 \u0434\u0440\u0443\u0433\u043e\u043c \u0431\u0443\u0434\u0435\u0442 \u0440\u0430\u0431\u043e\u0442\u0430\u0442\u044c \u043c\u0435\u0434\u043b\u0435\u043d\u043d\u0435\u0435, \u0447\u0435\u043c \u043f\u0430\u0440\u0430\u043b\u043b\u0435\u043b\u044c\u043d\u0430\u044f \u0433\u0435\u043d\u0435\u0440\u0430\u0446\u0438\u044f \u043f\u0430\u043b\u0438\u043d\u0434\u0440\u043e\u043c\u043e\u0432 \u0432 \u043e\u0431\u043e\u0438\u0445 \u043e\u0441\u043d\u043e\u0432\u0430\u043d\u0438\u044f\u0445 \u0438 \u0441\u0440\u0430\u0432\u043d\u0435\u043d\u0438\u0435.<\/p>\n<p>  \u0412 \u0438\u0442\u043e\u0433\u0435, \u043f\u043e\u043b\u0443\u0447\u0438\u043b\u0441\u044f \u0441\u043b\u0435\u0434\u0443\u044e\u0449\u0438\u0439 \u043a\u043e\u0434 \u043d\u0430 C++:<\/p>\n<p>  \u0412\u0441\u043f\u043e\u043c\u043e\u0433\u0430\u0442\u0435\u043b\u044c\u043d\u0430\u044f \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u0430 \u0441\u043e \u043d\u0435\u043e\u0431\u0445\u043e\u0434\u0438\u043c\u044b\u043c\u0438 \u0441\u0442\u0435\u043f\u0435\u043d\u044f\u043c\u0438 \u043e\u0441\u043d\u043e\u0432\u0430\u043d\u0438\u044f:  <\/p>\n<pre><code class=\"cpp\">#undef POWER #define POWER(exp)  m_powers[exp]  template&lt;typename IntT&gt; struct BaseData { \tstatic const size_t MAX_WIDTH = sizeof(IntT) * CHAR_BIT;  \tBaseData( \t\tsize_t base, \t\tIntT maxValue) \t\t: m_base(base) \t{ \t\tPOWER(0) = IntT(1); \t\tfor (size_t i = 1; i &lt; MAX_WIDTH; ++i) { \t\t\tPOWER(i) = POWER(i - 1) * IntT(base); \t\t\tif (POWER(i) &gt;= maxValue) { \t\t\t\tm_maxWidth = i - 1; \t\t\t\tbreak; \t\t\t} \t\t} \t}  \tsize_t  m_base; \tsize_t  m_maxWidth; \tIntT    m_powers[MAX_WIDTH]; }; <\/code><\/pre>\n<p>  \u0418\u0442\u0435\u0440\u0430\u0442\u043e\u0440 \u043f\u0430\u043b\u0438\u043d\u0434\u0440\u043e\u043c\u043e\u0432:  <\/p>\n<pre><code class=\"cpp\">template&lt;typename IntT&gt; class Iterator { \tstatic const size_t MAX_WIDTH = sizeof(IntT) * CHAR_BIT;  private: \tstruct IncrementData \t{ \t\tsize_t  m_counter;         \/\/\tcurrent counter value \t\tsize_t  m_counterLimit;    \/\/\tnumber of iterations, usually B, but B - 1 for last increment \t\tIntT    m_increment;       \/\/\tincrement value \t};  public: \tinline Iterator( \t\tconst size_t base, \t\tconst IntT * powers) \t\t: m_base(base) \t\t, m_powers(powers) \t{ \t\tm_value = POWER(0);  \t\tSetWidth(1); \t}  \tinline void operator ++() \t{ \t\t\/\/\talways increment by basic \t\tm_value += m_basicIncrement;  \t\tsize_t i = 0; \t\tdo { \t\t\tif (--m_counters[i].m_counter) \t\t\t\treturn;  \t\t\t\/\/\treset counter \t\t\tm_counters[i].m_counter = m_counters[i].m_counterLimit; \t\t\t\/\/\tcorrect value on digit overflow \t\t\tm_value += m_counters[i].m_increment; \t\t} while (++i &lt; m_countersSize);  \t\t\/\/\tprepare to next width \t\tSetWidth(m_width + 1); \t}  \tinline const IntT & operator *() const \t{ \t\treturn m_value; \t}  private: \tvoid SetWidth( \t\tsize_t width) \t{ \t\tm_width = width; \t\tm_countersSize = (m_width + 1) \/ 2;  \t\tm_basicIncrement = POWER(m_countersSize - 1);  \t\tsize_t i; \t\tfor (i = 0; i &lt; m_countersSize - 1; ++i) { \t\t\tm_counters[i].m_counter = m_counters[i].m_counterLimit = m_base; \t\t\tm_counters[i].m_increment = POWER(m_countersSize - i - 2) - POWER(m_countersSize - i - 2) * m_base * m_base; \t\t} \t\tm_counters[i].m_counter = m_counters[i].m_counterLimit = m_base - 1; \t\tm_counters[i].m_increment = POWER(0) - POWER(1);  \t\tif (m_width & 1) \t\t\tm_counters[0].m_increment += POWER(m_countersSize); \t\telse \t\t\tm_basicIncrement += POWER(m_countersSize); \t}  \tIntT           m_value;                 \/\/\tcurrent value \tIntT           m_basicIncrement;        \/\/\tbasic increment (100... for odd width, 1100... for even width \tsize_t         m_countersSize;          \/\/\tjust greater half of width: (width + 1) \/ 2 \tIncrementData  m_counters[MAX_WIDTH]; \tsize_t         m_width;                 \/\/\tcurrent width = number of digits \tsize_t         m_base; \tconst IntT   * m_powers; }; <\/code><\/pre>\n<p>  \u0418, \u043d\u0430\u043a\u043e\u043d\u0435\u0446 main:  <\/p>\n<pre><code class=\"cpp\">int _tmain(int argc, _TCHAR* argv[]) { \tint64 limit = 18279440804497281;  \tBaseData&lt;int64&gt; base0(2, limit); \tBaseData&lt;int64&gt; base1(10, limit);  \tIterator&lt;int64&gt; it0(base0.m_base, base0.m_powers); \tIterator&lt;int64&gt; it1(base1.m_base, base1.m_powers);  \twhile (*it0 &lt;= limit) { \t\tif (*it0 &lt; *it1) \t\t\t++it0; \t\telse if (*it0 &gt; *it1) \t\t\t++it1; \t\telse { \t\t\tstd::cout &lt;&lt; *it0 &lt;&lt; std::endl; \t\t\t++it0; \t\t\t++it1; \t\t} \t}  \treturn 0; } <\/code><\/pre>\n<p>  <b>56<\/b>-\u0439 \u043f\u0430\u043b\u0438\u043d\u0434\u0440\u043e\u043c, \u0440\u0430\u0432\u043d\u044b\u0439 <b>18279440804497281<\/b> \u0431\u044b\u043b \u043f\u043e\u043b\u0443\u0447\u0435\u043d \u0447\u0435\u0440\u0435\u0437 <b>1.85<\/b> \u0441\u0435\u043a\u0443\u043d\u0434\u044b, \u0447\u0442\u043e \u043f\u0440\u0438\u043c\u0435\u0440\u043d\u043e \u0432 <b>150<\/b> \u0440\u0430\u0437 \u0431\u044b\u0441\u0442\u0440\u0435\u0435 \u043f\u0440\u0435\u0434\u044b\u0434\u0443\u0449\u0435\u0433\u043e \u0440\u0435\u0437\u0443\u043b\u044c\u0442\u0430\u0442\u0430 (\u043f\u0440\u0435\u0434\u043f\u043e\u043b\u0430\u0433\u0430\u044f, \u0447\u0442\u043e \u043a\u043e\u043c\u043f\u044c\u044e\u0442\u0435\u0440  <a href=\"http:\/\/habrahabr.ru\/users\/grey_wolfs\/\" class=\"user_link\">grey_wolfs<\/a> \u0438\u043c\u0435\u043b \u0432\u044b\u0447\u0438\u0441\u043b\u0438\u0442\u0435\u043b\u044c\u043d\u0443\u044e \u043c\u043e\u0449\u044c, \u0441\u0445\u043e\u0434\u043d\u0443\u044e \u0441 \u043c\u043e\u0438\u043c Intel Core i7-3770 CPU @ 3.40GHz). \u042f \u0443\u0434\u043e\u0432\u043b\u0435\u0442\u0432\u043e\u0440\u0435\u043d\u043d\u043e \u043f\u043e\u0442\u0438\u0440\u0430\u043b \u0440\u0443\u043a\u0438: \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u0443\u0436\u0435 \u043f\u0435\u0440\u0435\u0431\u0438\u0440\u0430\u043b \u043f\u043e\u0447\u0442\u0438 <b>300 000 000<\/b> \u043f\u0430\u043b\u0438\u043d\u0434\u0440\u043e\u043c\u043e\u0432 \u0432 \u0441\u0435\u043a\u0443\u043d\u0434\u0443, \u0430 \u0443 \u043c\u0435\u043d\u044f \u0432 \u0437\u0430\u043f\u0430\u0441\u0435 \u0431\u044b\u043b\u043e \u0435\u0449\u0435 \u0434\u0432\u0430 \u043a\u043e\u0437\u044b\u0440\u044f: \u0433\u0435\u043d\u0435\u0440\u0438\u0440\u043e\u0432\u0430\u0442\u044c \u0442\u043e\u043b\u044c\u043a\u043e \u0447\u0435\u0442\u043d\u044b\u0435 \u0434\u0435\u0441\u044f\u0442\u0438\u0447\u043d\u044b\u0435 \u043f\u0430\u043b\u0438\u043d\u0434\u0440\u043e\u043c\u044b (<b>-20-25<\/b>%) \u0438 \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u0442\u044c \u043c\u043d\u043e\u0433\u043e\u043f\u043e\u0442\u043e\u0447\u043d\u043e\u0441\u0442\u044c (<b>-70-85<\/b>% \u043f\u0440\u0438 8 \u043f\u043e\u0442\u043e\u043a\u0430\u0445)\u2026<\/p>\n<p>  \u0418 \u0442\u0443\u0442 \u044f \u0443\u0432\u0438\u0434\u0435\u043b \u043a\u043e\u043c\u043c\u0435\u043d\u0442\u0430\u0440\u0438\u0439, \u043a\u043e\u0442\u043e\u0440\u044b\u0439 \u043c\u0435\u043d\u044f \u043f\u0440\u043e\u0441\u0442\u043e \u00ab\u0443\u0431\u0438\u043b\u00bb:<\/p>\n<blockquote><p>@hellman<br \/>  \u041d\u0435 \u0442\u0430\u043a \u0434\u0430\u0432\u043d\u043e \u043d\u0430 \u043e\u0434\u043d\u043e\u043c \u0438\u0437 \u043a\u043e\u043d\u0442\u0435\u0441\u0442\u043e\u0432 codechef \u0431\u044b\u043b\u0430 \u0442\u0430\u043a\u0430\u044f \u0436\u0435 <a href=\"https:\/\/www.codechef.com\/COOK61\/problems\/DUALPAL\">\u0437\u0430\u0434\u0430\u0447\u043a\u0430<\/a>. \u0422\u043e\u043b\u044c\u043a\u043e \u0431\u0430\u0437\u044b \u0441\u0438\u0441\u0442\u0435\u043c \u0438\u0441\u0447\u0438\u0441\u043b\u0435\u043d\u0438\u044f \u043f\u0440\u043e\u0438\u0437\u0432\u043e\u043b\u044c\u043d\u044b\u0435 \u043e\u0442 2 \u0434\u043e 16, \u0438 \u043d\u0443\u0436\u043d\u043e \u0431\u044b\u043b\u043e \u043f\u0435\u0440\u0432\u044b\u0435 1000 \u043f\u0430\u043b\u0438\u043d\u0434\u0440\u043e\u043c\u043e\u0432 \u043c\u0435\u043d\u044c\u0448\u0438\u0435 2^60. \u041e\u0433\u0440\u0430\u043d\u0438\u0447\u0435\u043d\u0438\u0435 \u043f\u043e \u0432\u0440\u0435\u043c\u0435\u043d\u0438 \u2014 8 \u0441\u0435\u043a (\u043f\u0440\u0430\u0432\u0434\u0430 \u043d\u0430 \u0432\u0445\u043e\u0434\u0435 \u043c\u043e\u0436\u0435\u0442 \u0431\u044b\u0442\u044c 5 \u0442\u0435\u0441\u0442\u043e\u0432). Editorial \u0442\u0430\u043c \u0436\u0435 \u0435\u0441\u0442\u044c.  <\/p><\/blockquote>\n<p>  \u041c\u043e\u0439 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u043d\u0430\u0445\u043e\u0434\u0438\u043b \u0432\u0441\u0435 \u043f\u0430\u043b\u0438\u043d\u0434\u0440\u043e\u043c\u044b \u0434\u043e <b>2^60<\/b> \u0437\u0430 <b>15<\/b> \u0441\u0435\u043a\u0443\u043d\u0434, \u0442.\u0435. \u0432 \u0445\u0443\u0434\u0448\u0435\u043c \u0441\u043b\u0443\u0447\u0430\u0435 \u043d\u0435 \u0443\u043a\u043b\u0430\u0434\u044b\u0432\u0430\u043b\u0441\u044f \u0431\u044b \u0432 \u043e\u0433\u0440\u0430\u043d\u0438\u0447\u0435\u043d\u0438\u0435 \u043f\u043e \u0432\u0440\u0435\u043c\u0435\u043d\u0438 \u0434\u0430\u0436\u0435 \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u044f \u043c\u043d\u043e\u0433\u043e\u043f\u043e\u0442\u043e\u0447\u043d\u043e\u0441\u0442\u044c. \u0410 \u0432\u0435\u0434\u044c \u0432 Editorial \u0431\u044b\u043b \u0435\u0449\u0435 \u0438 \u0438\u0437\u0434\u0435\u0432\u0430\u0442\u0435\u043b\u044c\u0441\u043a\u0438\u0439 \u043a\u043e\u043c\u043c\u0435\u043d\u0442\u0430\u0440\u0438\u0439 \u00abwhy does the time limit for this question is so high 8 sec I haven&#8217;t seen such high limit in any questions&#8230;?\u00bb.<\/p>\n<p>  \u0423\u0434\u043e\u0432\u043b\u0435\u0442\u0432\u043e\u0440\u0435\u043d\u0438\u0435 \u0431\u044b\u0441\u0442\u0440\u043e \u0441\u043c\u0435\u043d\u0438\u043b\u043e\u0441\u044c \u0440\u0430\u0437\u043e\u0447\u0430\u0440\u043e\u0432\u0430\u043d\u0438\u0435\u043c: \u043c\u043e\u044f \u0440\u0435\u0430\u043b\u0438\u0437\u0430\u0446\u0438\u044f \u043f\u0435\u0440\u0435\u0431\u043e\u0440\u0430 \u0441 \u0432\u044b\u0447\u0438\u0441\u043b\u0438\u0442\u0435\u043b\u044c\u043d\u043e\u0439 \u0441\u043b\u043e\u0436\u043d\u043e\u0441\u0442\u044c\u044e <b>O(N<sup>1\/2<\/sup> * log(N))<\/b> \u0445\u043e\u0442\u044c \u0438 \u0431\u044b\u043b\u0430 \u0431\u043b\u0438\u0437\u043a\u0430 \u0441 \u043c\u0438\u043d\u0438\u043c\u0430\u043b\u044c\u043d\u043e\u043c\u0443 \u0442\u0435\u043e\u0440\u0435\u0442\u0438\u0447\u0435\u0441\u043a\u043e\u043c\u0443 \u043f\u0440\u0435\u0434\u0435\u043b\u0443, \u043d\u043e \u044d\u0442\u043e\u0433\u043e \u0432\u0441\u0435 \u0440\u0430\u0432\u043d\u043e \u0431\u044b\u043b\u043e \u043d\u0435\u0434\u043e\u0441\u0442\u0430\u0442\u043e\u0447\u043d\u043e. \u042f \u043f\u043e\u043f\u044b\u0442\u0430\u043b\u0441\u044f \u0440\u0430\u0437\u043e\u0431\u0440\u0430\u0442\u044c\u0441\u044f \u0432 \u0442\u0435\u043e\u0440\u0435\u0442\u0438\u0447\u0435\u0441\u043a\u043e\u043c \u0440\u0435\u0448\u0435\u043d\u0438\u0438, \u043e\u043f\u0438\u0441\u0430\u043d\u043d\u043e\u043c \u0432 Editorial, \u0434\u0430\u0436\u0435 \u043f\u043e\u0441\u043c\u043e\u0442\u0440\u0435\u043b \u043d\u0430 \u0438\u0445 \u043a\u043e\u0434, \u043d\u043e \u0441 \u043f\u0435\u0440\u0432\u043e\u0433\u043e \u0440\u0430\u0437\u0430 \u043f\u043e\u043d\u044f\u043b \u0442\u043e\u043b\u044c\u043a\u043e \u0442\u043e, \u0447\u0442\u043e \u043e\u043d\u0438 \u0441\u0443\u043c\u0435\u043b\u0438 \u0440\u0435\u0448\u0438\u0442\u044c \u0437\u0430\u0434\u0430\u0447\u0443 \u0441 \u0432\u044b\u0447\u0438\u0441\u043b\u0438\u0442\u0435\u043b\u044c\u043d\u043e\u0439 \u0441\u043b\u043e\u0436\u043d\u043e\u0441\u0442\u044c\u044e <b>O(N<sup>1\/4<\/sup> * log(N))<\/b>.<\/p>\n<p>  \u0412 \u044d\u0442\u043e\u0442 \u043c\u043e\u043c\u0435\u043d\u0442 \u044f \u043f\u0440\u0435\u043a\u0440\u0430\u0442\u0438\u043b \u0440\u0430\u0431\u043e\u0442\u0443 \u043d\u0430\u0434 \u0437\u0430\u0434\u0430\u0447\u043a\u043e\u0439, \u043d\u043e \u043e\u043d\u0430 \u043d\u0435 \u0432\u044b\u0445\u043e\u0434\u0438\u043b\u0430 \u0443 \u043c\u0435\u043d\u044f \u0438\u0437 \u0433\u043e\u043b\u043e\u0432\u044b. \u0418 \u0447\u0435\u0440\u0435\u0437 \u043d\u0435\u0441\u043a\u043e\u043b\u044c\u043a\u043e \u0434\u043d\u0435\u0439 \u044f \u0441\u043d\u043e\u0432\u0430 \u043a \u043d\u0435\u0439 \u0432\u0435\u0440\u043d\u0443\u043b\u0441\u044f.<\/p>\n<p>  \u041f\u0440\u043e\u0434\u043e\u043b\u0436\u0435\u043d\u0438\u0435 \u0441\u043b\u0435\u0434\u0443\u0435\u0442.               <\/p>\n<div class=\"clear\"><\/div>\n<p> \u0441\u0441\u044b\u043b\u043a\u0430 \u043d\u0430 \u043e\u0440\u0438\u0433\u0438\u043d\u0430\u043b \u0441\u0442\u0430\u0442\u044c\u0438 <a href=\"http:\/\/habrahabr.ru\/post\/272555\/\"> http:\/\/habrahabr.ru\/post\/272555\/<\/a><\/p>\n","protected":false},"excerpt":{"rendered":"<p>       \u041d\u0435 \u0442\u0430\u043a \u0434\u0430\u0432\u043d\u043e \u043f\u0440\u043e\u0447\u0438\u0442\u0430\u043b \u043d\u0430 \u0445\u0430\u0431\u0440\u0435 <a href=\"http:\/\/habrahabr.ru\/post\/270325\/\">\u0441\u0442\u0430\u0442\u044c\u044e<\/a>  <a href=\"http:\/\/habrahabr.ru\/users\/grey_wolfs\/\" class=\"user_link\">grey_wolfs<\/a> \u043e \u0440\u0435\u0448\u0435\u043d\u0438\u0438 \u0438 \u043e\u043f\u0442\u0438\u043c\u0438\u0437\u0430\u0446\u0438\u0438 \u043b\u044e\u0431\u043e\u043f\u044b\u0442\u043d\u043e\u0439 \u043a\u043e\u043d\u043a\u0443\u0440\u0441\u043d\u043e\u0439 \u0437\u0430\u0434\u0430\u0447\u043a\u0438 \u0441 \u0432\u0435\u0441\u044c\u043c\u0430 \u043b\u0430\u043a\u043e\u043d\u0438\u0447\u043d\u044b\u043c \u043e\u043f\u0440\u0435\u0434\u0435\u043b\u0435\u043d\u0438\u0435\u043c:<\/p>\n<blockquote><p>\u00abThe decimal number 585 is 1001001001 in binary. It is palindromic in both bases. Find n-th palindromic number\u00bb. \u0418\u043b\u0438, \u043f\u043e-\u0440\u0443\u0441\u0441\u043a\u0438: \u00ab\u0414\u0435\u0441\u044f\u0442\u0438\u0447\u043d\u043e\u0435 \u0447\u0438\u0441\u043b\u043e 585 \u0432 \u0434\u0432\u043e\u0438\u0447\u043d\u043e\u0439 \u0441\u0438\u0441\u0442\u0435\u043c\u0435 \u0441\u0447\u0438\u0441\u043b\u0435\u043d\u0438\u044f \u0432\u044b\u0433\u043b\u044f\u0434\u0438\u0442 \u043a\u0430\u043a 1001001001. \u041e\u043d\u043e \u044f\u0432\u043b\u044f\u0435\u0442\u0441\u044f \u043f\u0430\u043b\u0438\u043d\u0434\u0440\u043e\u043c\u043e\u043c \u0432 \u043e\u0431\u0435\u0438\u0445 \u0441\u0438\u0441\u0442\u0435\u043c\u0430\u0445 \u0441\u0447\u0438\u0441\u043b\u0435\u043d\u0438\u044f. \u041d\u0430\u0439\u0434\u0438\u0442\u0435 n-\u0439 \u043f\u043e\u0434\u043e\u0431\u043d\u044b\u0439 \u043f\u0430\u043b\u0438\u043d\u0434\u0440\u043e\u043c\u00bb.<\/p><\/blockquote>\n<p>  <\/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-269776","post","type-post","status-publish","format-standard","hentry"],"_links":{"self":[{"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=\/wp\/v2\/posts\/269776","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=269776"}],"version-history":[{"count":0,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=\/wp\/v2\/posts\/269776\/revisions"}],"wp:attachment":[{"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=269776"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=269776"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=269776"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}