Решу егэ 510705

✎ Решение 1. Теоретическое:

• Рассмотрим алгоритм: редактор будет выполнять команды только тогда, когда в строке встречается цепочка «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 

1
2
3
4
5
6
7
8
9
10
11

begin
  var s := '123' * 40;
  while ('12' in s) or ('333' in s) do
  begin
    if '12' in s then
      s := s.Replace('12', '3', 1)
      else
      s := s.Replace('333', '3', 1);
  end; 
  print(s);
end.

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;
}

✎ Решение 1. Теоретическое:

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

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. Программное:
Pascalabc.net:

1
2
3
4
5
6
7
8
9
10
11

begin
  var s := '1122' * 71;
  while ('12' in s) or ('222' in s) do
  begin
    if '12' in s then
      s := s.Replace('12', '2', 1)
      else
      s := s.Replace('222', '2', 1);
  end; 
  print(s);
end.

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. Программное:
Pascalabc.net:

1 2 3 4 5 6 7 8 9 10 11

begin var s := '3' * 90 + '1'; while ('331' in s) or ('166' in s) do begin if '331' in s then s := s.Replace('331', '16', 1) else s := s.Replace('166', '31', 1); end; print(s); end.

Pascal (традиционный): 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)
С++: #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; }

✎ Решение 1. Теоретическое:

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

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. Программное:
Pascalabc.net:

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

begin
  var s := '5' * 500;
  var k := 0;
  while ('555' in s) or ('333' in s) do
  begin
    if '333' in s then
      s := s.Replace('333', '5', 1)
      else
    begin
      s := s.Replace('555', '3', 1);
      k += 3;
    end;
  end; 
  print(k);
end.

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. Программное:
Pascalabc.net:

1 2 3 4 5 6 7 8 9 10 11 12 13

begin var s := '5' * 200; while ('555' in s) or ('333' in s) do begin if '555' in s then s := s.Replace('555', '3', 1) else s := s.Replace('333', '5', 1) end; println(s); var sum := s.CountOf('5') * 5 + s.CountOf('3') * 3; print(sum) end.

Pascal (традиционный):
Python:	С++:

✎ Решение 1. Программное:

Pascalabc.net:

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

begin
  var s := '>' + '1' * 10 + '2' * 20 + '3' * 30;
  var k := 0;
  while ('>1' in s) or ('>2' in s) or ('>3' in s) do
  begin
    if '>1' in s then
      s := s.Replace('>1', '22>', 1);
    if '>2' in s then
      s := s.Replace('>2', '2>', 1);
    if '>3' in s then
      s := s.Replace('>3', '1>', 1);
  end; 
  var sum := s.CountOf('1') + s.CountOf('2') * 2 + s.CountOf('3') * 3;
  {или так:
   var sum: integer;
   for var i := 1 to s.Count do
   if (s[i]='1') or (s[i]='2') or(s[i]='3') then
      sum:=sum + StrToInt(s[i]);
  }
print(sum)
end.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

begin
  var s := '>' + '1' * 10 + '2' * 20 + '3' * 30;
  var p1 := pos('>1', s);
  var p2 := pos('>2', s);
  var p3 := pos('>3', s);
  while (p1 <> 0) or (p2 <> 0) or (p3 <> 0) do
  begin
    if p1 <> 0 then
    begin
      delete(s, p1, 2);
      insert('22>', s, p1)
    end;
    if p2 <> 0 then
    begin
      delete(s, p2, 2);
      insert('2>', s, p2)
    end;
    if p3 <> 0 then
    begin
      delete(s, p3, 2);
      insert('1>', s, p3)
    end;
    p1 := pos('>1', s);
    p2 := pos('>2', s);
    p3 := pos('>3', s);
  end;
  println(s);
  var sum : integer;
  for var i := 1 to s.Count do
     sum := s.CountOf('1') + s.CountOf('2') * 2 + s.CountOf('3') * 3;
  {или так:
   if (s[i]='1') or (s[i]='2') or(s[i]='3') then
      sum:=sum + StrToInt(s[i]);
  }
  print(sum)
end.

✎ Решение 1. Программное:
PascalABC.net:

1 2 3 4 5 6 7 8 9 10 11

begin var s := '1' + '2' * 51; while ('12' in s) or ('1' in s) do begin if '12' in s then s := s.Replace('12', '2221', 1) else s := s.Replace('1', '222222', 1); end; print(s.CountOf('2')) end.

Pascal (традиционный): 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 begin var s := '1' + '2' * 51; var p1 := pos('12', s); var p2 := pos('1', s); while (p1 <> 0) or (p2 <> 0) do begin if p1 <> 0 then begin delete(s, p1, 2); insert('2221', s, p1) end else begin delete(s, p2, 1); insert('222222', s, p2) end; p1 := pos('12', s); p2 := pos('1', s); end; print(s.CountOf('2')) end.
Python:	С++:

✎ Решение 1. Программное:

PascalABC.net: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 begin for var n1 := 1 to 50 do for var n2 := 1 to 50 do for var n3 := 1 to 50 do begin // зададим исходную строку var s := '0' + n1 * '1' + n2 * '2' + n3 * '3'; // начинаем цикл перебора и замены while ('01' in s) or ('02' in s) or ('03' in s) do begin s := s.replace('01', '30', 1); s := s.replace('02', '3103', 1); s := s.replace('03', '1201', 1); end; // выведем результат, удовлетворяющий условию задачи (с - количество "3" в исходной строке) if (s.countOf('1') = 31) and (s.countOf('2') = 24) and (s.countOf('3') = 46) then begin print(n3); exit; end; end; end.

Python: for n1 in range(50): for n2 in range(50): for n3 in range(50): # зададим исходную строку s = '0' + n1*'1' + n2*'2' + n3*'3' # начинаем цикл перебора и замены while ('01' in s) or ('02' in s) or ('03' in s): s = s.replace('01','30',1) s = s.replace('02','3103',1) s = s.replace('03','1201',1) # выведем результат, удовлетворяющий условию задачи (с - количество "3" в исходной строке) if s.count('1') == 31 and s.count('2') == 24 and s.count('3') == 46: print(n1) exit()

Pascal(2 способ, традиционный):

Исполнитель Редактор получает на вход строку цифр и преобразовывает её. Редактор может выполнять две команды, в обеих командах v и w обозначают цепочки символов.

заменить (v, w) 
нашлось (v)

Первая команда заменяет в строке первое слева вхождение цепочки v на цепочку w. Если цепочки v в строке нет, эта команда не изменяет строку. Вторая команда проверяет, встречается ли цепочка v в строке исполнителя Редактор.

✎ Решение 1. Программное:
PascalABC.net:

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

begin for var i := 301 to 1000 do begin var s := '5' * i; while ('555' in s) or ('888' in s) do begin s := s.Replace('555', '8', 1); s := s.Replace('888', '55', 1); end; if (s.countOf('5') = 1) and (s.countOf('8') = 1) then begin print(i); break; end end; end.

Pascal (традиционный): 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 begin for var i := 301 to 1000 do begin var s := '5' * i; var p1 := pos('555', s); var p2 := pos('888', s); while (p1 <> 0) or (p2 <> 0) do begin if p1 <> 0 then begin delete(s, p1, 3); insert('8', s, p1); end; p2 := pos('888', s); // обязательно! if p2 <> 0 then begin delete(s, p2, 3); insert('55', s, p2); end; p1 := pos('555', s); p2 := pos('888', s); end; if (s.countOf('5') = 1) and (s.countOf('8') = 1) then begin print(i); break; end end; end.

Python:

С++:

Исполнитель Редактор получает на вход строку цифр и преобразовывает её. Редактор может выполнять две команды, в обеих командах v и w обозначают цепочки символов.

заменить (v, w) 
нашлось (v)

Первая команда заменяет в строке первое слева вхождение цепочки v на цепочку w. Если цепочки v в строке нет, эта команда не изменяет строку. Вторая команда проверяет, встречается ли цепочка v в строке исполнителя Редактор.

✎ Решение 1. Программное:

PascalABC.net (1 способ): 1 2 3 4 5 6 7 8 9 10 11 12 13 begin for var i := 1 to 100 do begin var s := '3' * i; while '333' in s do begin s := s.Replace('333', '4', 1); s := s.Replace('4444', '3', 1); if (s = '43') then print(i); end; end; end. Вывод: 4 15 26 37 48 59 70 81 92

Python: for i in range(1,100): s="3"*i while "333" in s: s=s.replace("333","4",1) s=s.replace("4444","3",1) if s=="43": print(i) Вывод: 4 15 26 37 48 59 70 81 92

Pascal(2 способ, традиционный): 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 begin for var i := 1 to 100 do begin var s:= '3' * i; var p1 := pos('333', s); var p2 := pos('4444', s); while p1 <> 0 do begin if p1 <> 0 then begin delete(s, p1, 3); insert('4', s, p1); end; p2 := pos('4444', s); // обязательно! if p2 <> 0 then begin delete(s, p2, 4); insert('3', s, p2); end; p1 := pos('333', s); p2 := pos('4444', s); if (s = '43') then begin print(i); end end; end; end.

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

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

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

36 - 15 = 21

Например, если Чертёжник находится в точке с координатами (4, 2), то команда сместиться на (2, −3) переместит Чертёжника в точку (6, −1).

 
Цикл

ПОВТОРИ число РАЗ
последовательность команд
КОНЕЦ ПОВТОРИ

означает, что последовательность команд будет выполнена указанное число раз (число должно быть натуральным).