Привет всем!
Попалась на олимпиаде мне задачка про фишки. Я уверен, что она очень лёгкая, но математическая, а формулу то вывести не могу
Вот задачка. помогите плиз с идеей
Рассмотрим доску размером 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, что то не то

Ну насчет трех я просто больше не смог придумать.
а вот пример для 5
10111
10000
10001
00001
11101

Тесты в студию

Добавлено через 4 минуты и 59 секунд
Нашел ошибку не n*(n-2), а 4*(n-2)
так как четыре угла  

тесты на сайте по ссылке http://www.olympiads.ru/cgi-bin/new-client...8&action=34, но там регится над, непонятно почему второй тест не проходит

Ты исправил?

а по поводу трех то думаю там не как по другому не выйдет

Shadowlord, исправил, пытаюсь для шести сделать, вроде формула правильная, а вобще кто знает
111101
000001
000001
100000
100000
101111
вроде 14 выходит, то есть формула 2*((n-1)+n-2

Добавлено через 9 минут и 23 секунды
10111
10000
00001
00001
11101
А для пяти не так?

Это сообщение отредактировал(а) Hohhi - 16.4.2007, 21:49

Не прошло, жаль, будем думать

round(n/2)*4
для нечетных еще делаем -1.

как всё это в чистую математику свести - не пойму.



это ниработает. например для n=7 достаточно 15 фишек, а по формуле выходит 20.

Добавлено через 4 минуты и 35 секунд
round в большую сторону разумеется

для четных N*2
для не четных N*2+1

result := N*2 + (N mod 2)

Это сообщение отредактировал(а) greenpc - 17.4.2007, 10:08

а можно пример


greenpc, а как ты к этому пришел? 


Hohhi, посмотрел действительно выходит 
 

greenpc, 5 баллов   . И чего меня на этот round потянуло...

Shadowlord, 
решения для 3,4,5 - есть в топе 
проверил для 6 (заполнение идет от углов)
и S.A.P. дал ответ для 7

greenpc, да, да прошло, вот здорово, самое обидное, что я владею техниками программирования, решаю сложнейшие задачки, а натакой ерунде вечно горю, спасибо всем принимавшим участие, а особенно greenpc