Новый конкурс программистов

[Nataly-Mak]

Pavlovsky в сообщении #589173 писал(а):

Если все получится, буду искать решение 40х40 для С=6. В квадрате 40х40 раскрасить 28 диагоналей в два цвета возможно. Остается окрасить оставшиеся 79-28=51 диагонали в четыре цвета.

Очень реально, что существует решение для C=6 больше, чем N=36x36.
У меня очень быстро достроился из моего решения прямоугольник 37х36 6-coloring. Но пристроить ещё столбец вручную не получилось.

[Pavlovsky]

alexBlack в сообщении #589166 писал(а):

По крайней мере для одного вида решений для простых C очевидно, что при добавлении одного цвета можно увеличить размер на (C+1). Не так очевидно, но существует простая процедура, которая увеличивает размер еще на единицу.

Так Алексей начал колоться, а ведь мы еще не использовали утюг и паяльник.

У меня уже появились идеи как к оценке С^2-C+1 добавить еще единицу, надо вечером попробовать.

[Nataly-Mak]

alexBlack в сообщении #589166 писал(а):

Не так очевидно, но существует простая процедура, которая увеличивает размер еще на единицу.

Я об этом давно догадывалась, что такое расширение возможно.
Вот:

Цитата:

Если я правильно поняла приведённую выше формулу, она даёт:

C=12, N=133x133
C=14, N=183x183
C=18, N=307x307
C=20, N=381x381

Все полученные результаты на 1 больше.
Получается вроде того: все полученные по известному алгоритму квадраты как-то расширяются на 1.

То есть совсем не надо долго "трясти" решение для C=10, N=91x91, чтобы получить из него решение N=92x92. Делается это как-то очень красиво.

Тогда на моё сообщение никто не обратил внимания.
Только dimkadimon ответил: "Вы правильно поняли формулу, но есть исключения".
Оказывается, это совсем даже не исключения!

[Pavlovsky]

Возникает новый джентельменский набор.
1) Взять готовые результаты для (С=2,3,4).
2) Найти решение 36х36 для (С=6).
3) Реализовать алгоритм для С простых чисел (С=5,7,11,13,17,19).
4) Реализовать алгоритм для С, являющихся степенью простого числа (С=8,9,16).
5) Реализовать алгоритм C=p^k+1, p - простое число в степени, k>=1 с оценкой С^2-С+2 (С=10,12,14,18,20).
6) Получить решение для С+1, с оценкой F(С)+1, где F(C) решение для С (С=15,21).

При текущих рекордах получается 19,8509 балла.

Цитата:

4 Nick Gardner 19.850900 06-21-2012 @ 17:41:06

[Nataly-Mak]

Pavlovsky в сообщении #589191 писал(а):

5) Реализовать алгоритм C=p^k+1, p - простое число, k>=1 с оценкой С^2-С+2 (С=10,12,14,18,20).

Да, да, именно пункт 5 и был "зашит" в моём давнишнем сообщении

[dimkadimon]

Pavlovsky в сообщении #589161 писал(а):

dimkadimon в сообщении #589157 писал(а):

А можно я тоже буду считаться россиянином? Всё таки я родился в Москве и говорю по русски :)

Австралийцем быть прикольнее. Хочу в Австралию. Ведь там живут антиподы (Алиса в стране чудес).

Да ну может быть :) Австралия действительно классное место. Если вы когда-нибудь сюда собирётесь то сообщите и мы встретимся.

[Nataly-Mak]

Вот это достраивание мне точно снилось во сне



Именно оно - вполне гармоничное.
Решение родилось в творческих муках, во сне и наяву

Ох! А для С=9 я вообще не знаю, как делать разбиения
Придётся попробовать сначала решение для C=11, с этим проще, оно простое число. Знаю, как делать разбиения.

Надо ещё и для C=5 сделать, для порядка и для опыта.

[Nataly-Mak]

И вот оно решение C=6, N=31x31, очень красивое!



Уф! С замиранием души приступаю к решению для C=12
Решение для С=10 пока пропускаю, т.к. не умею для C=9 делать разбиения.

Кстати, интересно: можно ли достроить это решение 31х31 до решения 36х36?
Тут есть нечто красивое (не просто "потрясти")?
Полученное мной раньше решение 31х31 (точнее: 31х36) я достроила до 36х36 вручную в программе Эда. Получилось весьма симпатичное решение.

[Pavlovsky]

(Оффтоп)

Наталия может скроете картинку в оффтопик. Во-первых решение само по себе 31х31 приличное. Во-вторых явно виден алгоритм достраивания.

-- Вт июн 26, 2012 15:49:40 --

Наталия, офрмительский совет. В программе Эда есть галочка sub-grids. Можно красиво разбить квадрат на подквадраты.

[Zealint]

Nataly-Mak в сообщении #589244 писал(а):

И вот оно решение C=6, N=31x31, очень красивое!

Есть значительно красивее. Могу потом показать.

[Pavlovsky]

Чего то туплю. Помогите. Надо заполнить прямоугольник 5х9 максимальным количеством единичек. Чтобы не было запрещенных прямоугольников.

[Zealint]

Pavlovsky в сообщении #589398 писал(а):

Чего то туплю. Помогите. Надо заполнить прямоугольник 5х9 максимальным количеством единичек. Чтобы не было запрещенных прямоугольников.

Вручную у меня больше 16 не получается. А что, перебором не получается?

-- Вт июн 26, 2012 19:41:20 --

Zealint в сообщении #589402 писал(а):

Вручную у меня больше 16 не получается.

18 сделал

[Pavlovsky]

Zealint в сообщении #589402 писал(а):

18 сделал

Я тоже сделал 18! Оказывается достаточно написать, чтобы проблема решилась.

[Zealint]

Zealint в сообщении #589402 писал(а):

18 сделал

(Больше не получается)

Метод убывающих семёрок:

111100000
000111100
001000111
010001001
100010010

-- Вт июн 26, 2012 19:52:48 --

Pavlovsky в сообщении #589406 писал(а):

Я тоже сделал 18! Оказывается достаточно написать, чтобы проблема решилась.

Надо только доказать, что больше нельзя.

-- Вт июн 26, 2012 20:00:02 --

Pavlovsky в сообщении #589406 писал(а):

Оказывается достаточно написать, чтобы проблема решилась.

Да? Дайте-ка я напишу... Чего то туплю. Помогите. Надо заполнить прямоугольник 100х100 десятью цветами. Чтобы не было запрещенных прямоугольников.

-- Вт июн 26, 2012 20:01:42 --

Что-то не решается : )

-- Вт июн 26, 2012 20:12:23 --

Диагонального решения для 17x17, C=4 тоже не существует.

[Nataly-Mak]

Великолепная мозаика!



Ещё раз огромное спасибо Эду за программу!
Такая красота! Любуюсь, любуюсь...

Кстати, в этой мозаике есть нечто диагональное и даже пандиагональное (наличие разломанных диагоналей).