Информатика ЕГЭ 12 задание разбор

• Рассмотрим алгоритм: редактор будет выполнять команды только тогда, когда в строке встречается цепочка «12» или цепочка «333»;
• если в строке есть «12», то тогда эта цепочка заменяется на «3»;
• если в строке нет цепочки «12», но есть «333», то цепочка «333» заменяется на «3».
• Теперь вернемся к условию нашей задачи. Условие цикла истинно, соответственно выполняем блок ЕСЛИ, т.е. делаем замену: в каждом из 40 чисел ‘123‘, заменяем 12 на 3. Получим 40 + 40 = 80 троек (40 троек было изначально и 40 добавилось);

123123123...123
↓  ↓  ↓     ↓
3 33 33 3...3 3

• Так как больше чисел 12 у нас не встречается, то работает блок ИНАЧЕ. Сколько раз можно заменить в 80 подряд идущих тройках три тройки на одну? 80 делим на 3 получаем 26 раз + 2 тройки в остатке. Итого осталось 28 троек;

333 333 333 333... 333 33
   26 троек по три
получили:
3   3   3   3  ... 3 33
         26          + 2

• Теперь из 28 троек сколько раз мы можем заменить три тройки на одну? 28 делим на 3 и получаем 9 раз + 1 тройка в остатке. Итого 10 троек;

333 333 333 333... 333 3
   9 троек по три   + 1
получили:
3   3   3   3  ... 3 3
         9          + 1

• Делаем то же самое: 10 делим на 3 получаем 3 раза + 1 тройка в остатке = 4 тройки

333 333 333 3
3 тройки по три + 1
получили:
3   3   3   3

• Последний раз делим 4 на 3, получаем 1 тройку + 1 = 2 тройки

3 3 3 3
  ↓
  3   3 

Результат: 33
  
✎ Решение 2. С программированием:
Паскаль abc.net:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

begin
   var s := '123'*40;
   var p1 := Pos('12',s);
   var p2 := Pos('333',s);
   while (p1 > 0) or (p2 > 0) do begin
     if p1 > 0 then begin
       Delete( s, p1, 2 );
       Insert( '3', s, p1 );
     end
     else begin
       Delete( s, p2, 3 );
       Insert( '3', s, p2 );
     end;
     p1 := Pos('12',s);
     p2 := Pos('333',s);
   end; 
   write(s);
end.

s = 40*'123'
while "12" in s or "333" in s:
  if "12" in s:
    s = s.replace( "12", "3", 1 )
  else:
    s = s.replace( "333", "3", 1 )
print(s)

#include<iostream>
using namespace std;
int main()
{
   string s(40, '123'); 
   cout << s << endl;
   int p1 = s.find("12");
   int p2 = s.find("333");
   while( p1 != string::npos or p2 != string::npos ) {
      if( p1 != string::npos ) 
        s.replace( p1, 12, "3" );  
      else 
        s.replace( p2, 333, "3" );  
      p1 = s.find("12");
      p2 = s.find("333");
      cout << s << endl;
      }
   cout << s;
}

• Для удобства решения сначала сократим исходную цепочку до одной группы цифр:

1122

• Условие цикла истинно (ПОКА нашлось (12)), и условие в цикле истинно (ЕСЛИ нашлось (12)), значит, делаем замену: в первой группе цифр «1122«, заменяем 12 на 2:

1122 => 122

• Затем опять возвращаемся к условию цикла: условие цикла истинно (ПОКА нашлось (12)), и условие в цикле истинно (ЕСЛИ нашлось (12)), делаем опять замену: в первой группе цифр «122«, заменяем 12 на 2:

122 => 22

• Таким образом, получаем, что за две итерации цикла (2 шага), одна группа цифр превращается в две двойки.
• Поскольку по условию имеем 71 группу цифр, то, чтобы узнать сколько двоек мы получим в результате выполнения условия ЕСЛИ нашлось (12), нам необходимо 71 умножить на 2 (кол-во двоек, получаемых из одной группы цифр):

71 * 2 = 142 двойки из 71 группы 

• То есть в итоге работы цикла и условия ЕСЛИ нашлось (12) мы получили всего 142 двоек.
• Теперь работает условие ИНАЧЕ заменить (222, 2). Из 142 двоек каждые три заменяем на одну. Чтобы рассчитать итоговое количество двоек, необходимо 142 разделить на 3 (т.е. сколько раз можно заменять тройки двоек на одну двойку). Делить необходимо до тех пор, пока работает условие ИНАЧЕ заменить (222, 2):

• 142 / 3 = 47 двоек + 1 двойка (остаток) = 48 двоек
  

• 48 / 3 = 16 двоек

• 16 / 3 = 5 двоек + 1 двойка (остаток) = 6 двоек

• 6 / 3 = 2 двойки

• В итоге осталось 2 двойки.

✎ Решение 2. С программированием:
Паскаль abc.net:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

begin
   var s := '1122'*71;
   var p1 := Pos('12',s);
   var p2 := Pos('222',s);
   while (p1 > 0) or (p2 > 0) do begin
     if p1 > 0 then begin
       Delete( s, p1, 2 );
       Insert( '2', s, p1 );
     end
     else begin
       Delete( s, p2, 3 );
       Insert( '2', s, p2 );
     end;
     p1 := Pos('12',s);
     p2 := Pos('222',s);
   end; 
   write(s);
end.

s = 71*'1122'
while "12" in s or "222" in s:
  if "12" in s:
    s = s.replace( "12", "2", 1 )
  else:
    s = s.replace( "222", "2", 1 )
print(s)

#include<iostream>
using namespace std;
int main()
{
   string s(71, '1122'); 
   cout << s << endl;
   int p1 = s.find("12");
   int p2 = s.find("222");
   while( p1 != string::npos or p2 != string::npos ) {
      if( p1 != string::npos ) 
        s.replace( p1, 12, "2" );  
      else 
        s.replace( p2, 222, "2" );  
      p1 = s.find("12");
      p2 = s.find("222");
      cout << s << endl;
      }
   cout << s;
}

• Рассмотрим алгоритм: редактор будет выполнять команды только тогда, когда в строке встречается цепочка «99» или цепочка «777»;
• если в строке есть «777», то тогда эта цепочка заменяется на «9»;
• если в строке нет цепочки «777», но есть «99», то цепочка «99» заменяется на «7».
• Теперь вернемся к условию нашей задачи. Условие цикла истинно, условие ЕСЛИ нашлось 777 тоже истинно, делаем замену:
• сколько раз можно заменить в 200 семерках три семерки на одну девятку? 200 делим на 3 получаем 66 замен, т.е. 66 цифр «9» + 2 семерки в остатке;

777 777 ... 777 77
получили:
9...9   77
  ↓
  66

• После выполнения этих преобразований условие ЕСЛИ нашлось 777 ложно. Значит, выполняется блок ИНАЧЕ: Заменить 99 на 7:
• [66 цифр «9»] + «77» -> «7» + [64 цифры «9»] + «77»:

    66 цифр
99 999...999 77
 ↓
 7  999...999 77
     64 цифры

• «7» + [64 цифры «9»] + «77» -> «7» + «7» + [62 цифры «9»] + «77»:

    64 цифры
799 999...999 77
 ↓
77   999...999 77
       62 цифры

• «77» + [62 цифры «9»] + «77» -> «7» + «77» + [60 цифр «9»] + «77»:

     62 цифры
7799 999...999 77
  ↓
777  999...999 77
        60 цифр

• Затем условие ЕСЛИ нашлось 777 опять становится истинным. Выполняется команда Заменить 777 на 9:

      60 цифр
777 999...999  77
 ↓
 9   999...999 77
      61 цифра

• Вернулись к той же «картине», что и после первого пункта. За эти шаги произошли преобразования, заменившие 66 девяток на 61 девятку, т.е. количество цифр «9» уменьшилось на 5 раз, а две цифры «77» так и остались в конце общей цепочки.
• Чтобы рассчитать итоговое количество цифр «9», необходимо понять, сколько раз можно вычитать из 61 по 5 девяток:

61 : 5 = 12 раз 
12 раз возможно отнять по 5 девяток и 1 девятка останется "в остатке" 

• Таким образом, после выполнения алгоритма, остается одна цифра «9» (в остатке) и в конце так и останутся две семерки: 977.

✎ Решение 1. С программированием:
Паскаль abc.net:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18

begin var s := '3'*90 + '1'; var p1 := Pos('331',s); var p2 := Pos('166',s); while (p1 > 0) or (p2 > 0) do begin if p1 > 0 then begin Delete( s, p1, 3 ); Insert( '16', s, p1 ); end else begin Delete( s, p2, 3 ); Insert( '31', s, p2 ); end; p1 := Pos('331',s); p2 := Pos('166',s); end; write(s); end.

begin var s := '3'*90 + '1'; var p1 := Pos('331',s); var p2 := Pos('166',s); while (p1 > 0) or (p2 > 0) do begin if p1 > 0 then begin Delete( s, p1, 3 ); Insert( '16', s, p1 ); end else begin Delete( s, p2, 3 ); Insert( '31', s, p2 ); end; p1 := Pos('331',s); p2 := Pos('166',s); end; write(s); end.

Бейсик:

Python: s = 90*'3'+'1' while "331" in s or "166" in s: if "331" in s: s = s.replace( "331", "16", 1 ) else: s = s.replace( "166", "31", 1 ) print(s) s = 90*'3'+'1' while "331" in s or "166" in s: if "331" in s: s = s.replace( "331", "16", 1 ) else: s = s.replace( "166", "31", 1 ) print(s)

С++: #include<iostream> using namespace std; int main() { string s(90, '3'); s+='1'; cout << s << endl; int p1 = s.find("331"); int p2 = s.find("166"); while( p1 != string::npos or p2 != string::npos ) { if( p1 != string::npos ) s.replace( p1, 331, "16" ); else s.replace( p2, 166, "31" ); p1 = s.find("331"); p2 = s.find("166"); cout << s << endl; } cout << s; } #include<iostream> using namespace std; int main() { string s(90, '3'); s+='1'; cout << s << endl; int p1 = s.find("331"); int p2 = s.find("166"); while( p1 != string::npos or p2 != string::npos ) { if( p1 != string::npos ) s.replace( p1, 331, "16" ); else s.replace( p2, 166, "31" ); p1 = s.find("331"); p2 = s.find("166"); cout << s << endl; } cout << s; }

• Выполним несколько итераций цикла ПОКА. Когда мы получим ту же самую последовательность цифр пять, за исключением их количества — остановимся:

5..5
500шт 

1: Работает блок ИНАЧЕ (555->3):
35..5
 497шт

2: Работает блок ИНАЧЕ (555->3):
335..5
  494шт

3: Работает блок ИНАЧЕ(555->3):
3335..5
   491шт

4: Работает блок ЕСЛИ (333->5):
5..5
492шт

• Остановились, так как мы пришли к исходной последовательности цифр пять. Проанализируем действия программы за этот фрагмент выполнения: было удалено 9 пятерок и одна пятерка добавилась. Ключевой вывод: было удалено 9 пятерок.
• Всего за выполнение этого фрагмента программы «ушло» 8 пятерок: 500 - 492 = 8. Посчитаем, сколько раз можно выполнить данный фрагмент:

500 : 8 = 62 и 4 в остатке

• Т.е. 62 раза выполняется данный фрагмент и 4 цифр 5 еще остается (остаток = 4). Поскольку за одно выполнение фрагмента было удалено 9 цифр 5, посчитаем, сколько удалится за 62 выполнения:

62 * 9 = 558

• 558 цифр 5 было удалено. Посмотрим выполнение программы над оставшимися 4 цифрами 5:

Работает блок ИНАЧЕ(555->3):
5555 = 35
 

• Итого получаем удаленных цифр 5:

558 + 3 = 561

✎ Решение 2. С программированием:
Паскаль abc.net:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

begin
   var k:= 0;
   var s := '5'*500 ;
   var p1 := Pos('555',s);
   var p2 := Pos('333',s);
   while (p1 > 0) or (p2 > 0) do begin
     if p2 > 0 then begin
       Delete( s, p2, 3 );
       Insert( '5', s, p2 );
     end
     else begin
       Delete( s, p1, 3 );
       Insert( '3', s, p1 );
       inc(k,3);
     end;
     p1 := Pos('555',s);
     p2 := Pos('333',s);
   end; 
   write(k);
end.

s = 500*'5'
k=0
while "555" in s or "333" in s:
  if "333" in s:
    s = s.replace( "333", "5", 1 )
  else:
    s = s.replace( "555", "3", 1 )
    k+=3;
print(k)

#include<iostream>
using namespace std;
int main()
{
   string s(500, '5');
   int k = 0; 
   cout << s << endl;
   int p1 = s.find("555");
   int p2 = s.find("333");
   while( p1 != string::npos or p2 != string::npos ) {
      if( p2 != string::npos ) 
        s.replace( p2, 333, "5" );  
      else  
        {
        s.replace( p1, 555, "3" );  
        k+=2;
        }
      p1 = s.find("555");
      p2 = s.find("333");
      cout << s << endl;
      }
   cout << k;
}

• Рассмотрим тело внешнего цикла и операторы, которые в нем находятся:
• 1. В цикле выполняется проверка ЕСЛИ справа свободно ТО вправо: что означает движение на один шаг вправо (если это возможно)
• 2. Затем располагается цикл с условием пока снизу свободно вниз: что означает движение до конца вниз (пока это возможно)
• После чего внешний цикл повторяется.
• Таким образом, отметим «тупиковые» клетки, т.е. те, которые не позволят двигаться роботу к цели:

A5, A6, B1, B2, B6, C1, C2, D1, D2, D3, D4, D5, E3, E4, E5

• Таких клеток получилось 15. Вычислим подходящие клетки (всего клеток 36):

36 - 15 = 21