ВКОШП: ВКОШП 2021

Правительство Санкт-Битсбурга составляет техническое задание для украшения города к новому году.

Губернатор считает, что следует повесить на главной площади гирлянду из \(n\) лампочек. Лампочки будут включаться и выключаться, и гирлянда будет радовать жителей города.

Главный дизайнер города решил, что гирлянда будет менять свой вид каждую секунду. Каждая лампочка, входящая в состав гирлянды, может быть включена или выключена. Дизайнер решил, что раз в секунду ровно одна из лампочек будет менять свое состояние: с включенной на выключенную или наоборот, с выключенной на включенную. При этом дизайнер хочет, чтобы комбинации включенных и выключенных лампочек повторялись с периодом \(2^n\) секунд, причем за время периода в \(2^n\) секунд все возможные \(2^n\) комбинаций состояний лампочек были представлены на гирлянде.

Главный инженер города, однако, отметил, что постоянное включение и выключение лампочек приводит к их износу. Чтобы износ был равномерным, необходимо, чтобы все лампочки включались и выключались примерно одно и то же число раз.

Итоговое техническое задание для вас — главного программиста департамента информационных технологий правительства — выглядит так.

• Необходимо составить план из \(2^n\) конфигураций лампочек \(a_0, a_1, \ldots, a_{2^n-1}\), где \(a_k\) — строка из \(n\) нулей и единиц, \(a_k[i]=1\) означает, что лампочка \(i\) в конфигурации \(a_k\) включена, а \(a_k[i]=0\) означает, что лампочка \(i\) в конфигурации \(a_k\) выключена.
• Все конфигурации в плане должны быть различны.
• Этот план будет запущен по циклу, каждую секунду на гирлянде будет показываться очередная конфигурация, в \(t\)-ю секунду будет показываться конфигурация \(a_{t \bmod 2^n}\).
• Соседние конфигурации должны отличаться состоянием ровно одной лампочки, аналогично конфигурации \(a_{2^n-1}\) и \(a_0\) также должны отличаться состоянием ровно одной лампочки.
• Обозначим как \(c_i\) количество изменений состояния лампочки \(i\) за время полного цикла, включая конечный переход от \(a_{2^n-1}\) к \(a_0\). Тогда для любых \(i \ne j\) значения \(c_i\) и \(c_j\) должны различаться не более чем на \(2\).

За работу!