Решаем сложные и олимпиадные задачи

[muvick]

for (int i=0;i

(сделаем 2х мерный массив если одну коробку можно засунуть в другую то 1 иначе 0)

так как в каждую коробку можно положить только 1 коробку и каждую коробку только в одну, то если мы делаем вложение, v[j], то вся строка вычеркивается и столбец тоже.

чтобы коробок осталось как можно меньше надо чтобы как можно больше было "вложений" коробок, тоесть задача теперь в том чтобы в этом массиве надо выбрать как можно больше единиц.

нам по дискретке только что дали такую домашку =). Хорошо что хоть алгоритм дали, собсно используя этот алгоритм наверное можно решить эту задачу.

[0xDEADBEEF]

muvick

Тащи зачотку)

Алгоритм который у тебя на скане както ужасен)

Алгоритм Куна - 10 строчек кода) и кубическая сложность.

[muvick]

Прочитал алгоритм Куна куда проще и намного понятнее как он работает. Жаль мне все равно придется делать тот алгоритм(

Если кто хочет выложить свою задачу, пожалуйста

PS а причем тут якуты

[0xDEADBEEF]

Ну это вобщемто обоснование применения алгоритма максимального паросочетания.

"Как можно больше коробок друг в друга" конечно вполне убедительно, но, строго говоря, не является объяснением.

А решение звучит так:

Количество коробок - это ширина ЧУМ'а, образуемого этими коробками. Ширина ЧУМ'а это количество элементов в максимальной антицепи, которая в свою очередь равно минимальному количеству цепей (теорема Дилуорта) и т.д.

Ну кому интересно, можно погуглить на досуге.

[duk999]

Вот задания со Всеросийской олимпиада за 2008 год кому интересно:

вот эту задачю я решил:

[Серый84]

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

Однажды N белых и N чёрных лягушек решили поиграть. Они нашли 2N+1 кочку, пронумеровали их целыми числами от 0 до 2N и заняли кочки таким образом, что на кочках с номерами 0 .. N–1 сидят белые лягушки, на кочках с номерами N+1 .. 2N — чёрные лягушки, а кочка с номером N пуста. Цель игры: поменять белых и чёрных лягушек местами, то есть в конце игры на первых N кочках должны сидеть чёрные лягушки, а на последних N кочках — белые лягушки. За один ход чёрная лягушка может прыгнуть с кочки с номером i > 0 на кочку с номером i–1, если кочка i–1 пуста, либо с кочки с номером j > 1 на кочку с номером j–2, если кочка j–2 пуста, а на кочке с номером j–1 сидит белая лягушка. Белая лягушка за один ход может прыгнуть с кочки с номером i < 2N на кочку с номером i+1, если кочка i+1 пуста, либо с кочки с номером j < 2N–1 на кочку с номером j+2, если кочка j+2 пуста, а на кочке с номером j+1 сидит чёрная лягушка. Обычно в играх чёрные и белые ходят по очереди, но в этой игре чёрные и белые преследуют общую цель, поэтому могут ходить в любом порядке (более того, общее число ходов белых не обязано совпадать с общим числом ходов чёрных). Если после 1000000 сделанных ходов лягушки так и не поменялись местами, им надоедает эта игра, и они прыгают с кочек в воду.

Зная N, определите, смогут ли лягушки добиться своей цели.

Исходные данные

На вводе находится единственное целое число N, лежащее в пределах от 1 до 499.

Результат

Если лягушки не могут поменяться местами, выведите число –1. Иначе в первой строке выведите K — количество ходов, за которое лягушки могут достичь своей цели, а во второй строке через пробел выведите последовательность Сi (1 ≤ i ≤ K): на i-м ходу прыжок осуществляется с кочки с номером Сi. Если существует множество решений, выведите любое.

Примерисходные данные

1

результат

3

2 0 1

[toll]

Серый84

эту задачу можно на пальцах посчитать ...

алгоритм

1 черная идет на пуст клетку

2 белая лягушка прыгает через черную

итого n+1 ходв

3 белые лягушки прыгают на 1 клетку назад n ходов

и все эти три действия n раз

[Серый84]

ну на пальцах это понятно и ясно, меня сам код интересует, никто помочь не может это все дело запрограммировать???

[The_Ice]

Поофтоплю, чуток:

Недавно, ко мне в руки попала игрушка colobot

http://www.ceebot.com/colobot/index-e.php http://en.wikipedia.org/wiki/Colobot http://habrahabr.ru/blogs/programmers_games/59708/

http://ru.wikipedia.org/wiki/Colobot http://www.3dnews.ru/games/colobot#voting http://v673.com/programmers-games/colobot-and-ceebot/

Суть ее в том, чтобы писав сценарии на Си-подобном языке, выполнить определенные задачи.

Игрушка старенькая, а целевая аудитория - дети 10+ лет, задания не такие уж и сложные (я не много в нее рубился =) )

Но, если искать более обобщенное решение, то вполне получится интересно убить время (:

Так о чем, я - выложить?)

[Lakers]

угумс

[The_Ice]

Как всегда: соберешь материалы, переведешь описалово с официального сайта, сделаешь торрент и на тебе:

http://ulanovka.ru/forum/viewtopic.php?t=59264 =)

http://ulanovka.ru/forum/viewtopic.php?t=61132 - а это CeeBot - версия для учебных заведений)