Решение задач полякова информатика егэ

Задание 1:

На рисунке справа схема дорог Н-ского района изображена в виде графа, в таблице содержатся сведения о длинах этих дорог (в километрах).

Так как таблицу и схему рисовали независимо друг от друга, то нумерация населённых пунктов в таблице никак не связана с буквенными обозначениями на графе.
Определите длину кратчайшего пути из пункта Г в пункт В.

Задание 2:

Логическая функция F задаётся выражением

(x ≡ ¬z) → ((x ∨ w) ≡ y)

На рисунке приведён частично заполненный фрагмент таблицы истинности функции F, содержащий неповторяющиеся строки.
Определите, какому столбцу таблицы истинности функции F соответствует каждая из переменных x, y, z, w.

Программирование:

PascalABC.net:

Python: 1 2 3 4 5 6 7 8 print('x y z w') for x in 0, 1: for y in 0, 1: for z in 0, 1: for w in 0, 1: F = (x == (not z)) <= ((x or w)==y) if not F: print(x, y, z, w)

С++:

Ответ: xwyz

Задание 3:

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

Задание 4:

По каналу связи передаются сообщения, содержащие только семь букв: А, Б, К, О, Н, Р, Я. Для передачи используется двоичный код, удовлетворяющий условию Фано. Кодовые слова для некоторых букв известны:

А – 010, 
Р – 011, 
Я – 10 

Какое наименьшее количество двоичных знаков потребуется для кодирования слова КОРАН?

• Отобразим с помощью дерева известные коды:



• Остается расположить 4 кода. Поскольку в слове КОРАН все буквы встречаются по одному разу, то расположение букв на дереве не так важно. Но буква Б не встречается, поэтому ее можно располагать в дереве на нижние уровни:



• Посчитаем количество бит в каждой букве слова:

К(3) + О(4) + Р(3) + А(3) + Н(2) = 15

Ответ: 15

Задание 5:

На вход алгоритма подаётся натуральное число N. Алгоритм строит по нему новое число R следующим образом.

1) Строится двоичная запись числа N.
2) Затем справа дописываются два разряда: символы 01, если число N чётное, и 10, если нечётное.
Полученная таким образом запись (в ней на два разряда больше, чем в записи исходного числа N) является двоичной записью искомого числа R.

Укажите минимальное число R, большее 81, которое может являться результатом работы этого алгоритма. В ответе это число запишите в десятичной системе.

• Будем переводить числа в 2-ю с.с., начиная с 82, и рассматривать их на соответствие алгоритму:

82 = 01010010 - N четное, должно было добавиться 01
83 = 01010011 - в конце не может быть "11"
84 = 01010100 - в конце не может быть "00"
85 = 01010101 - N нечетное, должно было добавиться 10
86 = 01010110 - N нечетное, все верно!

Ответ: 86

Задание 6 (А.Г. Минак):

Определите, при каком наименьшем целом введённом значении переменной d программа выведет число 192.

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

var s, n, d: integer;
begin
  readln (d);
  s := 0;
  n := 0;
  while n < 200 do
  begin
    s := s + 64;
    n := n + d
  end;
  writeln(s)
end.

1
2
3
4
5
6
7

d = int(input())
s = 0
n = 0
while n < 200:
  s = s + 64
  n = n + d
print(s)

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

#include <iostream>
using namespace std;
int main() { 
int d, s = 0, n = 0;
cin >> d;    
while (n < 200) {
  s = s + 64;
  n = n + d;
  }
cout << s << endl;
return 0;
}

Программирование:

PascalABC.net:

Python: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 d = 1 while True: # внешний цикл, бесконечный d1 = d # --- код из условия задания --- s = 0 n = 0 while n < 200: s = s + 64 n = n + d1 # --- конец кода из условия задания --- if s == 192: print(d1) break d += 1

С++:

Ответ: 67

Задание 7:

Музыкальный фрагмент был записан в формате моно, оцифрован и сохранён в виде файла без использования сжатия данных. Размер полученного файла – 70 Мбайт. Затем тот же музыкальный фрагмент был записан повторно в формате стерео (двухканальная запись) и оцифрован с разрешением в 4 раза выше и частотой дискретизации в 3,5 раза меньше, чем в первый раз. Сжатие данных не производилось.
Укажите размер файла в Мбайт, полученного при повторной записи.

• Выпишем все известные данные до и после оцифровки:

S = 1 I = 70Мб
 

S = 2 
B > 4 
F < 3.5

• Получим изменение объема файла:

I2 = I1*2*4:3.5 = 70*2*4:3.5 = 160 Мб

Ответ: 160

Задание 8 (А.М. Кабанов):

Юрий составляет 4-буквенные слова из букв П, Р, И, К, А, З. Каждую букву можно использовать не более одного раза, при этом в слове нельзя использовать более одной гласной.

Сколько различных кодов может составить Юрий?

• Рассмотрим все варианты расположения гласной буквы:

2  4  3  2
г
4  2  3  2
   г
4  3  2  2
      г
4  3  2  2
         г

Получаем: 48 * 4 = 192

• Остался вариант, когда гласных нет:

4  3  2  1 = 24 

• Итого: 24 + 192 = 216

Ответ: 216

Задание 9 (А. Кабанов):

Откройте файл электронной таблицы 9-0.xls, содержащей результаты ежечасного измерения температуры воздуха на протяжении трёх месяцев.
Найдите среднее значение измерений, в которых температура не превышала 15 градусов. В ответе запишите только целую часть получившегося числа.

Задание 10 (А.Н. Носкин):

С помощью текстового редактора определите, сколько раз, не считая сносок, встречаются личные местоимения (я, ты, он, она, оно), без учета регистра в тексте А.П. Чехова «Воры» (файл 10-1.docx). В ответе укажите только число.

Задание 11:

При регистрации в компьютерной системе каждому пользователю выдаётся пароль, состоящий из 6 символов и содержащий только символы из 7-буквенного набора А, В, Е, К, М, Н, О. В базе данных для хранения сведений о каждом пользователе отведено одинаковое и минимально возможное целое число байт. При этом используют посимвольное кодирование паролей, все символы кодируются одинаковым и минимально возможным количеством бит. Кроме собственно пароля для каждого пользователя в системе хранятся дополнительные сведения, для чего отведено 10 байт.
Определите объём памяти в байтах, необходимый для хранения сведений о 100 пользователях.

• Мощность алфавита 7, соответственно имеем 2³ > 7, т.е. 3 бита для кодирования 1 символа.
• Для кодирования 6 символов пароля потребуется 6 * 3 = 18 бит. Так как для хранения паролей отведено одинаковое число байт, то для 18 бит потребуется 3 байта (8*3=24, 24>18).
• Всего на одного пользователя, включая дополнительные сведения, потребуется: 3 + 10 = 13 байтов.
• Для хранения сведений о 100 пользователях потребуется 13 * 100 = 1300 байтов.

Ответ: 1300

Задание 12 :

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

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

Дана программа для исполнителя Редактор:

НАЧАЛО
  ПОКА нашлось (111)
    заменить (111, 2)
    заменить (222, 3)
    заменить (333, 1)
  КОНЕЦ ПОКА
КОНЕЦ

Какая строка получится в результате применения приведённой программы к строке вида 1…13…3 (2018 единиц и 2050 троек)?

Программирование:

PascalABC.net:

Python: 1 2 3 4 5 6 s = 2018*'1'+2050*'3' while "111" in s: s = s.replace( "111", "2", 1 ) s = s.replace( "222", "3", 1 ) s = s.replace( "333", "1", 1 ) print(s)

С++:

Ответ: 332113

Задание 13:

На рисунке изображена схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К, Л, М. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой.
Сколько существует различных путей из города А в город М, не проходящих через город Е?

Ответ: 30

Задание 14 (М.В. Кузнецова):
Значение арифметического выражения:

95 + 325 – 20

записали в системе счисления с основанием 3.
Найдите сумму цифр в этой записи. Ответ запишите в десятичной системе.

Программирование:

PascalABC.net:

Python: 1 2 3 4 5 6 x = 9**5 + 3**25 - 20 s = 0 while x: s+=x % 3 x //= 3 print( s )

С++:

Ответ: 18

Задание 15:

Обозначим через ДЕЛ(n, m) утверждение «натуральное число n делится без остатка на натуральное число m». Для какого наименьшего натурального числа А формула

(ДЕЛ(x, A) ∧ ¬ДЕЛ(x, 36)) → ¬ДЕЛ(x, 12)

тождественно истинна (то есть принимает значение 1 при любом натуральном значении переменной х)?

Программирование:

PascalABC.net:

Python: 1 2 3 4 5 6 7 for A in range(1,500): OK = 1 for x in range(1,1000): OK *= ((x % A == 0) and (x % 36 != 0))<=(x % 12!= 0) if OK: print( A ) break

С++:

Ответ: 9

Задание 16:

Алгоритм вычисления значения функции F(n), где n – натуральное число, задан следующими соотношениями:

F(n) = n*n + 3*n + 9, при n ≤ 15
F(n) = F(n-1) + n - 2, при n > 15, кратных 3
F(n) = F(n-2) + n + 2, при n > 15, не кратных 3

Определите количество натуральных значений n из отрезка [1; 1000], для которых все цифры значения F(n) чётные.

Программирование:

PascalABC.net:

Python: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 def F( n ): if n <= 15: return n*n + 3*n + 9 if n>15 and n%3==0: return F(n-1) + n - 2 if n>15 and n%3!=0: return F(n-2) + n + 2 k=0 for i in range(1,1001): x = F(i) flag=True while x>0: digit = x%10 if digit%2 != 0: flag = False x//=10 if flag: k+=1 print (k)

С++:

Ответ: 33

Задание 17:

Рассматривается множество целых чисел, принадлежащих отрезку [1100;11000], которые делятся на 6 и не делятся на 7, 13, 17 и 23.
Найдите количество таких чисел и максимальное из них. В ответе запишите два числа через пробел: сначала количество, затем максимальное число.

Программирование:

PascalABC.net:

Python: 1 2 3 a = [n for n in range(1100,11000+1) if (n%6==0 and n%7!=0 and n%13!=0 and n%17!=0 and n%23!=0)] print(len(a),max(a))

С++:

Ответ: 1178 10992

Задание 18:

Квадрат разлинован на N×N клеток (1 < N < 17). Исполнитель Робот может перемещаться по клеткам, выполняя за одно перемещение одну из двух команд: вправо или вниз. По команде вправо Робот перемещается в соседнюю правую клетку, по команде вниз – в соседнюю нижнюю. При попытке выхода за границу квадрата Робот разрушается. Перед каждым запуском Робота в каждой клетке квадрата лежит монета достоинством от 1 до 100. Посетив клетку, Робот забирает монету с собой; это также относится к начальной и конечной клетке маршрута Робота.
Исходные данные записаны в файле 18-2.xls в виде электронной таблице размером N×N, каждая ячейка которой соответствует клетке квадрата.
Определите максимальную и минимальную денежную сумму, которую может собрать Робот, пройдя из левой верхней клетки в правую нижнюю. В ответе укажите два числа – сначала максимальную сумму, затем минимальную.

Задание 19, 20, 21 (А.Н. Носкин):

Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежат две кучи камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в одну из куч один камень или увеличить количество камней в куче в два раза. Чтобы делать ходы, у каждого игрока есть неограниченное количество камней. Игра завершается в тот момент, когда суммарное количество камней в кучах становится не менее 40. Победителем считается игрок, сделавший последний ход, т. е. первым получивший позицию, в которой в кучах будет 40 или больше камней.
В начальный момент в первой куче было 9 камней, во второй куче – S камней, 1 ≤ S ≤ 30. Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника.
Ответьте на следующие вопросы:
Вопрос 1 (задание 19). Известно, что Ваня выиграл своим первым ходом после неудачного первого хода Пети. Назовите минимальное значение S, при котором это возможно.
Вопрос 2 (задание 20). Найдите два таких значения S, при которых у Пети есть выигрышная стратегия, причём Петя не может выиграть первым ходом, но может выиграть своим вторым ходом независимо от того, как будет ходить Ваня. Найденные значения запишите в ответе в порядке возрастания.
Вопрос 3 (задание 21). Сколько существует значений S, при которых у Вани есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Пети, и при этом у Вани нет стратегии, которая позволит ему гарантированно выиграть первым ходом.

Программирование:

PascalABC.net:

Python: Задание 19: 1 2 3 4 5 6 7 8 9 10 11 def f(x,y,p): if x+y>=40 and p==3: return 1 elif x+y<40 and p==3: return 0 else: return f(x+1,y,p+1)+f(x*2,y,p+1)+f(x,y+1,p+1)+f(x,y*2,p+1) for i in range (1,1000): if f(9,i,1): print(i) break Ответ: 4 Задание 20: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 def f(x,y,p): if x+y>=40 and p==4: return 1 elif x+y<40 and p==4: return 0 elif x+y>40: return 0 elif p%2==1: return f(x+1,y,p+1)+f(x*2,y,p+1)+f(x,y+1,p+1)+f(x,y*2,p+1) else: return f(x+1,y,p+1)*f(x*2,y,p+1)*f(x,y+1,p+1)*f(x,y*2,p+1) for i in range (1,1000): if f(9,i,1): print(i) Ответ: 4 3 4 уже было в 19, убираем 14 15 - лишнее Задание 21: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 def f(x,y,p): if x+y>=40 and (p==3 or p==5): return 1 elif x+y<40 and p==5: return 0 elif x+y>40: return 0 elif p%2==0: return f(x+1,y,p+1)+f(x*2,y,p+1)+f(x,y+1,p+1)+f(x,y*2,p+1) else: return f(x+1,y,p+1)*f(x*2,y,p+1)*f(x,y+1,p+1)*f(x,y*2,p+1) for i in range (1,1000): if f(9,i,1): print(i) Ответ: 14 уже было в 20 15 уже было в 20 значит, ответ 0

С++:

Ответ:

19: 4
20: 3  14
21: 0

Задание 22:

Укажите наименьшее из таких чисел x, при вводе которых алгоритм печатает сначала 3, а потом 15.

1
2
3
4
5
6
7
8
9
10
11

var x, a, b: integer;
begin
  readln(x);
  a:=0; b:=1;
  while x > 0 do begin
    a:= a + 1;
    b:= b*(x mod 10);
    x:= x div 10;
  end;
  writeln(a); write(b);
end.

1
2
3
4
5
6
7
8
9

x = int(input())
a = 0 
b = 1
while x > 0: 
  a = a + 1
  b = b*(x % 10)
  x = x // 10
print(a)
print(b)

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

#include <stdio.h> 
int main(void)
{
 int a, b, x; 
 scanf(″%d″, &x);
 a = 0; b = 1;
 while (x > 0) {
   a = a + 1;
   b = b*(x % 10);
   x = x / 10;
 }
 printf(″%dn%d″, a, b);
}

Программирование:

PascalABC.net:

Python: 1 2 3 4 5 6 7 8 9 10 11 for x_ in range(1,1001): x = x_ a = 0 b = 1 while x > 0: a = a + 1 b = b*(x % 10) x = x // 10 if a==3 and b==15: print(x_) break

С++:

Ответ: 135

Задание 23:

Исполнитель Калькулятор преобразует число на экране. У исполнителя есть три команды, которым присвоены номера:

1. Прибавить 1
2. Прибавить 3
3. Умножить на 4

Программа для исполнителя Калькулятор – это последовательность команд.
Сколько существует программ, для которых при исходном числе 1 результатом является число 18?

Программирование:

PascalABC.net:

Python:

С++:

Ответ: 572

Задание 24:

Текстовый файл 24-s1.txt состоит не более чем из 10⁶ заглавных латинских букв (A..Z). Текст разбит на строки различной длины.
Определите количество строк, в которых буква K встречается чаще, чем буква U.

Программирование:

PascalABC.net:

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("K") > s.count("U"): k +=1 print(k)

С++:

Ответ: 470

Задание 25:

Напишите программу, которая ищет среди целых чисел, принадлежащих числовому отрезку [251811; 251826], числа, имеющие ровно 4 различных делителя. В ответе для каждого найденного числа запишите два его наибольших делителя в порядке возрастания.

Программирование:

PascalABC.net:

Python: 1 2 3 4 5 6 7 8 for n in range(251811, 251826+1): divs = [] # чистим список делителей for d in range(1,n+1): # if n % d == 0: divs = divs + [d] # добавляем делитель в список if len(divs) > 4: break if len(divs) == 4: print(*divs) ИЛИ: 1 2 3 4 for n in range(251811, 251826+1): divs = [d for d in range(1, n+1) if n % d == 0] if len(divs) == 4: print( *divs )

С++:

Ответ:

	8123 251813
50363 251815
83939 251817
601 251819
14813 251821

Задание 26 (Е. Джобс):

Системный администратор раз в неделю создаёт архив пользовательских файлов. Однако объём диска, куда он помещает архив, может быть меньше, чем суммарный объём архивируемых файлов. Известно, какой объём занимает файл каждого пользователя. Системный администратор старается сохранить файлы как можно большего размера. При этом используя выделенную память максимально эффективно – сохраняя файлы меньшего размера, если файлы большего не могут быть сохранены.

Входные данные. В первой строке входного файла 26-j3.txt находятся два числа: S – размер свободного места на диске (натуральное число, не превышающее 1000000) и N – количество пользователей (натуральное число, не превышающее 10000). В следующих N строках находятся значения объёмов файлов каждого пользователя (все числа натуральные, не превышающие 100), каждое в отдельной строке.
Запишите в ответе два числа: сначала число сохраненных файлов, затем размер наименьшего сохраненного файла.
Пример входного файла:

100 4 
70
10
25
3

При таких исходных данных можно сохранить три файла – 70, 25, 3. Поэтому ответ должен содержать два числа – 3 и 3.

Программирование:

PascalABC.net:

Python: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 f = open('26-j3.txt') data = f.readlines() s = data[0].split() s = int(s[0]) # del(data[0]) # удаляем самую первую строку, она уже не нужна   for i in range (0, len(data)): # переводим в целые числа data[i] = int(data[i]) minSize = 10**9 count = 0 data.sort(reverse = True) for x in data: if s >= x: s -= x minSize = x # минимальный элемент и будет последним удобвлетворяющим условию count += 1   print( count, minSize )

С++:

Ответ: 1054 732

Задание 27:

Имеется набор данных, состоящий из троек положительных целых чисел. Необходимо выбрать из каждой тройки два числа так, чтобы сумма всех выбранных чисел не делилась на 5 и при этом была максимально возможной. Гарантируется, что искомую сумму получить можно. Программа должна напечатать одно число – максимально возможную сумму, соответствующую условиям задачи.
Входные данные. Даны два входных файла (файл A и файл B), каждый из которых содержит в первой строке количество троек N (1 ≤ N ≤ 100000). Каждая из следующих N строк содержит три натуральных числа, не превышающих 10 000.
Пример входного файла:

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

Для указанных входных данных значением искомой суммы должно быть число 89.
В ответе укажите два числа: сначала искомое значение для файла А, затем для файла B.

Программирование:

PascalABC.net:

Python: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 f = open ('27-29a.txt') n=int(f.readline()) # количество data=f.readlines() summa=0 minim=10001 # для минимальной разницы for i in range(0, n): s = data[i].split() a=int(s[0]) b=int(s[1]) c=int(s[2])   if a > b: (a,b)=(b,a) if b > c: (b,c)=(c,b) if a > b: (a,b)=(b,a) # a,b,c отсортированы по возрастанию summa += c+b if abs(a-b) % 5 > 0: minim = min(abs(a-b),minim) if abs(a-c) % 5 > 0: minim = min(abs(a-c),minim) if summa % 5 != 0: print("s=",summa) else: print(summa - minim)

С++:

Ответ: 25034 76468978