Решение задачи Ходы на доске с Codeforces

С пояснением   Просмотров: 27


Вам задана доска размера n×n, где n нечетно (не кратно 2). Изначально в каждой клетке доски расположена одна фигура.

За один ход вы можете выбрать ровно одну фигуру, расположенную в какой-либо клетке и передвинуть ее в одну из клеток, имеющую общую сторону или угол с текущей клеткой, то есть из клетки (i,j) вы можете передвинуть фигуру в клетку:

(i−1,j−1);
(i−1,j);
(i−1,j+1);
(i,j−1);
(i,j+1);
(i+1,j−1);
(i+1,j);
(i+1,j+1);
Конечно же, вы не можете двигать фигуры в клетки за пределами доски. Допустимо, что после хода в одной клетке будет находиться несколько фигур.

Ваша задача — найти минимальное количество ходов, необходимое, чтобы собрать все фигуры в одной клетке (т.е. в n2−1 клетках должно быть расположено 0 фигур и в одной клетке должны быть расположены n2 фигур).

Вам нужно ответить на t независимых наборов тестовых данных.

Код

#include <bits/stdc++.h>

using namespace std;

int main() {
	int t;
	cin >> t;
	while (t--) {
		int n;
		cin >> n;
		long long ans = 0;
		for (long long i = 1; i <= n / 2; ++i) {
			ans += i * i;
		}
		cout << ans * 8 << endl;
	}

	return 0;
}

         

Администратор Photo Автор: Администратор


Довольно интуитивно (и доказуемо), что лучшей стратегией будет двигать каждую фигуру в центральную клетку (n+12,n+12). Теперь, с некоторой работой с литочком или простыми наблюдениями, мы можем заметить, что есть ровно 8 клеток с кратчайшей дистанцией 1, 16 кеток с кратчайшей дистанцией 2, 24 клетки с кратчайшей дистанцией 3 и так далее. Таким образом, у нас имеется 8i клеток с кратчайшей дистанцией i. Поэтому ответ равен 1⋅8+2⋅16+3⋅24+⋯+(n−12)2⋅8. Это может быть переписано как 8(1+4+9+⋯+(n−12)2), поэтому мы можем просто посчитать сумму квадратов всех целых чисел от 1 до n−12 при помощи цикла (или формулы n(n+1)(2n+1)6), а затем домножить ответ на 8.

Асимптотика решения: O(n) или O(1).


Комментарии

Чтобы написать комментарии вам нужно войти в систему или зарегистрироваться