Якщо ви тільки починаєте вивчати програмування або незнайомі із змаганнями з програмування, рекомендуємо ознайомитися з нашою системою на сторінці Допомога.
Потрібно написати перевірки для кожної медалі.
Для кожної клітинки без міни порахуємо, скільки в неї є сусідніх клітинок з мінами.
Розглянемо пластинки доміно, де більше число дорівнює \(m\): \((0, m), (1, m), (2, m), \dots, (m, m)\). Сума очок на цих пластинках дорівнює \((0 + m) + (1 + m) + (2 + m) + \dots + (m + m) = (0 + 1 + 2 + \dots + m) + (m + 1) \cdot m = \frac{m(m + 1)}{2} + m(m + 1) = \frac{3m(m+1)}{2}\).
Відповіддю на задачу є сума \(\frac{3m(m+1)}{2}\) за всіма можливими значеннями \(m\) від \(0\) до \(n\).
Складність такого розв’язку — \(O(n)\).
Бонус: як розв’язати задачу за \(O(1)\)?
Спочатку перетворимо координати полів так, щоб кожне поле мало координати \((i, j)\), де \(i\), \(j\) — цілі числа від 0 до 7.
Тоді з поля \((i, j)\) кінь може перейти в поля \((i + 1, j + 2), (i + 1, j - 2), (i - 1, j + 2), (i - 1, j - 2), (i + 2, j + 1), (i + 2, j - 1), (i - 2, j + 1), (i - 2, j - 1)\), якщо він не вийде за межі шахівниці.
Для кожного коня на полі спробуємо всі вісім можливих ходів і
позначимо поля літерою K.
E. Повторювані числа в матриці
Запишемо всі числа з матриці в один список (vector у
C++, list у Python) та посортуємо його.
Якщо число зустрічалося в матриці двічі, то обидва його входження в посортованому списку будуть сусідніми. Пройдемося по посортованому списку та подивимося на всі пари сусідніх елементів. Якщо сусідні елементи однакові, то запишемо цей елемент до відповіді.
Позначимо \(s_i = a_1 + a_2 + \dots + a_i\).
Нехай Марічка з’їсть перших \(i\) цукерок із сумарною смачністю \(a_1 + a_2 + \dots + a_i = s_i\), а Зеник з’їсть цукерки з номерами від \(j\) до \(n\) із сумарною смачністю \(a_j + a_{j+1} + \dots + a_n = s_n - s_{j-1}\). Повинні виконуватися такі дві умови: \(i < j\) та \(s_i \ge s_n - s_{j - 1}\). Друга умова означає, що Зеник не образить Марічку.
Щоб визначити, чи зможе Зеник з’їсти цукерки з номерами від \(j\) до \(n\), треба дізнатися, чи існує таке \(i < j\), що \(s_i \ge s_n - s_{j-1}\).
Для цього будемо ітеруватися індексом \(j\) по масиву \(a\) зліва направо та підтримувати змінну \(m\) — максимальне значення \(s_i\) для \(i < j\). Якщо \(m \ge s_n - s_{j - 1}\), то Зеник може з’їсти цукерки від \(j\) до \(n\) та можна оновити відповідь значенням \(s_n - s_{j - 1}\)
Складність розв’язку — \(O(n)\).
Розв’язок, який обчислює всі значення \(a_2, a_3, \dots, a_n\) та перевіряє знак \(a_n\), набирає частковий бал.
Зробимо спостереження: якщо \(a_0\) і \(a_1\) обидва додатні, то \(a_n\) теж додатне. Аналогічно, якщо вони від’ємні, \(a_n\) — від’ємне.
До розв’язку можна додати оптимізацію, яка використовує це спостереження: як тільки два сусідні елементи \(a_i\) та \(a_{i+1}\) стають обидва однакового знаку, то відразу можна зупинитися та вивести відповідь. Виявляється, цього досить, щоб розв’язати задачу на повний бал.
Доведемо, чому це так. Розглянемо чотири сусідні елементи такі, що в них чергуються знаки. Нехай, без обмеження загальності, \(a_i > 0, a_{i+1} < 0, a_{i+2} > 0, a_{i+3} < 0\).
Виконується \(a_{i+2}=a_i+a_{i+1}\), \(a_{i+3}=a_{i+1}+a_{i+2}\). Отже, \(a_{i+3} = a_i + 2 a_{i+1} < 0\). Звідси \(a_{i+1} < \frac{-a_i}{2}\).
Позаяк \(a_i\) та \(a_{i+1}\) мають різні знаки, то \(|a_{i+2}| = |a_i+a_{i+1}| = |a_i| - |a_{i+1}| = a_i + a_{i+1} < a_i + \frac{-a_i}{2} = \frac{a_i}{2}\). Ми одержали, що \(a_{i+2} < \frac{a_i}{2}\). Це означає, що якщо знаки елементів послідовності чергуються, то значення елементів за модулем за два кроки зменшуються принаймні вдвічі. Звідси випливає, що швидко станеться таке, що сусідні елементи матимуть однаковий знак.