Найти индекс элемента списка сумма которого и k следующих элементов равна заданной

@OnikS228 · Регистрация: 23.01.2016

Author24 — интернет-сервис помощи студентам

Дан массив целых чисел a[1], a[2], ..., a[n] и натуральные числа k и m. Укажите минимальное значение i, для которого a[i] + a[i+1] + ... + a[i + k] = m (то есть сумма k + 1 подряд идущих элементов массива равна m). Если такого значения нет, то выведите 0. Вложенные циклы не использовать.

Входные данные
На вход программе сначала подаются значения n, k и m (m <= 10000, 0 < k < n <= 30000; n - количество элементов в массиве). В следующей строке входных данных расположены сами элементы массива - целые числа, по модулю не превосходящие 100.

Выходные данные
Выведите ответ на задачу.

Примеры
входные данные
4 1 22
9 13 10 -11
выходные данные
1

Помогите пожалуйста решить

Jabbson · 16.03.2016, 20:33

а что у Вас именно не получается?

@OnikS228 · 17.03.2016, 15:47 **[ТС]**

Вообще ничего, даже не знаю с чего начать

@Marinero · 17.03.2016, 17:33

Начинают со считывания данных, потом перебор массива с вычислением суммы и сравнением с заданным значением.

@OnikS228 · 18.03.2016, 22:40 **[ТС]**

Мой вариант:

Python

1
2
3

n, k, m=(int(x) for x in input().split())
a=[int(x) for x in input().split()]
print(min(i for i in range(0,m-k-1) if sum(a[i:i+k+1])==int(m)))

Но он не рабочий :c

@Zuzik · 19.03.2016, 01:30

Сообщение от OnikS228

print(min(i for i in range(0,m-k-1) if sum(a[i:i+k+1])==int(m)))

Python

1	print(min(i for i in range(0,n-k-1) if sum(a[i:i+k+1])==m))

буквочку походу перепутали, вместо m n должно быть поидее говоря.

@Marinero · 19.03.2016, 11:29

OnikS228, в первой строке можно не использовать генератор, т.к. split уже возвращает список
min будет перебирать до конца списка и в общем случае это не здорово — нужно ведь только одно 1-е значение.Если k достаточно большое то имеет смысл рассчитать сумму элементов сразу от 1-го, а потом при каждой итеррации изменять уже полученную сумму (отнимать a[i-1] и добавлять a[i+k])

Python

s = sum(a[:i+k+1])
for i in range(n - k - 1):
    if s == m:
        print(i + 1)
        break
    s += (a[i+k+1] - a[i])
else:
    print(0)

@OnikS228 · 19.03.2016, 14:27 **[ТС]**

Python

n, k, m = (int(x) for x in input().split())
a = [int(x) for x in input().split()]
s = sum(a[:i+k+1])
for i in range(n - k - 1):
    if s == m:
        print(i + 1)
        break
    s += (a[i+k+1] - a[i])
else:
    print(0)

При таком варианте в 3 строке ошибка, что i не найдена

Python

n, k, m = (int(x) for x in input().split())
a = [int(x) for x in input().split()]
for i in range(n - k - 1):
    s = sum(a[:i+k+1])
    if s == m:
        print(i + 1)
        break
    s += (a[i+k+1] - a[i])
else:
    print(0)

При таком коде ответ при данных вводных данных получается верный, но тестирующая система при проверке получает неправильные ответы

@OnikS228 · 20.03.2016, 16:12 **[ТС]**

АКТУАЛЬНО

@vdm_mar · 20.03.2016, 17:20

Вы в первом своем варианте зря затащили i в строку 3. Первая сумма: s = sum(a[:k+1]). А во втором варианте, сумма постоянно будет увеличиваться за счет прибавления нового члена.

Python

n, k, m = (int(x) for x in input().split())
a = [int(x) for x in input().split()]
s = sum(a[:k+1])
for i in range(n - k - 1):
    if s == m:
        print(i + 1)
        break
    s += (a[i+k+1] - a[i])
else:
    print(0)

@OnikS228 · 20.03.2016, 17:28 **[ТС]**

теперь стали все правильными, кроме одного(

@vdm_mar · 20.03.2016, 18:02

в строке 4 не до конца проходит цикл, там должно быть range(n - k)

Python

n, k, m = (int(x) for x in input().split())
a = [int(x) for x in input().split()]
s = sum(a[:k+1])
for i in range(n - k):
    if s == m:
        print(i + 1)
        break
    s += (a[i+k+1] - a[i])
else:
    print(0)

@OnikS228 · 20.03.2016, 18:18 **[ТС]**

Хах, теперь ещё меньше правильных

Добавлено через 7 минут
Но теперь не "неправильный ответ", а "ошибка во время исполнения программы"

@vdm_mar · 20.03.2016, 18:24

ну ищите "мелочи" в оформлении, идея Marinero стопудово классная
попробуйте сместить print(0) в for

Python

n, k, m = (int(x) for x in input().split())
a = [int(x) for x in input().split()]
s = sum(a[:k+1])
for i in range(n - k):
    if s == m:
        print(i + 1)
        break
    elif i == n - k - 1:
        print(0)
    else:
        s += (a[i+k+1] - a[i])

@Semen-Semenich · 21.03.2016, 17:33

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

Добавлено через 3 часа 1 минуту
этот код вообще ни о чем. что вы пытаетесь найти?

Python

s = sum(a[:k+1])
for i in range(n - k):
    if s == m:
        print(i + 1)
        break

задали значение s вне цикла и теперь пытаетесь в цикле его сравнить с m? так всегда будет falhe если случайно по совпадению сумма первых к элементов будет равна м так тогда и весь цикл

Python

1 2	for i in range(n - k): if s == m

будет истина и вы получите первую i+1

@Marinero · 22.03.2016, 12:23

Сообщение от Marinero

s = sum(a[:i+k+1])

Конечно же

Python

3	s = sum(a[:k+1])

Сообщение от Semen-Semenich

задали значение s вне цикла и теперь пытаетесь в цикле его сравнить с m?

С какой радости Вы выбросили строку из кода и делаете выводы?

Python

8	s += (a[i+k+1] - a[i])

@Semen-Semenich · 22.03.2016, 14:50

пардон. не досмотрел.хотя при данных 4 2 22 9 13 10 -11 а так же 4 3 22 9 13 10 -11 результат 0 хотя 13+10+(-11) и есть 22 тут уж и два подряд идущих и три проверял.может что то недопонимаю в условии???

@Marinero · 22.03.2016, 17:01

Semen-Semenich, когда это 13 + 10 = 23 - 11 = 12 стало равно 22?

@Semen-Semenich · 22.03.2016, 17:20

прошу простить и понять сонный еще был((

@OnikS228 3 / 2 / 0 Регистрация: 23.01.2016 Сообщений: 98
		1
	Найти индекс элемента списка сумма которого и k следующих элементов равна заданной 16.03.2016, 20:23. Показов 10676. Ответов 18 Метки нет (Все метки) Дан массив целых чисел a[1], a[2], ..., a[n] и натуральные числа k и m. Укажите минимальное значение i, для которого a[i] + a[i+1] + ... + a[i + k] = m (то есть сумма k + 1 подряд идущих элементов массива равна m). Если такого значения нет, то выведите 0. Вложенные циклы не использовать. Входные данные На вход программе сначала подаются значения n, k и m (m <= 10000, 0 < k < n <= 30000; n - количество элементов в массиве). В следующей строке входных данных расположены сами элементы массива - целые числа, по модулю не превосходящие 100. Выходные данные Выведите ответ на задачу. Примеры входные данные 4 1 22 9 13 10 -11 выходные данные 1 Помогите пожалуйста решить 0

Jabbson 5898 / 3355 / 1035 Регистрация: 03.11.2009 Сообщений: 10,003
	16.03.2016, 20:33	2
	а что у Вас именно не получается? 0

@OnikS228 3 / 2 / 0 Регистрация: 23.01.2016 Сообщений: 98
	17.03.2016, 15:47 [ТС]	3
	Вообще ничего, даже не знаю с чего начать 0

@Marinero 2795 / 2038 / 682 Регистрация: 02.03.2015 Сообщений: 6,509
	17.03.2016, 17:33	4
	Начинают со считывания данных, потом перебор массива с вычислением суммы и сравнением с заданным значением. 0

@OnikS228 3 / 2 / 0 Регистрация: 23.01.2016 Сообщений: 98
	20.03.2016, 16:12 [ТС]	9
	АКТУАЛЬНО 0

@OnikS228 3 / 2 / 0 Регистрация: 23.01.2016 Сообщений: 98
	20.03.2016, 17:28 [ТС]	11
	теперь стали все правильными, кроме одного( 0

@OnikS228 3 / 2 / 0 Регистрация: 23.01.2016 Сообщений: 98
	20.03.2016, 18:18 [ТС]	13
	Хах, теперь ещё меньше правильных Добавлено через 7 минут Но теперь не "неправильный ответ", а "ошибка во время исполнения программы" 0

@Semen-Semenich 4937 / 3290 / 1140 Регистрация: 21.03.2016 Сообщений: 8,069
	22.03.2016, 14:50	17
	пардон. не досмотрел.хотя при данных 4 2 22 9 13 10 -11 а так же 4 3 22 9 13 10 -11 результат 0 хотя 13+10+(-11) и есть 22 тут уж и два подряд идущих и три проверял.может что то недопонимаю в условии??? 0

@Marinero 2795 / 2038 / 682 Регистрация: 02.03.2015 Сообщений: 6,509
	22.03.2016, 17:01	18
	Semen-Semenich, когда это 13 + 10 = 23 - 11 = 12 стало равно 22? 0

@Semen-Semenich 4937 / 3290 / 1140 Регистрация: 21.03.2016 Сообщений: 8,069
	22.03.2016, 17:20	19
	прошу простить и понять сонный еще был(( 0