{"id":303211,"date":"2020-05-08T03:00:26","date_gmt":"2020-05-08T03:00:26","guid":{"rendered":"http:\/\/savepearlharbor.com\/?p=303211"},"modified":"-0001-11-30T00:00:00","modified_gmt":"-0001-11-29T21:00:00","slug":"","status":"publish","type":"post","link":"https:\/\/savepearlharbor.com\/?p=303211","title":{"rendered":"\u0417\u0430\u043c\u043e\u0449\u0435\u043d\u0438\u0435 \u0434\u043e\u043c\u0438\u043d\u043e\u0448\u043a\u0430\u043c\u0438"},"content":{"rendered":"\n<div class=\"post__text post__text-html post__text_v1\" id=\"post-content-body\" data-io-article-url=\"https:\/\/habr.com\/ru\/post\/501008\/\">\n<p>\u041e\u0434\u043d\u0430 \u0438\u0437 \u043f\u0435\u0440\u0432\u044b\u0445 \u0434\u0435\u0439\u0441\u0442\u0432\u0438\u0442\u0435\u043b\u044c\u043d\u043e \u0438\u043d\u0442\u0435\u0440\u0435\u0441\u043d\u044b\u0445 \u0437\u0430\u0434\u0430\u0447 \u043f\u043e \u043c\u0430\u0442\u0435\u043c\u0430\u0442\u0438\u043a\u0435, \u0441 \u043a\u043e\u0442\u043e\u0440\u044b\u043c\u0438 \u044f \u0441\u0442\u043e\u043b\u043a\u043d\u0443\u043b\u0441\u044f \u0444\u043e\u0440\u043c\u0443\u043b\u0438\u0440\u0443\u0435\u0442\u0441\u044f \u0442\u0430\u043a: &quot;\u0438\u0437 \u0448\u0430\u0445\u043c\u0430\u0442\u043d\u043e\u0439 \u0434\u043e\u0441\u043a\u0438 \u0432\u044b\u0440\u0435\u0437\u0430\u043b\u0438 \u0434\u0432\u0435 \u043f\u0440\u043e\u0442\u0438\u0432\u043e\u043f\u043e\u043b\u043e\u0436\u043d\u044b\u0435 \u043f\u043e \u0434\u0438\u0430\u0433\u043e\u043d\u0430\u043b\u0438 \u0443\u0433\u043b\u043e\u0432\u044b\u0435 \u043a\u043b\u0435\u0442\u043a\u0438, \u043c\u043e\u0436\u043d\u043e \u043b\u0438 \u043e\u0441\u0442\u0430\u0432\u0448\u0443\u044e\u0441\u044f \u0447\u0430\u0441\u0442\u044c \u0440\u0430\u0437\u0440\u0435\u0437\u0430\u0442\u044c \u043d\u0430 &quot;\u0434\u043e\u043c\u0438\u043d\u043e\u0448\u043a\u0438&quot; \u2014 \u0444\u0438\u0433\u0443\u0440\u043a\u0438 \u0438\u0437 \u0434\u0432\u0443\u0445 \u043a\u043b\u0435\u0442\u043e\u043a, \u0443 \u043a\u043e\u0442\u043e\u0440\u044b\u0445 \u043e\u0434\u043d\u0430 \u0441\u0442\u043e\u0440\u043e\u043d\u0430 \u043e\u0431\u0449\u0430\u044f?&quot;. \u0423 \u043d\u0435\u0435 \u043e\u0447\u0435\u043d\u044c \u043f\u0440\u043e\u0441\u0442\u0430\u044f \u0444\u043e\u0440\u043c\u0443\u043b\u0438\u0440\u043e\u0432\u043a\u0430, \u0432 \u043e\u0442\u043b\u0438\u0447\u0438\u0435 \u043e\u0442 \u0432\u0435\u043b\u0438\u043a\u043e\u0439 \u0442\u0435\u043e\u0440\u0435\u043c\u044b \u0424\u0435\u0440\u043c\u0430 \u043e\u043d\u0430 \u0438\u043c\u0435\u0442 \u043f\u0440\u043e\u0441\u0442\u043e\u0435, \u044d\u043b\u0435\u0433\u0430\u043d\u0442\u043d\u043e\u0435, \u043d\u043e \u043d\u0435\u043e\u0447\u0435\u0432\u0438\u0434\u043d\u043e\u0435 \u0440\u0435\u0448\u0435\u043d\u0438\u0435 (\u0435\u0441\u043b\u0438 \u0432\u044b \u0437\u043d\u0430\u0435\u0442\u0435 \u0440\u0435\u0448\u0435\u043d\u0438\u0435 \u0437\u0430\u0434\u0430\u0447\u0438, \u0442\u043e \u043f\u043e\u043f\u0440\u043e\u0431\u0443\u0439\u0442\u0435 \u043f\u0440\u0438\u043c\u0435\u043d\u0438\u0442\u044c \u0435\u0433\u043e \u043a \u0444\u0438\u0433\u0443\u0440\u0435 \u0441\u043f\u0440\u0430\u0432\u0430).<\/p>\n<p>  <\/p>\n<p><img decoding=\"async\" width=\"45%\" src=\"https:\/\/habrastorage.org\/webt\/jx\/3k\/iy\/jx3kiy6ls43az8se19mqwzujijw.png\"> <img decoding=\"async\" width=\"45%\" src=\"https:\/\/habrastorage.org\/webt\/os\/ah\/m7\/osahm7ciwntrzpvkshhayxh53gi.png\"><\/p>\n<p>  <\/p>\n<p>\u0412 \u044d\u0442\u043e\u0439 \u0441\u0442\u0430\u0442\u044c\u044f \u044f \u0440\u0430\u0441\u0441\u043a\u0430\u0436\u0443 \u043e \u043d\u0435\u0441\u043a\u043e\u043b\u044c\u043a\u0438\u0445 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0430\u0445, \u043a\u043e\u0442\u043e\u0440\u044b\u0435 \u0443\u043c\u0435\u044e\u0442 \u043f\u043e\u043a\u0440\u044b\u0432\u0430\u0442\u044c \u0434\u043e\u043c\u0438\u043d\u043e\u0448\u043a\u0430\u043c\u0438 \u043f\u0440\u043e\u0438\u0437\u0432\u043e\u043b\u044c\u043d\u0443\u044e \u043a\u043b\u0435\u0442\u0447\u0430\u0442\u0443\u044e \u0444\u0438\u0433\u0443\u0440\u0443 \u043d\u0430 \u043f\u043b\u043e\u0441\u043a\u043e\u0441\u0442\u0438, \u0435\u0441\u043b\u0438 \u044d\u0442\u043e \u0432\u043e\u0437\u043c\u043e\u0436\u043d\u043e, \u043d\u0430\u0445\u043e\u0434\u0438\u0442\u044c \u0441\u0438\u0442\u0443\u0430\u0446\u0438\u0438, \u043a\u043e\u0433\u0434\u0430 \u044d\u0442\u043e \u043d\u0435\u0432\u043e\u0437\u043c\u043e\u0436\u043d\u043e \u0438 \u0441\u0447\u0438\u0442\u0430\u0442\u044c \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e \u0432\u043e\u0437\u043c\u043e\u0436\u043d\u044b\u0445 \u0437\u0430\u043c\u043e\u0449\u0435\u043d\u0438\u0439 \u0434\u043e\u043c\u0438\u043d\u043e\u0448\u043a\u0430\u043c\u0438.<\/p>\n<p><a name=\"habracut\"><\/a>  <\/p>\n<p><b>Nota bene!<\/b> \u041c\u0430\u0442\u0435\u0440\u0438\u0430\u043b \u044d\u0442\u043e\u0439 \u0441\u0442\u0430\u0442\u044c\u0438 \u2014 \u044d\u0442\u043e \u0443\u0441\u0435\u0447\u0435\u043d\u043d\u044b\u0439 \u0432\u0430\u0440\u0438\u0430\u043d\u0442 \u0432\u043e\u0442 <a href=\"https:\/\/github.com\/Malkovsky\/python-examples\/blob\/master\/domino_tiling.ipynb\" rel=\"nofollow\">\u044d\u0442\u043e\u0433\u043e jupyter-notebook<\/a>, \u0432\u0441\u0435 \u043a\u0430\u0440\u0442\u0438\u043d\u043a\u0438 \u0438 \u0430\u043d\u0438\u043c\u0430\u0446\u0438\u0438, \u043a\u043e\u0442\u043e\u0440\u044b\u0435 \u0432\u044b \u0443\u0432\u0438\u0434\u0438\u0442\u0435 \u0432 \u0441\u0442\u0430\u0442\u044c\u0435, \u0441\u0433\u0435\u043d\u0435\u0440\u0438\u0440\u043e\u0432\u0430\u043d\u044b \u043a\u043e\u0434\u043e\u043c \u0438\u0437 \u044d\u0442\u043e\u0433\u043e \u043d\u043e\u0443\u0442\u0431\u0443\u043a\u0430 (\u043f\u0440\u0430\u0432\u0434\u0430 \u0430\u043d\u0438\u043c\u0430\u0446\u0438\u0439 \u043d\u0435 \u0431\u0443\u0434\u0435\u0442 \u0432 github \u043f\u0440\u0435\u0434\u043f\u0440\u043e\u0441\u043c\u043e\u0442\u0440\u0435). \u041a \u0441\u043b\u043e\u0432\u0443, \u043a\u0430\u0440\u0442\u0438\u043d\u043a\u0438 \u0438\u0437 \u0437\u0430\u0433\u043e\u043b\u043e\u0432\u043a\u0430 \u0442\u0430\u043a\u0436\u0435 \u0441\u0433\u0435\u043d\u0435\u0440\u0438\u0440\u043e\u0432\u0430\u043d\u044b \u0441 \u043f\u043e\u043c\u043e\u0449\u044c\u044e python\/matplotlib<\/p>\n<p>  <\/p>\n<div class=\"spoiler\" role=\"button\" tabindex=\"0\">                         <b class=\"spoiler_title\">\u0412\u0441\u043f\u043e\u043c\u043e\u0433\u0430\u0442\u0435\u043b\u044c\u043d\u044b\u0439 \u043a\u043e\u0434 \u0434\u043b\u044f \u043e\u0442\u0440\u0438\u0441\u043e\u0432\u043a\u0438, \u043e\u043d \u0435\u0449\u0435 \u043f\u0440\u0438\u0433\u043e\u0434\u0438\u0442\u0441\u044f<\/b>                         <\/p>\n<div class=\"spoiler_text\">\n<pre><code class=\"python\">import matplotlib.pyplot as plt from matplotlib import colors as mcolors colors = dict(mcolors.BASE_COLORS, **mcolors.CSS4_COLORS)  # Sort colors by hue, saturation, value and name. by_hsv = sorted((tuple(mcolors.rgb_to_hsv(mcolors.to_rgba(color)[:3])), name)                 for name, color in colors.items()) names = [name for hsv, name in by_hsv if name not in {'black', 'k', 'w', 'white', 'crimson', 'royalblue', 'limegreen', 'yellow', 'orange'}] import random random.shuffle(names) names = ['crimson', 'royalblue', 'limegreen', 'yellow', 'orange', *names] names.append('red') names.append('white') names.append('black')<\/code><\/pre>\n<p>  <\/p>\n<pre><code class=\"python\">def fill_cell(i, j, color, ax):     ax.fill([i, i, i + 1, i + 1, i], [j, j + 1, j + 1, j, j], color=color)  def draw_filling(filling):     if filling is not None:         n = len(filling)         m = len(filling[0])         fig = plt.figure(figsize=(m * 0.75, n * 0.75))          ax = fig.add_axes([0, 0, 1, 1])         ax.get_xaxis().set_visible(False)         ax.get_yaxis().set_visible(False)                for name, spine in ax.spines.items():             spine.set_visible(False)             spine.set_visible(False)          for i, row in enumerate(filling):             i = n - i - 1             for j, cell in enumerate(row):                 fill_cell(j, i, names[cell], ax)          for i in range(n + 1):             ax.plot([0, m], [i, i], color='black')         for i in range(m + 1):             ax.plot([i, i], [0, n], color='black')         plt.close(fig)         return fig     else:         return None<\/code><\/pre>\n<\/div><\/div>\n<p>  <\/p>\n<div class=\"spoiler\" role=\"button\" tabindex=\"0\">                         <b class=\"spoiler_title\">\u041f\u0440\u0435\u0436\u0434\u0435, \u0447\u0435\u043c \u043f\u0435\u0440\u0435\u0439\u0442\u0438 \u0434\u0430\u043b\u044c\u0448\u0435, \u0440\u0435\u0448\u0435\u043d\u0438\u0435 \u0438\u0441\u0445\u043e\u0434\u043d\u043e\u0439 \u0437\u0430\u0434\u0430\u0447\u0438<\/b>                         <\/p>\n<div class=\"spoiler_text\">\n<p>\u0421\u0434\u0435\u043b\u0430\u0442\u044c \u044d\u0442\u043e \u043d\u0435\u0432\u043e\u0437\u043c\u043e\u0436\u043d\u043e, \u0438 \u044d\u0442\u043e\u043c\u0443 \u0435\u0441\u0442\u044c \u043a\u0440\u0430\u0441\u0438\u0432\u043e\u0435 \u0438 \u043f\u0440\u043e\u0441\u0442\u043e\u0435 \u043e\u0431\u044a\u044f\u0441\u043d\u0435\u043d\u0438\u0435:<\/p>\n<p>  <\/p>\n<ul>\n<li>\u041d\u0430 \u043e\u0441\u0442\u0430\u0432\u0448\u0435\u0439\u0441\u044f \u0447\u0430\u0441\u0442\u0438 \u0434\u043e\u0441\u043a\u0438 30 \u0447\u0435\u0440\u043d\u044b\u0445 \u0438 32 \u0431\u0435\u043b\u044b\u0445 \u043a\u043b\u0435\u0442\u043a\u0438<\/li>\n<li>\u041a\u0430\u0436\u0434\u0430\u044f \u0434\u043e\u043c\u0438\u043d\u043e\u0448\u043a\u0430 \u0441\u043e\u0441\u0442\u043e\u0438\u0442 \u0438\u0437 \u043e\u0434\u043d\u043e\u0439 \u0447\u0435\u0440\u043d\u043e\u0439 \u0438 \u043e\u0434\u043d\u043e\u0439 \u0431\u0435\u043b\u043e\u0439 \u043a\u043b\u0435\u0442\u043a\u0438<\/li>\n<li>\u041a\u0430\u043a \u0431\u044b \u043c\u044b \u043d\u0435 \u0440\u0430\u0437\u0440\u0435\u0437\u0430\u043b\u0438 \u0444\u0438\u0433\u0443\u0440\u0443 \u043d\u0430 \u0434\u043e\u043c\u0438\u043d\u043e\u0448\u043a\u0438, \u0432 \u0438\u0442\u043e\u0433\u0435 \u043d\u0430 \u0434\u043e\u043c\u0438\u043d\u043e\u0448\u043a\u0430\u0445 \u0431\u0443\u0434\u0435\u0442 \u0440\u0430\u0432\u043d\u043e\u0435 \u0447\u0438\u0441\u043b\u043e \u0431\u0435\u043b\u044b\u0445 \u0438 \u0447\u0435\u0440\u043d\u044b\u0445 \u043a\u043b\u0435\u0442\u043e\u043a<\/li>\n<\/ul>\n<\/div><\/div>\n<p>  <\/p>\n<h2 id=\"dinamicheskoe-programmirovanie-po-profilyu\">\u0414\u0438\u043d\u0430\u043c\u0438\u0447\u0435\u0441\u043a\u043e\u0435 \u043f\u0440\u043e\u0433\u0440\u0430\u043c\u043c\u0438\u0440\u043e\u0432\u0430\u043d\u0438\u0435 \u043f\u043e \u043f\u0440\u043e\u0444\u0438\u043b\u044e<\/h2>\n<p>  <\/p>\n<p>\u041f\u0440\u043e \u0434\u0438\u043d\u0430\u043c\u0438\u0447\u0435\u0441\u043a\u043e\u0433\u043e \u043f\u0440\u043e\u0433\u0440\u0430\u043c\u043c\u0438\u0440\u043e\u0432\u0430\u043d\u0438\u044f \u0435\u0441\u0442\u044c <a href=\"https:\/\/habr.com\/ru\/post\/191498\/\">\u0441\u0442\u0430\u0442\u044c\u044f \u043d\u0430 \u0445\u0430\u0431\u0440\u0435<\/a>, \u043a\u043e\u0442\u043e\u0440\u0430\u044f \u0434\u0430\u0436\u0435 \u0441\u043e\u0434\u0435\u0440\u0436\u0438\u0442 \u043f\u0440\u0438\u043c\u0435\u0440 \u0441 \u043f\u043e\u043a\u0440\u044b\u0442\u0438\u0435\u043c \u0434\u043e\u043c\u0438\u043d\u043e\u0448\u043a\u0430\u043c\u0438, \u044f \u043d\u0435\u043c\u043d\u043e\u0433\u043e \u0440\u0430\u0441\u0448\u0438\u0440\u044e \u044d\u0442\u043e\u0442 \u043f\u0440\u0438\u043c\u0435\u0440.<\/p>\n<p>  <\/p>\n<p>\u041e\u0441\u043d\u043e\u0432\u043d\u0430\u044f \u0441\u0443\u0442\u044c \u0434\u0438\u043d\u0430\u043c\u0438\u0447\u0435\u0441\u043a\u043e\u0433\u043e \u043f\u0440\u043e\u0433\u0440\u0430\u043c\u043c\u0438\u0440\u043e\u0432\u0430\u043d\u0438\u044f \u0437\u0430\u043a\u043b\u044e\u0447\u0430\u0435\u0442\u0441\u044f \u0432 \u0442\u043e\u043c, \u0447\u0442\u043e\u0431\u044b \u043f\u0440\u0438\u0434\u0443\u043c\u0430\u0442\u044c \u0434\u043b\u044f \u0438\u0441\u0445\u043e\u0434\u043d\u043e\u0439 \u0437\u0430\u0434\u0430\u0447\u0438 \u043a\u0430\u043a\u0438\u0435-\u0442\u043e \u043f\u0440\u043e\u043c\u0435\u0436\u0443\u0442\u043e\u0447\u043d\u044b\u0435 \u043f\u043e\u0434\u0437\u0430\u0434\u0430\u0447\u0438 \u0442\u0430\u043a, \u0447\u0442\u043e\u0431\u044b \u0438\u0445 \u043c\u043e\u0436\u043d\u043e \u0431\u044b\u043b\u043e \u043b\u0435\u0433\u043a\u043e \u0434\u0440\u0443\u0433 \u0447\u0435\u0440\u0435\u0437 \u0434\u0440\u0443\u0433\u0430 \u0432\u044b\u0440\u0430\u0437\u0438\u0442\u044c. \u041d\u0430\u043f\u0440\u0438\u043c\u0435\u0440, \u0435\u0441\u043b\u0438 \u043c\u044b \u0445\u043e\u0442\u0438\u043c \u0432\u044b\u0447\u0438\u0441\u043b\u0438\u0442\u044c \u0434\u0432\u0443\u0445\u0441\u043e\u0442\u043e\u0435 \u0447\u0438\u0441\u043b\u043e \u0424\u0438\u0431\u043e\u043d\u0430\u0447\u0447\u0438, \u0442\u043e \u0434\u043b\u044f \u044d\u0442\u043e\u0433\u043e \u043c\u043e\u0436\u043d\u043e \u043f\u043e\u0441\u043b\u0435\u0434\u043e\u0432\u0430\u0442\u0435\u043b\u044c\u043d\u043e \u0432\u044b\u0447\u0438\u0441\u043b\u0438\u0442\u044c \u0432\u0441\u0435 \u0447\u0438\u0441\u043b\u0430 \u0424\u0438\u0431\u043e\u043d\u0430\u0447\u0447\u0438 \u0432\u043f\u043b\u043e\u0442\u044c \u0434\u043e \u043d\u0443\u0436\u043d\u043e\u0433\u043e \u043d\u0430\u043c \u043f\u0440\u0438\u043c\u0435\u043d\u044f\u044f \u0441\u043e\u043e\u0442\u043d\u043e\u0448\u0435\u043d\u0438\u0435<\/p>\n<p>  <\/p>\n<p><math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/187\/484\/3a8\/1874843a8028aae2822ae33bac592d69.svg\" alt=\"$ F_{n+1}=F_n+F_{n-1}. $\" data-tex=\"display\"><\/math><\/p>\n<p>  <\/p>\n<p>\u0410\u043d\u0430\u043b\u043e\u0433\u0438\u0447\u043d\u043e \u043c\u043e\u0436\u043d\u043e \u0432\u044b\u0447\u0438\u0441\u043b\u0438\u0442\u044c \u0447\u0438\u0441\u043b\u043e &quot;\u0441\u043e\u0447\u0435\u0442\u0430\u043d\u0438\u0439&quot; <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/bbc\/289\/5e5\/bbc2895e5f173cca6296118530c50b4b.svg\" alt=\"$C_n^k$\" data-tex=\"inline\"><\/math>, \u0432\u043e\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u0432\u0448\u0438\u0441\u044c \u043e\u0434\u043d\u0438\u043c \u0438\u0437 \u0441\u043b\u0435\u0434\u0443\u044e\u0449\u0438\u0445 \u0440\u0435\u043a\u0443\u0440\u0440\u0435\u043d\u0442\u043d\u044b\u0445 \u0441\u043e\u043e\u0442\u043d\u043e\u0448\u0435\u043d\u0438\u0439<\/p>\n<p>  <\/p>\n<p><math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/591\/232\/aa9\/591232aa96074489c6eae1e9f4f67041.svg\" alt=\"$ C_n^k=\\frac{n}{k}C_{n-1}^{k-1}, $\" data-tex=\"display\"><\/math><\/p>\n<p>  <\/p>\n<p><math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/e20\/c9b\/a71\/e20c9ba713be96b75f9ea44ab937d736.svg\" alt=\"$ C_n^k=C_{n-1}^k+C_{n-1}^{k-1}. $\" data-tex=\"display\"><\/math><\/p>\n<p>  <\/p>\n<p>\u0414\u043b\u044f \u0437\u0430\u0434\u0430\u0447\u0438 &quot;\u043c\u043e\u0436\u043d\u043e \u043b\u0438 \u0437\u0430\u043c\u043e\u0441\u0442\u0438\u0442\u044c \u0434\u043e\u043c\u0438\u043d\u043e\u0448\u043a\u0430\u043c\u0438 \u043f\u0440\u044f\u043c\u043e\u0443\u0433\u043e\u043b\u044c\u043d\u0438\u043a <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/038\/f9e\/5bf\/038f9e5bf254d47500d869632af1d6ea.svg\" alt=\"$n\\times m$\" data-tex=\"inline\"><\/math>?&quot; \u043a \u0441\u043e\u0436\u0430\u043b\u0435\u043d\u0438\u044e \u043f\u043e\u0434\u043e\u0431\u043d\u044b\u0445 \u043f\u0440\u043e\u0441\u0442\u044b\u0445 \u0441\u043e\u043e\u0442\u043d\u043e\u0448\u0435\u043d\u0438\u0439 \u043d\u0435 \u0441\u0443\u0449\u0435\u0441\u0442\u0432\u0443\u0435\u0442. \u0422\u0435\u043c \u043d\u0435 \u043c\u0435\u043d\u0435\u0435, \u0435\u0441\u043b\u0438 \u043c\u044b \u0440\u0430\u0441\u0441\u043c\u043e\u0442\u0440\u0438\u043c \u0431\u043e\u043b\u0435\u0435 \u0448\u0438\u0440\u043e\u043a\u0438\u0439 \u043a\u043b\u0430\u0441\u0441 \u0444\u0438\u0433\u0443\u0440\u043e\u043a, \u0442\u043e \u0442\u0430\u043a\u0438\u0435 \u0441\u043e\u043e\u0442\u043d\u043e\u0448\u0435\u043d\u0438\u044f \u0443\u0436\u0435 \u0441\u0442\u0430\u043d\u0443\u0442 \u0432\u043e\u0437\u043c\u043e\u0436\u043d\u044b\u043c\u0438, \u0433\u043b\u0430\u0432\u043d\u043e\u0435 \u0447\u0442\u043e\u0431\u044b \u044d\u0442\u043e \u043d\u0435 \u0431\u044b\u043b\u0438 \u0441\u043b\u0438\u0448\u043a\u043e\u043c \u043c\u0430\u043b\u0435\u043d\u044c\u043a\u0438\u0435 \u043a\u043b\u0430\u0441\u0441\u044b \u0438 \u0434\u0438\u043d\u0430\u043c\u0438\u0447\u0435\u0441\u043a\u043e\u0435 \u043f\u0440\u043e\u0433\u0440\u0430\u043c\u043c\u0438\u0440\u043e\u0432\u0430\u043d\u0438\u0435 \u043d\u0435 \u043f\u0440\u0435\u0432\u0440\u0430\u0442\u0438\u043b\u043e\u0441\u044c \u0432 \u0431\u0430\u043d\u0430\u043b\u044c\u043d\u044b\u0439 \u043f\u0435\u0440\u0435\u0431\u043e\u0440.<\/p>\n<p>  <\/p>\n<p>\u041f\u043e\u0441\u043c\u043e\u0442\u0440\u0438\u043c \u043d\u0430 \u0441\u043b\u0435\u0434\u0443\u044e\u0449\u0438\u0439 \u043a\u043b\u0430\u0441\u0441 \u0444\u0438\u0433\u0443\u0440\u043e\u043a: \u0443 \u043d\u0430\u0441 \u0435\u0441\u0442\u044c \u043f\u0440\u044f\u043c\u043e\u0443\u0433\u043e\u043b\u044c\u043d\u0438\u043a <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/169\/ff9\/91e\/169ff991e991a4c9793394790dfeef4f.svg\" alt=\"$(k-1)\\times m$\" data-tex=\"inline\"><\/math>, \u043d\u0430 \u0441\u0442\u0440\u043e\u043a\u0435 <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/16d\/a50\/7b2\/16da507b2fc389688ef0659939dcc647.svg\" alt=\"$k$\" data-tex=\"inline\"><\/math> \u043f\u0440\u0438\u0441\u0443\u0442\u0441\u0442\u0432\u0443\u044e\u0442 \u043f\u0435\u0440\u0432\u044b\u0435 <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/b82\/8e2\/475\/b828e2475a3a56280b895f35eb250ea2.svg\" alt=\"$j$\" data-tex=\"inline\"><\/math> \u043a\u043b\u0435\u0442\u043e\u043a, \u043e\u0441\u0442\u0430\u043b\u044c\u043d\u044b\u0435 \u0437\u0430\u0434\u0430\u044e\u0442\u0441\u044f <strong>\u043f\u0440\u043e\u0444\u0438\u043b\u0435\u043c<\/strong>, \u043d\u0430 \u0441\u0442\u0440\u043e\u043a\u0435 <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/44c\/562\/936\/44c562936a615ceeecfca5c080e31de8.svg\" alt=\"$k+1$\" data-tex=\"inline\"><\/math> \u043f\u0435\u0440\u0432\u044b\u0435 <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/b82\/8e2\/475\/b828e2475a3a56280b895f35eb250ea2.svg\" alt=\"$j$\" data-tex=\"inline\"><\/math> \u043a\u043b\u0435\u0442\u043e\u043a \u0437\u0430\u0434\u0430\u044e\u0442\u0441\u044f \u043f\u0440\u043e\u0444\u0438\u043b\u0435\u043c, \u043e\u0441\u0442\u0430\u043b\u044c\u043d\u044b\u0435 \u043d\u0435 \u0443\u0447\u0430\u0441\u0442\u0432\u0443\u044e\u0442. \u041f\u0440\u043e\u0444\u0438\u043b\u044c \u2014 \u044d\u0442\u043e \u043f\u043e\u0441\u043b\u0435\u0434\u043e\u0432\u0430\u0442\u0435\u043b\u044c\u043d\u043e\u0441\u0442\u044c \u043d\u0443\u043b\u0435\u0439 \u0438 \u0435\u0434\u0438\u043d\u0438\u0447\u0435\u043a \u0434\u043b\u0438\u043d\u044b <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/e2e\/33f\/15a\/e2e33f15a96008ca33579599483c4531.svg\" alt=\"$m$\" data-tex=\"inline\"><\/math>: \u0435\u0441\u043b\u0438 \u043d\u0430 <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/bf8\/3b5\/32c\/bf83b532cd867d34004f8eded8c5c79a.svg\" alt=\"$i$\" data-tex=\"inline\"><\/math>-\u043e\u0439 \u043f\u043e\u0437\u0438\u0446\u0438\u0438 \u043f\u0440\u043e\u0444\u0438\u043b\u044f \u0435\u0434\u0438\u043d\u0438\u0447\u043a\u0430, \u044d\u0442\u043e \u0437\u043d\u0430\u0447\u0438\u0442 \u0447\u0442\u043e \u0432 \u044d\u0442\u043e\u0439 \u0444\u0438\u0433\u0443\u0440\u0435 \u0435\u0441\u0442\u044c \u0441\u043e\u043e\u0442\u0432\u0435\u0442\u0441\u0442\u0432\u0443\u044e\u0449\u0430\u044f \u043a\u043b\u0435\u0442\u043a\u0430, \u0432\u0441\u0435\u0433\u043e \u043f\u0440\u043e\u0444\u0438\u043b\u0435\u0439 <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/76c\/1ec\/f9d\/76c1ecf9db6b26ac97cce91695b56fa1.svg\" alt=\"$2^m$\" data-tex=\"inline\"><\/math> (\u043a\u0440\u0430\u0441\u043d\u044b\u0435 \u043a\u043b\u0435\u0442\u043a\u0438 \u2014 \u0435\u0434\u0438\u043d\u0438\u0447\u043a\u0438, \u0441\u0438\u043d\u0438\u0435 \u2014 \u043d\u0443\u043b\u0438).<\/p>\n<p>  <\/p>\n<div style=\"text-align:center;\"><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/webt\/xv\/pw\/4q\/xvpw4qc6whegtuje4gnhtzpea3k.png\"><\/div>\n<p>  <\/p>\n<p>\u041f\u0440\u043e\u0444\u0438\u043b\u044c \u043e\u0434\u043d\u043e\u0437\u043d\u0430\u0447\u043d\u043e \u0437\u0430\u0434\u0430\u0435\u0442\u0441\u044f \u0447\u0438\u0441\u043b\u043e\u043c <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/92b\/bd1\/52a\/92bbd152a5e2c19931e9eb351777db1f.svg\" alt=\"$[0, 2^m)$\" data-tex=\"inline\"><\/math> (\u0435\u0433\u043e \u0431\u0438\u043d\u0430\u0440\u043d\u043e\u0435 \u043f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u043b\u0435\u043d\u0438\u0435 \u0432\u043f\u043b\u043e\u0442\u044c \u0434\u043e <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/e2e\/33f\/15a\/e2e33f15a96008ca33579599483c4531.svg\" alt=\"$m$\" data-tex=\"inline\"><\/math> \u0440\u0430\u0437\u0440\u044f\u0434\u043e\u0432 \u044f\u0432\u043b\u044f\u0435\u0442\u0441\u044f \u043f\u043e\u0441\u043b\u0435\u0434\u043e\u0432\u0430\u0442\u0435\u043b\u044c\u043d\u043e\u0441\u0442\u0435\u0439 \u043d\u0443\u043b\u0435\u0439 \u0438 \u0435\u0434\u0438\u043d\u0438\u0447\u0435\u043a).<\/p>\n<p>  <\/p>\n<p>\u041f\u0440\u044f\u043c\u043e\u0443\u0433\u043e\u043b\u044c\u043d\u0438\u043a <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/038\/f9e\/5bf\/038f9e5bf254d47500d869632af1d6ea.svg\" alt=\"$n\\times m$\" data-tex=\"inline\"><\/math> \u0441\u043e\u043e\u0442\u0432\u0435\u0442\u0441\u0442\u0432\u0443\u0435\u0442 \u0444\u0438\u0433\u0443\u0440\u0435 \u0441 <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/fdb\/92a\/3e9\/fdb92a3e92244ee385f295be0b2695f5.svg\" alt=\"$k=n$\" data-tex=\"inline\"><\/math>, <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/08d\/ae0\/c6c\/08dae0c6cdec0ef67518e6d4cc0c383e.svg\" alt=\"$j=0$\" data-tex=\"inline\"><\/math> \u0438 \u043d\u0443\u043b\u0435\u0432\u044b\u043c \u043f\u0440\u043e\u0444\u0438\u043b\u0435\u043c. \u041d\u0430 \u0444\u0438\u0433\u0443\u0440\u043a\u0430\u0445 \u0442\u0430\u043a\u043e\u0433\u043e \u0442\u0438\u043f\u0430 \u043c\u044b \u043c\u043e\u0436\u0435\u043c \u0441\u0447\u0438\u0442\u0430\u0442\u044c \u0434\u0432\u0435 \u043e\u0441\u043d\u043e\u0432\u043d\u044b\u0435 \u0444\u0443\u043d\u043a\u0446\u0438\u0438<\/p>\n<p>  <\/p>\n<ul>\n<li>\u041c\u0430\u043a\u0441\u0438\u043c\u0430\u043b\u044c\u043d\u043e\u0435 \u0432\u043e\u0437\u043c\u043e\u0436\u043d\u043e\u0435 \u0447\u0438\u0441\u043b\u043e \u043f\u043e\u043a\u0440\u044b\u0442\u044b\u0445 \u0434\u043e\u043c\u0438\u043d\u043e\u0448\u043a\u0430\u043c\u0438 \u043a\u043b\u0435\u0442\u043e\u043a \u0432 \u044d\u0442\u043e\u0439 \u0444\u0438\u0433\u0443\u0440\u0435<\/li>\n<li>\u041a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e \u0441\u043f\u043e\u0441\u043e\u0431\u043e\u0432 \u043f\u043e\u043b\u043d\u043e\u0441\u0442\u044c\u044e \u043f\u043e\u043a\u0440\u044b\u0442\u044c \u0434\u043e\u043c\u0438\u043d\u043e\u0448\u043a\u0430\u043c\u0438 \u044d\u0442\u0443 \u0444\u0438\u0433\u0443\u0440\u0443<\/li>\n<\/ul>\n<p>  <\/p>\n<p>\u0414\u0430\u0432\u0430\u0439\u0442\u0435 \u043e\u0431\u043e\u0437\u043d\u0430\u0447\u0438\u043c \u0437\u0430 <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/24c\/11f\/f3d\/24c11ff3dfa130eb0eececb695f3a1b4.svg\" alt=\"$ g(k, j, m, p)$\" data-tex=\"inline\"><\/math> \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e \u0441\u043f\u043e\u0441\u043e\u0431\u043e\u0432 \u0437\u0430\u043c\u043e\u0441\u0442\u0438\u0442\u044c \u0442\u0430\u043a\u0443\u044e \u0444\u0438\u0433\u0443\u0440\u043a\u0443, \u0442\u043e\u0433\u0434\u0430 <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/831\/0b9\/d8d\/8310b9d8d08a56b457a869795dac277b.svg\" alt=\"$g(k, m, m, p)=g(k+1, 0, m, p)$\" data-tex=\"inline\"><\/math> \u0438 \u043f\u0440\u0438 \u044d\u0442\u043e\u043c <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/24c\/11f\/f3d\/24c11ff3dfa130eb0eececb695f3a1b4.svg\" alt=\"$g(k, j, m, p)$\" data-tex=\"inline\"><\/math> \u0432\u044b\u0440\u0430\u0436\u0430\u0435\u0442\u0441\u044f \u0447\u0435\u0440\u0435\u0437 \u0441\u0443\u043c\u043c\u0443 \u043d\u0435\u0441\u043a\u043e\u043b\u044c\u043a\u0438\u0445 <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/a3d\/0fb\/288\/a3d0fb288ea3498b3a7f3e75bceb56aa.svg\" alt=\"$g(k, j-1, m, \\cdot)$\" data-tex=\"inline\"><\/math>, \u043f\u043e \u0431\u043e\u043b\u044c\u0448\u043e\u043c\u0443 \u0441\u0447\u0435\u0442\u0443 \u043f\u0435\u0440\u0435\u0445\u043e\u0434 \u043e\u0442 <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/b82\/8e2\/475\/b828e2475a3a56280b895f35eb250ea2.svg\" alt=\"$j$\" data-tex=\"inline\"><\/math> \u043a <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/02a\/a7d\/e38\/02aa7de38a957f1fb81ccc94010cceb3.svg\" alt=\"$j+1$\" data-tex=\"inline\"><\/math> \u2014 \u044d\u0442\u043e \u043f\u0435\u0440\u0435\u0431\u043e\u0440 \u0442\u0440\u0435\u0445 \u0441\u043b\u0443\u0447\u0430\u0435\u0432: \u043f\u043e\u0441\u0442\u0430\u0432\u0438\u0442\u044c \u0432\u0435\u0440\u0442\u0438\u043a\u0430\u043b\u044c\u043d\u0443\u044e \u0434\u043e\u043c\u0438\u043d\u043e\u0448\u043a\u0443, \u0435\u0441\u043b\u0438 \u044d\u0442\u043e \u0432\u043e\u0437\u043c\u043e\u0436\u043d\u043e<br \/>  <img decoding=\"async\" width=\"45%\" src=\"https:\/\/habrastorage.org\/webt\/wj\/be\/0v\/wjbe0ve_kp4oih2ppuwchvhmsw4.png\"><img decoding=\"async\" width=\"45%\" src=\"https:\/\/habrastorage.org\/webt\/pr\/ha\/nw\/prhanwbxyddjzjza3ux8asg6vl4.png\"><br \/>  \u0433\u043e\u0440\u0438\u0437\u043e\u043d\u0442\u0430\u043b\u044c\u043d\u0443\u044e \u0434\u043e\u043c\u0438\u043d\u043e\u0448\u043a\u0443, \u0435\u0441\u043b\u0438 \u044d\u0442\u043e \u0432\u043e\u0437\u043c\u043e\u0436\u043d\u043e<br \/>  <img decoding=\"async\" width=\"45%\" src=\"https:\/\/habrastorage.org\/webt\/6d\/gd\/u1\/6dgdu1-prszdkkgr4rdbon8ypz0.png\"><img decoding=\"async\" width=\"45%\" src=\"https:\/\/habrastorage.org\/webt\/i1\/q6\/s4\/i1q6s4hm4myqbh0oxpswapa9-ba.png\"><br \/>  \u0438 \u043f\u0440\u043e\u043f\u0443\u0441\u0442\u0438\u0442\u044c \u0437\u0430\u043d\u044f\u0442\u0443\u044e \u043a\u043b\u0435\u0442\u043a\u0443. \u0412 \u0441\u043b\u0443\u0447\u0430\u0435, \u0435\u0441\u043b\u0438 \u043c\u044b \u043f\u044b\u0442\u0430\u0435\u043c\u0441\u044f \u043f\u043e\u043d\u044f\u0442\u044c, \u043a\u0430\u043a\u043e\u0435 \u043c\u0430\u043a\u0441\u0438\u043c\u0430\u043b\u044c\u043d\u043e\u0435 \u0447\u0438\u0441\u043b\u043e \u043a\u043b\u0435\u0442\u043e\u043a \u0444\u0438\u0433\u0443\u0440\u043a\u0438 \u0432\u043e\u0437\u043c\u043e\u0436\u043d\u043e \u0437\u0430\u043c\u043e\u0441\u0442\u0438\u0442\u044c, \u0442\u043e \u0441\u0443\u043c\u043c\u0430 \u0437\u0430\u043c\u0435\u043d\u044f\u0435\u0442\u0441\u044f \u043d\u0430 \u043c\u0430\u043a\u0441\u0438\u043c\u0443\u043c \u0438 \u0434\u043e\u0431\u0430\u0432\u043b\u044f\u0435\u0442\u0441\u044f \u043e\u0434\u0438\u043d \u043d\u0435\u0441\u043b\u043e\u0436\u043d\u044b\u0439 \u043f\u0435\u0440\u0435\u0445\u043e\u0434 \u2014 \u043f\u0440\u043e\u043f\u0443\u0441\u043a \u0441\u0432\u043e\u0431\u043e\u0434\u043d\u043e\u0439 \u043a\u043b\u0435\u0442\u043a\u0438. \u0412\u0430\u0436\u043d\u044b\u043c \u043c\u043e\u043c\u0435\u043d\u0442\u043e\u043c \u0442\u0430\u043a\u0436\u0435 \u044f\u0432\u043b\u044f\u0435\u0442\u0441\u044f \u0442\u043e, \u0447\u0442\u043e \u043c\u044b \u043c\u043e\u0436\u0435\u043c \u0437\u0430\u0440\u0430\u043d\u0435\u0435 \u0432\u044b\u0440\u0435\u0437\u0430\u0442\u044c \u043d\u0435\u0441\u043a\u043e\u043b\u044c\u043a\u043e \u043a\u043b\u0435\u0442\u043e\u043a, \u043f\u0440\u0438\u043d\u0446\u0438\u043f\u0438\u0430\u043b\u044c\u043d\u043e \u043e\u0442 \u044d\u0442\u043e\u0433\u043e \u043d\u0438\u0447\u0435\u0433\u043e \u043d\u0435 \u043f\u043e\u043c\u0435\u043d\u044f\u0435\u0442\u0441\u044f.<\/p>\n<p>  <\/p>\n<p>\u0414\u0430\u0432\u0430\u0439\u0442\u0435 \u0442\u0435\u043f\u0435\u0440\u044c \u043f\u043e\u043f\u0440\u043e\u0431\u0443\u0435\u043c \u0440\u0435\u0430\u043b\u0438\u0437\u043e\u0432\u0430\u0442\u044c \u044d\u0442\u043e (\u043a\u043e\u0434\u0430 \u0431\u0443\u0434\u0435\u0442 \u043c\u043d\u043e\u0433\u043e, \u0442\u0430\u043a \u0447\u0442\u043e \u0431\u043e\u043b\u044c\u0448\u0438\u043d\u0441\u0442\u0432\u043e \u044f \u0432\u044b\u043d\u0435\u0441\u0443 \u0432 \u0441\u043f\u043e\u0439\u043b\u0435\u0440). \u0417\u0430\u0434\u0430\u0434\u0438\u043c \u0438\u043d\u0442\u0435\u0440\u0435\u0441\u0443\u044e\u0449\u0438\u0439 \u043d\u0430\u0441 \u043f\u0440\u044f\u043c\u043e\u0443\u0433\u043e\u043b\u044c\u043d\u0438\u043a \u043a\u0430\u043a \u043c\u043d\u043e\u0436\u0435\u0441\u0442\u0432\u043e \u0441\u0442\u0440\u043e\u043a \u0438\u0437 \u0442\u043e\u0447\u0435\u043a \u0438 \u0440\u0435\u0448\u0435\u0442\u043e\u043a (\u0442\u043e\u0447\u043a\u0430 \u2014 \u0441\u0432\u043e\u0431\u043e\u0434\u043d\u0430\u044f \u043a\u043b\u0435\u0442\u043a\u0430, \u0440\u0435\u0448\u0435\u0442\u043a\u0430 \u2014 \u0437\u0430\u043d\u044f\u0442\u0430\u044f), \u043f\u043e\u043a\u0430 \u0432\u0441\u0435 \u043a\u043b\u0435\u0442\u043a\u0438 \u0431\u0443\u0434\u0443\u0442 \u0441\u0432\u043e\u0431\u043e\u0434\u043d\u044b\u043c\u0438, \u043f\u043e\u0442\u043e\u043c \u043f\u043e\u0442\u0438\u0445\u043e\u043d\u044c\u043a\u0443 \u0431\u0443\u0434\u0435\u043c \u043a\u0430\u043a\u0438\u0435-\u043d\u0438\u0431\u0443\u0434\u044c \u0432\u044b\u0440\u0435\u0437\u0430\u0442\u044c<\/p>\n<p>  <\/p>\n<pre><code class=\"python\">tiling = [     '........',     '........',     '........',     '........',     '........',     '........',     '........',     '........', ]<\/code><\/pre>\n<p>  <\/p>\n<p>\u041d\u0430\u0447\u043d\u0435\u043c \u0441 <\/p>\n<p>  <\/p>\n<div class=\"spoiler\" role=\"button\" tabindex=\"0\">                         <b class=\"spoiler_title\">\u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u0430 \u0441\u043f\u043e\u0441\u043e\u0431\u043e\u0432 \u0437\u0430\u043c\u043e\u0449\u0435\u043d\u0438\u0439 \u0434\u043e\u043c\u0438\u043d\u043e\u0448\u043a\u0430\u043c\u0438<\/b>                         <\/p>\n<div class=\"spoiler_text\">\n<pre><code class=\"python\">def count_tilings(tiling):     n = len(tiling)     m = len(tiling[0])     if ((n + 1) * m * 2 ** m) &lt;= 10000000:         dp = [[[(0 if k != 0 or j != 0 or mask != 0 else 1) for mask in range(2 ** m)] for j in range(m)] for k in range(n + 1)]     for k in range(n):         for j in range(m):             for mask in range(2 ** m):                 # \u0412\u0435\u0440\u0442\u0438\u043a\u0430\u043b\u044c\u043d\u0430\u044f \u0434\u043e\u043c\u0438\u043d\u043e\u0448\u043a\u0430                 if k &lt; n - 1 and tiling[k][j] == '.' and tiling[k + 1][j] == '.' and (mask &amp;  (1 &lt;&lt; j)) == 0:                     dp[k + ((j + 1) \/\/ m)][(j + 1) % m][mask + (1 &lt;&lt; j)] += dp[k][j][mask]                 # \u0413\u043e\u0440\u0438\u0437\u043e\u043d\u0442\u0430\u043b\u044c\u043d\u0430\u044f \u0434\u043e\u043c\u0438\u043d\u043e\u0448\u043a\u0430                 if j &lt; m - 1 and tiling[k][j] == '.' and tiling[k][j + 1] == '.' and (mask &amp; (3 &lt;&lt; j)) == 0:                     dp[k + ((j + 1) \/\/ m)][(j + 1) % m][mask + (2 &lt;&lt; j)] += dp[k][j][mask]                 # \u041a\u043b\u0435\u0442\u043a\u0430 \u0437\u0430\u043d\u044f\u0442\u0430                 if ((1 &lt;&lt; j) &amp;  mask) != 0 or tiling[k][j] != '.':                     dp[k + ((j + 1) \/\/ m)][(j + 1) % m][(mask | (1 &lt;&lt; j)) - (1 &lt;&lt; j)] += dp[k][j][mask]     return dp<\/code><\/pre>\n<\/div><\/div>\n<p>  <\/p>\n<pre><code class=\"python\">dp = count_tilings(tiling) print(dp[8][0][0])<\/code><\/pre>\n<p>  <\/p>\n<p>\u043f\u043e\u043b\u0443\u0447\u0430\u0435\u043c<\/p>\n<p>  <\/p>\n<pre><code class=\"python\">12988816<\/code><\/pre>\n<p>  <\/p>\n<p>\u0421\u0432\u0435\u0440\u044f\u0435\u043c\u0441\u044f \u0441 <a href=\"https:\/\/en.wikipedia.org\/wiki\/Domino_tiling#Counting_tilings_of_regions\" rel=\"nofollow\">\u0432\u0438\u043a\u0438\u043f\u0435\u0434\u0438\u0435\u0439<\/a>, \u043f\u043e\u043a\u0430 \u0432\u0441\u0435 \u0432 \u043f\u043e\u0440\u044f\u0434\u043a\u0435. \u0414\u0430\u0432\u0430\u0439\u0442\u0435 \u0435\u0449\u0435 \u043d\u0430 \u0432\u0441\u044f\u043a\u0438\u0439 \u0441\u043b\u0443\u0447\u0430\u0439 \u043f\u0440\u043e\u0432\u0435\u0440\u0438\u043c, \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e \u0441\u043f\u043e\u0441\u043e\u0431\u043e\u0432 \u0437\u0430\u043c\u043e\u0441\u0442\u0438\u0442\u044c \u043f\u043e\u043b\u043e\u0441\u043a\u0443 <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/e61\/659\/b0c\/e61659b0c31baab04a8f92f6fd76fd98.svg\" alt=\"$n\\times 2$\" data-tex=\"inline\"><\/math> \u2014 \u0434\u043e\u043b\u0436\u043d\u043e \u043f\u043e\u043b\u0443\u0447\u0438\u0442\u044c\u0441\u044f \u0447\u0438\u0441\u043b\u043e \u0424\u0438\u0431\u043e\u043d\u0430\u0447\u0447\u0438.<\/p>\n<p>  <\/p>\n<pre><code class=\"python\">tiling_fib = [     '..',     '..',     '..',     '..',     '..',     '..',     '..',     '..' ] dp = count_tilings(tiling_fib) for i in range(8):     print(dp[i][0][0], end=' ')<\/code><\/pre>\n<p>  <\/p>\n<pre><code class=\"python\">1 1 2 3 5 8 13 21<\/code><\/pre>\n<p>  <\/p>\n<p>\u0427\u0442\u043e \u0436, \u043f\u043e\u0435\u0445\u0430\u043b\u0438 \u0434\u0430\u043b\u044c\u0448\u0435, \u043f\u0440\u043e\u0432\u0435\u0440\u0438\u043c \u043d\u0430 \u0434\u043e\u0441\u043a\u0435 \u0441 \u0432\u044b\u0440\u0435\u0437\u0430\u043d\u043d\u044b\u043c\u0438 \u0443\u0433\u043b\u0430\u043c\u0438<\/p>\n<p>  <\/p>\n<pre><code class=\"python\">tiling_no_corners_opposite = [     '.......#',     '........',     '........',     '........',     '........',     '........',     '........',     '#.......', ] dp = count_tilings(tiling_no_corners_opposite) print(dp[8][0][0])<\/code><\/pre>\n<p>  <\/p>\n<pre><code class=\"python\">0<\/code><\/pre>\n<p>  <\/p>\n<p>\u0421\u0443\u043f\u0435\u0440. \u0414\u043e\u043f\u0443\u0441\u0442\u0438\u043c \u0432\u044b\u0447\u0438\u0441\u043b\u044f\u0442\u044c \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e \u043c\u044b \u043d\u0430\u0443\u0447\u0438\u043b\u0438\u0441\u044c, \u043c\u043e\u0436\u0435\u0442 \u043d\u0430\u0439\u0434\u0435\u043c \u0445\u043e\u0442\u044f \u0431\u044b \u043e\u0434\u043d\u043e \u043a\u043e\u043d\u043a\u0440\u0435\u0442\u043d\u043e\u0435 \u0437\u0430\u043c\u043e\u0449\u0435\u043d\u0438\u0435 \u0434\u043b\u044f \u043d\u0430\u0433\u043b\u044f\u0434\u043d\u043e\u0441\u0442\u0438?<\/p>\n<p>  <\/p>\n<div class=\"spoiler\" role=\"button\" tabindex=\"0\">                         <b class=\"spoiler_title\">\u043a\u043e\u0434 \u0434\u043b\u044f \u043f\u043e\u043b\u0443\u0447\u0435\u043d\u0438\u044f \u043f\u043e\u043a\u0440\u044b\u0442\u0438\u044f<\/b>                         <\/p>\n<div class=\"spoiler_text\">\n<pre><code class=\"python\">def cover_if_possible(tiling, dp=None):     if dp is None:         dp = count_tilings(tiling)     n = len(dp) - 1     m = len(dp[0])     if dp[n][0][0] == 0:         return None      result = [[-1 if tiling[i][j] == '#' else 0 for j in range(m)] for i in range(n)]     num = 0      k = n     j = 0     mask = 0      while k &gt; 0 or j &gt; 0:         #print(k, j, mask)         prev_j = j - 1         prev_k = k         if prev_j == -1:             prev_j += m             prev_k -= 1          # \u041d\u0430\u0447\u0438\u043d\u0430\u0435\u043c \u043f\u0435\u0440\u0435\u0431\u0438\u0440\u0430\u0442\u044c \u0432\u0430\u0440\u0438\u0430\u043d\u0442\u044b, \u043a\u0430\u043a\u0438\u043c \u043e\u0431\u0440\u0430\u0437\u043e\u043c \u043c\u044b \u043c\u043e\u0433\u043b\u0438 \u043f\u043e\u043f\u0430\u0441\u0442\u044c \u0432 i, j, mask         # \u042d\u0442\u043e\u0442 \u0432\u0430\u0440\u0438\u0430\u043d\u0442 \u043e\u0447\u0435\u043d\u044c \u043d\u0435 \u043e\u043f\u0442\u0438\u043c\u0430\u043b\u0435\u043d, \u043d\u043e \u0437\u0430\u043d\u0438\u043c\u0430\u0435\u0442 \u043c\u0435\u043d\u044c\u0448\u0435 \u043a\u043e\u0434\u0430 \u0438 \u0432\u0441\u0435 \u0440\u0430\u0432\u043d\u043e \u0431\u044b\u0441\u0442\u0440\u0435\u0435          # \u0441\u0430\u043c\u043e\u0433\u043e \u043f\u043e\u0434\u0441\u0447\u0435\u0442\u0430 \u0434\u0438\u043d\u0430\u043c\u0438\u043a\u0438         for prev_mask in range(2 ** m):             if prev_k &lt; n - 1 and tiling[prev_k][prev_j] == '.' and tiling[prev_k + 1][prev_j] == '.' and \\                 (prev_mask &amp; (1 &lt;&lt; prev_j)) == 0 and (prev_mask + (1 &lt;&lt; prev_j)) == mask and dp[prev_k][prev_j][prev_mask] != 0:                 mask = prev_mask                 result[prev_k][prev_j] = num                 result[prev_k + 1][prev_j] = num                 #print(f'Vertical at ({prev_k}, {prev_j}) ({prev_k + 1}, {prev_j})')                 num += 1                 break             elif prev_j &lt; m - 1 and tiling[prev_k][prev_j] == '.' and tiling[prev_k][prev_j + 1] == '.' and (prev_mask &amp; (3 &lt;&lt; prev_j)) == 0 and \\                 prev_mask + (2 &lt;&lt; prev_j) == mask and dp[prev_k][prev_j][prev_mask] != 0:                 mask = prev_mask                 result[prev_k][prev_j] = num                 result[prev_k][prev_j + 1] = num                 #print(f'Horisontal at ({prev_k}, {prev_j}) ({prev_k}, {prev_j + 1})')                 num += 1                 break             elif (((1 &lt;&lt; prev_j) &amp; prev_mask) != 0 or tiling[prev_k][prev_j] != '.') and \\                 (prev_mask | (1 &lt;&lt; prev_j)) - (1 &lt;&lt; prev_j) == mask and dp[prev_k][prev_j][prev_mask] != 0:                 mask = prev_mask                 break          j = prev_j         k = prev_k      return result<\/code><\/pre>\n<\/div><\/div>\n<p>  <\/p>\n<pre><code class=\"python\">filling = cover_if_possible(tiling) draw_filling(filling)<\/code><\/pre>\n<p>  <\/p>\n<div style=\"text-align:center;\"><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/webt\/vc\/q-\/cn\/vcq-cn6lizoeim6pi76i_1w8a_0.png\"><\/div>\n<p>  <\/p>\n<p>\u0421\u043b\u0438\u0448\u043a\u043e\u043c \u043f\u0440\u043e\u0441\u0442\u043e, \u0434\u0430\u0432\u0430\u0439\u0442\u0435 \u0432\u044b\u0440\u0435\u0436\u0435\u043c \u043d\u0435\u0441\u043a\u043e\u043b\u044c\u043a\u043e \u043a\u043b\u0435\u0442\u043e\u043a<\/p>\n<p>  <\/p>\n<pre><code class=\"python\">tiling_random = [     '........',     '#.#.....',     '..#.....',     '........',     '........',     '........',     '........',     '...#....' ] filling_random = cover_if_possible(tiling_random) draw_filling(filling_random)<\/code><\/pre>\n<p>  <\/p>\n<div style=\"text-align:center;\"><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/webt\/tc\/9q\/8h\/tc9q8hbox4nvvpn2l7pdql3yxgc.png\"><\/div>\n<p>  <\/p>\n<p>\u041f\u043e\u043f\u0440\u043e\u0431\u0443\u0435\u043c \u0442\u0435\u043f\u0435\u0440\u044c \u0441\u0434\u0435\u043b\u0430\u0442\u044c \u0442\u043e\u0436\u0435 \u0441\u0430\u043c\u043e\u0435 \u0434\u043b\u044f \u0437\u0430\u043c\u043e\u0449\u0435\u043d\u0438\u044f \u043c\u0430\u043a\u0441\u0438\u043c\u0430\u043b\u044c\u043d\u043e\u0439 \u0432\u043e\u0437\u043c\u043e\u0436\u043d\u043e\u0439 \u0447\u0430\u0441\u0442\u0438 \u0444\u0438\u0433\u0443\u0440\u044b<\/p>\n<p>  <\/p>\n<div class=\"spoiler\" role=\"button\" tabindex=\"0\">                         <b class=\"spoiler_title\">\u041a\u043e\u0434 \u0434\u043b\u044f \u043c\u0430\u043a\u0441\u0438\u043c\u0430\u043b\u044c\u043d\u043e\u0433\u043e \u0437\u0430\u043c\u043e\u0449\u0435\u043d\u0438\u044f<\/b>                         <\/p>\n<div class=\"spoiler_text\">\n<pre><code class=\"python\">def maxmimum_cover(tiling):     n = len(tiling)     m = len(tiling[0])     if ((n + 1) * m * 2 ** m) &lt;= 10000000:         dp = [[[(n * m if k != 0 or j != 0 or mask != 0 else 0) for mask in range(2 ** m)] for j in range(m)] for k in range(n + 1)]     for k in range(n):         for j in range(m):             for mask in range(2 ** m):                 next_k, next_j = k + ((j + 1) \/\/ m), (j + 1) % m                 # \u0412\u0435\u0440\u0442\u0438\u043a\u0430\u043b\u044c\u043d\u0430\u044f \u0434\u043e\u043c\u0438\u043d\u043e\u0448\u043a\u0430                 if k &lt; n - 1 and tiling[k][j] == '.' and tiling[k + 1][j] == '.' and (mask &amp;  (1 &lt;&lt; j)) == 0:                     dp[next_k][next_j][mask + (1 &lt;&lt; j)] = min(dp[next_k][next_j][mask + (1 &lt;&lt; j)], dp[k][j][mask])                 # \u0413\u043e\u0440\u0438\u0437\u043e\u043d\u0442\u0430\u043b\u044c\u043d\u0430\u044f \u0434\u043e\u043c\u0438\u043d\u043e\u0448\u043a\u0430                 if j &lt; m - 1 and tiling[k][j] == '.' and tiling[k][j + 1] == '.' and (mask &amp; (3 &lt;&lt; j)) == 0:                     dp[next_k][next_j][mask + (2 &lt;&lt; j)] = min(dp[next_k][next_j][mask + (2 &lt;&lt; j)], dp[k][j][mask])                 # \u041a\u043b\u0435\u0442\u043a\u0430 \u0437\u0430\u043d\u044f\u0442\u0430                 if ((1 &lt;&lt; j) &amp;  mask) != 0 or tiling[k][j] != '.':                     dp[next_k][next_j][(mask | (1 &lt;&lt; j)) - (1 &lt;&lt; j)] = \\                         min(dp[next_k][next_j][(mask | (1 &lt;&lt; j)) - (1 &lt;&lt; j)], dp[k][j][mask])                 # \u041a\u043b\u0435\u0442\u043a\u0430 \u043d\u0435 \u0437\u0430\u043d\u044f\u0442\u0430, \u0440\u0430\u0441\u0441\u043c\u043e\u0442\u0440\u0438\u0432\u0430\u0435\u043c \u0441\u043b\u0443\u0447\u0430\u0439 \u0435\u0451 \u043f\u0440\u043e\u043f\u0443\u0441\u043a\u0430                 else:                     dp[next_k][next_j][(mask | (1 &lt;&lt; j)) - (1 &lt;&lt; j)] = \\                         min(dp[next_k][next_j][(mask | (1 &lt;&lt; j)) - (1 &lt;&lt; j)], dp[k][j][mask] + 1)     return dp  def cover_maximum_possible(tiling, dp=None):     if dp is None:         dp = maxmimum_cover(tiling)     n = len(dp) - 1     m = len(dp[0])      result = [[-1 if tiling[i][j] == '#' else -2 for j in range(m)] for i in range(n)]     num = 0      k = n     j = 0     mask = 0      while k &gt; 0 or j &gt; 0:         #print(k, j, mask)         prev_j = j - 1         prev_k = k         if prev_j == -1:             prev_j += m             prev_k -= 1          # \u041d\u0430\u0447\u0438\u043d\u0430\u0435\u043c \u043f\u0435\u0440\u0435\u0431\u0438\u0440\u0430\u0442\u044c \u0432\u0430\u0440\u0438\u0430\u043d\u0442\u044b, \u043a\u0430\u043a\u0438\u043c \u043e\u0431\u0440\u0430\u0437\u043e\u043c \u043c\u044b \u043c\u043e\u0433\u043b\u0438 \u043f\u043e\u043f\u0430\u0441\u0442\u044c \u0432 i, j, mask         # \u042d\u0442\u043e\u0442 \u0432\u0430\u0440\u0438\u0430\u043d\u0442 \u043e\u0447\u0435\u043d\u044c \u043d\u0435 \u043e\u043f\u0442\u0438\u043c\u0430\u043b\u0435\u043d, \u043d\u043e \u0437\u0430\u043d\u0438\u043c\u0430\u0435\u0442 \u043c\u0435\u043d\u044c\u0448\u0435 \u043a\u043e\u0434\u0430 \u0438 \u0432\u0441\u0435 \u0440\u0430\u0432\u043d\u043e \u0431\u044b\u0441\u0442\u0440\u0435\u0435          # \u0441\u0430\u043c\u043e\u0433\u043e \u043f\u043e\u0434\u0441\u0447\u0435\u0442\u0430 \u0434\u0438\u043d\u0430\u043c\u0438\u043a\u0438         for prev_mask in range(2 ** m):             # \u0420\u0430\u043d\u044c\u0448\u0435 \u043c\u044b \u0437\u0434\u0435\u0441\u044c \u043f\u0440\u043e\u0432\u0435\u0440\u044f\u043b\u0438, \u0447\u0442\u043e \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e \u0432\u0430\u0440\u0438\u0430\u043d\u0442\u043e\u0432 \u0432 \u044d\u0442\u043e\u0439 \u0432\u0435\u0442\u043a\u0435 \u043d\u0435 0, \u0441\u0435\u0439\u0447\u0430\u0441 \u043d\u0443\u0436\u043d\u043e             # \u043f\u0440\u043e\u0432\u0435\u0440\u0438\u0442\u044c, \u0447\u0442\u043e \u044d\u0442\u0430 \u0432\u0435\u0442\u043a\u0430 \u0432\u0435\u0434\u0435\u0442 \u043a \u043c\u0430\u043a\u0441\u0438\u043c\u0430\u043b\u044c\u043d\u043e\u043c\u0443 \u043f\u043e\u043a\u0440\u044b\u0442\u0438\u044e             if prev_k &lt; n - 1 and tiling[prev_k][prev_j] == '.' and tiling[prev_k + 1][prev_j] == '.' and \\                     (prev_mask &amp; (1 &lt;&lt; prev_j)) == 0 and (prev_mask + (1 &lt;&lt; prev_j)) == mask and \\                     dp[prev_k][prev_j][prev_mask] == dp[k][j][mask]:                 mask = prev_mask                 result[prev_k][prev_j] = num                 result[prev_k + 1][prev_j] = num                 num += 1                 break             elif prev_j &lt; m - 1 and tiling[prev_k][prev_j] == '.' and tiling[prev_k][prev_j + 1] == '.' and (prev_mask &amp; (3 &lt;&lt; prev_j)) == 0 and \\                     prev_mask + (2 &lt;&lt; prev_j) == mask and dp[prev_k][prev_j][prev_mask] == dp[k][j][mask]:                 mask = prev_mask                 result[prev_k][prev_j] = num                 result[prev_k][prev_j + 1] = num                 num += 1                 break             elif (((1 &lt;&lt; prev_j) &amp; prev_mask) != 0 or tiling[prev_k][prev_j] != '.') and \\                     (prev_mask | (1 &lt;&lt; prev_j)) - (1 &lt;&lt; prev_j) == mask and dp[prev_k][prev_j][prev_mask] == dp[k][j][mask]:                 mask = prev_mask                 break             elif ((1 &lt;&lt; prev_j) &amp; prev_mask) == 0 and tiling[prev_k][prev_j] == '.' and \\                     (prev_mask | (1 &lt;&lt; prev_j)) - (1 &lt;&lt; prev_j) == mask and dp[prev_k][prev_j][prev_mask] + 1 == dp[k][j][mask]:                 mask = prev_mask                 break          j = prev_j         k = prev_k      return result<\/code><\/pre>\n<\/div><\/div>\n<p>  <\/p>\n<p>\u0418 \u043f\u043e\u043f\u0440\u043e\u0431\u0443\u0435\u043c \u0444\u0438\u0433\u0443\u0440\u043a\u0443 \u0438\u0437 \u0437\u0430\u0433\u043e\u043b\u043e\u0432\u043a\u0430<\/p>\n<p>  <\/p>\n<pre><code class=\"python\">tiling_custom=[     '...####',     '....###',     '......#',     '#.#....',     '#......',     '##.....',     '###...#', ] filling = cover_maximum_possible(tiling_custom) draw_filling(filling)<\/code><\/pre>\n<p>  <\/p>\n<div style=\"text-align:center;\"><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/webt\/hz\/u4\/vl\/hzu4vl6f1afde1ro_d89chasfsm.png\"><\/div>\n<p>  <\/p>\n<p>\u041e\u043f\u0430! \u041d\u0435 \u043f\u043e\u043b\u0443\u0447\u0438\u043b\u043e\u0441\u044c, \u0432 \u043e\u0431\u0449\u0435\u043c \u0442\u0430\u043a \u0438 \u0434\u043e\u043b\u0436\u043d\u043e \u0431\u044b\u043b\u043e \u0431\u044b\u0442\u044c. \u041f\u0440\u0435\u0436\u0434\u0435, \u0447\u0435\u043c \u043f\u043e\u0439\u0442\u0438 \u0434\u0430\u043b\u044c\u0448\u0435 \u043f\u0430\u0440\u0443 \u0441\u043b\u043e\u0432 \u043e \u0441\u043b\u043e\u0436\u043d\u043e\u0441\u0442\u0438 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u043e\u0432. \u0412\u0441\u0435\u0433\u043e \u0444\u0438\u0433\u0443\u0440\u043e\u043a <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/a89\/ec7\/49f\/a89ec749fcaed96e6844ec4e53eaca87.svg\" alt=\"$n\\times m\\times 2^m$\" data-tex=\"inline\"><\/math>, \u0432\u0441\u0435 \u043f\u0435\u0440\u0435\u0445\u043e\u0434\u044b \u043a\u043e\u043d\u0441\u0442\u0430\u043d\u0442\u043d\u044b\u0435, \u043e\u0442\u0441\u044e\u0434\u0430 \u0430\u0441\u0438\u043c\u043f\u0442\u043e\u0442\u0438\u043a\u0430 <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/7df\/378\/7cf\/7df3787cfa6fa70e9d7ac5ae65d502d1.svg\" alt=\"$\\mathcal{O}(nm2^m)$\" data-tex=\"inline\"><\/math>, \u043a\u043e\u0442\u043e\u0440\u0430\u044f \u043c\u043e\u0436\u0435\u0442 \u0431\u044b\u0442\u044c \u0443\u043b\u0443\u0447\u0448\u0435\u043d\u0430 \u0434\u043e <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/fd5\/954\/3da\/fd59543dabdef6f592dfb5dddaf244d3.svg\" alt=\"$\\mathcal{O}(nm2^{\\min(n, m)})$\" data-tex=\"inline\"><\/math> \u0435\u0441\u043b\u0438 \u0434\u043e\u0431\u0430\u0432\u0438\u0442\u044c \u0442\u0440\u0430\u043d\u0441\u043f\u043e\u043d\u0438\u0440\u043e\u0432\u0430\u043d\u0438\u0435 \u0432 \u0441\u043b\u0443\u0447\u0430\u0435, \u0435\u0441\u043b\u0438 <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/2fe\/394\/616\/2fe3946166225b928d5fa9a3789058ac.svg\" alt=\"$n&lt;m$\" data-tex=\"inline\"><\/math>. \u041f\u043e\u0441\u0442\u0440\u043e\u0435\u043d\u0438\u0435 \u043a\u043e\u043d\u043a\u0440\u0435\u0442\u043d\u043e\u0433\u043e \u0437\u0430\u043c\u043e\u0449\u0435\u043d\u0438\u044f \u0432 \u043f\u0440\u0438\u0432\u0435\u0434\u0435\u043d\u043d\u044b\u0445 \u0440\u0435\u0430\u043b\u0438\u0437\u0430\u0446\u0438\u044f\u0445 \u0438\u043c\u0435\u0435\u0442 \u0441\u043b\u043e\u0436\u043d\u043e\u0441\u0442\u044c <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/7df\/378\/7cf\/7df3787cfa6fa70e9d7ac5ae65d502d1.svg\" alt=\"$\\mathcal{O}(nm2^m)$\" data-tex=\"inline\"><\/math>, \u043d\u043e \u043c\u043e\u0436\u043d\u043e \u0441\u0434\u0435\u043b\u0430\u0442\u044c \u0442\u0430\u043a, \u0447\u0442\u043e\u0431\u044b \u0431\u044b\u043b\u043e \u043f\u0440\u043e\u0441\u0442\u043e <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/d78\/52e\/e96\/d7852ee968d972a0c105f067fafc9837.svg\" alt=\"$\\mathcal{O}(nm)$\" data-tex=\"inline\"><\/math>, \u043d\u043e \u044d\u0442\u043e \u0431\u0430\u043d\u0430\u043b\u044c\u043d\u043e \u0431\u043e\u043b\u044c\u0448\u0435 \u043a\u043e\u0434\u0430.<\/p>\n<p>  <\/p>\n<h2 id=\"zamoschenie-s-pomoschyu-resheniya-zadachi-o-maksimalnom-parosochetanii\">\u0417\u0430\u043c\u043e\u0449\u0435\u043d\u0438\u0435 \u0441 \u043f\u043e\u043c\u043e\u0449\u044c\u044e \u0440\u0435\u0448\u0435\u043d\u0438\u044f \u0437\u0430\u0434\u0430\u0447\u0438 \u043e \u043c\u0430\u043a\u0441\u0438\u043c\u0430\u043b\u044c\u043d\u043e\u043c \u043f\u0430\u0440\u043e\u0441\u043e\u0447\u0435\u0442\u0430\u043d\u0438\u0438<\/h2>\n<p>  <\/p>\n<p>\u0412\u043e\u0437\u0432\u0440\u0430\u0449\u0430\u044f\u0441\u044c \u043a \u0447\u0435\u0440\u043d\u043e-\u0431\u0435\u043b\u043e\u0439 \u0440\u0430\u0441\u043a\u0440\u0430\u0441\u043a\u0435 \u043a\u0430\u043a \u043d\u0430 \u0448\u0430\u0445\u043c\u0430\u0442\u043d\u043e\u0439 \u0434\u043e\u0441\u043a\u0435 \u043c\u043e\u0436\u043d\u043e \u0437\u0430\u043c\u0435\u0442\u0438\u0442\u044c \u0438\u043d\u0442\u0435\u0440\u0435\u0441\u043d\u0443\u044e \u0438\u043d\u0442\u0435\u0440\u043f\u0440\u0435\u0442\u0430\u0446\u0438\u044e \u0437\u0430\u0434\u0430\u0447\u0438 \u0437\u0430\u043c\u043e\u0449\u0435\u043d\u0438\u044f \u0434\u043e\u043c\u0438\u043d\u043e\u0448\u043a\u0430\u043c\u0438. \u0414\u0430\u0432\u0430\u0439\u0442\u0435 \u043f\u043e\u0441\u043c\u043e\u0442\u0440\u0438\u043c \u043d\u0430 \u0433\u0440\u0430\u0444, \u0432 \u043a\u043e\u0442\u043e\u0440\u043e\u043c \u043a\u043b\u0435\u0442\u043a\u0438 \u0444\u0438\u0433\u0443\u0440\u044b \u2014 \u044d\u0442\u043e \u0432\u0435\u0440\u0448\u0438\u043d\u044b, \u0440\u0435\u0431\u0440\u0430\u043c\u0438 \u0441\u043e\u0435\u0434\u0438\u043d\u0435\u043d\u044b \u043a\u043b\u0435\u0442\u043a\u0438, \u0438\u043c\u0435\u044e\u0449\u0438\u0435 \u043e\u0431\u0449\u0443\u044e \u0441\u0442\u043e\u0440\u043e\u043d\u0443. \u0422\u0430\u043a \u0432\u043e\u0442, \u0434\u043e\u043c\u0438\u043d\u043e\u0448\u043a\u0430 \u0432 \u044d\u0442\u043e\u043c \u0433\u0440\u0430\u0444\u0435 \u2014 \u044d\u0442\u043e \u043a\u0430\u043a \u0440\u0430\u0437 \u0440\u0435\u0431\u0440\u043e. \u0415\u0441\u043b\u0438 \u0440\u0430\u0441\u043a\u0440\u0430\u0441\u0438\u0442\u044c \u0433\u0440\u0430\u0444 \u0432 \u0448\u0430\u0445\u043c\u0430\u0442\u043d\u043e\u043c \u043f\u043e\u0440\u044f\u0434\u043a\u0435, \u0442\u043e \u0432\u043d\u0435\u0437\u0430\u043f\u043d\u043e \u043c\u043e\u0436\u043d\u043e \u043e\u0431\u043d\u0430\u0440\u0443\u0436\u0438\u0442\u044c, \u0447\u0442\u043e \u044d\u0442\u043e\u0442 \u0433\u0440\u0430\u0444 \u2014 \u0434\u0432\u0443\u0434\u043e\u043b\u044c\u043d\u044b\u0439, \u0447\u0435\u0440\u043d\u044b\u0435 \u2014 \u043e\u0434\u043d\u0430 \u0434\u043e\u043b\u044f, \u0431\u0435\u043b\u044b\u0435 \u2014 \u0434\u0440\u0443\u0433\u0430\u044f. \u0415\u0441\u043b\u0438 \u043f\u0435\u0440\u0435\u0444\u043e\u0440\u043c\u0443\u043b\u0438\u0440\u043e\u0432\u0430\u0442\u044c \u0437\u0430\u0434\u0430\u0447\u0443 \u0437\u0430\u043c\u043e\u0449\u0435\u043d\u0438\u044f \u043d\u0430\u0438\u0431\u043e\u043b\u044c\u0448\u0435\u0433\u043e \u0447\u0438\u0441\u043b\u0430 \u043a\u043b\u0435\u0442\u043e\u043a \u0432 \u0442\u0435\u0440\u043c\u0438\u043d\u0430\u0445 \u044d\u0442\u043e\u0433\u043e \u0433\u0440\u0430\u0444\u0430, \u0442\u043e \u043f\u043e\u043b\u0443\u0447\u0430\u0435\u0442\u0441\u044f, \u0447\u0442\u043e \u043d\u0443\u0436\u043d\u043e \u043d\u0430\u0439\u0442\u0438 \u043c\u0430\u043a\u0441\u0438\u043c\u0430\u043b\u044c\u043d\u043e\u0435 \u043f\u043e \u0440\u0430\u0437\u043c\u0435\u0440\u0443 \u043c\u043d\u043e\u0436\u0435\u0441\u0442\u0432\u043e \u0440\u0435\u0431\u0435\u0440 \u0442\u0430\u043a\u043e\u0435, \u0447\u0442\u043e\u0431\u044b \u0432\u0435\u0440\u0448\u0438\u043d\u044b \u044f\u0432\u043b\u044f\u043b\u0438\u0441\u044c \u043a\u043e\u043d\u0446\u043e\u043c \u043d\u0435 \u0431\u043e\u043b\u0435\u0435 \u043e\u0434\u043d\u043e\u0433\u043e \u0440\u0435\u0431\u0440\u0430. \u0412 \u043e\u0431\u0449\u0435\u043c \u0442\u043e, \u044d\u0442\u043e \u0434\u043e\u0432\u043e\u043b\u044c\u043d\u043e \u0438\u0437\u0432\u0435\u0441\u0442\u043d\u0430\u044f <a href=\"https:\/\/ru.wikipedia.org\/wiki\/%D0%9F%D0%B0%D1%80%D0%BE%D1%81%D0%BE%D1%87%D0%B5%D1%82%D0%B0%D0%BD%D0%B8%D0%B5\" rel=\"nofollow\">\u0437\u0430\u0434\u0430\u0447\u0430 \u043e \u043c\u0430\u043a\u0441\u0438\u043c\u0430\u043b\u044c\u043d\u043e\u043c \u043f\u0430\u0440\u043e\u0441\u043e\u0447\u0435\u0442\u0430\u043d\u0438\u0438<\/a>. \u0414\u0430\u0432\u0430\u0439\u0442\u0435 \u043f\u043e\u043f\u0440\u043e\u0431\u0443\u0435\u043c \u0435\u0451 \u043f\u0440\u0438\u043c\u0435\u043d\u0438\u0442\u044c \u0434\u043b\u044f \u0440\u0435\u0448\u0435\u043d\u0438\u044f \u044d\u0442\u043e\u0439 \u0437\u0430\u0434\u0430\u0447\u0438, \u0442\u0443\u0442 \u043f\u043e\u043b\u0443\u0447\u0438\u0442\u0441\u044f \u0434\u0430\u0436\u0435 \u0441 \u0430\u043d\u0438\u043c\u0430\u0446\u0438\u0435\u0439, \u043f\u0440\u0438\u0432\u0435\u0434\u0443 \u0431\u0430\u0437\u043e\u0432\u044b\u0439 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u041a\u0443\u043d\u0430 \u0434\u043b\u044f \u043d\u0430\u0445\u043e\u0436\u0434\u0435\u043d\u0438\u044f \u043c\u0430\u043a\u0441\u0438\u043c\u0430\u043b\u044c\u043d\u043e\u0433\u043e \u043f\u0430\u0440\u043e\u0441\u043e\u0447\u0435\u0442\u0430\u043d\u0438\u044f.<\/p>\n<p>  <\/p>\n<div class=\"spoiler\" role=\"button\" tabindex=\"0\">                         <b class=\"spoiler_title\">\u0420\u0435\u0430\u043b\u0438\u0437\u0430\u0446\u0438\u044f \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0430 \u041a\u0443\u043d\u0430 \u0434\u043b\u044f \u043f\u0430\u0440\u043e\u0441\u043e\u0447\u0435\u0442\u0430\u043d\u0438\u0439 \u043d\u0430 \u0433\u0440\u0430\u0444\u0435 \u0434\u043e\u043c\u0438\u043d\u043e\u0448\u0435\u043a<\/b>                         <\/p>\n<div class=\"spoiler_text\">\n<pre><code class=\"python\">def check_valid(i, j, n, m, tiling):     return 0 &lt;= i and i &lt; n and 0 &lt;= j and j &lt; m and tiling[i][j] != '#'  def find_augmenting_path(x, y, n, m, visited, matched, tiling):     if not check_valid(x, y, n, m, tiling):         return False     if (x, y) in visited:         return False     visited.add((x, y))      for dx, dy in [(-1, 0), (1, 0), (0, -1), (0, 1)]:         if not check_valid(x + dx, y + dy, n, m, tiling):             continue         if (x + dx, y + dy) not in matched or find_augmenting_path(*matched[(x + dx , y + dy)], n, m, visited, matched, tiling):             matched[(x + dx, y + dy)] = (x, y)             return True     return False  def convert_match(matched, tiling, n, m):     result = [[-1 if tiling[i][j] == '#' else -2 for j in range(m)] for i in range(n)]     num = 0     for x, y in matched:         _x, _y = matched[(x, y)]         result[x][y] = num         result[_x][_y] = num         num += 1     return result  def match_with_flow(tiling):     result_slices = []     n = len(tiling)     m = len(tiling[0])      matched = dict()     # \u0414\u043b\u044f \u043d\u0430\u0433\u043b\u044f\u0434\u043d\u043e\u0441\u0442\u0438 \u0432\u0438\u0437\u0443\u0430\u043b\u0438\u0437\u0430\u0446\u0438\u0438     rows = list(range(n))     columns = list(range(m))     random.shuffle(rows)     random.shuffle(columns)     result_slices.append(convert_match(matched, tiling, n, m))      for i in rows:         for j in columns:             if (i + j) % 2 == 1:                 continue             visited = set()             if find_augmenting_path(i, j, n, m, visited, matched, tiling):                 result_slices.append(convert_match(matched, tiling, n, m))      return result_slices<\/code><\/pre>\n<\/div><\/div>\n<p>  <\/p>\n<p>\u0417\u0434\u0435\u0441\u044c \u0434\u0430\u0436\u0435 \u043f\u043e\u043b\u0443\u0447\u0430\u0435\u0442\u0441\u044f \u043f\u0440\u043e\u0430\u043d\u0438\u043c\u0438\u0440\u043e\u0432\u0430\u0442\u044c \u043f\u0440\u043e\u0446\u0435\u0441\u0441<\/p>\n<p>  <\/p>\n<pre><code class=\"python\">sequencial_match = match_with_flow(tiling_custom) <\/code><\/pre>\n<p>  <\/p>\n<div style=\"text-align:center;\"><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/webt\/s1\/fz\/no\/s1fznoqfhy93n6twvp69qppfey8.gif\"><\/div>\n<p>  <\/p>\n<p>\u0421\u0443\u0442\u044c \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0430 \u041a\u0443\u043d\u0430 (\u0434\u0430 \u0438 \u043b\u044e\u0431\u043e\u0433\u043e \u0434\u0440\u0443\u0433\u043e\u0433\u043e \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u0434\u043b\u044f \u043d\u0430\u0445\u043e\u0436\u0434\u0435\u043d\u0438\u044f \u043c\u0430\u043a\u0441\u0438\u043c\u0430\u043b\u044c\u043d\u043e\u0433\u043e \u043f\u0430\u0440\u043e\u0441\u043e\u0447\u0435\u0442\u0430\u043d\u0438\u044f) \u0437\u0430\u043a\u043b\u044e\u0447\u0430\u0435\u0442\u0441\u044f \u0432 \u043d\u0430\u0445\u043e\u0436\u0434\u0435\u043d\u0438\u0438 &quot;\u0430\u0443\u0433\u043c\u0435\u043d\u0442\u0438\u0440\u0443\u044e\u0449\u0438\u0445 \u043f\u0443\u0442\u0435\u0439&quot;. \u0412 \u0442\u0435\u0440\u043c\u0438\u043d\u0430\u0445 \u0434\u043e\u043c\u0438\u043d\u043e\u0448\u0435\u043a \u044d\u0442\u043e \u0446\u0435\u043f\u043e\u0447\u043a\u0430 \u0438\u0437 \u0434\u043e\u043c\u0438\u043d\u043e\u0448\u0435\u043a, \u0443 \u043a\u043e\u0442\u043e\u0440\u043e\u0439 \u0440\u044f\u0434\u043e\u043c \u0441 \u0434\u043e\u043c\u0438\u043d\u043e\u0448\u043a\u0430\u043c\u0438 \u043d\u0430 \u043a\u043e\u043d\u0446\u0430\u0445 \u0435\u0441\u0442\u044c \u043f\u043e \u0441\u0432\u043e\u0431\u043e\u0434\u043d\u043e\u0439 \u043a\u043b\u0435\u0442\u043a\u0435, \u0442\u0430\u043a\u0438\u0435 \u0446\u0435\u043f\u043e\u0447\u043a\u0438 \u043c\u043e\u0436\u043d\u043e \u0437\u0430\u043c\u0435\u043d\u0438\u0442\u044c \u043d\u0430 \u0446\u0435\u043f\u043e\u0447\u043a\u0438 \u0431\u043e\u043b\u044c\u0448\u0435\u0439 \u0434\u043b\u0438\u043d\u044b, \u043e\u0445\u0432\u0430\u0442\u044b\u0432\u0430\u044e\u0449\u0438\u0435 \u0442\u0435 \u0436\u0435 \u043a\u043b\u0435\u0442\u043a\u0438 \u0438 \u0437\u0430\u043f\u043e\u043b\u043d\u044f\u044f \u0434\u0432\u0435 \u0441\u0432\u043e\u0431\u043e\u0434\u043d\u044b\u0435 \u043a\u043b\u0435\u0442\u043a\u0438 \u0440\u044f\u0434\u043e\u043c \u0441 \u043a\u043e\u043d\u0446\u0430\u043c\u0438 \u0446\u0435\u043f\u043e\u0447\u043a\u0438. \u0411\u043e\u043b\u0435\u0435 \u0442\u043e\u0433\u043e, \u043e\u0441\u043d\u043e\u0432\u043d\u043e\u0435 \u0443\u0442\u0432\u0435\u0440\u0436\u0434\u0435\u043d\u0438\u0435, \u043d\u0430 \u043a\u043e\u0442\u043e\u0440\u043e\u043c \u0440\u0430\u0431\u043e\u0442\u0430\u044e\u0442 \u0432\u0441\u0435 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u044b \u043d\u0430\u0445\u043e\u0436\u0434\u0435\u043d\u0438\u044f \u043c\u0430\u043a\u0441\u0438\u043c\u0430\u043b\u044c\u043d\u043e\u0433\u043e \u043f\u0430\u0440\u043e\u0441\u043e\u0447\u0435\u0442\u0430\u043d\u0438\u044f, \u0437\u0430\u043a\u043b\u044e\u0447\u0430\u0435\u0442\u0441\u044f \u0432 \u0442\u043e\u043c, \u0447\u0442\u043e \u0435\u0441\u043b\u0438 \u0442\u0430\u043a\u043e\u0439 \u0446\u0435\u043f\u043e\u0447\u043a\u0438 \u043d\u0435 \u0443\u0434\u0430\u0435\u0442\u0441\u044f \u043d\u0430\u0439\u0442\u0438, \u0442\u043e \u0437\u043d\u0430\u0447\u0438\u0442 \u0431\u043e\u043b\u044c\u0448\u0435\u0433\u043e \u0437\u0430\u043c\u043e\u0449\u0435\u043d\u0438\u044f \u043d\u0430\u043c \u043d\u0435 \u043f\u043e\u043b\u0443\u0447\u0438\u0442\u044c.<\/p>\n<p>  <\/p>\n<h2 id=\"bonus-raskraska-planarnogo-grafa-v-5-cvetov\">\u0411\u043e\u043d\u0443\u0441! \u0420\u0430\u0441\u043a\u0440\u0430\u0441\u043a\u0430 \u043f\u043b\u0430\u043d\u0430\u0440\u043d\u043e\u0433\u043e \u0433\u0440\u0430\u0444\u0430 \u0432 5 \u0446\u0432\u0435\u0442\u043e\u0432.<\/h2>\n<p>  <\/p>\n<p>\u0414\u043b\u044f \u0432\u0438\u0437\u0443\u0430\u043b\u0438\u0437\u0430\u0446\u0438\u0438 \u0437\u0430\u043c\u043e\u0449\u0435\u043d\u0438\u044f \u044f \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u043b \u043e\u0442\u0434\u0435\u043b\u044c\u043d\u044b\u0439 \u0446\u0432\u0435\u0442 \u0434\u043b\u044f \u043a\u0430\u0436\u0434\u043e\u0439 \u0434\u043e\u043c\u0438\u043d\u043e\u0448\u043a\u0438. \u041a \u0441\u043e\u0436\u0430\u043b\u0435\u043d\u0438\u044e \u043d\u0435\u043a\u043e\u0442\u043e\u0440\u044b\u0435 \u0446\u0432\u0435\u0442\u0430 \u043d\u0435 \u043e\u0447\u0435\u043d\u044c \u0445\u043e\u0440\u043e\u0448\u043e \u0441\u043c\u043e\u0442\u0440\u044f\u0442\u0441\u044f, \u0430 \u043d\u0435\u043a\u043e\u0442\u043e\u0440\u044b\u0435 \u043f\u043b\u043e\u0445\u043e \u043a\u043e\u043d\u0442\u0440\u0430\u0441\u0442\u0438\u0440\u0443\u044e\u0442 \u0434\u0440\u0443\u0433 \u0441 \u0434\u0440\u0443\u0433\u043e\u043c. \u0412 \u044d\u0442\u043e\u043c \u0441\u043b\u0443\u0447\u0430\u0435 \u043f\u043e\u0434\u043e\u0431\u0440\u0430\u0442\u044c \u0446\u0432\u0435\u0442\u0430 \u0434\u043b\u044f \u0445\u043e\u0440\u043e\u0448\u0435\u0433\u043e \u043a\u043e\u043d\u0442\u0440\u0430\u0441\u0442\u0430 \u043d\u0435 \u0442\u0430\u043a \u0443\u0436 \u043f\u0440\u043e\u0441\u0442\u043e, \u043e\u0441\u043e\u0431\u0435\u043d\u043d\u043e \u0435\u0441\u043b\u0438 \u0434\u043e\u043c\u0438\u043d\u043e\u0448\u0435\u043a \u043c\u043d\u043e\u0433\u043e. \u0417\u0430\u0442\u043e \u043c\u043e\u0436\u043d\u043e \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u0442\u044c \u043c\u0435\u043d\u044c\u0448\u0435 \u0446\u0432\u0435\u0442\u043e\u0432: \u0434\u043e\u043c\u0438\u043d\u043e\u0448\u043a\u0438, \u043a\u043e\u0442\u043e\u0440\u044b\u0435 \u043d\u0435 \u043d\u0430\u0445\u043e\u0434\u044f\u0442\u0441\u044f \u0440\u044f\u0434\u043e\u043c \u0434\u0440\u0443\u0433 \u0441 \u0434\u0440\u0443\u0433\u043e\u043c \u043c\u043e\u0436\u043d\u043e \u0440\u0430\u0441\u043a\u0440\u0430\u0441\u0438\u0442\u044c \u0432 \u043e\u0434\u0438\u043d\u0430\u043a\u043e\u0432\u044b\u0439 \u0446\u0432\u0435\u0442, \u0442\u043e\u0433\u0434\u0430 \u0432\u0438\u0437\u0443\u0430\u043b\u044c\u043d\u043e \u0432\u0441\u0435 \u0435\u0449\u0435 \u0431\u0443\u0434\u0435\u0442 \u043f\u043e\u043d\u044f\u0442\u043d\u043e, \u043a\u0430\u043a \u0438\u043c\u0435\u043d\u043d\u043e \u0432\u044b\u0433\u043b\u044f\u0434\u0438\u0442 \u043f\u043e\u043a\u0440\u044b\u0442\u0438\u0435. \u0412 \u043e\u0431\u0449\u0435\u043c \u0442\u043e \u044d\u0442\u043e \u043a\u043b\u0430\u0441\u0441\u0438\u0447\u0435\u0441\u043a\u0430\u044f \u0437\u0430\u0434\u0430\u0447\u0430 \u043e \u0440\u0430\u0441\u043a\u0440\u0430\u0441\u043a\u0435 \u0432\u0435\u0440\u0448\u0438\u043d \u043f\u043b\u0430\u043d\u0430\u0440\u043d\u043e\u0433\u043e \u0433\u0440\u0430\u0444\u0430. \u041b\u044e\u0431\u043e\u0439 \u043f\u043b\u0430\u043d\u0430\u0440\u043d\u044b\u0439 \u0433\u0440\u0430\u0444 \u043c\u043e\u0436\u043d\u043e <a href=\"https:\/\/ru.wikipedia.org\/wiki\/%D0%A2%D0%B5%D0%BE%D1%80%D0%B5%D0%BC%D0%B0_%D0%BE_%D1%87%D0%B5%D1%82%D1%8B%D1%80%D1%91%D1%85_%D0%BA%D1%80%D0%B0%D1%81%D0%BA%D0%B0%D1%85\" rel=\"nofollow\">\u043f\u043e\u043a\u0440\u0430\u0441\u0438\u0442\u044c \u0432 4 \u0446\u0432\u0435\u0442\u0430<\/a>, \u043f\u0440\u0430\u0432\u0434\u0430 \u0445\u043e\u0440\u043e\u0448\u0435\u0433\u043e \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0430 \u0434\u043b\u044f \u0442\u0430\u043a\u043e\u0439 \u043f\u043e\u043a\u0440\u0430\u0441\u043a\u0438 \u043d\u0435\u0442. \u0417\u0430\u0442\u043e \u0435\u0441\u0442\u044c \u0434\u043e\u0432\u043e\u043b\u044c\u043d\u043e \u043f\u0440\u043e\u0441\u0442\u043e\u0439 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u0434\u043b\u044f \u043f\u043e\u043a\u0440\u0430\u0441\u043a\u0438 \u0432 5 \u0446\u0432\u0435\u0442\u043e\u0432, \u043a\u043e\u0433\u0434\u0430 \u043f\u0440\u0430\u0432\u0434\u0430 \u0432\u0441\u0435 \u0435\u0449\u0435 \u043c\u043d\u043e\u0433\u043e, \u0438 \u044f \u0435\u0433\u043e \u043c\u0430\u043b\u043e \u0442\u0435\u0441\u0442\u0438\u0440\u043e\u0432\u0430\u043b (\u0435\u0441\u043b\u0438 \u043d\u0435\u043e\u0431\u0445\u043e\u0434\u0438\u043c 5\u044b\u0439 \u0446\u0432\u0435\u0442, \u0442\u043e \u0432\u043e\u0437\u043c\u043e\u0436\u043d\u044b \u0431\u0430\u0433\u0438)<\/p>\n<p>  <\/p>\n<div class=\"spoiler\" role=\"button\" tabindex=\"0\">                         <b class=\"spoiler_title\">\u041f\u043e\u043a\u0440\u0430\u0441\u043a\u0430 \u0434\u043e\u043c\u0438\u043d\u043e\u0448\u0435\u043a \u0432 5 \u0446\u0432\u0435\u0442\u043e\u0432<\/b>                         <\/p>\n<div class=\"spoiler_text\">\n<pre><code class=\"python\">def color_5(filling):     result = [[i for i in row] for row in filling]     # \u0421\u0442\u0440\u043e\u0438\u043c \u0433\u0440\u0430\u0444     domino_tiles = [[] for i in range(max(map(max, filling)) + 1)]     domino_neighbours = [set() for i in range(max(map(max, filling)) + 1)]     degree = [0 for i in range(max(map(max, filling)) + 1)]      n = len(filling)     m = len(filling[0])      for i, row in enumerate(filling):         for j, num in enumerate(row):             if num &gt;= 0:                 domino_tiles[num].append((i, j))      for i, tiles in enumerate(domino_tiles):         for x, y in tiles:             for dx, dy in [(-1, 0), (1, 0), (0, -1), (0, 1), (-1, -1), (-1, 1), (1, -1), (1, 1)]:                 a, b = x + dx, y + dy                 if 0 &lt;= a and a &lt; n and 0 &lt;= b and b &lt; m and filling[a][b] &gt;= 0 and filling[a][b] != i \\                         and filling[a][b] not in domino_neighbours[i]:                     domino_neighbours[i].add(filling[a][b])                     degree[i] += 1      # \u041f\u0435\u0440\u0432\u044b\u043c \u0434\u0435\u043b\u043e\u043c \u043d\u0443\u0436\u043d\u043e \u043d\u0430\u0439\u0442\u0438 \u0442\u0430\u043a\u043e\u0439 \u043f\u043e\u0440\u044f\u0434\u043e\u043a \u0432\u0435\u0440\u0448\u0438\u043d, \u0432\u0441\u0435 \u0432\u0435\u0440\u0448\u0438\u043d\u044b \u0438\u043c\u0435\u043b\u0438 \u043d\u0435 \u0431\u043e\u043b\u044c\u0448\u0435 5 \u0441\u043e\u0441\u0435\u0434\u0435\u0439 \u0441\u0440\u0435\u0434\u0438     # \u043f\u0440\u0435\u0434\u044b\u0434\u0443\u0449\u0438\u0445. \u0422\u0430\u043a\u043e\u0439 \u0441\u0443\u0449\u0435\u0441\u0442\u0432\u0443\u0435\u0442 \u0432 \u0441\u0438\u043b\u0443 \u0442\u043e\u0433\u043e, \u0447\u0442\u043e \u0433\u0440\u0430\u0444 \u043f\u043b\u0430\u043d\u0430\u0440\u043d\u044b\u0439, \u0430 \u043d\u0430\u0439\u0442\u0438 \u0435\u0433\u043e \u044d\u0444\u0444\u0435\u043a\u0442\u0438\u0432\u043d\u0435\u0435 \u0432\u0441\u0435\u0433\u043e     # \u043f\u043e \u043e\u0447\u0435\u0440\u0435\u0434\u0438 \u043d\u0430\u0445\u043e\u0434\u044f \u0432\u0435\u0440\u0448\u0438\u043d\u0443 \u043d\u0430\u0438\u043c\u0435\u043d\u044c\u0448\u0435\u0439 \u0441\u0442\u0435\u043f\u0435\u043d\u0438 \u0438 \u0443\u0434\u0430\u043b\u044f\u044f \u0435\u0451 \u0438\u0437 \u0433\u0440\u0430\u0444\u0430, \u0442\u0430\u043a \u043c\u044b \u043f\u043e\u043b\u0443\u0447\u0430\u0435\u043c \u043e\u0431\u0440\u0430\u0442\u043d\u044b\u0439 \u043f\u043e\u0440\u044f\u0434\u043e\u043a     active_degrees = [set() for i in range(max(degree) + 1)]     for i, deg in enumerate(degree):         active_degrees[deg].add(i)      reversed_order = []      for step in range(len(domino_tiles)):         min_degree = min([i for i, dominoes in enumerate(active_degrees) if len(dominoes) &gt; 0])         domino = active_degrees[min_degree].pop()          reversed_order.append(domino)         for other in domino_neighbours[domino]:             if other in active_degrees[degree[other]]:                 active_degrees[degree[other]].remove(other)                 degree[other] -= 1                 active_degrees[degree[other]].add(other)                      # \u0422\u0435\u043f\u0435\u0440\u044c \u043f\u0435\u0440\u0435\u0431\u0438\u0440\u0430\u0435\u043c \u0432 \u043e\u0431\u0440\u0430\u0442\u043d\u043e\u043c \u043f\u043e\u0440\u044f\u0434\u043a\u0435 \u0438 \u043b\u0438\u0431\u043e \u043a\u0440\u0430\u0441\u0438\u043c \u0432 \u0435\u0449\u0435 \u043d\u0435 \u0437\u0430\u043d\u044f\u0442\u044b\u0439 \u0446\u0432\u0435\u0442,     # \u0435\u0441\u043b\u0438 \u0435\u0441\u0442\u044c \u0441\u0432\u043e\u0431\u043e\u0434\u043d\u044b\u0439 \u0438\u0437 5 \u0446\u0432\u0435\u0442\u043e\u0432, \u0438\u043d\u0430\u0447\u0435 \u043d\u0430\u0445\u043e\u0434\u0438\u043c \u0446\u0435\u043f\u043e\u0447\u043a\u0443 \u0438\u0437 \u0447\u0435\u0440\u0435\u0434\u0443\u044e\u0449\u0438\u0445\u0441\u044f \u0446\u0432\u0435\u0442\u043e\u0432,     # \u043a\u043e\u0442\u043e\u0440\u044b\u0435 \u043c\u043e\u0433\u0443\u0442 \u0431\u044b\u0442\u044c \u043f\u0435\u0440\u0435\u043a\u0440\u0430\u0448\u0435\u043d\u044b. \u0422\u0430\u043a\u0430\u044f \u043d\u0430\u0439\u0434\u0435\u0442\u0441\u044f \u0432 \u0441\u0438\u043b\u0443 \u043f\u043b\u0430\u043d\u0430\u0440\u043d\u043e\u0441\u0442\u0438     colors = [-1 for domino in domino_tiles]     slices = [draw_filling(result)]     for domino in reversed(reversed_order):         used_colors = [colors[other] for other in domino_neighbours[domino] if colors[other] != -1]          domino_color = len(used_colors)         for i, color in enumerate(sorted(set(used_colors))):             if i != color:                 domino_color = i                 break          if domino_color &lt; 5:             colors[domino] = domino_color             for x, y in domino_tiles[domino]:                 result[x][y] = domino_color              slices.append(draw_filling(result))                     continue          # \u041d\u0430\u0447\u0438\u043d\u0430\u044f \u043e\u0442\u0441\u044e\u0434\u0430 \u043a\u043e\u0434 \u044f \u043d\u0435 \u0442\u0435\u0441\u0442\u0438\u0440\u043e\u0432\u0430\u043b, \u043d\u0435 \u043d\u0430\u0448\u0435\u043b \u043f\u0440\u0438\u043c\u0435\u0440\u0430                 c = 0         other = [other for other in domino_neighbours[domino] if colors[other] == c]         visited = set([other])         q = Queue()         q.put(other)         domino_was_reached = False         while not q.empty():             cur = q.get()             for other in domino_neighbours[cur]:                 if other == domino:                     domino_was_reached = True                     break                 if color[other] == c or color[other] == c + 1 and other not in visited:                     visited.add(other)                     q.put(other)          if not domino_was_reached:             for other in visited:                 color[other] = color[other] ^ 1                 for x, y in domino_tiles[other]:                     result[x][y] = color[other]             color[domino] = c             for x, y in domino_tiles[domino]:                 result[x][y] = c              slices.append(draw_filling(result))             continue          # \u041f\u0440\u043e\u0434\u0435\u043b\u044b\u0432\u0430\u0435\u043c \u0442\u043e\u0436\u0435 \u0441\u0430\u043c\u043e\u0435 \u0434\u043b\u044f 2 \u0438 3.         c = 2         other = [other for other in domino_neighbours[domino] if colors[other] == c]         visited = set([other])         q = Queue()         q.put(other)         domino_was_reached = False         while not q.empty():             cur = q.get()             for other in domino_neighbours[cur]:                 if other == domino:                     domino_was_reached = True                     break                 if color[other] == c or color[other] == c + 1 and other not in visited:                     visited.add(other)                     q.put(other)         for other in visited:             color[other] = color[other] ^ 1             for x, y in domino_tiles[other]:                 result[x][y] = color[other]         color[domino] = c         for x, y in domino_tiles[domino]:             result[x][y] = c         slices.append(draw_filling(result))      return result, slices      <\/code><\/pre>\n<\/div><\/div>\n<p>  <\/p>\n<p>\u0415\u0441\u043b\u0438 \u0432\u044b \u0441\u043e\u0431\u0438\u0440\u0430\u0435\u0442\u0435\u0441\u044c \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u0442\u044c \u044d\u0442\u043e\u0442 \u043a\u043e\u0434, \u0442\u043e \u043e\u0431\u0440\u0430\u0442\u0438\u0442\u0435 \u0432\u043d\u0438\u043c\u0430\u043d\u0438\u0435, \u0447\u0442\u043e \u0442\u0430\u043c \u043f\u0440\u043e\u0438\u0441\u0445\u043e\u0434\u0438\u0442 \u043e\u0442\u0440\u0438\u0441\u043e\u0432\u043a\u0430 \u043a\u0430\u0436\u0434\u043e\u0433\u043e \u0448\u0430\u0433\u0430 \u2014 \u044d\u0442\u043e \u0431\u044b\u043b\u043e \u043d\u0443\u0436\u043d\u043e \u0434\u043b\u044f \u0430\u043d\u0438\u043c\u0430\u0446\u0438\u0438, \u0447\u0442\u043e \u0441\u0438\u043b\u044c\u043d\u043e \u0437\u0430\u043c\u0435\u0434\u043b\u044f\u0435\u0442 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c. \u0415\u0441\u043b\u0438 \u0432\u0430\u043c \u043d\u0443\u0436\u043d\u0430 \u0442\u043e\u043b\u044c\u043a\u043e \u043a\u043e\u043d\u0435\u0447\u043d\u0430\u044f \u043f\u043e\u043a\u0440\u0430\u0441\u043a\u0430, \u0442\u043e \u0443\u0431\u0435\u0440\u0438\u0442\u0435 \u0432\u0435\u0441\u044c \u043a\u043e\u0434, \u0437\u0430\u0434\u0435\u0439\u0441\u0442\u0432\u0443\u044e\u0449\u0438\u0439 \u043f\u0435\u0440\u0435\u043c\u0435\u043d\u043d\u0443\u044e slices.<\/p>\n<p>  <\/p>\n<div style=\"text-align:center;\"><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/webt\/jw\/2e\/01\/jw2e01dgfsqg9dkfpq3ptakee_u.gif\"><\/div>\n<p>  <\/p>\n<p>\u041d\u0443 \u0438 \u043d\u0430\u043a\u043e\u043d\u0435\u0446 \u043f\u043e\u043f\u0440\u043e\u0431\u0443\u0435\u043c \u043e\u0434\u0438\u043d \u0438\u0437 \u043f\u0440\u0438\u043c\u0435\u0440\u043e\u0432, \u043a\u043e\u0442\u043e\u0440\u044b\u0439 \u0431\u044b\u043b \u0447\u0443\u0442\u044c \u0440\u0430\u043d\u044c\u0448\u0435<\/p>\n<p>  <\/p>\n<div style=\"text-align:center;\"><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/webt\/ls\/da\/wv\/lsdawve2wjirgjzt3w2q1ctloou.png\"><\/div>\n<\/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=\"https:\/\/habr.com\/ru\/post\/501008\/\"> https:\/\/habr.com\/ru\/post\/501008\/<\/a><\/p>\n","protected":false},"excerpt":{"rendered":"\n<div class=\"post__text post__text-html post__text_v1\" id=\"post-content-body\" data-io-article-url=\"https:\/\/habr.com\/ru\/post\/501008\/\">\n<p>\u041e\u0434\u043d\u0430 \u0438\u0437 \u043f\u0435\u0440\u0432\u044b\u0445 \u0434\u0435\u0439\u0441\u0442\u0432\u0438\u0442\u0435\u043b\u044c\u043d\u043e \u0438\u043d\u0442\u0435\u0440\u0435\u0441\u043d\u044b\u0445 \u0437\u0430\u0434\u0430\u0447 \u043f\u043e \u043c\u0430\u0442\u0435\u043c\u0430\u0442\u0438\u043a\u0435, \u0441 \u043a\u043e\u0442\u043e\u0440\u044b\u043c\u0438 \u044f \u0441\u0442\u043e\u043b\u043a\u043d\u0443\u043b\u0441\u044f \u0444\u043e\u0440\u043c\u0443\u043b\u0438\u0440\u0443\u0435\u0442\u0441\u044f \u0442\u0430\u043a: &quot;\u0438\u0437 \u0448\u0430\u0445\u043c\u0430\u0442\u043d\u043e\u0439 \u0434\u043e\u0441\u043a\u0438 \u0432\u044b\u0440\u0435\u0437\u0430\u043b\u0438 \u0434\u0432\u0435 \u043f\u0440\u043e\u0442\u0438\u0432\u043e\u043f\u043e\u043b\u043e\u0436\u043d\u044b\u0435 \u043f\u043e \u0434\u0438\u0430\u0433\u043e\u043d\u0430\u043b\u0438 \u0443\u0433\u043b\u043e\u0432\u044b\u0435 \u043a\u043b\u0435\u0442\u043a\u0438, \u043c\u043e\u0436\u043d\u043e \u043b\u0438 \u043e\u0441\u0442\u0430\u0432\u0448\u0443\u044e\u0441\u044f \u0447\u0430\u0441\u0442\u044c \u0440\u0430\u0437\u0440\u0435\u0437\u0430\u0442\u044c \u043d\u0430 &quot;\u0434\u043e\u043c\u0438\u043d\u043e\u0448\u043a\u0438&quot; \u2014 \u0444\u0438\u0433\u0443\u0440\u043a\u0438 \u0438\u0437 \u0434\u0432\u0443\u0445 \u043a\u043b\u0435\u0442\u043e\u043a, \u0443 \u043a\u043e\u0442\u043e\u0440\u044b\u0445 \u043e\u0434\u043d\u0430 \u0441\u0442\u043e\u0440\u043e\u043d\u0430 \u043e\u0431\u0449\u0430\u044f?&quot;. \u0423 \u043d\u0435\u0435 \u043e\u0447\u0435\u043d\u044c \u043f\u0440\u043e\u0441\u0442\u0430\u044f \u0444\u043e\u0440\u043c\u0443\u043b\u0438\u0440\u043e\u0432\u043a\u0430, \u0432 \u043e\u0442\u043b\u0438\u0447\u0438\u0435 \u043e\u0442 \u0432\u0435\u043b\u0438\u043a\u043e\u0439 \u0442\u0435\u043e\u0440\u0435\u043c\u044b \u0424\u0435\u0440\u043c\u0430 \u043e\u043d\u0430 \u0438\u043c\u0435\u0442 \u043f\u0440\u043e\u0441\u0442\u043e\u0435, \u044d\u043b\u0435\u0433\u0430\u043d\u0442\u043d\u043e\u0435, \u043d\u043e \u043d\u0435\u043e\u0447\u0435\u0432\u0438\u0434\u043d\u043e\u0435 \u0440\u0435\u0448\u0435\u043d\u0438\u0435 (\u0435\u0441\u043b\u0438 \u0432\u044b \u0437\u043d\u0430\u0435\u0442\u0435 \u0440\u0435\u0448\u0435\u043d\u0438\u0435 \u0437\u0430\u0434\u0430\u0447\u0438, \u0442\u043e \u043f\u043e\u043f\u0440\u043e\u0431\u0443\u0439\u0442\u0435 \u043f\u0440\u0438\u043c\u0435\u043d\u0438\u0442\u044c \u0435\u0433\u043e \u043a \u0444\u0438\u0433\u0443\u0440\u0435 \u0441\u043f\u0440\u0430\u0432\u0430).<\/p>\n<p>  <\/p>\n<p><img decoding=\"async\" width=\"45%\" src=\"https:\/\/habrastorage.org\/webt\/jx\/3k\/iy\/jx3kiy6ls43az8se19mqwzujijw.png\"> <img decoding=\"async\" width=\"45%\" src=\"https:\/\/habrastorage.org\/webt\/os\/ah\/m7\/osahm7ciwntrzpvkshhayxh53gi.png\"><\/p>\n<p>  <\/p>\n<p>\u0412 \u044d\u0442\u043e\u0439 \u0441\u0442\u0430\u0442\u044c\u044f \u044f \u0440\u0430\u0441\u0441\u043a\u0430\u0436\u0443 \u043e \u043d\u0435\u0441\u043a\u043e\u043b\u044c\u043a\u0438\u0445 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0430\u0445, \u043a\u043e\u0442\u043e\u0440\u044b\u0435 \u0443\u043c\u0435\u044e\u0442 \u043f\u043e\u043a\u0440\u044b\u0432\u0430\u0442\u044c \u0434\u043e\u043c\u0438\u043d\u043e\u0448\u043a\u0430\u043c\u0438 \u043f\u0440\u043e\u0438\u0437\u0432\u043e\u043b\u044c\u043d\u0443\u044e \u043a\u043b\u0435\u0442\u0447\u0430\u0442\u0443\u044e \u0444\u0438\u0433\u0443\u0440\u0443 \u043d\u0430 \u043f\u043b\u043e\u0441\u043a\u043e\u0441\u0442\u0438, \u0435\u0441\u043b\u0438 \u044d\u0442\u043e \u0432\u043e\u0437\u043c\u043e\u0436\u043d\u043e, \u043d\u0430\u0445\u043e\u0434\u0438\u0442\u044c \u0441\u0438\u0442\u0443\u0430\u0446\u0438\u0438, \u043a\u043e\u0433\u0434\u0430 \u044d\u0442\u043e \u043d\u0435\u0432\u043e\u0437\u043c\u043e\u0436\u043d\u043e \u0438 \u0441\u0447\u0438\u0442\u0430\u0442\u044c \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e \u0432\u043e\u0437\u043c\u043e\u0436\u043d\u044b\u0445 \u0437\u0430\u043c\u043e\u0449\u0435\u043d\u0438\u0439 \u0434\u043e\u043c\u0438\u043d\u043e\u0448\u043a\u0430\u043c\u0438.<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[],"tags":[],"class_list":["post-303211","post","type-post","status-publish","format-standard","hentry"],"_links":{"self":[{"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=\/wp\/v2\/posts\/303211","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=303211"}],"version-history":[{"count":0,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=\/wp\/v2\/posts\/303211\/revisions"}],"wp:attachment":[{"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=303211"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=303211"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=303211"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}