Дистанционная подготовка: Задача Головоломка про ферзей
Задача Головоломка про ферзей
от Роман Захаров - Пятница 4 Апрель 2008, 22:00
  вот решаю задачу вроде бы она простая, но что то не доходит как делать сижу думаю и всё никак( подскажите пожалуйста
вот задача
Вероятно, что многие из вас играли в шахматы. Поэтому вы знаете, что ферзь может двигаться как под диагоналям, так и по горизонталям.

Вася недавно начал заниматься шахматами и где-то прочел головоломку, в которой нужно было расставить максимальное количество ферзей на доске 8х8 так, чтобы хотя бы одно поле оказалось небитым. Эта задача легко решается для доски 3х3, т.к. понятно, что более двух ферзей расставить таким образом на ней невозможно.

Помогите Васе решить эту задачу для доски NxN.
Входные данные

В единственной строке входного файла INPUT.TXT записано натуральное число N – размеры шахматной доски NxN (1 ≤ N ≤ 100).
Выходные данные

В единственную строку выходного файла OUTPUT.TXT нужно вывести максимальное количество ферзей, которых можно расставить на шахматной доске NxN так, чтобы одна клетка оставалась небитой.
вход 3
выход 2
вот ссылка на задачу
http://acm.dvpion.ru/?main=task&id_task=86
Re: Задача Головоломка про ферзей
от Роман Джабаров - Пятница 4 Апрель 2008, 23:27
  допустим есть доска n*n. Возьмем одного ферзя будем ставить его в произовольную клетку доски, определим позиции которые будут под ударом ферзя, теперь будем считать, что в конечном итоге именно эта клетка будет не под ударом, легко сосчитать сколько ферзей можно поставить что бы эта клетка была свободна. Среди всех клеток выбирать ту для которой количество ферзей будет максимальным
Re: Задача Головоломка про ферзей
от Роман Захаров - Суббота 5 Апрель 2008, 23:49
 

Спасибо я разобралсяУлыбка

Re: Задача Головоломка про ферзей
от Роман Захаров - Суббота 5 Апрель 2008, 23:49
 

Спасибо я разобралсяУлыбка