В задачі треба було додати три числа, і від суми відняти максимум з трьох заданих чисел. Також можна було перебрати три можливі пари двох чисел, і знайти найменшу суму серед таких пар.
Для того, щоб струм передавався між двома сусідніми вимикачами — вони
мають бути в протилежних станах. Тобто, \/, або
/\.
Звідси можемо здогадатися, що для того, щоб струм передавався між
всіма вимикачами — потрібно, щоб їхні стани чергувалися. Тобто, існує
всього два можливі варіанти правильного розміщення вимикачів:
\/\/\/...\/\, або /\/\/\.../\/.
Для розв’язку задачі достатньо просто обчислити кількість перемикань потрібних, щоб досягти кожного з двох правильних розміщень. А тоді серед них обрати мінімальний.
Найпростіший розв’язок який проходить перші два блоки тестів і набирає 60 балів полягає в тому, щоб для кожного заданого рядка перебрати усі можливі позиції куди можна вставити потрібний символ, і серед усіх таких варіантів вибрати лексикографічно найменший. Для того, щоб реалізувати такий розв’язок треба вміти виконувати операції з рядками: перебирати його символи, вставляти та видаляти символи в рядок, порівнювати їх. Це все можна без проблем робити засобами більшості сучасних мов програмування. Проте, такий розв’язок є надто повільний, щоб отримати 100 балів за задачу.
Для того, щоб розв’язати задачу з повними обмеженнями, треба придумати як для рядка оптимально знаходити місце куди вставити символ, щоб дістати лексикографічно найменший рядок. Цього можна досягнути, якщо вставити символ одразу перед першим таким символом в рядку, який йде пізніше в алфавіті. Якщо ж таких символів немає, треба додати символ в кінець рядка. Правильність такого розв’язку випливає з визначення лексикографічного порядку рядків.
Тому розв’язок наступний:
Для кожного рядка \(s_i\) знайдемо перше входження символу більшого за \(c\), і вставимо символ \(c\) перед ним. Якщо якийсь рядок не містить таких символів, то додамо \(c\) в кінець.
Серед усіх утворених рядків знайдемо лексикографічно найменший по черзі перебираючи усі рядки.
В задачі потрібно порахувати, скільки акумуляторів підійме платформа. Потрібно врахувати, що акумулятори можуть розташовуватися на ній частково, та згодом можуть підіймати інші акумулятори.
Зауважимо наступне. Якщо на платформі вже знаходиться певна конструкція з акумуляторів, які займають проміжок координат [\(l\), \(r\)] — можна ігнорувати всі акумулятори, які будуть опускати поза межами цього проміжку. А для того, щоб підняти акумулятор — потрібно хоча б частково бути під ним.
Тому для розв’язку будемо тримати межі конструкції платформи з акумуляторами (на початку це проміжок \([l=p\), \(r=p]\), оскільки ширина платформи рівна одиниці). Тоді, перевірятимемо кожен акумулятор. Якщо хоча б якась його частина входитиме в проміжок \([l, r]\) — це означатиме, що платформа з іншими акумуляторами зможе його підняти. І оскільки він стане частиною конструкції, що підіймається — потрібно розширити межі конструкції. \([l, r] \rightarrow [min(l, x), max(r, x+1)]\). Залишається лише обчислити кількість таких акумуляторів.