Форум программистов, компьютерный форум, киберфорум
Алгоритмы
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.67/9: Рейтинг темы: голосов - 9, средняя оценка - 4.67
9 / 9 / 1
Регистрация: 28.11.2013
Сообщений: 153
1

Подсуммы (олимпиадная задачка), нужны идеи

10.04.2015, 20:54. Просмотров 1821. Ответов 18
Метки нет (Все метки)

64 megabytes / 1 seconds / stdin / stdout

Не все числа одинаково полезны. Если, например, вам потребуется насобирать сумму
как можно больше, то вам ни к чему использовать отрицательные числа. Но может
получиться так, что и выбора не останется и придется их использовать. Да и вообще
воспользуемся модулем, чтобы уровнять положительный и отрицательные числа. И совсем
не требуется насобирать максимальную сумму, достаточно чтобы модуль суммы был
больше M. Требуется найти количество способов выбрать подотрезок в последовательности
с заданным свойством.

Входные данные:
В первой строке задаются числа N M — количество чисел в последовательности и нижний
предел модуля суммы (1 ≤ N ≤ 105, 1 ≤ M ≤ 109).
В следующей строке задается N чисел Ai — числа последовательности (|Ai| ≤ 104).
Выходные данные:
В единственной строке выведите искомое количество подотрезков.

Пример
ввод
10 8
-2 9 3 6 3 8 -1 10 -6 7
вывод
42
Я думал про sqrt-декомпозицию, но что-то ничего не придумал :(
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
10.04.2015, 20:54
Ответы с готовыми решениями:

Олимпиадная задачка. Если есть идеи то помогите. Вместе решим
B. Время исполнения Time Limit: 1000 ms Memory Limit: 1024 kb При проектировании программы на...

олимпиадная задачка
На доске наклеено несколько листов объявлений. Все они прямоугольной формы. Некоторые письма...

Олимпиадная задачка
cut Помогите пожалуйста, напишите программу на C++. Входной файл: input.txt Выходной файл:...

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

18
219 / 164 / 47
Регистрация: 17.07.2012
Сообщений: 587
10.04.2015, 21:08 2
011, ну вроде могу рассказать на словах как делать.
0
011
10.04.2015, 21:09  [ТС]
  #3

Не по теме:

SlavaSSU, можно в скайп, если я правильно понял:)

0
219 / 164 / 47
Регистрация: 17.07.2012
Сообщений: 587
10.04.2015, 21:12 4
011, тут! для начала: ты знаешь, что такое префиксные(частичные) суммы?
0
9 / 9 / 1
Регистрация: 28.11.2013
Сообщений: 153
10.04.2015, 21:14  [ТС] 5
SlavaSSU, только из матана знаю, что такое частичная сумма

Добавлено через 1 минуту
SlavaSSU, какая асимптотика у твоего решения?
0
219 / 164 / 47
Регистрация: 17.07.2012
Сообщений: 587
10.04.2015, 21:16 6
011, n * log(n)
0
9 / 9 / 1
Регистрация: 28.11.2013
Сообщений: 153
10.04.2015, 21:16  [ТС] 7
SlavaSSU, круто, то, что нужно)
Пожалуйста, рассказывай дальше.
0
219 / 164 / 47
Регистрация: 17.07.2012
Сообщений: 587
10.04.2015, 21:17 8
011, кстати, дай ссылку на задачу на всякий случай
0
9 / 9 / 1
Регистрация: 28.11.2013
Сообщений: 153
11.04.2015, 13:41  [ТС] 9

Не по теме:

SlavaSSU, смотри ЛС



Добавлено через 16 часов 20 минут
(up)
0
189 / 170 / 29
Регистрация: 10.07.2012
Сообщений: 796
11.04.2015, 15:14 10
Цитата Сообщение от SlavaSSU Посмотреть сообщение
011, кстати, дай ссылку на задачу на всякий случай
дайте ее, пожалуйста, всем.
0
9 / 9 / 1
Регистрация: 28.11.2013
Сообщений: 153
11.04.2015, 15:57  [ТС] 11
salam, в этом нет смысла: нужно быть зарегистрированным в контесте.
Вот как выглядит условие:
условие
0
4341 / 2007 / 255
Регистрация: 01.03.2013
Сообщений: 5,391
Записей в блоге: 22
11.04.2015, 20:34 12
Да, куда больше смысла зарегистрироваться в контесте, и вместо того, чтобы думать своей головой, идти на форумы, чтобы решили за тебя.
0
9 / 9 / 1
Регистрация: 28.11.2013
Сообщений: 153
11.04.2015, 20:41  [ТС] 13
_Ivana, спасибо за ценный комментарий. Есть что по делу?

Меня эта задача интересует только с академической точки зрения, в след. этап уже и без нее прошел.
0
4341 / 2007 / 255
Регистрация: 01.03.2013
Сообщений: 5,391
Записей в блоге: 22
11.04.2015, 20:47 14
По делу уже сказали выше, про префиксные/суффиксные суммы.
0
9 / 9 / 1
Регистрация: 28.11.2013
Сообщений: 153
11.04.2015, 20:59  [ТС] 15
_Ivana, Где об этом можно почитать?
0
343 / 133 / 28
Регистрация: 16.12.2012
Сообщений: 607
Записей в блоге: 1
Завершенные тесты: 1
11.04.2015, 21:04 16
Да тут бахнуть массив b, где https://www.cyberforum.ru/cgi-bin/latex.cgi?b[i] = \sum_{j=0}^{i}a[j]
А потом пробежаться по всем b[i] и найти j, такое что, abs(b[i]-b[j-1]) > m
0
219 / 164 / 47
Регистрация: 17.07.2012
Сообщений: 587
11.04.2015, 21:10 17
это соревнование сейчас идет. во время соревнования не принято обсуждать задачи, даже если и без нее хватает на проход.
0
9 / 9 / 1
Регистрация: 28.11.2013
Сообщений: 153
11.04.2015, 21:11  [ТС] 18
Ромаха, у вас все подотрезки начинаются с a[0]? Но ведь это не обязательно должно быть так...
Также непонятно почему вы сравниваете модуль разности сумм для двух подотрезков с m...
Мне кажется, или это идеи полного перебора?
0
343 / 133 / 28
Регистрация: 16.12.2012
Сообщений: 607
Записей в блоге: 1
Завершенные тесты: 1
11.04.2015, 21:43 19
Помогать Вам я не буду. Ибо обсуждать задачи идущего соревнования - как минимум - неправильно
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
11.04.2015, 21:43

Заказываю контрольные, курсовые, дипломные и любые другие студенческие работы здесь.

Олимпиадная задачка
Мальчик Вася, чтобы попасть к себе домой на 10-й этаж, сначала поднимается до 7-го, а потом идет 3...

Олимпиадная задачка (B-lvl)
Здравствуйте! Объясните пожалуйста как работает алгоритм: #include<bits/stdc++.h> using namespace...

Олимпиадная задачка на C++ (или на Python)
Помогите решить задачку! Кроме слежки за офисом из окна своего дома, летом Вася читал книжку....

Олимпиадная задачка на C++ (или на Python)
Решаю олимпиадную задачку. Вот текст Числовая последовательность называется пилообразной если...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
19
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2020, vBulletin Solutions, Inc.