Предметный тур. Информатика. 3 этап
Имя входного файла: стандартный ввод или input.txt.
Имя выходного файла: стандартный вывод или output.txt.
Ограничение по времени выполнения программы: 1 с.
Ограничение по памяти: 256 Мбайт.
Для синтеза молекулы ДНК требуется потратить \(x\) энергии для добавления нуклеотида в первую спираль и \(y\) энергии — во вторую. Чтобы увеличить длину существующей молекулы ДНК, необходимо добавить один нуклеотид в первую и вторую спирали одновременно. Какой максимальной длины можно синтезировать молекулу ДНК, если сейчас есть \(k\) энергии?
Формат входных данных
В первой строке содержится целое число \(k\) \((1 \leqslant k \leqslant 10^9)\) — количество энергии, которое есть в данный момент.
Во второй строке содержится целое число \(x\) \((1 \leqslant x \leqslant 10^9)\) — количество энергии, которое нужно для добавления одного нуклеотида в первую спираль.
В третьей строке содержится целое число \(y\) \((1 \leqslant y \leqslant 10^9)\) — количество энергии, которое нужно для добавления одного нуклеотида во вторую спираль.
Формат выходных данных
В единственной строке выведите одно число — максимальную длину молекулы ДНК, которую сможем синтезировать.
Тестовые данные
| Номер теста | Стандартный ввод | Стандартный вывод |
|---|---|---|
1 |
3 2 1 |
1 |
2 |
5 1 10 |
0 |
Для добавления одной пары нуклеотидов (то есть увеличения длины на 1) требуется \(x + y\) энергии.
Если есть \(k\) энергии, то количество пар нуклеотидов, которые можно добавить, равно целой части от деления \(k\) на \((x + y)\).
Пример программы-решения
Ниже представлено решение на языке Python.
k = int(input())
x = int(input())
y = int(input())
print(k // (x + y))Имя входного файла: стандартный ввод или input.txt.
Имя выходного файла: стандартный вывод или output.txt.
Ограничение по времени выполнения программы: 2 с.
Ограничение по памяти: 256 Мбайт.
В научной лаборатории \(n\) кабинетов. Изначально команда Ивана располагалась в \(k\)-м кабинете.
Но сегодня утром руководство решило всех перемешать и выпустило \(m\) распоряжений о том, что команды, располагающиеся в кабинетах под номерами \(a_i\) и \(b_i\), меняют местами.
Определите, в каком кабинете окажется команда Ивана после \(m\) распоряжений, если они выполняются от первого к последнему.
Формат входных данных
В первой строке через пробел вводятся три целые числа \(n, k\) и \(m\) (\(1 \leqslant n \leqslant 10^5\), \(1\leqslant k \leqslant n\), \(1\leqslant m \leqslant 10^5\)) — количество кабинетов, кабинет команды Ивана и количество распоряжений.
В \(i\)-й из следующих \(m\) строк содержатся два целых числа \(a_i, b_i\) (\(1\leqslant a_i\), \(b_i\leqslant n\), \(a_i \neq b_i\)) — номера кабинетов, которые должны поменяться по \(i\)-му распоряжению.
Формат выходных данных
Выведите единственное число — номер кабинета, в котором будет находиться Иван после всех распоряжений.
Тестовые данные
| Номер теста | Стандартный ввод | Стандартный вывод |
|---|---|---|
1 |
3 1 2 1 2 2 3 |
3 |
Вместо того чтобы моделировать перемещения всех команд (что было бы неэффективно при больших \(n\)), достаточно отслеживать только текущее положение команды Ивана.
Если в распоряжении есть текущий кабинет Ивана, то меняем его, иначе ничего не делаем.
Пример программы-решения
Ниже представлено решение на языке Python.
n, k, m = map(int, input().split())
nums = [(i + 1) for i in range(n)]
for i in range(m):
a, b = map(int, input().split())
nums[a - 1], nums[b - 1] = nums[b - 1], nums[a - 1]
print(nums.index(k) + 1)Имя входного файла: стандартный ввод или input.txt.
Имя выходного файла: стандартный вывод или output.txt.
Ограничение по времени выполнения программы: 1 с.
Ограничение по памяти: 256 Мбайт.
У Кати есть две любимые линейные молекулы одинаковой длины. Коля решил подарить Кате новую линейную молекулу, причем на \(i\)-ю позицию он выберет либо \(i\)-й атом из первой молекулы, либо \(i\)-й атом из второй молекулы.
При этом Коля считает, что молекула будет наиболее красивой, если в ней какой-то атом встретится наибольшее возможное число раз.
Помогите Коле получить самую красивую молекулу, которую Коля может подарить Кате.
Формат входных данных
Первая строка содержит одну строку, состоящую из заглавных латинских букв — первую любимую молекулу Кати.
Вторая строка содержит одну строку, состоящую из заглавных латинских букв — вторую любимую молекулу Кати.
Гарантируется, что длина первой молекулы равна длине второй молекулы и не превосходит 200000.
Формат выходных данных
Выведите самую красивую молекулу, которую может подарить Коля Кате. Если таких молекул несколько, то выведите любую.
Тестовые данные
| Номер теста | Стандартный ввод | Стандартный вывод |
|---|---|---|
1 |
ABRACADABRA ABACABADABA |
ABAAAAAAARA |
Рассматриваем все возможные комбинации букв от A до Z и сохраняем наилучший результат. Чтобы увеличить количество повторяющихся букв, следуем правилу: если необходимая буква уже присутствует в какой-либо из строк, выбираем именно ее; в противном случае можно выбрать любую букву.
Пример программы-решения
Ниже представлено решение на языке Python.
s1 = input()
s2 = input()
maxCh = 'A'
maxKol = 0
for ch in "QWERTYUIOPASDFGHJKLZXCVBNM":
kol = 0
for i in range(len(s1)):
if ch == s1[i] or ch == s2[i]:
kol += 1
if kol > maxKol:
maxKol = kol
maxCh = ch
for i in range(len(s1)):
if maxCh == s1[i] or maxCh == s2[i]:
print(maxCh, end='')
else:
print(s1[i], end='')
print()Имя входного файла: стандартный ввод или input.txt.
Имя выходного файла: стандартный вывод или output.txt.
Ограничение по времени выполнения программы: 2 с.
Ограничение по памяти: 512 Мбайт.
Ученые разработали новую линейную молекулу. Она представляет собой \(n\) последовательных атомов. Эффективность \(i\)-го атома составляет \(a_i\). Чтобы подсчитать инновационность линейной молекулы, надо воспользоваться формулой: \[\sum\limits_{1 \leqslant i < j < k \leqslant n} a_i \cdot a_j \cdot a_k \text{.}\]
Помогите ученым рассчитать инновационность линейной молекулы. Так как ответ может оказаться большим, посчитайте значение инновационности по модулю 1000000007.
Формат входных данных
В первой строке дано одно целое число \(n\) (\(3 \leqslant n \leqslant 10^6\)) — количество атомов в линейной молекуле.
Во второй строке даны \(n\) целых чисел \(a_i\) (\(0 \leqslant a_i \leqslant 10^6\)) — соответствующие эффективности атомов.
Формат выходных данных
Выведите требуемое число по модулю 1000000007.
Тестовые данные
| Номер теста | Стандартный ввод | Стандартный вывод |
|---|---|---|
1 |
3 1 2 3 |
6 |
2 |
4 0 5 6 7 |
210 |
Рассмотрим каждую тройку индексов \((i, j, k)\) в сумме и зафиксируем \(j\). Для фиксированного \(j\) в сумму входят произведения по всем \(i < j\) и всем \(k > j\).
Иными словами, перепишем сумму как: \[\sum\limits_{j = 1}^n \Big(a_j \cdot \sum\limits_{i < j, k > j} a_i \cdot a_k\Big).\]
Поскольку выбор индекса \(i\) не зависит от выбора индекса \(k\) (и наоборот), можно переписать это как \[\sum\limits_{j = 1}^n \Big(a_j \cdot \big(\sum\limits_{i = 1}^{j - 1} a_i\big) \cdot \big(\sum\limits_{k = j + 1}^n a_k\big)\Big).\]
Заметим, что теперь каждое такое слагаемое можно считать за \(\mathcal{O}(1)\) с \(\mathcal{O}(n)\) предподсчета. Посчитаем префиксные суммы \(b_i = a_1 + \ldots + a_i\) в одном цикле как \(b_i = b_{i-1} + a_i\). Тогда теперь нам осталось просуммировать слагаемые вида \[a_j \cdot b_{j-1} \cdot (b_n - b_j)\] по всем \(j\) от \(1\) до \(n\). Суммарное время работы — \(\mathcal{O}(n)\).
Пример программы-решения
Ниже представлено решение на языке Python.
import sys
import random
MOD = 1000000007
def add(a, b):
a += b
if a >= MOD:
a -= MOD
return a
def sum(a, b):
return add(a, b)
def mult(a, b):
return (a * b) % MOD
n = int(input().strip())
arr = list(map(int, input().split()))
pref = [0]
suff = [0]
for i in range(n):
pref.append(sum(pref[-1], arr[i]))
suff.append(sum(suff[-1], arr[n - 1 - i]))
ans = 0
for i in range(n):
ans = add(ans, mult(arr[i], mult(pref[i], suff[n - 1 - i])))
print(ans)
Имя входного файла: стандартный ввод или input.txt.
Имя выходного файла: стандартный вывод или output.txt.
Ограничение по времени выполнения программы: 0,5 с.
Ограничение по памяти: 256 Мбайт.
Во время эксперимента на столе стояли два таймера. Один таймер завели на \(x\) с, второй — на \(y\) с. Каждую секунду время, которое показывают таймеры, уменьшается на единицу. Посчитайте, сколько раз за время эксперимента будет момент, что время, которое показывает один таймер, нацело делится на время, которое показывает другой таймер. (Когда один из таймеров покажет 0, эксперимент прекратится.)
Формат входных данных
В единственной строке через пробел вводятся целые числа \(x\) и \(y\) (\(1 \leqslant x, y \leqslant 10^9\)) — оставшееся время на первом и втором таймере соответственно.
Формат выходных данных
В единственной строке выведите одно целое число — количество моментов, когда время на одном таймере будет нацело делиться на время на втором таймере.
Тестовые данные
| Номер теста | Стандартный ввод | Стандартный вывод |
|---|---|---|
1 |
3 30 |
2 |
2 |
16 4 |
4 |
Количество искомых моментов равно количеству общих делителей разницы \(d = b - a\) и меньшего числа \(a\).
Для доказательства есть два случая:
- Для \(a = b\): в каждый момент \(t < a\) значения таймеров равны и делятся друг на друга, поэтому ответ \(a\).
Для \(a \neq b\):
- Ищем делители \(d = b - a\).
- Каждый делитель \(k\) должен удовлетворять \(k \leqslant a\).
- Для каждого такого \(k\) существует момент \(t = a - k\), когда: \[\begin{aligned} a - t &= k, \\ b - t &= k + d = k + (b - a). \end{aligned}\] При этом \(k + (b - a)\) делится на \(k\), так как \(b - a\) делится на \(k\).
Пример программы-решения
Ниже представлено решение на языке Python.
a, b = map(int, input().split())
if a > b:
a, b = b, a
d = b - a
i = 1
res = 0
while i * i <= d:
if d % i == 0:
if i <= a:
res += 1
if i * i != d and d // i <= a:
res += 1
i += 1
if a == b:
res = a
print(res)
