eolymp
bolt
Try our new interface for solving problems
Problems

Оптимальні підпослідовності

Оптимальні підпослідовності

У заданій базовій числовій послідовності встановити підпослідовність або декілька підпослідовностей, можливо навіть різної довжини, сума елементів яких найменше відрізняється від деякого цільового значення. Вимоги до програми: Програма повинна зчитувати вхідні дані із консолі. У першому рядку міститься два числа, що розділені пропуском: ціле число – кількість N елементів базової послідовності (1 ≤ N ≤ 10 000) та дійсне число – цільове значення суми S елементів шуканих підпослідовностей. У наступному рядку записано N дійсних чисел, що відокремлені пропуском, – елементи базової послідовності. Результат виконання програми повинен записуватися у консоль. У першому рядку виводиться одне дійсне число – мінімальна абсолютна величина різниці між заданим цільовим значенням та сумою елементів шуканих підпослідовностей, обчислена з точністю 0.001. У другому рядку виводиться одне ціле число K – кількість знайдених оптимальних підпослідовностей. У третьму рядку послідовно виводиться K пар цілих чисел, що відокремлені пропусками: перше з двох – позиція у базовій послідовності початку шуканої підпослідовності, друге – кількість елементів у такій підпослідовності. Вивід результатів здійснюється у порядку зростання стартових позицій. Якщо є декілька підпослідовностей з однаковими позиціями початку, то вивід проводиться у порядку зростання довжин підпослідовностей.
Time limit 2 seconds
Memory limit 256 MiB
Input example #1
5 5
1 1 1 1 1
Output example #1
0.000
1
1 5
Input example #2
5 5.001
1 2 3 4 5
Output example #2
0.001
2
2 2 5 1
Input example #3
5 4.5
1 1 1 1 1
Output example #3
0.500
3
1 4 1 5 2 4
Input example #4
5 3.7
1.1 1.0 1.1 1.0 1.1
Output example #4
0.500
4
1 3 1 4 2 4 3 3
Source ІІІ етап Всеукраїнської учнівської олімпіади з інформатики у 2021/2022 навчальному році у Рівненській області (11-12 січня 2022 р.)