1 Ответ
1. Вася с детства любит числа. Не складывать, не умножать, а выстраивать их в ряды — как солдатиков, как книги на полке, как вагоны поезда. У каждого числа в его ряду должно быть своё особенное место, определённое по заданным правилам. Однажды Вася решил построить бесконечный ряд из чисел, подчиняющийся следующим правилам: на первое место в ряду Вася поставил число 1;
каждое следующее число — это последняя цифра числа, полученного следующим образом: предыдущее число умножают на два и прибавляют 1. Так, чтобы получить второе число в ряду, мы берём предыдущее, то есть 1, умножаем его на 2, получаем 2, прибавляем 1, получаем 3 и берём последнюю цифру результата, это 3. Таким образом, вторым числом в ряду будет 3. Обращаем внимание, что числа в ряду могут повторяться. Какие числа стоят на 4, 10, 2029 позициях в ряду?
Ответ: 4-я позиция — 5; 10-я позиция — 3; 2029-я позиция — 1
2. Каждый участник благотворительного вечера в пользу детей объявил максимальную цену, которую готов заплатить за билет. Организаторы должны назначить одну общую положительную целую цену билета. Каждый желающий покупает ровно один билет, если установленная цена не превышает его личного предела. Количество мест не ограничено. На благотворительный вечер хотят прийти семь человек. Максимальные цены, которые они готовы заплатить:
3, 5, 5, 8, 9, 12, 14.
Какую максимальную суммарную выручку организаторы могут получить от продажи билетов?
Ответ: 32
3. Перед первой ступенькой лестницы на полу стоит робот. На каждой ступеньке написано целое число. Первоначально у робота 0 очков. Пол не считается ступенькой, и число на нём не написано. За один прыжок робот может подняться на одну или на две ступеньки. Делать два прыжка на две ступеньки подряд запрещено: между ними должен быть хотя бы один прыжок на одну ступеньку. Таким образом, первым прыжком робот может попасть на первую или сразу на вторую ступеньку. При приземлении на ступеньку робот прибавляет написанное на ней число к своим очкам. Если число отрицательное, очки уменьшаются. Количество очков может становиться отрицательным. Числа на перепрыгнутых ступеньках не учитываются. Робот должен закончить движение на последней ступеньке. Помогите ему набрать как можно больше очков.
На лестнице 8 ступенек. На них снизу вверх написаны числа:
5, −4, 6, 3, −7, 8, 2, 4.
На лестнице 8 ступенек. На них снизу вверх написаны числа:
4, −6, 7, −3, 9, −5, 8, 5.
Ответ: первый набор — 28; второй набор — 30
4. Робот рисует на длинной бумажной полосе. Сначала он закрашивает прямоугольник длиной a сантиметров и шириной b сантиметров. Затем робот n раз сдвигает кисть вправо на c сантиметров, где 0 < c < a, и оставляет такой же отпечаток. Таким образом, всего робот рисует n + 1 прямоугольник. Все отпечатки имеют одинаковую ширину и лежат на одной прямой. Соседние отпечатки перекрываются. Числа a, b, c и n — положительные целые. Составьте формулу для определения площади бумаги, которая окажется закрашенной. Участки, закрашенные несколько раз, нужно учитывать только один раз.
Ответ: (a + n * c) * b
5. Каждый участник благотворительного вечера в пользу детей объявил максимальную цену, которую готов заплатить за билет. Организаторы должны назначить одну общую положительную целую цену билета. Каждый желающий покупает ровно один билет, если установленная цена не превышает его личного предела. Количество мест не ограничено. В этой задаче две подзадачи.
На благотворительный вечер хотят прийти семь человек. Максимальные цены, которые они готовы заплатить:
3, 5, 5, 8, 9, 12, 14.
Какую максимальную суммарную выручку организаторы могут получить от продажи билетов?
Во втором случае максимальные цены, которые готовы заплатить желающие прийти на благотворительное мероприятие, находятся в приложенном файле. Скачайте файл в одном из трёх форматов: текстовый файл (.txt), таблица Microsoft Excel (.xlsx) и таблица Libre Office Calc (.ods). Во всех файлах содержатся одинаковые данные. Какую максимальную суммарную выручку организаторы могут получить от продажи билетов?
Ответ: первый случай — 32; второй случай — 1129690
6. На поле размером 4 × 9 в каждой клетке стоит выключенный фонарик. Перед началом игры можно включить некоторые фонарики. Затем каждую минуту включается каждый фонарик, у которого хотя бы два соседа по стороне уже горели к началу этой минуты. Соседями считаются фонарики в клетках сверху, снизу, слева и справа. Фонарики, граничащие по диагонали, соседями не считаются. Все фонарики, которые должны включиться в некоторую минуту, включаются одновременно. Загоревшиеся фонарики больше не гаснут. Как можно включить первоначально наименьшее количество фонариков, чтобы через некоторое время загорелось всё поле? Отметьте их положения на схеме.
Ответ:
7. Ограничение по времени: 1 секунда Ограничение по памяти: 256 мегабайт Для участия в игре нужны жетоны. Один жетон стоит 1 рубль. При покупке каждых k оплаченных жетонов посетитель получает ещё один жетон бесплатно. Пете нужно получить не меньше n жетонов. Какую наименьшую сумму он должен потратить?
Формат входных данных
В первой строке дано целое число k (1 ⩽ k ⩽ 109). Во второй строке дано целое число n (1 ⩽ n ⩽ 109).
Формат выходных данных
Выведите одно целое число — наименьшую сумму в рублях.
Замечание
В первом примере Петя платит по 1 рублю за 1-й, 2-й, 4-й, 5-й, 7-й и 8-й жетоны, а 3-й и 6-й получает в подарок. Всего Петя заплатит 6 рублей.
Пример 1 ввода: 2 8
Пример 1 вывода: 6
Пример 2 ввода: 3 3
Пример 2 вывода: 3
Пример 3 ввода: 1 5
Пример 3 вывода: 3
Ответ:
k = int(input())
n = int(input())
print(n — n // (k + 1))
8. Ограничение по времени: 1 секунда Ограничение по памяти: 256 мегабайт Для выставки подготовили два прямоугольных плаката размером a × b и c × d сантиметров. Их нужно разместить на квадратном стенде. Каждый плакат разрешается поворачивать на 90 градусов. Стороны плакатов должны быть параллельны сторонам стенда. Плакаты могут соприкасаться границами, но не должны перекрываться или выходить за границы стенда. Найдите минимальную целую длину стороны стенда в сантиметрах, при которой можно разместить оба плаката.
Ответ:
a = int(input())
b = int(input())
c = int(input())
d = int(input())
best = None
for w1, h1 in ((a, b), (b, a)):
for w2, h2 in ((c, d), (d, c)):
side = max(w1 + w2, h1, h2)
if best is None or side < best:
best = side
print(best)
9. Ограничение по времени: 1 секунда Ограничение по памяти: 256 мегабайт Туристическая фирма водит группы в походы по лесу. Маршрут похода проходит через овраг ширины w. Раньше через этот овраг был перекинут мостик, но сейчас его сорвало ураганом. Вдоль оврага растут деревья, для каждого дерева известны его высота и расстояние от него до оврага. Если свалить дерево в сторону оврага так, чтобы оно перекрыло его ширину, то по этому дереву можно будет перейти через овраг. Например, пусть овраг имеет ширину 3, дерево расположено на расстоянии 5 от него и имеет высоту 10. Если свалить это дерево в сторону оврага, то оно его перекроет и по этому дереву можно будет перейти. А если дерево расположено на расстоянии 4 и имеет высоту 6, то при его падении тот же овраг ширины 3 не перекроется и его нельзя будет перейти. На завтра запланированы две группы, поэтому для их переправы нужно свалить два дерева. Определите, сколькими способами это можно сделать. Обратите внимание, что значение ответа в этой задаче может превышать возможное значение 32-битной целочисленной переменной, поэтому необходимо использовать 64-битные целочисленные типы данных (тип int64 в языке Pascal, тип long long в C++, тип long в Java и C#).
Ответ:
import sys
data = sys.stdin.read().split()
w = int(data[0])
n = int(data[1])
k = 0
for i in range(n):
x = int(data[2 + 2 * i])
h = int(data[3 + 2 * i])
if x + w <= h:
k += 1
print(k * (k — 1) // 2)
