Условие:
Есть массив 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 + ... + an
Шаг 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: Реализация
Теперь давайте реализуем это в коде:
Теперь проверим, как работает наш алгоритм на примерах, приведенных в задаче. Мы должны убедиться, что он возвращает правильные результаты для каждого набора входных данных. Таким образом, мы получили решение, которое считает количество подходящих позиций для каждого набора входных данных.