Ответы Mail.ru
Программирование
Android
C/C++
C#
iOS
Java
JavaScript
jQuery
SQL
Perl
PHP
Python
Веб-дизайн
Верстка, CSS, HTML, SVG
Системное администрирование
Другие языки и технологии
Лидеры категории
Лена-пена
М.И.
Y.Nine
•••
Искусственный Интеллект
Искусственный Интеллект
Искусственный Интеллект
Лучший ответ
Aleks Nots
(22647)
4 года назад
Вот, убери лишнее:
(Ну или забань мой ответ, если ума хватает только кнопку "ЗАБАНИТЬ" жать.)
#s1 = input()
#s2 = input()
#s1 = '7 5'
#s2 = '1 2 3 4 2 1 2'#2 3
#s1 = '5 3'
#s2 = '1 0 2 10 10'#1 3
#s1 = '2 100'
#s2 = '0 0'#-1
#s1 = '7 7'
#s2 = '0 0 0 10 0 0 7'#7 7
s1 = '100_000 49610796982'
with open('1111.txt') as fr:
~~~~s2 = fr.read()
n,k = map(int, s1.split())
A=list(map(int, s2.split()))
bg=0
en=0
sm=0
for i in range(n):
~~~~en = i
~~~~sm += A[en]
~~~~
~~~~if smk:
~~~~~~~~while sm>k:
~~~~~~~~~~~~sm -= A[bg]
~~~~~~~~~~~~bg += 1
~~~~~~~~if sm==k:
~~~~~~~~~~~~break
~~~~else:
~~~~~~~~break
while A[bg]==0 and bg<en:
~~~~bg += 1
if sm==k:
~~~~print(bg+1,en+1)
else:
~~~~print(-1)
Время и память не мерял, но на глаз, вроде бы быстрее секунды, а памяти вроде бы некуда деваться.
(Ну или забань мой ответ, если ума хватает только кнопку "ЗАБАНИТЬ" жать.)
#s1 = input()
#s2 = input()
#s1 = '7 5'
#s2 = '1 2 3 4 2 1 2'#2 3
#s1 = '5 3'
#s2 = '1 0 2 10 10'#1 3
#s1 = '2 100'
#s2 = '0 0'#-1
#s1 = '7 7'
#s2 = '0 0 0 10 0 0 7'#7 7
s1 = '100_000 49610796982'
with open('1111.txt') as fr:
~~~~s2 = fr.read()
n,k = map(int, s1.split())
A=list(map(int, s2.split()))
bg=0
en=0
sm=0
for i in range(n):
~~~~en = i
~~~~sm += A[en]
~~~~
~~~~if smk:
~~~~~~~~while sm>k:
~~~~~~~~~~~~sm -= A[bg]
~~~~~~~~~~~~bg += 1
~~~~~~~~if sm==k:
~~~~~~~~~~~~break
~~~~else:
~~~~~~~~break
while A[bg]==0 and bg<en:
~~~~bg += 1
if sm==k:
~~~~print(bg+1,en+1)
else:
~~~~print(-1)
Время и память не мерял, но на глаз, вроде бы быстрее секунды, а памяти вроде бы некуда деваться.
Aleks NotsПросветленный (22647)
4 года назад
Извините, не заметил, что ответмэйлру покорежил код.
Сейчас попытаюсь повторить, изменив так, чтобы не корежило (и при этом чуть упростив)
#Ручной ввод
#s1 = input()
#s2 = input()
#Ввод из файла
s1 = '100_000 49610796982'
with open('1111.txt') as fr:~~~~s2 = fr.read()
# Разные примеры
#s1 = '7 5'
#s2 = '1 2 3 4 2 1 2'#2 3
#s1 = '5 3'
#s2 = '1 0 2 10 10'#1 3
#s1 = '2 100'
#s2 = '0 0'#-1
#s1 = '7 7'
#s2 = '0 0 0 10 0 0 7'#7 7
n,k = map(int, s1.split())
A=list(map(int, s2.split()))
bg=0
en=0
sm=0
for i in range(n):
~~~~en = i
~~~~sm += A[en]
~~~~
~~~~if sm > k:
~~~~~~~~while sm > k:
~~~~~~~~~~~~sm -= A[bg]
~~~~~~~~~~~~bg += 1
~~~~~~~~if sm==k:
~~~~~~~~~~~~break
~~~~if sm == k:
~~~~~~~~break
while A[bg] == 0 and bg < en:
~~~~bg += 1
if sm==k:
~~~~print(bg+1,en+1)
else:
~~~~print(-1)
Сейчас попытаюсь повторить, изменив так, чтобы не корежило (и при этом чуть упростив)
#Ручной ввод
#s1 = input()
#s2 = input()
#Ввод из файла
s1 = '100_000 49610796982'
with open('1111.txt') as fr:~~~~s2 = fr.read()
# Разные примеры
#s1 = '7 5'
#s2 = '1 2 3 4 2 1 2'#2 3
#s1 = '5 3'
#s2 = '1 0 2 10 10'#1 3
#s1 = '2 100'
#s2 = '0 0'#-1
#s1 = '7 7'
#s2 = '0 0 0 10 0 0 7'#7 7
n,k = map(int, s1.split())
A=list(map(int, s2.split()))
bg=0
en=0
sm=0
for i in range(n):
~~~~en = i
~~~~sm += A[en]
~~~~
~~~~if sm > k:
~~~~~~~~while sm > k:
~~~~~~~~~~~~sm -= A[bg]
~~~~~~~~~~~~bg += 1
~~~~~~~~if sm==k:
~~~~~~~~~~~~break
~~~~if sm == k:
~~~~~~~~break
while A[bg] == 0 and bg < en:
~~~~bg += 1
if sm==k:
~~~~print(bg+1,en+1)
else:
~~~~print(-1)
Aleks Nots
Просветленный
(22647)
Теперь можно копипастить, ничего не покорежило.
Остальные ответы
Похожие вопросы
1.0 с
ограничение по памяти на тест
256 МБ
ввод
стандартный ввод
вывод
стандартный вывод
В 2029 году три финала Всероссийской олимпиады — по химии, информатике и физкультуре — проводятся в Самаре. Из Саратова прошло много участников по каждому из этих предметов, и все они планируют ехать в Самару на поезде. Руководитель сборной по химии уже купил билеты для своих подопечных. Руководитель сборной по информатике как раз сейчас планирует этим заняться. Но программисты — странные люди, у которых есть много запросов к купленным местам. Например, они категорически не хотят ехать в одном вагоне со спортсменами (участниками сборной по физкультуре), а также со всеми другими людьми, не прошедшими на всерос (то есть, из всех возможных людей, они готовы терпеть только всероссников по химии).
К счастью, пока кроме химиков ещё никто не успел купить билеты на поезд, так что всё, что нужно обеспечить руководителю, это чтобы после покупки билетов, в вагонах, в которых поедут участники сборной по информатике не осталось свободных мест (тогда там точно не поедут посторонние).
Но у руководителя есть и свои ограничения — он хочет, чтобы вагонов, в которых поедут его подопечные, было как можно меньше и они шли подряд (при этом допускается, чтобы между ними были целиком занятые вагоны).
Помогите руководителю сборной выбрать, в каких вагонах информатики поедут на олимпиаду, или определите, что это невозможно.
Входные данные
В первой строке дано два целых числа n
и k (1≤n≤105,1≤k≤109
) — число вагонов и участников сборной соответственно.
Во второй строке даны n
целых чисел ai (0≤ai≤109
) — количество свободных мест в вагонах.
Гарантируется, что суммарное число свободных мест в поезде не превосходит 109
.
Выходные данные
Выведите два целых числа — номера первого и последнего вагона, в которых поедут участники сборной.
Если же купить билеты, соблюдя все требования, невозможно, выведите -1.
Система оценки
Примеры
Входные данные
Скопировать
7 5
1 2 3 4 2 1 2
Выходные данные
Скопировать
2 3
Входные данные
Скопировать
5 3
1 0 2 10 10
Выходные данные
Скопировать
1 3