Как найти количество подцепочек

Как найти количество подцепочек

Get it on Apple Store

Get it on Google Play

Public user contributions licensed under
cc-wiki license with attribution required

Skolkovo resident

Источник

Информатика. ЕГЭ

Задания для подготовки

Задачи разных лет из реальных экзаменов, демо-вариантов, сборников задач и других источников

  • 2
  • 14
  • 16
  • 17
  • 18
  • 19
  • 23
  • 24
  • 25
  • 26
  • 27

Задание 24. Информатика. Фоксфорд-2

Текстовый файл содержит только заглавные буквы латинского алфавита ( (ABCldots Z)). Определите количество цепочек, состоящих из пяти символов вида ( AA*BB), в которой на месте (*) может стоять любая буква. В ответе запишите количество таких цепочек, затем укажите букву, которая чаще всего встречается на месте (*). Если таких букв несколько, то укажите ту, которая в алфавите стоит дальше.

Файл с данными

Показать решение…

Задание 24. Информатика. Фоксфорд-3

Текстовый файл содержит только заглавные буквы латинского алфавита ( (ABCldots Z)). Определите количество цепочек, состоящих из пяти символов, в которых символы стоят в неубывающем алфавитном порядке. (Например, (FGPSZ), (AAAAA), (CCMMM)). В ответе укажите количество таких цепочек и порядковый номер первого символа последней найденной цепочки.

Файл с данными

Показать решение…

Задание 24. Информатика. Фоксфорд-4

Текстовый файл содержит строки различной длины. Строки содержат только заглавные буквы латинского алфавита ( (ABCldots Z)). Необходимо найти строку, в которой буква (A) встречается чаще, чем в других строках, но при этом в этой строке отсутствуют буквы (X), (Y) и (Z). Если таких строк несколько, надо взять ту, которая находится в файле раньше. В ответе записать без пробела первый и последний символы найденной строки.

Файл с данными

Показать решение…

Задание 24. Информатика. Фоксфорд-5

Текстовый файл содержит только заглавные буквы латинского алфавита ((ABCldots Z)). Найдите максимальную длину цепочки вида (GIAGIAGIAGIldots) (последний фрагмент (GIA) может быть неполным).

Файл с данными

Показать решение…

Задание 24. Информатика. Фоксфорд-6

Текстовый файл содержит только заглавные буквы латинского алфавита ( (ABC ldots Z)). Найдите количество подцепочек длиной 2022, в которых количество букв (A) и (Z) одинаково.

Файл с данными

Показать решение…

Источник

На уроке рассмотрен материал для подготовки к ЕГЭ по информатике, разбор 24 задания. Объясняется тема о программной обработке символьной информации.

Содержание:

  • ЕГЭ по информатике 24 задание объяснение
  • Выполнение 24 задания ЕГЭ
    • Последовательности (цепочки) символов
    • Работа с числами (цифрами) в текстовом файле
    • Работа с отдельными строками файла

24-е задание: «Программная обработка символьной информации»

Уровень сложности

— повышенный,

Требуется использование специализированного программного обеспечения

— нет,

Максимальный балл

— 1,

Примерное время выполнения

— 8 минут.

  
Проверяемые элементы содержания: Умение создавать собственные программы (10–20 строк) для обработки символьной информации

Выполнение 24 задания ЕГЭ

Плейлист видеоразборов задания на YouTube:

Задание демонстрационного варианта 2022 года ФИПИ

Последовательности (цепочки) символов

24_1: Демоверсия варианта ЕГЭ по информатике 2021, ФИПИ:

  

Задание выполняется с использованием прилагаемых файлов

 
Текстовый файл состоит не более чем из 106 символов X, Y и Z.
Определите максимальное количество идущих подряд символов, среди которых каждые два соседних различны.
Для выполнения этого задания следует написать программу.

Ответ: 35
✍ Решение:

    Паскаль:

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

    var
  f: text;
  i, k, max: integer;
  s: string;
 
begin
  assign(f, 'D:24.txt');
  reset(f);
  readln(f, s);
  max := 1;
  k := 1; // кол-во подряд идущих
  for i := 2 to length(s) do
  begin
    if s[i] <> s[i - 1] then
    begin
      inc(k);
      if k > max then max := k;
    end
    else k := 1;
  end;
  write(max)
end.

    Python:

    1
2
3
4
5
6
7
8
9
10
11

    f=open('D:/24.txt')
s=f.readline()
m=1
k=1
for i in range(1,len(s)):
    if s[i]!=s[i-1]:
        k+=1
        m=max(k,m)
    else:
        k=1
print(m)

📹 Видеоразбор:
📹 YouTube здесь

📹 Видеорешение на RuTube здесь

24_2:

Задание выполняется с использованием прилагаемых файлов

 
В текстовом файле (выше по ссылке) находится цепочка из символов латинского алфавита A, B, C.

Найдите длину самой длинной подцепочки, состоящей из символов C.

Ответ: 0

✍ Решение:

    PascalABC.net:

    1
2
3
4
5
6
7
8
9
10

    begin
  assign(input, 'k7-0.txt');
  var s: string;
  var c: string;
  read(s);
  c := 'C';
  while c in s do
    c := c + 'C';
  print(length(c) - 1)
end.

    Python:
    способ 1:

    1
2
3
4
5
6
7
8

    with open("k7-0.txt") as Fin:
  s = Fin.readline()
 
c = 'C'
while c in s: # ищем CC, потом CCC и т.д
  c += 'C'
print(len(c)-1 )
# минус 1, чтобы убрать лишнюю (последнюю добавленную С)

    способ 2:

    1
2
3
4
5
6
7
8
9
10
11

    f=open('k7-0.txt')
s = f.readline() # считали строку
m = 0 # макс длина цепочки
l = 0 # начальная длина цепочки
for i in range(0,len(s)):
    if s[i]=='C':
        l+=1
        m = max(l,m) # перезаписали Макс длину
    else:
        l = 0 #  сбрасываем счетчик
print(m)

24_3:

Задание выполняется с использованием прилагаемых файлов

 
В текстовом файле (выше по ссылке) находится цепочка из символов латинского алфавита A, B, C, D, E.

Найдите длину самой длинной подцепочки, состоящей из символов A, B или C (в произвольном порядке).

Ответ: 16

✍ Решение:

    PascalABC.net:

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

    begin
  assign(input, 'k7a-1.txt');
  var s: string;
  read(s);
  var k := 0;
  var maxim := 0;
  for var i := 1 to length(s) do
    if s[i] in 'ABC' then
    begin
      k += 1;
      if k > maxim then maxim := k
    end
    else k := 0 ;
  write(maxim)
end.

    Python:

    1
2
3
4
5
6
7
8
9
10
11

    f = open('k7a-1.txt')
s = f.readline() # считали строку
m = 0 # макс длина цепочки из "A,B,С"
l = 0 # начальная длина цепочки из "A,B,С"
for i in range(0,len(s)):
    if s[i] in'ABC':
        l+=1
        m = max(l,m) # перезаписали Макс длину
    else:
        l = 0 # другая буква - сбрасываем счетчик
print(m)

24_4:

Задание выполняется с использованием прилагаемых файлов

 
В текстовом файле (по ссылке выше) находится цепочка из символов латинского алфавита A, B, C, D, E, F.

Найдите длину самой длинной подцепочки, не содержащей гласных букв.

Ответ: 20

✍ Решение:

    PascalABC.net:
    Вариант 1:

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

    begin
  assign(input, 'k7a-6.txt');
  var s: string;
  read(s);
  var k := 0;
  var maxim := 0;
  for var i := 1 to length(s) do
    if s[i] in 'BCDF' then
    begin
      k += 1;
      if k > maxim then maxim := k
    end
    else k := 0 ;
  write(maxim)
end.

    Вариант 2:

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

    begin
  var s := readAllText('d:k7a-6.txt').Trim;
  var (k, max) := (0, 0);
  foreach var c in s do 
    if not (c in 'AE') then
    begin
      k += 1;
      if k > max then max := k;
    end else
      k := 0;
  print(max)
end.

    Python:

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

    with open("k7a-6.txt") as F:
  s = F.readline() # считали строку
 
k = 0 # начальная длина цепочки из "B,C,D,F"
Max = 0 # макс длина цепочки из "B,C,D,F"
for c in s:
  if c in 'BCDF':
    k += 1
    if k > Max:
      Max = k # перезаписали Макс длину
  else:
      k = 0 # другая буква - сбрасываем счетчик
print(Max)

24_5:

Задание выполняется с использованием прилагаемых файлов

 
В текстовом файле (по ссылке выше) находится цепочка из символов латинского алфавита A, B, C, D, E.

Найдите максимальную длину цепочки вида EABEABEABE… (состоящей из фрагментов EAB, последний фрагмент может быть неполным).

Ответ: 7
✍ Решение:

    PascalABC.net:

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

    begin
  assign(input, 'k7b-1.txt');
  var s: string;
  read(s);
  var c := 'EAB';
  while c in s do
  begin
    if c[length(c)] = 'B' then
      c += 'E'
    else if c[length(c)] = 'A' then
      c += 'B'
    else if c[length(c)] = 'E' then
      c += 'A';
  end;
  print(length(c) - 1)
end.

    Python:
    Способ 1:

    1
2
3
4
5
6
7
8
9

    with open("k7b-1.txt") as Fin:
  s = Fin.readline()
 
c = 'EAB'
while c in s: # ищем EAB, потом EABE и т.д
    if c[-1]=="B": c +="E"
    elif c[-1]=="A": c +="B"
    elif c[-1]=="E": c +="A"
print(len(c)-1)

    Постоянно повторяется фрагмент EAB, поэтому возможны 3 варианта окончания строки:

  • 1 тип = ..EABE — неполный последний фрагмент
  • 2 тип = ..EABEB — неполный последний фрагмент
  • 3 тип = ..EAB — полный последний фрагмент

    • Способ 2:

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

    f=open('k7b-1.txt')
s = f.readline()
m = 0
i = 0
for char in s:
    if (char == 'E' and i%3 == 0) or 
       (char == 'A' and i%3 == 1) or 
       (char == 'B'and i%3 == 2): 
        i += 1
        m = max(i,m)
    elif char == 'E':
        i = 1
    else:
        i = 0
print(m)

24_6:

Задание выполняется с использованием прилагаемых файлов

 
В текстовом файле (по ссылке выше) находится цепочка из символов латинского алфавита A, B, C, D, E.
Найдите количество цепочек длины 3, удовлетворяющих следующим условиям:

  • 1-й символ – один из символов B, C или D;
  • 2-й символ – один из символов B, D, E, который не совпадает с первым;
  • 3-й символ – один из символов B, C, E, который не совпадает со вторым.

    • Ответ: 1280

    ✍ Решение:

      PascalABC.net:

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

      begin
  assign(input, 'k7c-1.txt');
  var s: string;
  read(s); // весь текст файла
  var k := 0;
  var c1 := 'BCD';
  var c2 := 'BDE';
  var c3 := 'BCE';
  for var i := 1 to length(s) - 2 do
  begin
    if (s[i] in c1) and (s[i + 1] in c2) and (s[i + 2] in c3)
    and (s[i] <> s[i + 1]) and (s[i + 1] <> s[i + 2]) then
      k += 1
  end;
  print(k)
end.

      Python:

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

      with open("k7c-1.txt") as Fin:
  s = Fin.readline()
 
k = 0
c1 = 'BCD'# строка проверки первого символа
c2 = 'BDE'# строка проверки второго символа
c3 = 'BCE'# строка проверки третьего символа
for i in range(len(s)-2):
    if s[i] in c1 and s[i+1] in c2 and s[i+2] in c3 
       and s[i]!=s[i+1] and s[i+1]!=s[i+2]: # проверка повтора символов
      k += 1
print(k)

    24_7:

    Задание выполняется с использованием прилагаемых файлов

     
    В текстовом файле (по ссылке выше) находится цепочка из символов, в которую могут входить заглавные буквы латинского алфавита A…Z и десятичные цифры. Найдите длину самой длинной подцепочки, состоящей из одинаковых символов. Если в файле несколько цепочек одинаковой длины, нужно взять первую из них. Выведите сначала символ, из которого строится эта подцепочка, а затем через пробел – длину этой подцепочки.

    Ответ: 2 3

    ✍ Решение:

      PascalABC.net:

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

      begin
  assign(input, 'D:/k8-0.txt');
  var s: string;
  read(s); // весь текст файла
  var k := 1; //длина текущей цепочки одинаковых символов 
  var max := 0; // макс длина цепочки одинаковых символов
  var c := s[1]; //символ, из которого строится самая длинная подцепочка
  for var i := 1 to length(s) - 1 do
  begin
    if s[i] = s[i + 1] then
    begin
      k += 1;
      if k > max then  
      begin
        max := k;
        c := s[i]; // запомнили новый символ
      end
    end
    else
      k := 1;
  end;
  print(c, max)
end.

      Python:

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

      f=open('k8-0.txt')
s=f.readline()
k=1
m=0
for i in range (1,len(s)):
    if s[i]==s[i-1] :
        k+=1
        if k>m:
            m=k
            symb=s[i]
    else:
        k=1
 
print(symb,m)

    📹 Видеоразбор:
    📹 YouTube здесь

    📹 Видеорешение на RuTube здесь

    24_8:

    Задание выполняется с использованием прилагаемых файлов

     
    Текстовый файл (по ссылке выше) содержит последовательность из строчных и заглавных букв английского алфавита и цифр, всего не более 106 символов. Определите длину наибольшей убывающей подпоследовательности.

    🎦 Видеоразбор

    Ответ: 3

    ✍ Решение:

      Общая идея:

    • В цикле сравнивается текущий элемент с предыдущим (цикл начинается со второго символа строки и заканчивается длиной строки). 
      •  for var i := 2 to length(s) do
  begin
    if s[i] < s[i - 1] then
    • Если текущий элемент меньше предыдущего, то последовательность убывает, — увеличиваем счетчик длины последовательности.
    • Начальное значение счетчика длины последовательности должно быть = 1, так как в цикле сравниваются два элемента, и при истинности условия в последовательность уже должна быть равна двум, а не единице (в случае если счетчик обнуляется).
    • Увеличивая счетчик, сразу же необходимо сравнивать его значение с максимумом, и выполнять переприсваивание максимума, если это требуется. 
      •  ...
     if k > max then  
          max := k;
    • В случае, если условие убывающей последовательности ложно, переходим в блок Иначе (else) и сбрасываем счетчик для работы со следующей последовательностью. Счетчик присваиваем единице!
    • После цикла выводим максимальное значение.

      • PascalABC.net:

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

      begin
  assign(input, 'D:/24.txt');
  var s: string;
  read(s); // весь текст файла
  var k := 1; //длина текущей бывающей последовательности символов 
  var max := 0; // макс длина
  for var i := 2 to length(s) do
  begin
    if s[i] < s[i - 1] then
    begin
      k += 1; // увеличиваем счетчик длины последовательности
      if k > max then  
        max := k;
    end
    else
      k := 1; // сбрасываем счетчик для работы со след. последовательностью
  end;
  print(max)
end.

      Python:

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

      F= open("24.txt") 
s = F.readline() # считали строку (весь текст файла в одной строке)
k = 1
maxim = 0
for i in range(1, len(s)):
      if s[i] < s[i - 1]:
          k += 1 # увеличиваем счетчик длины последовательности
          if k > maxim:
              maxim = k
      else:
          k = 1 # сбрасываем счетчик для работы со след. последовательностью
print(maxim)

    Работа с числами (цифрами) в текстовом файле

    24_8:

    Задание выполняется с использованием прилагаемых файлов

     
    Текстовый файл (по ссылке выше) состоит не более чем из 106 символов. Определите максимальное нечётное число, записанное в этом файле.

    🎦 Видеоразбор

    Ответ: 7642289

    ✍ Решение:

      PascalABC.net:

      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

      begin
  assign(input, '24-1.txt');
  var s: string;
  var b:integer;
  read(s); // весь текст файла находится в s
  var max := 0; // для максимального нечётного числа
  var num:integer;
  var strnum:string; // накапливает строковое представление числа
  strnum:='';
  for var i := 1 to length(s)-1 do
  begin
    if s[i].IsDigit() then // проверяем очередной символ - цифра ли это
      strnum += s[i] //добавляем очередную цифру в число
    else 
      if (strnum <> '') then //если встретилась не цифра, а strnum не пустая строка
        begin
        Val(strnum, num, b); // переводим в число
        if (num mod 2 <> 0) and (num > max) then // условие для поиска макс четного
          max := num;
        strnum:='';  // сбрасываем на начальное значение, чтобы накапливать новое число
        end;
  end;
  // проверка на случай, если самое большое нечётное в самом конце строки
  if (s[length(s)].isdigit()) then
    begin
    Val(strnum, num, b);
    if (num mod 2 <> 0) and (num > max) then
       max:= num;
    end;
print(max)
end.

      Python:

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

      F = open("24-1.txt")
s = F.readline() # считали строку
 
strnum = ''   #пустая строка,  strnum накапливает строковое представление числа
maxim = 0            # для максимального нечётного числа
for sym in s:
      if sym.isdigit(): # проверяем очередной символ - цифра ли это
          strnum += sym # добавляем очередную цифру в число
      elif strnum: # если встретилась не цифра, а strnum не пустая строка
          num = int(strnum) # переводим в число и сохраняем в num
          if num % 2 and num > maxim: # условие для поиска макс четного
              maxim = num
          strnum = '' # сбрасываем на начальное значение, чтобы накапливать новое число
  # проверка на случай, если самое большое нечётное в самом конце строки
if s[-1].isdigit():
   num = int(strnum)
   if num % 2 and num > maxim:
      maxim = num
print(maxim)

    Работа с отдельными строками файла

    24_9:

    Задание выполняется с использованием прилагаемых файлов

     
    Текстовый файл (по ссылке выше) состоит не более чем из 106 заглавных латинских букв (A..Z). Текст разбит на строки различной длины.
    Определите количество строк, в которых буква J встречается чаще, чем буква E.

    Ответ: 482

    ✍ Решение:

      Общая идея:

    • Так как текст разбит на строки, то используем бесконечный цикл для считывания каждой строки.
    • Если строка пустая (т.е. достигнут конец файла), используем досрочный выход из цикла (оператор break).
    • Для подсчета количества встреченных символов используем строковый метод count(), который возвращает количество найденных вхождений символа (или сочетания символов), заданного аргументом.

      • PascalABC.net:

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

      begin
  assign(input, '24-s1.txt');
  var s: string;
  var k := 0;
  while true do // бесконечный цикл
  begin
    readln(s); // считываем очередную строку
    if s = '' then break; // если строка пустая (т.е. достигнут конец файла), выходим
    if s.Count(c -> c = 'J') > s.Count(c -> c = 'E') then
      k += 1;
  end;
  print(k)
end.

      Python:

      1
2
3
4
5
6
7
8

      f= open("24-s1.txt")
k = 0 # счетчик строк 
while True: # бесконечный цикл
    s = f.readline() # считываем очередную строку
    if not s: break # если строка пустая (т.е. достигнут конец файла), выходим
    if s.count("J") > s.count("E"):
        k +=1
print(k)
    Источник

    №2 В текстовом файле k7-3.txt находится цепочка из символов латинского алфавита A, B, C. Найдите длину самой длинной подцепочки, состоящей из символов C.

    f=open(‘k7-3.txt’)

    s=f.readline()

    k=0

    m=0

    for i in range (0,len(s)):

    if s[i]==’C’:

    k=k+1

    if k>m: m=k

    else:

    k=0

    print (m)

    ответ 1

    №23 (А.М. Кабанов) В текстовом файле k7a-3.txt находится цепочка из символов латинского алфавита A, B, C, D, E, F. Найдите длину самой длинной подцепочки, состоящей из символов A, B, E, F (в произвольном порядке).

    f=open(‘k7a-3.txt’)

    s=f.readline()

    k=0

    m=0

    for i in range (0,len(s)):

    if s[i]==’A’ or s[i]==’B’ or s[i]==’E’ or s[i]==’F’:

    k=k+1

    if k>m: m=k

    else:

    k=0

    print (m)

    Ответ 20

    №25 (А.М. Кабанов) В текстовом файле k7a-5.txt находится цепочка из символов латинского алфавита A, B, C, D, E, F. Найдите длину самой длинной подцепочки, не содержащей символов C и F.

    f=open(‘k7a-5.txt’)

    s=f.readline()

    k=0

    m=0

    for i in range (0,len(s)):

    if s[i]!=’C’ and s[i]!=’F’:

    k=k+1

    if k>m: m=k

    else:

    k=0

    print (m)

    Ответ 19

    №28 (А.М. Кабанов) В текстовом файле k7b-2.txt находится цепочка из символов латинского алфавита A, B, C, D, E, F. Найдите максимальную длину цепочки вида DBACDBACDBAC…. (состоящей из фрагментов DBAC, последний фрагмент может быть неполным).

    f=open(‘k7b-2.txt’)

    s=f.readline()

    k=0

    m=0

    for i in range (0,len(s)):

    if (s[i]==’D’ and k%4==0) or (s[i]==’B’ and k%4==1) or (s[i]==’A’ and k%4==2)
    or (s[i]==’C’ and k%4==3):

    k=k+1

    if k>m: m=k

    else:

    if s[i]==’D’:

    k=1

    else:

    k=0

    print (m)

    Ответ 95

    №33 (А.М. Кабанов) В текстовом файле k7c-1.txt находится цепочка из символов латинского алфавита A, B, C, D, E. Найдите количество цепочек длины 3, удовлетворяющих следующим условиям:

    · 1-й символ – один из символов B, C или D;

    · 2-й символ – один из символов B, D, E, который не совпадает с первым;

    · 3-й символ – один из символов B, C, E, который не совпадает со вторым.

    f=open(‘k7c-1.txt’)

    s=f.readline()

    k=0

    for i in range (0,len(s)-2):

    if (s[i]==’B’ or s[i]==’C’ or s[i]==’D’) and ((s[i+1]==’B’ or s[i+1]==’D’ or
    s[i+1]==’E’) and s[i]!=s[i+1]) and ((s[i+2]==’B’ or s[i+2]==’C’ or s[i+2]==’E’)
    and s[i+1]!=s[i+2]):

    k=k+1

    print (k)

    ответ 1280

    №52 В текстовом файле k8-0.txt находится цепочка из символов, в которую могут входить заглавные буквы латинского алфавита A…Z и десятичные цифры. Найдите длину самой длинной подцепочки, состоящей из одинаковых символов. Если в файле несколько цепочек одинаковой длины, нужно взять первую из них. Выведите сначала символ, из которого строится эта подцепочка, а затем через пробел – длину этой подцепочки.

    f=open(‘k8-0.txt’)

    s=f.readline()

    k = 1

    m=0

    for i in range(len(s)-1):

    if s[i]==s[i+1]:

    k += 1

    if k>m:

    m=k

    d=s[i]

    else:

    k=1

    print(d,m)

    Ответ 2 3

    №72 В текстовом файле k8-0.txt находится цепочка из символов, в которую могут входить заглавные буквы латинского алфавита A…Z и десятичные цифры. Найдите длину самой длинной подцепочки, состоящей из одинаковых символов. Для каждой цепочки максимальной длины выведите в отдельной строке сначала символ, из которого строится эта цепочка, а затем через пробел – длину этой цепочки.

    f=open(‘k8-0.txt’)

    s=f.readline()

    k = 1

    m=0

    t1=[]

    t2=[]

    for i in range(len(s)-1):

    if s[i]==s[i+1]:

    k += 1

    else:

    t1.append(k)

    t2.append(s[i])

    k=1

    p=max(t1)

    for i in range(len(t1)):

    if t1[i]==p:

    print (t2[i],t1[i])

    Ответ

    2 3
    7 3
    7 3
    5 3

    №77 Текстовый файл k8-1.txt состоит не более чем из 106 символов. Определите максимальное количество идущих подряд символов, среди которых каждые два соседних различны.

    f=open(‘k8-1.txt’)

    s=f.readline()

    k = 1

    m=0

    for i in range(len(s)-1):

    if s[i]!=s[i+1]:

    k += 1

    if k>m: m=k

    else:

    k=1

    print (m)

    Ответ 159

    Источник

    Привет! Сегодня поговорим, как искать количество подпоследовательностей чисел в 27 задании.

    Мы уже рассматривали, как искать сумму и длину цепочек чисел, удовлетворяющих определённым условиям.

    Приступим к примерным задачам из 27 задания ЕГЭ по информатике на количество подпоследовательностей чисел.

    Задача (Количество подпоследовательностей)

    Дана последовательность натуральных чисел. Необходимо определить
    количество её непрерывных подпоследовательностей, сумма элементов
    которых кратна 13.

    Входные данные

    Первая строка входного файла содержит целое число N – общее количество
    чисел в наборе. Каждая из следующих N строк содержит одно число.
    Гарантируется, что общая сумма всех чисел и число в ответе не превышают 109.

    Вам даны два входных файла (A и B), каждый из которых имеет описанную
    выше структуру. В ответе укажите два числа: сначала искомое количество
    для файла A, затем – для файла B.

    Решение:

    Напишем программу на языке Python.

    f=open('27_9a.txt')
n=int(f.readline())

k_ost=[0]*13
k_ost[0]=1

k=0
s=0

for i in range(n):
    x=int(f.readline())
    s = s + x
    ost = s % 13
    k=k+k_ost[ost]
    k_ost[ost]=k_ost[ost]+1
    
print(k)

    Как всегда в подобных задачах начинаем суммировать каждый элемент последовательности в переменную s. На каждом шаге вычисляем остаток этой суммы от деления на 13.

    ЕГЭ по информатике - задание 27 (Количество подпоследовательностей)

    Когда мы первый раз получили некоторый остаток s%13, мы ещё не имеем такую цепочку чисел, сумма которой делится на 13. Поэтому и количество цепочек не меняется. Когда второй раз получили этот же конкретный остаток, то получается уже одна подпоследовательность чисел, которую нужно засчитать (об этом мы подробно говорили в этой статье).

    ЕГЭ по информатике - задание 27 (Количество подпоследовательностей 2)

    Если ещё раз получится такое значение s с этим же остатком, то добавляется столько цепочек, сколько раз уже встречался этот остаток до этого. На рисунке показано, что добавляются ещё две цепочки.

    Список k_ost хранит в себе количество значений s для всех остатков от деления на 13.

    Таким образом, при получение очередного остатка ost, мы прибавляем к счётчику k то значение k_ost[ost], которое было уже сформировано до этого. И прибавляем в ячейку k_ost[ost] единицу, чтобы учесть это значение s с конкретным остатком ost для последующих подсчётов.

    Для остатка ноль в список k_ost кладём в начале 1, т.к. при получении первого значение s, где s%13==0, мы получаем уже одну нужную цепочку автоматически.

    Ответ:

    Задача (Наложено два условия)

    Дана последовательность натуральных чисел. Необходимо определить
    количество её непрерывных подпоследовательностей, сумма элементов
    которых кратна 21, а количество чисел, оканчивающихся на 9, кратно 5.

    Входные данные

    Первая строка входного файла содержит целое число N – общее количество
    чисел в наборе. Каждая из следующих N строк содержит одно число.
    Гарантируется, что общая сумма всех чисел и число в ответе не превышают 109.

    Вам даны два входных файла (A и B), каждый из которых имеет описанную
    выше структуру. В ответе укажите два числа: сначала искомое количество
    для файла A, затем – для файла B.

    Решение:

    Чтобы понимать эту задачу, нужно хорошо ознакомится с задачей “Количество особых чисел кратно K” из этой статьи.

    Здесь на цепочки чисел налагается два условия: с одной стороны сумма элементов должна быть кратна 21, а с другой, количество чисел, оканчивающихся на 9, должно быть кратно 5.

    Здесь нужно “отрезать” хвостик, который соответствует двум условиям одновременно.

    Заведём двумерный список k_ost. Как раз он позволяет сохранять одно значение, которое соответствует двум параметрам.

    ЕГЭ по информатике демоверсия 2023 - задание 26 (двумерный список)

    Как и в прошлой задаче будем хранить в этом списке количество значений s, которое уже встречалось до этого момента, для параметров s%21 и count%5, где s, как всегда, сумма от 0-ого до i-ого элемента, а count – это количество чисел, оканчивающихся на 9, на данный момент времени.

    f=open('27_10b.txt')
n=int(f.readline())

# Заводим двумерный список 21 на 5
k_ost=[0]*21
for i in range(21):
    k_ost[i]=[0]*5

k_ost[0][0]=1

k=0
s=0
count=0

for i in range(n):
    x=int(f.readline())
    s = s + x

    if x%10==9: count=count+1
    
    k=k+k_ost[s % 21][count % 5]
    k_ost[s % 21][count % 5]=k_ost[s % 21][count % 5]+1
    
print(k)

    Для начального значения, когда count%5=0 и s%21=0, кладём в список k_ost единицу, аналогично предыдущей задаче.

    С помощью ввода двумерного массива, можно аналогично найти цепочку и с максимальной суммой.

    Ответ:

    Задача (Длина подпоследовательности не менее 7)

    Дана последовательность натуральных чисел. Рассматриваются все её непрерывные подпоследовательности длиной не менее 7 чисел, такие что сумма чисел каждой из них кратна 30. Найдите количество таких подпоследовательностей.

    Входные данные

    Первая строка входного файла содержит целое число N – общее количество
    чисел в наборе. Каждая из следующих N строк содержит одно число.
    Гарантируется, что общая сумма всех чисел и число в ответе не превышают 109.

    Вам даны два входных файла (A и B), каждый из которых имеет описанную
    выше структуру. В ответе укажите два числа: сначала искомое количество
    для файла A, затем – для файла B.

    Решение: 

    f=open('27_11b.txt')
n=int(f.readline())
q=[]
s=0
for i in range(6):
    x=int(f.readline())
    s=s+x
    q.append(s)

k_ost = [0]*30
k_ost[0] = 1
k=0

for i in range(n-6):
    x=int(f.readline())
    s=s+x

    k=k+k_ost[s%30]
    
    k_ost[q[0]%30] = k_ost[q[0]%30] + 1

    q.pop(0)
    q.append(s)

print(k)

    Как мы говорили, чтобы найти количество подпоследовательностей, нужно для каждого остатка s%30 знать, а сколько таких значений s с этим же остатком было до этого.

    Но здесь нельзя подсчитывать цепочки, которые по длине меньше 7. Т.е. нельзя брать во внимание те значения s, которые получились совсем недавно, на предыдущих 6 шагах.

    Чтобы это реализовать, заводится список q. Он играет роль буфера. В нём сохраняем 7 значений s, которые получаются на последних 7 шагах.

    На каждом шаге мы обрабатываем ячейку q[0], добавляя в список k_ost единицу для соответствующего остатка, как бы с задержкой в 6 шагов.

    Таким образом, у нас не будут учитываться цепочки, длина которых меньше 7 элементов.

    На каждом шаге мы удаляем первый элемент из списка q, и добавляем новое значение s, чтобы в этом списке были значения s последних семи шагов.

    Ответ:

    Источник

    Добавить комментарий