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