Задание 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 (сайт К.Ю Полякова). Решение с помощью электронных таблиц.

Задание 8 (комбинаторика)

Задание 8, № 192 (с сайта К.Ю. Полякова)
(А. Богданов) Марина собирает восьмибуквенные слова из букв своего имени. Первые четыре буквы новых слов берутся из первых четырех букв имени, так чтобы ни одна буква не повторялась. А последние четыре буквы из последних трех букв имени, и они могут многократно повторяться. На каком месте окажется имя МАРИАННА в отсортированном по алфавиту списке сгенерированных слов? Нумерация начинается с 1.

Решение:
1. Выясним количество вариантов для первой половины слова (последовательность из 4х букв, состоящая из букв М, А, Р, И, в которой буквы не повторяются):

  • слово начинается с А: 3*2*1=6 слов
  • слово начинается с И: 3*2*1=6 слов
  • слово начинается с М (запишем слова в алфавитном порядке):

МАИР
МАРИ

Таким образом, перед словом, начинающимся с МАРИ, возможны 13 вариантов начала слова.
2. Рассмотрим вторую половину слова (последовательность из 4х букв, составленная из букв А, И, Н). Всего здесь можно составить 34=81 слово.
3. 13*81=1053 различных слова до слова, начинающегося с МАРИ.
4. Рассмотрим слова, начинающиеся с МАРИ. Посчитаем, на каком месте в этом списке находится слово в окончанием АННА.
Для этого обозначим буквы цифрами: А — 0, И — 1, Н — 2.
АННА -> 02205=24.
Т.к. на первом месте стоит 0 (АААА), то 24 стоит на 25 месте.
5. Посчитаем окончательный ответ: 1053+25=1078.

Задание 8, № 193 (с сайта К.Ю. Полякова)
(Е. Джобс) Сколько существует четных пятеричных чисел длиной 6, начинающихся с цифры 3?

Решение:
Важно помнить, что в системе счисления с нечетным основанием четность числа зависит от суммы его цифр. Если число нечётных цифр чётное (сумма цифр числа четная), то всё число чётное, а если число нечётных цифр нечётное (сумма цифр нечетная), то число нечётное.
Т.к. на первом месте стоит 3 (нечетная цифра), то сумма следующих 5 цифр должна быть нечетной. Т.е. эти 5 знакомест содержат 1,3 или 5 нечетных цифр.
1) Оставшиеся 5 цифр содержат 1 нечетную цифру: 2*34=162.
Т.к. нечетная цифра может находиться на любой из 5 позиций, 162*5=810.
2) Оставшиеся 5 цифр содержат 3 нечетные цифры: 2*2*2*3*3=72.
Количество вариантов расстановки нечетных цифр: 5!/(2!*3!)=10;
72*10=720
3) Все цифры нечетные: 25=32

810+720+32=1562.

Задание 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