Перейти к содержанию

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


Рекомендуемые сообщения

Lakers

старая задача ... жизнь называлася ... я ее на тр7 когда то делал ... :)

Добавлено спустя 5 минут 44 секунды:

Вот вам задача

Есть некоторое количество точек на плоскости N с координатами х1 y1 ...xN yN

нада наити такую окружность минимального радиуса , которая будет содержать максимальное количество точек ... но не менее N -n где n некоторое количество точек которые можно откинуть...

ввод: координаты точек, n

вывод: коодинаты центра окружности, радиус , коодинаты откинутых точек ...

Ссылка на комментарий

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

Ссылка на комментарий

toll

Сначала реши предыдущую, потом загадывай.

И как насчёт ограничений? без них любую задачу перебром решить можно)

Написал правила в первом посте

Lakers

Эти бактерии пока для меня загадка, сам-то решил?

Ссылка на комментарий

Э бактерии - смех, один.

игра жизнь live + перебор комбинаций, засеивания клеток, и проверка похоже ли?

Классическая задача+перебор заполнения матрицы MxN.

Ссылка на комментарий

если она решается тупым перебором то действительно смешно.но както я сомневаюсь что она так проста. на acm.timus.ru её пробовали решить 9 человек а релил 1%, т.е. 1человек.скорее всего все валются на временном ограничении.или какаято хитрость в ней всёже есть.

Ссылка на комментарий

+1 Перебор не подходит хотябы потому, что невозможно заключить можем ли мы получить исходную картину. Собственно мы либо её получаем, либо бесконечно "живём".

Ссылка на комментарий

Вобщем это гроб дубовый, из топа тимуса (а это мировые призёры и чемпионы) почти никто не решил.

Автор, предлагаю дать другую. Либо пробуем решить toll'a с ограничениями "перебор не проходит"

Ссылка на комментарий

0xDEADBEEF что за топ тимуса?

а по мойму ее можно решить перебром с конца т.е.:

всего клетка может быть заселена 5 бактериями - одна собственная и 4 от соседних, следует

если на определенной итерации у клетки нет 4 заселенных соседей, значит единичка в ней реальная а не получена путем погибания 4 бактерий

нужно искать единицы и расселять(1 ставить в ноль а соседнии уменьшать на один) эту клетку,

если попытка не удалась то обратно заселять и искать новую единичку

что значит попытка не удалась:

1.неосталось единичек, все перебрали или их нет вообще

2.получены две соседнии клетки с реальными единичками

3.получена клетка у которой количество бактерий больше чем количество заселенных соседних клеток +1 (например если нет заселенных соседних клеток то не может быть больше одной бактерии)

Ссылка на комментарий

ладно,думаю на эту задачу только времени уйдет больше.лучше чтонибудь не такое жёское=)

Шифровка

Ограничение времени: 1.0 секунды

Ограничение памяти: 64 МБ

Мюллер много раз пытался поймать Штирлица с поличным, но тот всё время выкручивался. Как-то раз Штирлиц просматривал электронную почту. В это время незаметно вошел Мюллер и увидел, как у него на экране появился бессмысленный набор символов. «Шифровка», — подумал Мюллер. «UTF-8», — подумал Штирлиц.

Известно, что Штирлиц шифрует текст следующим образом:

Убирает все пробелы и знаки препинания.

Заменяет все подряд идущие одинаковые буквы на одну такую букву.

Многократно вставляет в произвольное место текста две одинаковых буквы.

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

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

В единственной строке записана шифровка Штирлица, состоящая из строчных латинских букв. Длина шифровки не превосходит 200000.

Результат

Выведите восстановленный текст.

Пример

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

wwstdaadierfflitzzz

результат

stierlitz

номер задачи: 1654.

Добавлено спустя 1 минуту 3 секунды:

заадча простая...

Ссылка на комментарий

0xDEADBEEF

В моей задаче перебор есть... вот только две точки будут лежать на окружности но не обязательно на диаметре, и не обязательно какая то из точек будет центром окружности (возьмем для примера 3 точки ) вот в чем вся первая изюминка этой задачи, вторая это условие как можно отбросить несколько точек

А про бактерии или я неправильно понял условие ... но если взять пример и последовательно сделать планы заселения то исходная картина не получается

Ссылка на комментарий

triwire

http://acm.timus.ru/ranklist.aspx

Даю 99% что этот алгоритм не пройдёт.

Lakers

Собственно решение задачи описанно в условии. В реализации обойдёмся стэком, сравнивая каждый новый элемент с вершиной.

toll

Мнда, первая изюминка всё портит. Выходит преребираем все n точек, выкидываем их, из оставшихся ищем 2 наиболее удалённые (можно выпуклой оболочкой, можно качением), минимальная из всех и будет ответом.

я прав?

Ссылка на комментарий

0xDEADBEEF

эту задачу я придумал сам ... конкретного решения нет есть только предположения как можно решить ...

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

2 две самые адаленные точки будут принадлежать окружности ... те отрезок между ними это есть хорда ...

3 центр окружности будет лежать на перпендикуляре к этому отрезку

4 ну и собсвенно на компьютере перебор окружностей .... перемещая центр и сжимая радиус ...

----------------------------------------------------

Ссылка на комментарий

Что-то у меня никак не получается получить холст из примера заполняя по ответу из примера

Пробовал два алгоритма:

1)

цикл

{

заселяется клетка,

увеличиваются на единицу соседи этой клетки, которые не равны 4 (справа,слева,сверху,снизу), если же ==4, то 1

}

2)

цикл

{

заселяется клетка,

увеличиваются на единицу все клетки, у которых заселены соседи

}

Я неверно понял задачу?

Ссылка на комментарий

toll, я до инкремента проверяю равно ли 4, если равно, то 1, если нет то инкремент.

2-й вариант который я показал и есть с размножением, только все равно не сходится... может задание переведено не так? скиньте в оригинале

Ссылка на комментарий

Пожалуйста, войдите, чтобы комментировать

Вы сможете оставить комментарий после входа в



Войти
  • Последние посетители   0 пользователей онлайн

    • Ни одного зарегистрированного пользователя не просматривает данную страницу
×
×
  • Создать...