Привет всем!
Попалась на олимпиаде мне задачка про фишки. Я уверен, что она очень лёгкая, но математическая, а формулу то вывести не могу
Вот задачка. помогите плиз с идеей
Рассмотрим доску размером NxN. Какое наименьшее число фишек нужно поставить на клетки доски для того, чтобы на каждой прямой, проходящей через центр произвольной клетки и параллельной каким-либо сторонам или диагоналям доски, стояла хотя бы одна фишка? (Фишки ставятся в центры клеток).
Пример входных данных:
4
Пример выходных данных:
8
  Никак не выведу

Что-то вроде 2N+N-2.

ЗЫ А причем тут раздел Паскаль?  

Retro, Да не знаю причём здесь Паскаль,просто слосил, надеюсь перенесут
2n+n-2=3n-2, а это формула не работает, если ты имел в виду 2n*(n-2), то получаем 8*2=16, тож нито, еслит 2n*n-2, имеем 2*16-2=30, тож нито. Что-то тут нечисто, писать алгоритм расстановки можно, но мне кажется что есть формула

Как же не работает, может я условие недопонял? Или ты чего-то не дописал?

А можно картинку, как у тебя получилось 8, при N = 4?
У меня выходит 10.

Retro, я бы тоже хотел картинку, а дали только условие, наро=исовать, как у них не получается, я тож условие не до конца понял, если бы понял, то сюда бы не писал

Ответ 8 при четырех дан в условие?

Это сообщение отредактировал(а) Shadowlord - 15.4.2007, 23:35

Вот вариант для n=4 
1=фишке
1011
1000
0001
1101

Для n>3 работает (n-2)*4 расстановка по той же схеме.
Для трех пока смог только с  помощью 7
111
010
111
При n=2 естественно 4



Это сообщение отредактировал(а) Shadowlord - 16.4.2007, 10:22

Кажется понял суть задачи, вначале я не то подумал...


101
101
010

Добавлено через 8 минут и 35 секунд
Опять гоню, надо поспать.
По любому должны быть закрыты углы.

Shadowlord, Спасибо, постараюсь, оттолкнуться от твоей идеи, вроде должно работать

Shadowlord, А как ты формулу выводил? Поделись рассуждениями

Все банально, взял лист в клетку за единичный отрезок две клетки начертил квадрат 4*4 линии карандашом через центры клеток (параллельные сторонам и диагоналям) Ставя фишку обводил черной ручкой те линии которые она кроет, вот так и пришол к такому выводу нарисовав штук 15 квадратов и переведя три тетрадных страницы
С начало уперся в то что фишки должны стоять на главной диагонали, оказалось нет.Потом догнал что углы должны обязательно быть закрытыми и вот так потихоньку и вывел

Hohhi, а точно нет никаких дополнительных условий, ведь получается, что нет формулы общего вида.


А можно пример для 5-ти?

Retro, точно, cоpy pastил я условие
Насчёт првильности, вечером тесты мне дадут отпишу

Shadowlord, тесты у меня закрытые, то есть я отправляю прогу на тестирование, и второй тест не проходит, прога 100% правильная, слишком элементарно, чтоб ошибиться вот код

вобщем, скорее всего фрмула не та, и логически для N=3, аж 7, для n=4, кол-во увеличивается на 1, зато для 5, уже аж 7, что то не то