Якщо ви тільки починаєте вивчати програмування або незнайомі із змаганнями з програмування, рекомендуємо ознайомитися з нашою системою на сторінці Допомога.
Потрібно написати перевірки для кожної медалі.
Для кожної клітинки без міни порахуємо, скільки в неї є сусідніх клітинок з мінами.
Розглянемо пластинки доміно, де більше число дорівнює m: (0,m),(1,m),(2,m),…,(m,m). Сума очок на цих пластинках дорівнює (0+m)+(1+m)+(2+m)+⋯+(m+m)=(0+1+2+⋯+m)+(m+1)⋅m=m(m+1)2+m(m+1)=3m(m+1)2.
Відповіддю на задачу є сума 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) та посортуємо його.
Якщо число зустрічалося в матриці двічі, то обидва його входження в посортованому списку будуть сусідніми. Пройдемося по посортованому списку та подивимося на всі пари сусідніх елементів. Якщо сусідні елементи однакові, то запишемо цей елемент до відповіді.
Позначимо si=a1+a2+⋯+ai.
Нехай Марічка з’їсть перших i цукерок із сумарною смачністю a1+a2+⋯+ai=si, а Зеник з’їсть цукерки з номерами від j до n із сумарною смачністю aj+aj+1+⋯+an=sn−sj−1. Повинні виконуватися такі дві умови: i<j та si≥sn−sj−1. Друга умова означає, що Зеник не образить Марічку.
Щоб визначити, чи зможе Зеник з’їсти цукерки з номерами від j до n, треба дізнатися, чи існує таке i<j, що si≥sn−sj−1.
Для цього будемо ітеруватися індексом j по масиву a зліва направо та підтримувати змінну m — максимальне значення si для i<j. Якщо m≥sn−sj−1, то Зеник може з’їсти цукерки від j до n та можна оновити відповідь значенням sn−sj−1
Складність розв’язку — O(n).
Розв’язок, який обчислює всі значення a2,a3,…,an та перевіряє знак an, набирає частковий бал.
Зробимо спостереження: якщо a0 і a1 обидва додатні, то an теж додатне. Аналогічно, якщо вони від’ємні, an — від’ємне.
До розв’язку можна додати оптимізацію, яка використовує це спостереження: як тільки два сусідні елементи ai та ai+1 стають обидва однакового знаку, то відразу можна зупинитися та вивести відповідь. Виявляється, цього досить, щоб розв’язати задачу на повний бал.
Доведемо, чому це так. Розглянемо чотири сусідні елементи такі, що в них чергуються знаки. Нехай, без обмеження загальності, ai>0,ai+1<0,ai+2>0,ai+3<0.
Виконується ai+2=ai+ai+1, ai+3=ai+1+ai+2. Отже, ai+3=ai+2ai+1<0. Звідси ai+1<−ai2.
Позаяк ai та ai+1 мають різні знаки, то |ai+2|=|ai+ai+1|=|ai|−|ai+1|=ai+ai+1<ai+−ai2=ai2. Ми одержали, що ai+2<ai2. Це означає, що якщо знаки елементів послідовності чергуються, то значення елементів за модулем за два кроки зменшуються принаймні вдвічі. Звідси випливає, що швидко станеться таке, що сусідні елементи матимуть однаковий знак.