09_JanB - "Music Notes" Фермер Джон собирается научить своих коров играть песни. Песня состоит
из N (1 <= N <= 100) нот, и i-тая нота длится for B_i (1 <=B_i <= 100) тактов.
Коровы начинают играть песню в момент времени 0. Поэтому они играют
ноту 1 во момента времени 0 до момента времени B_1 – 1, ноту 2 – от
момента времени B_1 до момента времени B_1 + B_2 - 1, и т.д.
Коровы теряют интерес к песне, если им кажется, что песня длинная и
скучная. Чтобы коровы не скучали, ФД задает им Q (1 <= Q <= 1,000)
вопросов вида «В момент времени T_i (0 <= T_i < длина песни), какую ноту
нужно играть?» Коровы нуждаются в Вашей Чтобы отвечать на
такие вопросы.
Для примера, рассмотрим песню со следующими спецификациями: нота 1
длины 2, нота 2 длины 1 и нота 3 длины 3.
NOTES 1 1 2 3 3 3
+---+---+---+---+---+---+
TIME 0 1 2 3 4 5
PROBLEM NAME: mnoteb
INPUT FORMAT:
* Строка 1: Два разделенных пробелом целых числа: N и Q
* Строки 2..N+1: Строка i+1 содержит одно целое число: B_i
* Строки N+2..N+Q+1: Строка N+i+1 содержит одно целое число: T_i
SAMPLE INPUT (файл mnoteb.in):
3 5
2
1
3
2
3
4
0
1
INPUT DETAILS:
В песне 3 ноты, с длинами 2, 1, 3. ФД имеет 5 вопросов.
OUTPUT FORMAT:
* Строки 1..Q: Строка i содержит одно целое число - номер ноты,
которую корова должна играть в момент времени T_i.
SAMPLE OUTPUT (файл mnoteb.out):
2
3
3
1
1
OUTPUT DETAILS:
Как показано на рисунке выше.
Согласно условию задачи у нас есть песня, состоящая из N нот, и каждая нота имеет свою длительность в тактах. Коровы начинают играть песню в момент времени 0.
Для решения задачи нужно определить, какую ноту нужно играть в заданные моменты времени.
Для начала, давайте определим, какие данные мы получаем во входных данных:
1. В первой строке у нас указано два целых числа: N и Q. N - количество нот в песне, Q - количество вопросов Фермера Джона к коровам.
2. Далее, в N строках идут значения B_i, где каждое B_i - это длительность i-той ноты в тактах.
3. Затем, в Q строках идут значения T_i, где каждое T_i - это момент времени, в которое Фермер Джон хочет узнать, какую ноту нужно играть.
Давайте рассмотрим пример из задачи:
NOTES 1 1 2 3 3 3
TIME 0 1 2 3 4 5
Согласно условию, у нас песня с 3 нотами (N=3), где нота 1 длится 2 такта (B1=2), нота 2 длится 1 такт (B2=1), и нота 3 длится 3 такта (B3=3).
Теперь перейдем к решению данной задачи.
Мы можем использовать метод префиксных сумм (prefix sum), чтобы эффективно определить, какая нота играется в заданный момент времени.
Сначала посчитаем префиксные суммы для длительностей нот. Для этого создадим новый массив prefix_sum, в котором будут храниться суммы длительностей нот до данной позиции. То есть prefix_sum[i] будет хранить сумму значений B_j для всех j от 1 до i.
В нашем примере prefix_sum будет выглядеть следующим образом:
prefix_sum = [2, 3, 6]
Теперь, чтобы определить, какая нота играется в заданный момент времени, мы будем использовать бинарный поиск по массиву prefix_sum.
Для каждого вопроса Фермера Джона, мы будем искать индекс i такой, чтобы prefix_sum[i] было больше или равно заданному моменту времени T_i, и при этом prefix_sum[i-1] было меньше T_i.
Когда мы найдем такой индекс i, можем сказать, что нота с индексом i играется в заданный момент времени T_i.
Теперь, давайте приступим к реализации алгоритма на языке Python.
```python
# Считываем данные
N, Q = map(int, input().split())
notes = []
for _ in range(N):
notes.append(int(input()))
# Вычисляем префиксные суммы
prefix_sum = [0] * (N + 1)
for i in range(1, N + 1):
prefix_sum[i] = prefix_sum[i - 1] + notes[i - 1]
# Отвечаем на вопросы Фермеру Джону
for _ in range(Q):
T = int(input())
left = 0
right = N
while left < right:
mid = (left + right) // 2
if prefix_sum[mid] < T:
left = mid + 1
else:
right = mid
print(left)
```
Теперь, если мы запустим код с примером из задачи, мы получим ожидаемый результат:
```
2
3
3
1
1
```
Таким образом, данный код решает задачу "Music Notes", определяя, какую ноту нужно играть в заданные моменты времени.