First books#212

First books (Editorial)

Книжок рівно , тому всіх порядків прочитання лише . Це настільки мало, що жодної теорії не потрібно — достатньо перебрати всі перестановки й для кожної порахувати зацікавленість за формулою з умови:

a_{p_1} + \sum_{i=2}^{5} \max\bigl(0,\; a_{p_i} - a_{p_{i-1}}\bigr).

Відповідь — максимум по всіх перестановках.

У більшості мов перебір перестановок є в стандартній бібліотеці (наприклад, next_permutation у C++ або itertools.permutations у Python). Щоб next_permutation перебрав усі варіанти, масив спочатку треба відсортувати за зростанням.

Зверніть увагу на структуру формули: перша книжка дає повну свою цікавість, а кожна наступна — лише приріст над попередньою, і то якщо він додатний. Через це вигідно чергувати цікаві та нецікаві книжки: після нецікавої будь-яка цікава дає великий приріст. Але формально доводити це не потрібно — перебір усе одно швидший за будь-які міркування.