Якщо ви тільки починаєте вивчати програмування або незнайомі із змаганнями з програмування, рекомендуємо ознайомитися з нашою системою на сторінці Допомога.
Потрібно написати перевірки для кожної медалі.
Для кожної клітинки без міни порахуємо, скільки в неї є сусідніх клітинок з мінами.
Розглянемо пластинки доміно, де більше число дорівнює mm: (0,m),(1,m),(2,m),…,(m,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(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)23m(m+1)2 за всіма можливими значеннями mm від 00 до nn.
Складність такого розв’язку — O(n)O(n).
Бонус: як розв’язати задачу за O(1)O(1)?
Спочатку перетворимо координати полів так, щоб кожне поле мало координати (i,j)(i,j), де ii, jj — цілі числа від 0 до 7.
Тоді з поля (i,j)(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)(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+⋯+aisi=a1+a2+⋯+ai.
Нехай Марічка з’їсть перших ii цукерок із сумарною смачністю a1+a2+⋯+ai=sia1+a2+⋯+ai=si, а Зеник з’їсть цукерки з номерами від jj до nn із сумарною смачністю aj+aj+1+⋯+an=sn−sj−1aj+aj+1+⋯+an=sn−sj−1. Повинні виконуватися такі дві умови: i<ji<j та si≥sn−sj−1si≥sn−sj−1. Друга умова означає, що Зеник не образить Марічку.
Щоб визначити, чи зможе Зеник з’їсти цукерки з номерами від jj до nn, треба дізнатися, чи існує таке i<ji<j, що si≥sn−sj−1si≥sn−sj−1.
Для цього будемо ітеруватися індексом jj по масиву aa зліва направо та підтримувати змінну mm — максимальне значення sisi для i<ji<j. Якщо m≥sn−sj−1m≥sn−sj−1, то Зеник може з’їсти цукерки від jj до nn та можна оновити відповідь значенням sn−sj−1sn−sj−1
Складність розв’язку — O(n)O(n).
Розв’язок, який обчислює всі значення a2,a3,…,ana2,a3,…,an та перевіряє знак anan, набирає частковий бал.
Зробимо спостереження: якщо a0a0 і a1a1 обидва додатні, то anan теж додатне. Аналогічно, якщо вони від’ємні, anan — від’ємне.
До розв’язку можна додати оптимізацію, яка використовує це спостереження: як тільки два сусідні елементи aiai та ai+1ai+1 стають обидва однакового знаку, то відразу можна зупинитися та вивести відповідь. Виявляється, цього досить, щоб розв’язати задачу на повний бал.
Доведемо, чому це так. Розглянемо чотири сусідні елементи такі, що в них чергуються знаки. Нехай, без обмеження загальності, ai>0,ai+1<0,ai+2>0,ai+3<0ai>0,ai+1<0,ai+2>0,ai+3<0.
Виконується ai+2=ai+ai+1ai+2=ai+ai+1, ai+3=ai+1+ai+2ai+3=ai+1+ai+2. Отже, ai+3=ai+2ai+1<0ai+3=ai+2ai+1<0. Звідси ai+1<−ai2ai+1<−ai2.
Позаяк aiai та ai+1ai+1 мають різні знаки, то |ai+2|=|ai+ai+1|=|ai|−|ai+1|=ai+ai+1<ai+−ai2=ai2|ai+2|=|ai+ai+1|=|ai|−|ai+1|=ai+ai+1<ai+−ai2=ai2. Ми одержали, що ai+2<ai2. Це означає, що якщо знаки елементів послідовності чергуються, то значення елементів за модулем за два кроки зменшуються принаймні вдвічі. Звідси випливає, що швидко станеться таке, що сусідні елементи матимуть однаковий знак.