Каскадный · [ Стандартный ] · Линейный+ ПОИГРАЕМ 2

[kuchin]

Ошибочка... Решение не правильное, поэтому стерто

[This message has been edited by kuchin (edited 26 January 2002).]

[kuchin]

Решение.

1. Нахождение середины - посылаешь два сообщения, одно со скоростью 1, второе со скоростью 1/3, когда они встречаются - там и середина.
2. Если в рассмотренном блоке четное число компов, крайний комп (в блоке) дальше не участвует, а рядом стоящий его запоминает.
3. Начинаем искать середину, при нахождении начинаем искать середины в каждом из двух найденных блоков, и так далее по рекурсии.
4. Каждый такт рядом стоящие компы посылают соседу сообщение, в котором написано, являются ли они серединой или нет.
5. Как только оба компа справа и слева передали компу то, что они являются серединой, через 2 такта после этого он стреляет.
6. Почему через 2 такта - те, которые запомнили выброшенных компов, должны успеть сказать им стрелять тоже.
7. Там есть еще крайние случаи, но их тоже можно решить. Это уже непринципиально

[vcd_rus]

2kuchin: Молодец! В общих чертах решение верное (можно для лёгкости считать, что компов 2^N).
Если компьютер уже чья-то середина, то все сообщения слева он посылает обратно, а справа, например, он может только получить сообщения от соседа, что тот стал серединой, и соответственно уже через 2 такта стрелять.
Если комп ещё не середина, то все сообщения слева он посылает направо (если скорость 1/3 то это "жди два такта и потом передавай дальше") кроме случая, когда он получает 1/3-мессагу слева и 1-мессагу справа, и это не сообщение о середине; тогда он становится серединой.

Твой ход

[kuchin]

У меня вопрос простой:
Что такое божественная сила?

[vcd_rus]

Масса на божественное ускорение
(или то, или другое надо брать обычным, а то получится сила, божественная в квадрате )

[kuchin]

Правильно!

Я думал, что скажут божественная масса на божественное ускорение, ан нет!

[kuchin]

vcd_rus, твой ход

З.Ы. А насчет массы или ускорения - возникает интересный физико-теологический вопрос - если масса не божественная, то чья же? (ну или наоборот - ускорение)

[Tallarna]

А масса того, на кого(что) действует божественная сила, придающая божественное ускорение

Прикольнее второе - если божественная сила действует на что-то, обладающее божественной массой, то возникает ускорение этого чего-то в соответствии с обычным (читай: небожественным) законом Ньютона

Это я просто ответил, я на ход не претендую

[This message has been edited by Tallarna (edited 27 January 2002).]

[kuchin]

[FloatCrash]

Ок,проехали

[This message has been edited by FloatCrash (edited 27 January 2002).]

[kuchin]

Старо

[vcd_rus]

Даже не знаю, что и спросить... а где мона игрушки скачать?

Тогда ещё один с Microsoft interviews
Есть Linked List (в каждом объекте, есть указатель на следующий) и надо узнать, есть ли в нём циклы (т.е. идёшь по указателям вперёд и вдруг приходишь к объекту, который ты уже посещал)? Конечно, можно пройтись сперва и создать в каждом объекте поле "visited=false" а потом идти с начала, и отмечать их как true. Но на это требуется время и место. Как можно довольно быстро и эффективно узнать, есть ли циклы, ничего не добавляя, и не создавая вспомогательных структур?

[Nightmare]

Мда, прикольный флейм вышел! А с поздравлением на задачу о колодце я несколько поторопился, признаю свою ошибку, посыпаю голову пеплом.

ЗЫ: блин, ну и задачки пошли. Ломаю голову, но ничего путнего не приходит.

[Tallarna]

Вариант 1: Начинаешь удалять по очереди объекты. Если в конце пришел к концу - нет колец, если к несуществующему (ранее удаленному) объекту - было колечко

И еще - в простейшем (однолинковом) связанном списке может либо не быть кольца, либо быть, но всего 1, так ведь?

Вариант 2 (если известно количество объектов) - пройти N объектов вперед. Если конец списка - нет кольца, если объект - кольцо... Но я понимаю, что Linked List на то и такой, что количество неизвестно, поэтому ответ маловероятный.

Вариант 3. Решение. Цикл while "пока не конец списка". Идем вперед по списку вспомогательной ссылкой, увеличивая счетчик (номер объекта с начала списка), каждый раз останавливаясь и второй вспомогательной ссылкой пересчитывая с начала, до того момента, когда мы дойдем до объекта, расположенного по первой вспомогательной ссылке. Если пересчитанный заново номер стал меньше, чем пошагово увеличиваемый - мы в начале кольца

[This message has been edited by Tallarna (edited 28 January 2002).]

[vcd_rus]

quote:

---

Originally posted by Tallarna:
Вариант 1: Начинаешь удалять по очереди объекты. Если в конце пришел к концу - нет колец, если к несуществующему (ранее удаленному) объекту - было колечко
И еще - в простейшем (однолинковом) связанном списке может либо не быть кольца, либо быть, но всего 1, так ведь?

---

удалять объекты, это ещё хуже, чем добавлять новое поле Да, однолинковый, если цикл есть, то один.

quote:

---

Вариант 2 (если известно количество объектов) - пройти N объектов вперед. Если конец списка - нет кольца, если объект - кольцо... Но я понимаю, что Linked List на то и такой, что количество неизвестно, поэтому ответ маловероятный.

---

Нет, не известно. Что-то тут есть от предыдущей задачи

quote:

---

Вариант 3. [b]Решение. Цикл while "пока не конец списка". Идем вперед по списку вспомогательной ссылкой, увеличивая счетчик (номер объекта с начала списка), каждый раз останавливаясь и второй вспомогательной ссылкой пересчитывая с начала, до того момента, когда мы дойдем до объекта, расположенного по первой вспомогательной ссылке. Если пересчитанный заново номер стал меньше, чем пошагово увеличиваемый - мы в начале кольца
[/B]

---

уже ближе, но по времени это займёт O(N^2), а можно за линейное время

[Tallarna]

Спасибо за подсказку! LOL!

Итак ессе "Линейное время":

Берется 2 вспомогательных линка и (пока не конец списка) шагается вперед с разной скоростью! Если более быстрый (первый) наткнулся на второй (медленный) - мы в кольце

[vcd_rus]

.. с двойной скоростью, можете проверить.

2Tallarna: Просто, как всё гениальное, правда? Твой ход Тебе бы стоило передать право хода уже только за упорность!

[Tallarna]

1. За упорность не надо! Только за правильный ответ!
2. Спасибо за разминку мозгов А то совсем паутиной поросли

Задача (старая... и в общем, кто знает - тот знает...):
Наверное все в детстве пытались нарисовать перечеркнутый по диагоналям квадрат не отрывая карандаша от бумаги и не проводя дважды по одной и той же линии. У какой-то из традиционных восточных цивилизаций есть даже целое искусство по этому поводу - рисование орнаментов не отрывая карандаша от бумаги. Итак, вопрос: как можно, увидев рисунок практически любой сложности, определить, возможно ли его нарисовать таким способом? И почему перечеркнутый квадрат нельзя? Удачи...

[vcd_rus]

Это задача каких-то там мостов Если в какой-то вершине (пересечении линий) нечётное число линий, то это либо начало, либо конец. Т.е. таких вершин не может быть больше двух. Ну и связный должен быть граф..
В остальных случаях, думаю, можно.

[kuchin]

Не, ну если хотите, есть несколько сайтов, где лежат Майкрософтовские задачи