Задание 27, задача 48

Задание 27, задача 48 (сайт К.Ю Полякова)
Данную задачу можно решить средствами электронных таблиц. Выгружаем пары чисел в столбцы А и B. В столбец С выносим максимальные числа из пары, в столбец D — модули разностей чисел из пары. Можно выполнить сортировку последнего столбца по возрастанию, расширив диапазон сортировки (при этом пара с минимальной разностью окажется в самом начале). Дальше считаем сумму максимальных чисел из пар (столбец С) и количество четных и нечетных. Видим, что сумма четная, а количество нечетных больше, чем четных. Поэтому нужно из этой суммы вычесть минимальную нечетную разность (это равносильно тому, что мы из суммы вычтем четное число и прибавим нечетное из пары с минимальной нечетной разностью).
Решение на языке Python полностью имитирует данный процесс:


Fin = open("27-48b.txt")
s_max=0
N = int( Fin.readline() )
count_ch=0
min_razn=999999999999
for i in range(N):
  ab = list(map( int, Fin.readline().split() ))
  s_max+=max(ab)
  if max(ab)%2==0: count_ch+=1
  if abs(ab[0]-ab[1])%2!=0:
      min_razn=min(min_razn, abs(ab[0]-ab[1]))



Fin.close()

print( s_max, count_ch, N-count_ch, min_razn)
print (s_max-min_razn)

Задание 18, задача 127

Задание 18, задача 127 (сайт К.Ю Полякова). Решение с помощью электронных таблиц.

Задание 27, задача 8

Задание 27, № 8 (с сайта К.Ю. Полякова)
Имеется набор данных, состоящий из положительных целых чисел, каждое из которых не превышает 1000. Они представляют собой результаты измерений, выполняемых прибором с интервалом 1 минута. Требуется найти для этой последовательности контрольное значение – наименьшую сумму квадратов двух результатов измерений, выполненных с интервалом не менее, чем в 5 минут.
Входные данные: Даны два входных файла: файл A (27-8a.txt) и файл B (27-8b.txt), каждый из которых содержит в первой строке количество чисел N (5 ≤ N ≤ 100000). Каждая из следующих N строк содержит одно натуральное число, не превышающее 1000.
Пример входного файла:
9
12
45
5
4
21
20
10
12
26
Для указанных данных искомое контрольное значение равно 169.
В ответе укажите два числа: сначала контрольное значение для файла А, затем для файла B.

Решение (Python) (данные вводятся копированием из файла в окно программы)

s=5
n=int(input())
queue = []
for i in range(s):
____queue.append( int(input()) )
min=1001
Res=2*1000**2+1
for i in range(n-s):
____a= queue.pop(0)
____if a<min: min=a
____x=int(input())
____queue.append(x)
____if x**2+min**2<Res: Res=x**2+min**2
print (Res)

Основные теоретические сведения для ЕГЭ

  1. Системы счисления
    • В числе хn (an ≤ хn ≤ an+1) n+1 цифра.
      Примеры:
      3610 = 11003; 33 ≤ 36 ≤ 34; в числе 11003 4 цифры
      53 = 10005 – 4 цифры
    • n-значное число в системе счисления с основанием а находится в пределах an-1 ≤ x < an (для задачи 25)
    • -2n = -2n+1 + 2n
      -an = -а n+1 + (а-1)*аn

    • где (а-1) – старшая цифра в системе счисления с основанием а
    • старшая цифра в системе счисления с основанием а равна а – 1
  1. Алгебра логики
  1. Измерение информации
    • Текст
      I = K*i,
      где К – количество символов в тексте,
      i – информационный вес одного символа
      N = 2i , N – мощность алфавита
    • Графическая информация:
      I = K*i, где К – размер изображения в пикселях, i – битовая глубина
      Количество цветов N = 2i
    • Звук:
      I = k*q*i*t,
      где
      k – количество дорожек;
      q – частота дискретизации;
      i – битовая глубина;
      t – время записи (звучания)
      Количество уровней дискретизации N = 2i
    • M = Qn,
    • где
      Q – мощность алфавита, которым кодируем
      n – длина слова
      М – количество слов, которые можно составить

  1. Количество пар однородных элементов (задача 27)
    • N(N-1)//2 (// — целочисленное деление)

Задание 26 с конфетами (2020 г.)

Задание 26, № 97 (задание с сайта К.Ю. Полякова)

(Д.И.Перминов, г.Барнаул) Два игрока, Петя и Ваня, играют в сле-дующую игру. Перед игроками лежит куча, состоящая из S конфет. Игроки ходят по очереди, первый ход делает Петя. За один ход иг-рок может съесть не более половины от всех оставшихся конфет, но не менее одной конфеты.

Игра завершается в тот момент, когда в куче не остается ни одной конфеты. Победителем считается игрок, который съел последнюю конфету.

Задание 1. Кто из игроков имеет выигрышную стратегию при S= 5, 6, 7 ?

Задание 2.Какое минимальное количество ходов должен совер-шить игрок, чтобы победить при S= 12 ? Назовите имя этого игрока.

Задание 3. Укажите максимальное значение S, меньшее 15, при котором выигрышную стратегию имеет Ваня.

Решение.

Сначала просчитаем выигрышные и проигрышные позиции.

1 конфета: игрок, который ходит из этой позиции выигрывает.

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

3 и 4 конфеты: игрок может перевести противника в проигрышную позицию «2» и выиграть. Позиция выигрышная.

5 конфет: игрок может съесть не более 2 конфет. Позиция проиг-рышная

Определим дальнейшие позиции.

Из позиций [6..10] игрок может съесть такое количество конфет, чтобы в куче осталось 5 конфет. Таким образом, он приводит противника в проигрышную позицию и выигрывает.

Следующая позиция – 11. Игрок может съесть максимум от 1 до 5 конфет. И в любом случае, в куче остается от 6 до 10 конфет, т.е он привел противника в выигрышную для него позицию и проиграл.

Представим это на шкале:

 

Очевидно, что позиции [12..22] – выигрышные 4 ходом, а 23 – проиг-рышная.

Таким образом, номер каждой следующей проигрышной позиции равен 2n + 1, где n – номер текущей проигрышной позиции. Все позиции от одной проигрышной до другой – выигрышные.

Вернемся к решению задачи.

Задание 1. При S= 5 выигрышную стратегию имеет Ваня.

При S= 6, 7 выигрышную стратегию имеет Петя. Ему нужно оста-вить в куче 5 конфет.

Задание 2. При S=12 игрок минимально совершит 4 шага. Из этой пози-ции выиграет Петя.

Задание 3. 11.

Теперь, зная, как высчитать выигрышные и проигрышные пози-ции, решим задачи № 98 и 99.

№ 98. (Д.И.Перминов, г.Барнаул) Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча, состоящая из S кон-фет. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может съесть не более половины от всех оставшихся конфет, но не менее одной конфеты.

Игра завершается в тот момент, когда в куче не остается ни одной конфеты. Победителем считается игрок, который съел последнюю конфету.

Задание 1. Кто из игроков имеет выигрышную стратегию при S= 17, 18, 19 ?

Задание 2.Какое максимальное количество ходов может совер-шить игрок, чтобы победить при S= 20 ? Назовите имя этого игрока.

Задание 3. Укажите минимальное значение S, большее 40, при ко-тором выигрышную стратегию имеет Ваня.

Решение

Задание 1. При S= 17, 18, 19 выигрышную стратегию имеет Петя. Ему нужно оставить в куче 11 конфет.

Задание 2. При S= 20 выигрывает Петя на 4 ходу.

Задание 3. 47 (23*2+1).

№ 99. (Д.И.Перминов, г.Барнаул) Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча, состоящая из S кон-фет. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может съесть не более половины от всех оставшихся конфет, но не менее одной конфеты.

Игра завершается в тот момент, когда в куче не остается ни одной конфеты. Победителем считается игрок, который съел последнюю конфету.

Задание 1. Кто из игроков имеет выигрышную стратегию при S= 150 ?

Задание 2. За какое наименьшее количество ходов может завер-шиться игра при S=23 ?

Кто при этом победит?

Задание 3. Укажите все трехзначные S при которых выигрышную стратегию имеет Ваня.

Задание 1. S= 150 не является проигрышной позицией, поэтому выигрышную стратегию имеет Петя. Ему нужно оставить 95 кон-фет.

Задание 2. При S=23 игра закончится за 8 шагов, выиграет Ваня.

Задание 3. 95*2+1=191,

191*2+1 = 383

383*2+1=767