Решение олимпиадных задач от образовательного центра «Сириус»

Автор: Шибаева Надежда Николаевна

Организация: МБОУ СОШ №48 г.Чебоксары

Населенный пункт: Чувашской Республика, г.Чебоксары

Олимпиадные задания

2024-2025

Библиотечный метод

Продемонстрируйте работу метода сортировки вставками по возрастанию. Для этого выведите состояние данного массива после каждой вставки на отдельных строках. Если после рассмотрения очередного элемента массив не изменился, то его выводить не нужно. Если массив упорядочен изначально, то следует не выводить ничего.

Входные данные

На первой строке дано число N (1≤N≤100) — количество элементов в массиве. На второй строке задан сам массив: последовательность натуральных чисел, не превышающих 109.

Выходные данные

Выведите строки (по количеству вставок) по N чисел каждая.

Примеры

Ввод

2 4

Вывод

2 1 2 1 5 3

1 2 1 2 5 3

1 2 3 5

 

Программа:

n = int(input())

a = [int(x) for x in input().split()]

for i in range(1, len(a)):

flag = False

tmp = a[i]

j = i - 1

while j >= 0 and a[j] > tmp:

a[j + 1] = a[j]

j -= 1

flag = True

a[j + 1] = tmp

if flag:

print(*a)

 

Результаты олимпиады

Во время проведения олимпиады каждый из участников получил свой идентификационный номер — натуральное число. Необходимо отсортировать список участников олимпиады по количеству набранных ими баллов от больших баллов к меньшим, а при равенстве баллов — по возрастанию идентификационных номеров. Встроенные алгоритмы сортировки не использовать.

Входные данные

На первой строке дано число N(1≤N≤1000) — количество участников. На каждой следующей строке даны идентификационный номер и набранное число баллов соответствующего участника. Все числа во входном файле не превышают 105.

Выходные данные

Выведите исходный список в порядке убывания баллов. Если у некоторых участников одинаковые баллы, то их между собой нужно выводить в порядке возрастания идентификационных номеров.

Программа:

n = int(input())

f = []

for i in range(n):

f.append(list(map(int,input().split())))

for i in range(n):

for j in range(n - 1):

if f[j][1] < f[j + 1][1]:

f[j], f[j + 1] = f[j + 1], f[j]

elif f[j][1] == f[j + 1][1]:

if f[j][0] > f[j + 1][0]:

f[j], f[j + 1] = f[j + 1], f[j]

for i in range(n):

print(f[i][0], " ", f[i][1], sep = "", end = "\n")

Мячик на лесенке

На вершине лесенки, содержащей N ступенек, находится мячик, который начинает прыгать по ним вниз, к основанию. Мячик может прыгнуть на следующую ступеньку, на ступеньку через одну или через 22. (То есть если мячик лежит на 88-ой ступеньке, то он может переместиться на 55-ю, 66-ю, или 77-ю.) Определите число всевозможных "маршрутов" мячика с вершины на землю.

Входные данные

Вводится одно число 0<N<3 10<𝑁<31.

Выходные данные

Выведите одно число — количество маршрутов.

Программа 1:

n=4

def steps(n):

a, b, c = 0, 1, 1

if n < 2:

return [a, b, c][n]

while n:

a, b, c = b, c, a+b+c

n -= 1

return b

print(steps(n))

___________________________________

Программа 2:

limit = int(input())

a = [0,1,1]

for _ in range (limit-1):

a.append(sum(a[-3:]))

print(a[-1])

Калькулятор

Имеется калькулятор, который выполняет три операции:

• прибавить к числу X единицу;
• умножить число X на 22;
• умножить число X на 33.

Определите, какое наименьшее число операций необходимо для того, чтобы получить из числа 11 заданное число N.

Входные данные

Программа получает на вход одно число, не превосходящее 106.

Выходные данные

Требуется вывести одно число: наименьшее количество искомых операций.

________________________

Программа:

from math import inf

n = int(input())

op = [0] * (n + 1)

for i in range(2, n+1):

op[i] = min(op[i-1], i % 2 and inf or op[i//2], i % 3 and inf or op[i//3]) + 1

print(op[n])

 

 

 

 

 

 

 

 

Без двух нулей подряд

Требуется посчитать количество последовательностей длины n, состоящих из цифр от 00 до k−1 таких, что никакие два соседних элемента последовательности не равны нулю одновременно.

Входные данные

Заданы два натуральных числа N и K (2≤K≤10; 2≤N; 4≤N+K≤18).

Выходные данные

Необходимо вывести целое число — ответ на задачу.

Примеры

Ввод

Вывод

2 2 3

3 9 7 12

Программа:

n, k = map(int, input().split())

a, b = 1, k - 1

for _ in range(n - 1):

a, b = b, (k - 1) * (a + b)

print(a + b)

 

Без трёх единиц

Определите количество последовательностей из нулей и единиц длины N (длина — это общее количество нулей и единиц), в которых никакие три единицы не стоят рядом.

Входные данные

Дано натуральное число N, не превосходящее 40.

Выходные данные

Выведите количество искомых последовательностей. Гарантируется, что ответ не превосходит 231−1.

Примеры

Ввод

Вывод

3 7

Программа:

n = int(input())

f = [0] * 40

f[1] = 2; f[2] = 4; f[3] = 7

i = 4

while i <= n:

f[i] = (f[i-1] + f[i-2] + f[i-3])

i+=1

print(f[n])

Гвоздики

В дощечку в один ряд вбиты гвоздики. Любые два гвоздика можно соединить ниточкой. Требуется соединить некоторые пары гвоздиков ниточками так, чтобы к каждому гвоздику была привязана хотя бы одна ниточка, а суммарная длина всех ниточек была минимальна.

Входные данные

В первой строке входных данных записано число N — количество гвоздиков (2≤N≤100). В следующей строке заданы N чисел — координаты всех гвоздиков (неотрицательные целые числа, не превосходящие 10000).

Выходные данные

Выведите единственное число — минимальную суммарную длину всех ниточек.

Примеры

Ввод

Вывод

6

3 4 6 12 13 14 5

Программа1:

def maxl (i):

if i > n-3:

return 0

if m[i] == 0:

m[i]= x[i+1] - x[i] + max (maxl (i+2), maxl (i+3));

return m[i]

Программа2:

n=int(input())

x= list(map(int, input().split()))

x=sorted(x)

m= [0 for i in range (n)]

print (x[-1] - x[0] - max( maxl(1),maxl (2)))

Покупка билетов

За билетами на премьеру нового мюзикла выстроилась очередь из N человек, каждый из которых хочет купить 11 билет. На всю очередь работала только одна касса, поэтому продажа билетов шла очень медленно, приводя «постояльцев» очереди в отчаяние. Самые сообразительные быстро заметили, что, как правило, несколько билетов в одни руки кассир продаёт быстрее, чем когда эти же билеты продаются по одному. Поэтому они предложили нескольким подряд стоящим людям отдавать деньги первому из них, чтобы он купил билеты на всех.

Однако для борьбы со спекулянтами кассир продавала не более 33 билетов в одни руки, поэтому договориться таким образом между собой могли лишь 22 или 33 подряд стоящих человека.

Известно, что на продажу i-му человеку из очереди одного билета кассир тратит Ai секунд, на продажу двух билетов — Bi секунд, трёх билетов — Ci секунд. Напишите программу, которая подсчитает минимальное время, за которое могли быть обслужены все покупатели.

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

Входные данные

На вход программы поступает сначала число N — количество покупателей в очереди (1≤N≤5000). Далее идут N троек натуральных чисел Ai, Bi, Ci. Каждое из этих чисел не превышает 3600. Люди в очереди нумеруются, начиная от кассы.

Выходные данные

Требуется вывести одно число — минимальное время в секундах, за которое могли быть обслужены все покупатели.

Примеры

Ввод

Вывод

5 12

5 10 15

2 10 15

5 5 5

20 20 1

20 1 1

Программа:

N = int(input())

times = []

for i in range(N):

times.append(list(map(int, input().split())))

a = [times[i][0] for i in range(len(times))]

b = [times[i][1] for i in range(len(times))]

c = [times[i][2] for i in range(len(times))]

d = [0] * (N+1)

d[1] = a[0]

if N > 1:

d[2] = min(a[0]+a[1], b[0])

if N > 2:

d[3] = min(d[2]+a[2], d[1]+b[1], c[0])

for i in range(N+1):

if i >=4:

d[i] = (min(d[i-1]+a[i-1], d[i-2]+b[i-2], d[i-3]+c[i-3]))

print(d[N])

Компьютерная игра

Вы можете вспомнить хоть одного своего знакомого до двадцатилетнего возраста, который в детстве не играл в компьютерные игры? Если да, то может быть вы и сами не знакомы с этим развлечением? Впрочем, трудностей при решении этой задачи это создать не должно.

Во многих старых играх с двумерной графикой можно столкнуться с подобной ситуацией. Какой-нибудь герой прыгает по платформам (или островкам), которые висят в воздухе. Он должен перебраться от одного края экрана до другого. При этом при прыжке с одной платформы на соседнюю у героя уходит |y2–y1| единиц энергии, где y1 и y2 — высоты, на которых расположены эти платформы. Кроме того, у героя есть суперприём, который позволяет перескочить через платформу, но на это затрачивается 3⋅|y3–y1|единиц энергии. Конечно же, энергию следует расходовать максимально экономно.

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

Входные данные

В первой строке записано количество платформ n (1 ≤ n ≤ 30000). Вторая строка содержит n натуральных чисел, не превосходящих 30000 — высоты, на которых располагаются платформы.

Выходные данные

Выведите единственное число — минимальное количество энергии, которую должен потратить игрок на преодоление платформ (конечно же, в предположении, что cheat-коды использовать нельзя).

Примеры

Ввод

Вывод

2 100 1

99

3 1 100 80

119

Программа:

n = int(input())

a = list(map(int, input().split()))

dp = [0] * n

dp[1] = abs(a[1] - a[0])

for i in range(2, n):

dp[i] = min(dp[i-1] + abs(a[i] - a[i-1]), dp [i-2] + 3 * abs(a[i] - a[i-2]))

print(dp[n-1])

Энты

Энты были созданы в Первоначальную эпоху вместе с другими обитателями Средиземья. Эльфийские легенды гласят, что когда Варда зажгла звёзды и пробудились эльфы, вместе с ними пробудились и энты в Великих Лесах Арды.

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

Эльфы выработали хорошую технику обучения энтов своему языку. Первый энт, которого обучили эльфы, выучил всего два слова — «tancave» (да) и «la» (нет). Обученный энт выбрал одного старого и одного молодого энта, не умеющих говорить, и обучил их всем словам, которые знал сам. Затем обучение этих двух энтов продолжили сами эльфы. Каждый обучившийся у эльфов энт снова выбирал из неговорящих сородичей одного старого и одного молодого, обучал их всем словам, которые знал, передавал эльфам и так далее.

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

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

Входные данные Даны натуральные числа K и P (K≤106, 1≤P≤109 ), записанные через пробел.

Выходные данные

Мы понимаем, что число энтов, знающих в точности K слов, может быть слишком велико, поэтому просим вывести лишь количество энтов, знающих ровно K слов, по модулю P.

Примеры

Ввод

Вывод

4 10 2

8 10 5

360 1000 179

 

Программа:

def get_ents_num_modulo_p(k, p):

if k < 2:

return 0

num = (k+1)*[0]

num[2]=1

for i in range(2,k):

num[i+1] = (num[i+1] + num[i]) % p

if 2*i <= k:

num[2*i] = num[i]

return num[k]

k, p = map(int,input().split())

print(get_ents_num_modulo_p(k, p))

Наибольшее число

Напишите программу, которая определяет, есть ли во введённой строке десятичные цифры, и выводит наибольшее число, которое можно составить из этих цифр. Ведущих нулей в числе быть не должно (за исключением числа 0, запись которого содержит ровно одну цифру). Если цифр нет, программа должна вывести число −1.

Использовать встроенные сортировки запрещено.

Входные данные

Входная строка содержит произвольные символы.

Выходные данные

Программа должна вывести наибольшее число, которое можно составить из присутствующих в строке десятичных цифр, или число −1, если цифр нет.

Примеры

Ввод

Вывод

Day 10, mice 8: "Year" 7 is a mistake 91.

987110

Программа:

res = list(filter(lambda x:x.isdigit(), input()))

print(''.join(sorted(res,reverse = True)) if res else -1)

1. file0.docx (170,1 КБ)

Опубликовано: 30.10.2024