У даній задачі необхідно знайти за скільки днів закінчаться солдати в кожній ворожій країні. І взяти максимум з цих значень, тобто \(max(\frac{A}{C}, \frac{B}{D})\). Врахуйте те що результат є цілим числом і тому можна використовувати цілочисельне ділення.
Якщо ми порахуємо суму втрат за \(n - 1\) день, тоді різниця загальних втрат і цієї суми буде рівна кількості втрат в загублений день. Зауважте, що якщо отримане число не є додатнім, тоді Зеник допустив десь помилку.
Враховуючи умову про те що вантажівка може за один раз доставляти
незвичні матеріали лише в один рядок, нам необхідно для кожного рядка
порахувати мінімальну кількість поїздок аби розставити потрібні
матеріали. У кінці отримані значення для рядків необхідно буде
просумувати. Зауважимо, що для рядка нам не важливо де знаходяться
«*», а цікавить лише їх кількість — \(cnt\). Тоді будемо жадібно возити
матеріали, веземо повну вантажівку з \(k\) одиницями матеріалу, або ту кількість
що залишилась. Також цю кількість можна було порахувати формулою \(\lceil\frac{cnt}{k}\rceil\), цю формулу
можна рахувати використавши цілочисельне ділення в формулі \(\lfloor\frac{cnt + k - 1}{k}\rfloor\).
Для того аби отримати хоча б 10 балів було достатньо відтворити процес вказаний в умові, тобто ітеруємось по масиву, щоб знайти сусідні клітинки з найбільшою різницею і поміняємо місцями їх значення. Цей процес будемо робити поки масив не стане посортованим. Проте такий розв’язок є доволі повільним. Тому необхідно зауважити, що якщо є два елементи \(i\) та \(j\) для яких виконується \(i < j\) та \(a_i > a_j\), тоді колись ми їх поміняємо місцями. А пару елементів для якої виконується \(i < j\) та \(a_i < a_j\) ми ніколи не будемо міняти місцями. Отже, задача зводиться до того аби порахувати кількість інверсій, тобто кількість таких пар \(i < j\), що \(a_i > a_j\). І це можна зробити використавши два вкладені цикли по \(i\) та по \(j\).
Перш за все впорядкуємо військові об’єкти за відстанню від початку колони. Оскільки об’єкти не рухаються, то нема змісту обстрілювати одну ділянку більше одного разу.
Використаємо підхід динамічного програмування. Будемо знищувати об’єкти зліва направо. Стан буде характеризуватися кількістю знищених військових об’єктів від початку колони \(cnt\). Також, враховуючи те що в нас є обмеження на кількість пострілів з хаймарсу, це теж необхідно вказати в стані динаміки. А отже наша динаміка виглядатиме так: \(dp[cnt][himars]\) — мінімальна кількість пострілів, щоб знищити перші \(cnt\) об’єктів зробивши при цьому рівно \(himars\) пострілів з хаймарсу. Тоді, для того аби перерахувати цю динаміку, будемо вважати що останній зроблений постріл має правий кінець рівно в позиції \(cnt\)-го об’єкту. Усі об’єкти з координатою в проміжку \([a_{cnt} - x, a_{cnt}]\) будуть знищені з граду і \([a_{cnt} - y, a_{cnt}]\) з хаймарсу. А отже нам потрібно для кожного варіанту пострілу знайти найлівіший об’єкт який буде обстріляний цим пострілом. Це можна зробити двійковим пошуком, або методом двох вказівників, оскільки це не залежить від змінної \(himars\). Тоді ми знаємо скільки зліва залишиться об’єктів, також нам відомо для них значення динаміки, тобто найменшу кількість пострілів щоб знищити цей префікс. Зрозуміло, що постріл з хаймарсу можна зробити лише якщо \(himars > 0\) і тоді значення динаміки буде мінімумом з двох варіантів пострілу.
Для того аби знайти відповідь на задачу потрібно перебрати \(himars\) — яку кількість пострілів з хаймарсу ми зробимо. Відповідь буде рівна мінімуму серед значень динаміки \(dp[n][himars]\).
Використаємо алгоритм Дейкстри. Для кожного міста \(v\) будемо підтримувати \(D[v]\) — поточний мінімальний час за який туди можна потрапити з першої вершини. Початково значення \(D[v]\) встановимо достатньо великим числом.
Візьмемо місто, серед ще не розглянутих, з найменшим часом. Спробуємо через дане місто доїхати до сусідніх міст, які з’єднані прямою дорогою \(e\) з даним містом. Порахуємо найменший момент часу у який ми зможемо доїхати до сусіднього міста по даній дорозі. Для цього подивимось коли ми зможемо поїхати по даній дорозі і не потрапити під обстріл. Оскільки обстріли зациклені, то ситуація на цій дорозі в момент часу \(D[v]\) така ж як і в момент часу \(t = D[v] \mod (c[e] + d[e])\), де \(\mod\) рахує остачу від ділення. Якщо зараз дорога обстрілюється (\(t < c[e]\)), то ми повинні зачекати до перезарядки і почати рух в той момент коливона почнеться. Якщо ж дорога не обстрілюється (\(c[e] \le t\)), то нам необхідно перевірити чи ми встигнемо доїхати до початку нового обстрілу (\(t + l[e] \le c[e] + d[e]\)). Якщо встигаємо то просто їдемо і доїжджаємо в момент часу \(D[v] + l[e]\), інакше необхідно чекати коли наступний обстріл закінчиться і тоді їхати. Зауважимо, що якщо для того аби проїхати по дорозі нам необхідно більше часу ніж час перезаряджання, тоді ми ніколи не зможемо по цій дорозі проїхати. Цей процес будемо продовжувати поки у нас залишаються ще нерозглянуті міста.
Зауважимо, що нам цікаво лише які клітинки, з мінами і журналістами, ми відвідували і в якій клітинці ми зараз стоїмо. Використаємо підхід динамічного програмування. Будемо підтримувати бітмаску розміру \(2 \cdot k\) для тих клітинок які вже відвідані, а також в якій клітинці з \(2 \cdot k\) цікавих ми стоїмо. Значення динаміки \(dp[mask][v]\) — найкоротша відстань щоб пройти від стартової клітинки по відвіданих клітинках в \(mask\) і остання клітинка в якій ми зупинимось буде \(v\). Для обрахунку цієї динаміки переберемо з якої клітинки ми прийшли і серед усіх варіантів знайдемо мінімум. Зауважимо, що стан з якого ми прийшли буде містити на 1 біт менше у своїй бітмасці, і буде мати значення бітмаски менше. Тому якщо ми перебиратимемо маски по зрозстанню, то для обрахунку поточного значення будемо використовувати вже обраховані значення динаміки.
Проте ми не враховували, що пес Патрон початково не знаходиться в жодній з цікавих клітинок, тому значення динаміки для станів з однією знешкодженою міною буде рівне відстані що пройде пес Патрон від своєї початкової клітинки до цієї міни. У кінці нам потрібно буде лише перебрати останню клітинку в якій ми зупинемось, а бітмаска буде містити усі біти. Серед таких станів нам потрібно знайти найменше значення динаміки.
Зауважимо, що для пришвидшення цієї динаміки можна пропускати недосяжні стани, наприклад, якщо пес Патрон відвідав більше журналістів ніж мін.