Знаючи відстань і швидкість, час подорожі можна порахувати відомою формулою t=sv, отже відповідь — це 225000000v.
Зчитавши циклом кожну оцінку, потрібно перевірити, чи є хоча б одна оцінка нижча за 51. Якщо така оцінка є, стипендії не буде. Інакше потрібно перевірити, чи є хоча б одна оцінка нижча за 90, тоді стипендія буде звичайною. У протилежному разі стипендія буде підвищеною.
Потрібно знайти кількість прямокутників з координатами верхнього лівого кута (x1,y1) та нижнього правого (x2,y2), у межах якого кількість одиниць більша за кількість нулів.
Перепозначимо 0 як -1 у заданій таблиці. Це дозволить нам шукати кількість прямокутників, сума чисел у яких є додатною.
Переберемо x1 та x2, і для кожного j (1≤j≤m) будемо підтримувати суму sj усіх елементів у стовпці j між рядками x1 та x2. Після цього задача зводиться до одновимірного випадку — потрібно знайти кількість проміжків з додатною сумою. Аналогічно першим циклом переберемо y1, а другим — y2, підтримуючи суму усіх sj між ними. Якщо ця сума додатна, то прямокутник між (x1,y1) та (x2,y2) є шуканим, тому додаємо 1 до відповіді.
Складність розв’язку — O(n2m2) з дуже малою константою.
D. Зеник і Марсіанська перестановка
Зауважмо, що для того, аби поміняти місцями два елементи з індексами i та j, потрібно аби абсолютна різниця цих індексів |i−j| ділилася на k. Це можна пояснити тим, що будь-яка операція обміну, описана в умові, відбувається завжди між елементами в індексах з однаковою остачею від ділення на k.
Отже, для того, аби посортувати перестановку, потрібно аби абсолютна різниця поточної позиції елемента та його позиції в посортованому масиві (|pi−i|) ділилась на k для всіх i від 1 до n включно. Обчислимо g — найбільший спільний дільник (НСД) усіх абсолютних різниць |pi−i|. Неважко побачити, що число g, а також усі його дільники, будуть відповіддю до задачі.