Единый государственный экзамен ЕГЭ по информатике Часть 2. Основная волна 16.06.2016. Вариант 52.

Единый государственный экзамен ЕГЭ по информатике Часть 2. Основная волна 16.06.2016. Вариант 52.

1. Ученик написал программу, определяющую, какой степенью числа 5 является введенное. Например, для 25 это 2, так как 52 = 25. Если же такой степени нет, то необходимо вывести сообщение “Не существует”. К сожалению, ученик написал программу неверно.

Паскаль

Delphi/Pascal
1234567891011121314 var n,k: longint;begin  readln(n);  k := 0;  while k mod 5 = 0 do    begin    n := n div 5;    k := k + 1;  end;  if k <= 5 then  writeln(k)  else    writeln('Не существует');end.

Последовательно выполните следующее.

1. Что выдаст программа при вводе числа 125?
2. При вводе какого числа программа выдаст верный ответ? Укажите этот ответ.
3. Исправьте программу. Запишите ошибочную строку, затем не исправленной вариант. Помните, что нужно исправить имеющуюся программу, а не писать свою, хоть и с лучшим алгоритмом’

Решение:

Python

Если массив имеет значение с 0-го индекса:

Python
12345 k=0for i in range(1,N): if a[i]%4==0 and a[i-1]%4==0: k+=1print(k)

3. Паша и Валя играют в следующую игру: перед игроками лежит куча камней, каждый игрок за один ход может добавить в кучу 1 камень или удвоить количество камней в куче. Камни для ходов не ограничены. Выигрывает тот игрок, после хода которого в кучу оказалось 24 и более камней, но не более 38. Если после хода игрока в куче более 38 камней, выигрывает его соперник. Первым ходит Паша.

Пусть S — начальное количество камней в куче.
а) При каких значениях S Паша может выиграть первым ходом?
б) У кого есть выигрышная стратегия при S = 20, 21, 22.
в) У кого выигрышная стратегия при S = 10, 11?
г) У какого игрока выигрышная стратегия при S = 9? Нарисуйте дерево решений.

Решение:

Введем обозначения:

“+1” – добавить в куяу 1 камень

“x2” – удвоить количество камней в куче

а) При S=23 Паша +1 -> Победа Паши

При S∈[12;19] Паша x2 -> Победа Паши

б) Так как все три значения S >19, то x2 нельзя. Для победы S должно быть ≥ 24. Если S > 19 и S – четное(S=20, 22), то выиграет Валя, так как после его хода S станет четным(как 24); при S 19 и S нечетное(S=21), выиграет Паша, так как после его хода число станет четным.

в) При S=10 выигрышная стратегия есть у Паши: x2(S=20), так как S > 19 и S – четное, а ход за Валей, то можно сделать вывод(в том числе исходя из пункта б), что выиграет Паша.

То же самое для S=11(x2, тогда S=22…)

г) При S=9 выигрышная стратегия есть у Вали:

S=9 Паша Валя
+1 S=10 x2 S=20 т.к.S>19 и S-чётное, а ход Паши, то выиграет Валя.
ч2 S=18 x2 S=20 Победа Вали

4. На вход даны пары чисел. Нужно выбрать из каждой пары по одному числу так, чтобы сумма всех выбранных чисел не была кратна 4 и при этом была максимально возможной. Напишите программу, выводящую такую сумму на экран. Если же ее невозможно получить, выведите 0. Баллы начисляются за ту из подзадач, что решена на большее количество баллов. Задача А дает 2 балла, задача Б – 4 балла. В задаче А приведите неэффективный алгоритм. При решении указывайте, какую подзадачу делаете. За алгоритм, неэффективный по времени ИЛИ памяти, дается 3 балла, по времени И памяти – 2 балла.

Задача А. Количество пар известно заранее и равно 6. Числа не превышают 30 000.

Задача Б. Количество пар N не известно заранее и может принимать значения 2 <= N <= 200 000. На вход подается сначала количество пар, затем сами пары. Числа по модулю не превышают 30 000.

Решение:

Задача Б – Python
Python

1234567891011121314151617181920 n=int(input()) mx1=0 #максимальная суммаr=30000*2 #минимальная разница между парой элементовmx2=0 #марница между максимальной суммой и мимнальной разинцей ra=0:b=0for i in range(0,n): a,b=map(int,input().split()) if a>b: mx1+=a else: mx1+=b if abs(a-b)<r and abs(a-b)%4!=0 and a!=b: r=abs(a-b)if mx1%4==0 and r=30000*2: print(0)elif mx1%4==0: mx2=mx1-r print(mx2)else: print(mx1)