Добро пожаловать, гость
:: алгоритмы  и методы :: :: олимпиадные задачи :: :: связь :: :: о сайте :: :: форум ::

Форум работает в режиме архива, только для чтения и поиска.
Архив 2004 Архив 2007 Архив 2013

 
 
Опции темы Поиск в этой теме Опции просмотра
  #1  
Старый 04.04.2008, 00:09
гость

 
Сообщений: n/a

Головоломка про ферзей
вот решаю задачу вроде бы она простая, но что то не доходит как делать сижу думаю рисую и всё никак( подскажите пожалуйста
вот задача
Вероятно, что многие из вас играли в шахматы. Поэтому вы знаете, что ферзь может двигаться как под диагоналям, так и по горизонталям.

Вася недавно начал заниматься шахматами и где-то прочел головоломку, в которой нужно было расставить максимальное количество ферзей на доске 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
  #2  
Старый 05.04.2008, 18:32
Вася

 
Сообщений: n/a

По моим скромным рассчетам получается
n*n - ((n*3) - 2)
Проверь, работает ли формула на досках с разными размерами. Если все будет ок, то объясню как к этому пришел
  #3  
Старый 06.04.2008, 00:42
гость

 
Сообщений: n/a

там доска квадратная поэтому прямоугольные доски можно не расматривать
  #4  
Старый 06.04.2008, 02:51
Вася

 
Сообщений: n/a

А причем здесь прямоугольные доски?
Короче, начнем с того, что в условии есть логическая неточность - "хотя бы одно поле". Будем считать, что имеется ввиду не "хотя бы", а ровно одно поле - клетка.
Можно представить, что на этой небитой клетке стоит белый ферзь. (А остальные, которых нужно расставить максимальное количество - черные)
1. Понятно, что по горизонтали, вертикали и диагонялям от белого не может быть других ферзей.
2. Количество клеток, которые бьет белый ферзь должно быть минимальным. Логика проста - черные ферзи можно расставить только на те клеки (причем на все из них), которые не бьет белый. Поэтому, чем меньше клеток "занимает" белый, тем больше остается для черных.
3. Минимальное количество получается, когда белый находится либо в углах доски, либо на одной из крайних полос. Это ровно 3n - 2 клеток.
Остается отнять полученное от количества всех клеток: n*n - (3n - 2)
Вот и все
  #5  
Старый 06.04.2008, 03:15
Вася

 
Сообщений: n/a

Вот нарисовал 3 варианта для доски 6*6


1 и 2 - белый ферзь бьет минимальное количество клеток, поэтому черных ферзей можно расставить:
n*n - (3n - 2) = 6*6 - (3*6-2) = 36 - (18 - 2) = 36 - 16 = 20

3 - черных меньше (16) потому что белый бьет не минимальное количество клеток.
  #6  
Старый 09.04.2008, 02:51
гость

 
Сообщений: n/a

Спасибо большое разобрался ура!!!
 


Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск
Опции просмотра