Есть массив a, состоящий из n целых положительных чисел и целое положительное число k. Из массива a создается массив b по следующим правилам: массив b содержит n⋅k чисел; первые n чисел массива b совпадают с числами массива a, то есть bi=ai для i≤n ; для

1 октября 2025
Программирование

Условие:

Есть массив a, состоящий из n целых положительных чисел и целое положительное число k. Из массива a создается массив b

по следующим правилам:

массив b

содержит n⋅k
чисел;
первые n
чисел массива b совпадают с числами массива a, то есть bi=ai для i≤n
;
для любого i>n
выполняется bi=bi−n

.

Например, если a=[2,3,1,4]
и k=3, то b=[2,3,1,4,2,3,1,4,2,3,1,4]

.

Дано число x
. Необходимо посчитать количество таких позиций l (1≤l≤n⋅k), для которых найдется такая позиция r≥l, что сумма элементов массива b на отрезке [l,r] составит не менее x (то есть bl+bl+1+⋯+br≥x

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

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число t
(1≤t≤104

) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит три целых числа n
, k, x (1≤n,k≤105; 1≤x≤1018

).

Вторая строка каждого набора входных данных содержит n
целых положительных чисел ai (1≤ai≤108

).

Дополнительные ограничения на входные данные:

сумма n

по всем наборам входных данных не превышает 2⋅105
;
сумма k
по всем наборам входных данных не превышает 2⋅105

.

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

Для каждого набора входных данных выведите одно целое число — количество подходящих позиций l
в массиве b

.
Пример
Входные данные
Скопировать

7
5 3 10
3 4 2 1 5
15 97623 1300111
105 95 108 111 118 101 95 118 97 108 111 114 97 110 116
1 100000 1234567891011
1
1 1 1
1
1 1 1
2
2 1 2
1 1
2 1 5
2 1

Выходные данные
Скопировать

12
1452188
0
1
1
1
0

Примечание

В первом наборе входных данных массив b

выглядит так:

[3,4,2,1,5,3,4,2,1,5,3,4,2,1,5]

Существует 12
позиций l, для которых найдется подходящая позиция r

. Вот некоторые (не все) из них:

l=1

, для которой есть позиция r=6, сумма на отрезке [1,6] равна 18
;
l=2
, для которой есть позиция r=5, сумма на отрезке [2,5] равна 12
;
l=6
, для которой есть позиция r=9, сумма на отрезке [6,9] равна 10.

Решение:

Для решения данной задачи, давайте разберем шаги, которые нам нужно выполнить.

Шаг 1: Понимание задачи

У нас есть массив a длиной n, который повторяется k раз для создания массива b длиной n * k. Нам нужно найти количество позиций l в массиве b, для которых существует позиция r (где r = l), такая что сумма элементов от l до r не менее x.

Шаг 2: Определение суммы элементов

Сначала определим сумму элементов массива a:

S = a1 + a2 + ... + a_n

Шаг 3: Определение количества подходящих позиций

Поскольку массив b является циклическим, мы можем использовать свойства суммы для упрощения вычислений. Если мы знаем сумму S, то:

- Для l от 1 до n, мы можем просто проверять, сколько элементов нам нужно добавить, чтобы сумма стала больше или равна x.
- Если S x, то нам нужно будет использовать несколько полных циклов массива a (то есть несколько повторений массива b).

Шаг 4: Алгоритм

1. Для каждого l от 1 до n:
- Начинаем с текущей суммы current_sum = 0.
- Увеличиваем current_sum добавляя элементы массива b начиная с позиции l.
- Если current_sum становится больше или равным x, фиксируем позицию l как подходящую.
- Если current_sum не достигает x после полного прохода по массиву b, переходим к следующему l.

2. Если S = x, то для каждого l мы можем просто найти максимальное r так, чтобы сумма от l до r была больше или равна x.

Шаг 5: Реализация

Теперь давайте реализуем это в коде:

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