Оптимальні підпослідовності
У заданій базовій числовій послідовності встановити підпослідовність або декілька підпослідовностей, можливо навіть різної довжини, сума елементів яких найменше відрізняється від деякого цільового значення.
Вимоги до програми:
Програма повинна зчитувати вхідні дані із консолі. У першому рядку міститься два числа, що розділені пропуском: ціле число – кількість N елементів базової послідовності (1 ≤ N ≤ 10 000) та дійсне число – цільове значення суми S елементів шуканих підпослідовностей. У наступному рядку записано N дійсних чисел, що відокремлені пропуском, – елементи базової послідовності.
Результат виконання програми повинен записуватися у консоль. У першому рядку виводиться одне дійсне число – мінімальна абсолютна величина різниці між заданим цільовим значенням та сумою елементів шуканих підпослідовностей, обчислена з точністю 0.001. У другому рядку виводиться одне ціле число K – кількість знайдених оптимальних підпослідовностей. У третьму рядку послідовно виводиться K пар цілих чисел, що відокремлені пропусками: перше з двох – позиція у базовій послідовності початку шуканої підпослідовності, друге – кількість елементів у такій підпослідовності. Вивід результатів здійснюється у порядку зростання стартових позицій. Якщо є декілька підпослідовностей з однаковими позиціями початку, то вивід проводиться у порядку зростання довжин підпослідовностей.