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", определяя, какую ноту нужно играть в заданные моменты времени.