Задача 6 (6 баллов)
--------
Первый член последовательности представляет собой непустую
последовательность нулей и единиц. Каждый следующий член получается
приписыванием справа знака 0 или 1. Выбирается такой знак, чтобы число
единиц и число нулей в каждом члене последовательности не отличались
друг от друга больше, чем на 2.

Построить n-й член последовательности, если n кодируется порядковым
номером символа, который Корректор видит в начальный момент в своем
окошке. Считать, что символ "1" кодирует n=1, и в начальный момент на
ленте не могут быть записаны символы с меньшим порядковым номером.
Сразу справа от n на ленте записан первый правильный член
последовательности.

п р о в е р к а  к у р а т о р а

Следует признать, что решение этой задачи, предложенное Казанцевым
Львом, лучше решения куратора с принципиальных позиций.

Куратор использовал символ "ф" как точку отсчета для выяснения баланса
нулей и единиц в первом члене (во имя одного прохода записи). Это
очень плохо. Ведь если завтра алфавит корректора изменится (увеличится
или уменьшится по количеству символов, например), алгоритм, завязанный
на "ф" придется выбрасывать в корзину.

Другое дело, алгоритм Льва: в нем за один проход отдельно
подсчитываются 0 и 1, а потом сравниваются. Как за один проход? Нули
подсчитываются "честно" в ящике (благо он становится свободен после
завода рекурсивной пружины), а вот единицы "подсчитываются" рекурсией:
когда исполнитель видит единицу, он закручивает еще одну рекурсивную
пружинку (команда ПЛЮС). А что ему бедному остается делать? Ведь ящик
занят подсчетом нулей! Работа пружины ПЛЮС начинается тогда, когда
исполнитель достигнет конца записи: единицы быстро просуммируюся
командой ПЛЮС на ленте, а в ящике уже подсчитанные нули. Остается их
только сравнить для принятия решения, что ставить первым 0 или 1,
потом эти знаки будут чередоваться.

Когда я это все увидел, даже подпрыгнул на стуле: ай, да Лев, ай, да
молодец! Действительно, царский подарок нашему курсу.

Прошу обязательно вникнуть в суть этого решения и насладится его
потрясающей красотой (как полотном мадонны Рафаэля).


Автор решения Казанцев Лев (3115)
--------------------------
Алгоритм
--------
Исполнитель уменьшает число на ленте до
единицы (рекурсивной процедурой Вход), затем
процедурой Счет считает количество нулей и единиц
(нули- ящиком, единицы- рекурсией) и, в соответствии с тем,
чего оказалось меньше, дописывает первый знак (процедура Сравнение).
Остальные знаки дописываются путем инвертирования последнего
знака (процедура Дописать_цифру).

Программа
---------
ЭТО Вход                               
 ЕСЛИ 1                               //Проверка числа на ленте.
  ТО { ПИШИ ПУСТО Счет Сравнение }    //Стирание единицы, счёт.
  ИНАЧЕ { МИНУС Вход Дописать_цифру } //Рекурсивный отсчёт. 
КОНЕЦ                                  
                                       
ЭТО Дописать_цифру                     
 ЕСЛИ 1 ТО { ВПРАВО ПИШИ 0 }     //Дописывание нулей      
        ИНАЧЕ { ВПРАВО ПИШИ 1 }  //или единиц.
КОНЕЦ                                  

ЭТО Счет
 ВПРАВО
 ЕСЛИ 1
  ТО { Счет Плюс }   //Рекурсивный счёт единиц.
  ИНАЧЕ ЕСЛИ НЕ ПУСТО ТО { Ящик Счет } //Счёт нулей в ящике.
КОНЕЦ
                                       
ЭТО Плюс                               
 ЕСЛИ ПУСТО ТО ПИШИ 1
            ИНАЧЕ ПЛЮС                 
КОНЕЦ

ЭТО Ящик                               
 ОБМЕН
 Плюс                                  
 ОБМЕН                                 
КОНЕЦ                                  
                                       
ЭТО Сравнение                          
 ЕСЛИ Я<Л ТО ПИШИ 0      //Сравнение нулей и единиц.
          ИНАЧЕ ПИШИ 1                 
КОНЕЦ


Команда 3104
------------
.\04\04.txt
Оценка: 0

Команда 3106
------------
.\06\06.txt
Оценка: 2
Автор решения: Лавыгин Сергей, Ганиев Женя

Алгоритм
--------
Идея:Найти разницу в количествах нулей и единиц.Для этого сначала
двигаемся в конец записи и подсчитываем цифры в записанной
последовательности. Затем, двигаясь в обратном направлении, прибавляем
к полученной сумме по 1, если встречается, 1 и вычитаем 1, если
встречается 0.Затем если эта разность 2, то пишем 0, в противном
случае пишем 1. Можно, конечно, предусмотреть 0 и при разности равной
1 (хотя жесткого условия нет)



ЭТО Штрих      //добавляем 2 единицы
  ПЛЮС        //к номеру искомого
  ПЛЮС        //элемента, чтобы не
  Вход        //получать на первом
КОНЕЦ         //месте 1 и 0

ЭТО Вход
 ЕСЛИ НЕ 1 ТО
    {
      ЕСЛИ НЕ 0 ТО
        {
         ОБМЕН    //Внесем значение
         ПИШИ 2   //максимальной
         ОБМЕН   //разности. Это нуж-
//но, чтобы разность никогда не была
//пустой.
         МИНУС  //Уменьшаем значение
//счетчика на 1, т.к. предыдущий эле-
//мент последовательности уже сформи-
//рован, включая первый.


         ЕСЛИ 2 ТО ПИШИ ПУСТО
         ЕСЛИ НЕ ПУСТО ТО Вправо
          //начинаем формирование
//нового элемента последовательности
         }
              ИНАЧЕ ВЛЕВО
    }
КОНЕЦ

ЭТО Вправо
  ВПРАВО
 ЕСЛИ НЕ ПУСТО ТО
   {
  ОБМЕН     //Подсчет количества
  ПЛЮС      //цифр, включая номер
  ОБМЕН     //элемента( на 1-ом
  Вправо    //месте)
  Цифра
      }
      ИНАЧЕ Влево

КОНЕЦ

ЭТО Влево
ВЛЕВО
ЕСЛИ НЕ ПУСТО ТО
        {           //Если клетка не
          Счет      //пустая, то
          Влево     //считаем 1 и 0
          }
       Назад
КОНЕЦ

ЭТО Назад
  ВПРАВО
  ЕСЛИ НЕ ПУСТО ТО
        {          //Вычитаем из
         ОБМЕН     //счетчика длину
         МИНУС     //самого элемента
         ОБМЕН     //последователь-
                   //ности

         }
           ИНАЧЕ ОБМЕН
КОНЕЦ


ЭТО Счет
  ЕСЛИ 1 ТО
      {         //Если эта цифра-1,
       ОБМЕН    //то добавляем к
       ПЛЮС     //к счетчику, если-
       ОБМЕН    //0, то
         }
       ИНАЧЕ
          ЕСЛИ 0 ТО
            {
              ОБМЕН    //минусуем 1
              МИНУС    //из счетчика
              ОБМЕН
                 }

КОНЕЦ

ЭТО Цифра
 ЕСЛИ 3 ТО  МИНУС  //3 может
//получиться, т.к. при подсчете
//длины мы считаем все цифры, в
//том числе и показывающие номер,
//по которому определяется номер
//элемента.

 ЕСЛИ 2 ТО
      ПИШИ 0
        ИНАЧЕ
          {
             ЕСЛИ НЕ ПУСТО ТО ПИШИ 1
                             }
В_начало
КОНЕЦ

ЭТО В_начало
 ЕСЛИ НЕ ПУСТО ТО  //Возвращаем курсор
       {           //на исходную пози-
        ВЛЕВО      //цию
        В_начало
        }

              ВПРАВО
              Вход  //Все сначала

КОНЕЦ

к о м м е н т а р и й  к у р а т о р а
Нерациональное решение -- много проходов. А главное, неверное.
Например, на правильном входе "200000111" программа выдает "Не могу".


Команда 3107
------------
.\07\07.txt
.\07\tur6.kor
Оценка: 3

// Авторы решения: Андреева И. и
// Доронкина С.
//
// -------------------------------     
//  Описание алгоритма:                
//                                     
//  Находим исходную разность и
//  в зависимости от нее выбираем      
//  способ записи след. членов.        
//  Равновесие нулей и единиц коди-    
//  руется числом 2, 0 соответствует
//  избытку в 2 нуля, а 4 - избытку    
//  2-х единиц. Если начальное         
//  значение разности имеет код 0,
//  чередуем добавление 1 и 0.
//  В противном случае - чередуются    
//  0 и 1, что обеспечивает выполнение 
//  условия задачи.                    
ЭТО вход                               
ОБМЕН  // Записываем в ящик            
ПИШИ 2 // начальное значение           
ОБМЕН  // счетчика = 2
МИНУС    // кол-во оставшихся членов   
//                                     
//Определяем начальную разность
//                                     
 ПОКА НЕ ПУСТО // Двигаемся вдоль      
  {         // числа и считаем 1 за    
ВПРАВО      // +1, а 0 - за -1 к счет-
 ЕСЛИ 1     // чику                    
  ТО        //                         
  {         //                         
   ОБМЕН
   ПЛЮС      // Плюс 1 к счетчику      
   ОБМЕН                               
  }
 ИНАЧЕ
  ЕСЛИ 0                               
  ТО                                   
  {                                    
   ОБМЕН                               
   МИНУС   // Минус 1 от счетчика      
   ОБМЕН   // В ящике - разность       
  }
  }        // Конец ПОКА.              
// Окно стоит на первом пустом месте   
//
// Выбираем метод получения            
// следующего члена                    
//                                     
 ОБМЕН   // Считываем начальную
         // разность на ленту          
 ЕСЛИ 0                                
  ТО    метод0                         
  ИНАЧЕ метод1
  уборка   // Удаление лишних цифр     
КОНЕЦ                                  
//-------------------------------------
// описание
ЭТО метод0  //На ленте начальная       
            // разность                
// Метод состоит в чередовании         
// последующих цифр, начиная с 1       
//                                     
//                                     
 ПОКА НЕ ПУСТО ВЛЕВО // в начало
 ВПРАВО               // записи        
 МИНУС    // Минус 1 от счетчика       
 ЯЩИК+    // Копируем счетчик в ящик
 ПОКА НЕ ПУСТО  // В конец записи      
  ВПРАВО         // Установка на       
 ВЛЕВО          // последнюю цифру     
 ПИШИ 1         // запись цифры поверх
               // начальной разности   
 ОБМЕН         // Счетчик -> на ленту  
 ПОКА НЕ 0                             
  {
  МИНУС        // уменьшение счетчика  
  след_цифра    // пишем след. цифру   
   }
КОНЕЦ
//-------------------------------------
// описание                            
ЭТО метод1                             
// Метод состоит в чередовании         
// последующих цифр, начиная с 0       
// (комментарии - аналогично метод0)   

 ПОКА НЕ ПУСТО ВЛЕВО                   
 ВПРАВО                                
 МИНУС
 ЯЩИК+                                 
 ПОКА НЕ ПУСТО ВПРАВО                  
 ВЛЕВО                                 
 ПИШИ 0
 ОБМЕН                                 
 ПОКА НЕ 0                             
   {                                   
  МИНУС след_цифра
    }                                  
КОНЕЦ                                  
//-------------------------------------
// описание
ЭТО уборка                             
 ОБМЕН    // Восстановление последнего 
          // символа                   
ПОКА НЕ ПУСТО ВЛЕВО // очистка         
ВПРАВО              // ячейки с но-    
ПИШИ ПУСТО          // мером члена     
КОНЕЦ
//-------------------------------------
// описание                            
ЭТО след_цифра
                                       
ОБМЕН       // Счетчик -> в ящик,      
            // возврат последней цифры 
            // на ленту
ЕСЛИ 1 ТО    // инвертирование         
             // последней цифры        
  {                                    
   ВПРАВО
   ПИШИ 0                              
  }                                    
 ИНАЧЕ
  {
   ВПРАВО     // это инверсия нуля     
   ПИШИ 1
  }                                    
ОБМЕН    // Восстановление счетчика    
         // на ленте                   
КОНЕЦ                                  

к о м м е н т а р и й  к у р а т о р а
Решение было бы хорошим, однопроходным, но к сожалению, из-за
неверного алгоритма подсчета авсолютной разницы 0 и 1, программа
неверная. Например, на правильном входе "2000011" программа выдает "Не
могу".

Команда 3108
------------
.\08\08.txt
Оценка: 2
Автор решения: Сухаренко Маша

Описание алгоритма:существует счетчик циклов и флажок выбора варианта
действия

ЭТО Цепочка_6
Подготовка
Работа
Уборка
КОНЕЦ
ЭТО Уборка
ПИШИ ПУСТО
ВЛЕВО
ЕСЛИ НЕ ПУСТО ТО Уборка
ВПРАВО
КОНЕЦ
ЭТО Подготовка  //установить символ |, за которым следует "ячейка"-флажок
ВЛЕВО           //выбора действия
ПИШИ |
ВЛЕВО
ПИШИ 0          //присваиваем "флажку" значение 0
ПОВТОРИ 2 ВПРАВО  //к ячейке, содержащей n
КОНЕЦ
ЭТО Работа
ЕСЛИ НЕ 1 ТО
{
Подсчет_0 //подсчет единиц
Подсчет_1 //подсчет нулей
ПОКА НЕ | ВЛЕВО //изменить "флажок"
 ВЛЕВО          //выбора действия
 ПЛЮС
Счетчик_1
Изменить_счетчик
Работа
}
КОНЕЦ
ЭТО Счетчик_1
ЕСЛИ 1 ТО Алгоритм_1
ИНАЧЕ ЕСЛИ 2 ТО
{
 ПИШИ 0
 Алгоритм_2
}
ПОКА ПУСТО ВЛЕВО
КОНЕЦ
ЭТО Подсчет_0
Обнуление
Действие_1
КОНЕЦ
ЭТО Обнуление  //обнуление ящика
ОБМЕН
ПИШИ 0
ОБМЕН
КОНЕЦ
ЭТО Действие_1
ПОКА НЕ ПУСТО
{
ВПРАВО
ЕСЛИ 0 ТО           //проверка очередной цифры числа
{                   //если цифра - 0
ОБМЕН
ПЛЮС                //к ящику-счетчику прибавляется 1
ОБМЕН
}
}
ВПРАВО
ЯЩИК-               //"запоминание" числа нулей на ленте
ПОКА НЕ | ВЛЕВО     //вернуться к первой цифре числа
ВПРАВО
КОНЕЦ
ЭТО Подсчет_1
Обнуление
Действие_2
КОНЕЦ
ЭТО Действие_2
ПОКА НЕ ПУСТО
{
ВПРАВО
ЕСЛИ 1 ТО          //проверка очередной цифры числа
{                  //если она равна 1,
ОБМЕН
ПЛЮС              //к ящику-счетчику прибавляется 1
ОБМЕН
}
}
ВПРАВО           //число единиц хранится в ящике
КОНЕЦ
ЭТО Алгоритм_1
ПОКА НЕ ПУСТО ВПРАВО   // к ячейке, в которой записано число нулей
ВПРАВО
ЕСЛИ Я=Л ТО
          {
           ВЛЕВО
           ПИШИ 1     //если число нулей равно числу единиц, то
           ВПРАВО
           Уборка_1
           }          //очередная цифра числа 1
ИНАЧЕ Сравнение
КОНЕЦ
ЭТО Алгоритм_2
ПОКА НЕ ПУСТО ВПРАВО
ВПРАВО
ЕСЛИ Я=Л ТО          //если число нулей равно числу  единиц, то
{                    //очередная цифра числа 0
 ВЛЕВО
 ПИШИ 0
 ВПРАВО
 Уборка_1
}
ИНАЧЕ Сравнение
КОНЕЦ
ЭТО Сравнение
ЕСЛИ Я<Л ТО  //Нулей больше
{
 Вычитание
ВПРАВО
ПИШИ 0 //Символ - нулей больше
}
ИНАЧЕ ЕСЛИ Я>Л ТО //Единиц больше
{
ОБМЕН
Вычитание
ВПРАВО
ПИШИ 1 //Символ того, что 1 больше
}
ЕСЛИ 0 ТО
       {
       ОБМЕН
       ПИШИ 2
       ОБМЕН
       ВЛЕВО
        ЕСЛИ Я>Л ТО //Нулей недост.
                 {
                  ВЛЕВО
                  ПИШИ 0
                  ВПРАВО
                  Уборка_1
                  }
        ИНАЧЕ //Нулей 2
        {
        ВЛЕВО
        ПИШИ 1
        ВПРАВО
        Уборка_1
        }
 }
ИНАЧЕ
{
ОБМЕН
ПИШИ 2
ОБМЕН
ВЛЕВО //Сравнение разности нулей и
              //единиц с числом 2
     ЕСЛИ Я>Л ТО //Единиц недостаточно
      {
     ВЛЕВО
     ПИШИ 1
     ВПРАВО
     Уборка_1
       }
     ИНАЧЕ  //Единиц достаточно
     {
      ВЛЕВО
      ПИШИ 0
      ВПРАВО
      Уборка_1
      }
}
КОНЕЦ
ЭТО Уборка_1
ПОКА НЕ ПУСТО
{
ПИШИ ПУСТО
ВПРАВО
}
КОНЕЦ
ЭТО Вычитание
МИНУС
ОБМЕН
МИНУС
ЕСЛИ НЕ 0 ТО
{
ОБМЕН
Вычитание
}
ИНАЧЕ ОБМЕН
КОНЕЦ
ЭТО Изменить_счетчик
ПОКА НЕ | ВЛЕВО
ВПРАВО
МИНУС
КОНЕЦ

к о м м е н т а р и й  к у р а т о р а
Колоссально по числу проходов! Сколько же километров пробежит Корректор,
что бы выполнить ваш алгоритм! А вот программа неверная. Например,
на верных входах "20" и "21" выдает сообщение "Не могу".

Команда 3110
------------
.\10\10.txt
.\10\1011.kor
Оценка: 0

Команда 3113
------------
.\13\13.txt
.\13\1321.kor
Оценка: 0

Команда 3114
------------
.\14\14.txt
.\14\1461.kor
Оценка: 1.5

ЭТО вход
ЕСЛИ НЕ ПУСТО ТО проход                
                                       
КОНЕЦ

ЭТО проход                             
ЕСЛИ НЕ ПУСТО ТО // при наличии        
// символа в ячейке ленты сравниваем
// количество нулей и единиц в первом  
// члене последовательности, чтобы     
// опредилить, какой следующий знак    
// приписать справа                    
{ ЯЩИК+  // скопировать содержимое     
         // оконной ячейки ленты в     
         // ящик                       
  ВПРАВО  // переход в следующую ячей-
          // ку ленты                  
  ПОКА НЕ ПУСТО {                      
      ЕСЛИ 1 ТО { ОБМЕН
// поменять позициями символы, располо-
// женные в ящике и оконной ячейки     
// ленты                               
                  ПЛЮС
// заменить символ в оконной ячейке    
// ленты на следующий в смысле алфави- 
// та исполнителя
                  ОБМЕН
// возвращаем элементы ячейки ленты    
// и ящика на первоначальные позиции   
 }
              ИНАЧЕ { ОБМЕН            
                      МИНУС            
// заменить символ в оконной ячейке на 
// предыдущий в смысле алфавита испол- 
// нителя                              
                      ОБМЕН }          
       ВПРАВО  // переход в следующую  
               // ячейку ленты
}                                      
}                                      
ПОКА НЕ ПУСТО ВЛЕВО
        // переход в следующую ячейку  
        // ленты, пока не найдет пустую
        // ячейку                      
ЕСЛИ Я>Л ТО
            { ПОКА НЕ ПУСТО  ВПРАВО    
// переход в следующую ячейку ленты,   
// пока не найдет пустую ячейку
              ПИШИ 1
              ПОКА НЕ ПУСТО ВЛЕВО      
              ВПРАВО                   
// переход в следующую ячейку ленты
              МИНУС                    
// заменить символ в оконной ячейке на 
// предыдущий в смысле алфавита        
// исполнителя                         
              ЯЩИК+                    
// скопировать содержимое оконной      
// ячейки ленты в ящик                 
              ПИШИ ПУСТО
              ВПРАВО                   
// переход в следующую ячейку ленты    
              ПОКА НЕ ПУСТО ВПРАВО
              ЯЩИК-                    
              конец_последовательности 
                  }                    

          ИНАЧЕ                        
             { ПОКА НЕ ПУСТО ВПРАВО    
               ПИШИ 0
             }
КОНЕЦ                                  
ЭТО конец_последовательности           
ЕСЛИ НЕ ПУСТО ТО продолжи
КОНЕЦ                                  
ЭТО продолжи                           
ЕСЛИ НЕ ПУСТО ТО { ЯЩИК+               
// скопировать содержимое оконной      
// ячейки ленты в ящик                 
                   ПИШИ 0              
                   ВПРАВО              
// переход в следуююющую ячейку ленты
                   ЯЩИК-               
// скопировать в оконную ячейку ленты  
// символ из ящика
                   МИНУС               
// заменить символ в оконной ячейке    
// предыдущий в смысле алфавита        
// исполнителя
         ЕСЛИ НЕ ПУСТО ТО              
                 { ЯЩИК+               
// скопировать содержание оконной
// ячейки ленты в ящик
                   ПИШИ 1              
                   ВПРАВО              
// переход в следующую ячейку ленты
                   ЯЩИК-
// скопировать в оконную ячейку ленты  
// символ из ящика                     
                   МИНУС               
// заменить символ символ в оконной    
// ячейке на предыдущий в смысле алфа- 
// вита исполнителя                    
 } }
конец_последовательности               
КОНЕЦ                                  

к о м м е н т а р и й  к у р а т о р а
Программа неверная.

"10" переводит в "010" (правильно "0")
"20" переводит в "0101" (правильно "01" или "00")
"200000111" выдает "Не могу" (правильно "000001111")


Команда 3115
------------
.\15\15.txt

Автор решения Казанцев Лев.
Описание алгоритма:
Исполнитель уменьшает число на ленте до
единицы (рекурсивной процедурой Вход), затем
процедурой Счет считает количество нулей и единиц
(нули- ящиком, единицы- рекурсией) и, в соответствии с тем,
чего оказалось меньше, дописывает первый знак (процедура Сравнение).
Остальные знаки дописываются путем инвертирования последнего
знака (процедура Дописать_цифру).

Программа, описание программы

ЭТО Вход                               
 ЕСЛИ 1                               //Проверка числа на ленте.
  ТО { ПИШИ ПУСТО Счет Сравнение }    //Стирание единицы, счёт.
  ИНАЧЕ { МИНУС Вход Дописать_цифру } //Рекурсивный отсчёт. 
КОНЕЦ                                  

ЭТО Дописать_цифру                     
 ЕСЛИ 1 ТО { ВПРАВО ПИШИ 0 }     //Дописывание нулей      
        ИНАЧЕ { ВПРАВО ПИШИ 1 }  //или единиц.
КОНЕЦ                                  
                                       
ЭТО Счет
 ВПРАВО                                
 ЕСЛИ 1
  ТО { Счет Плюс }   //Рекурсивный счёт единиц.
  ИНАЧЕ ЕСЛИ НЕ ПУСТО ТО { Ящик Счет } //Счёт нулей в ящике.
КОНЕЦ
                                       
ЭТО Плюс                               
 ЕСЛИ ПУСТО ТО ПИШИ 1                  
            ИНАЧЕ ПЛЮС                 
КОНЕЦ
                                       
ЭТО Ящик                               
 ОБМЕН
 Плюс                                  
 ОБМЕН                                 
КОНЕЦ
                                       
ЭТО Сравнение                          
 ЕСЛИ Я<Л ТО ПИШИ 0      //Сравнение нулей и единиц.
          ИНАЧЕ ПИШИ 1                 
КОНЕЦ                                  

к о м м е н т а р и й  к у р а т о р а
Отличное решение! "Подсчет" единиц рекурсией позволило избавиться от
очень нехорошего символа "ф", который использовал куратор.

