Заряжаю!

Развиваем многостороннее образование. Вопрос из области истории: Из какой страны в Россию пришла традиция ставить новогоднюю елку?

Пли-и-и-и-и!...

Ясный перец, что из Германии!

Nightmare: Тогда ты и пли дальше

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

Перезаряжаю! Огонь! (правда задачку я передрал )

Итак...

Есть кабель о шести проводах. У вас в руках простой пробник за два писят из Радиотоваров - есть контакт/нет контакта. Вы сидите в одном канализационном колодце, гадком и вонючем. Другой конец кабеля - в другом канализационном колодце в десяти, нет, в ста, метрах. Нет, пусть будет в километре от вас. Короче, идти далеко, холодно и влом. Надо найти соответстие проводов на обоих концах. Т.е., просечь, какой из шести проводов на этой стороне соответствует какому из шести на той, сходив туда всего один раз. Кабель пока что ни к чему не подключен.

easy:

Мы находимся в колодце номер 1. в колодец 2 сходить надо один раз. Итак начем:

1. нумеруем провода в колодце 1 и замыкаем попарно. например замкнуты 1 и 2, 3 и 4, 5 и 6.

2. Идем в колодец 2.
Нумеруем и тестируем парность. например оказалось что замкнуты 3 и 4, 5 и 2, 6 и 1.
замечательно! осталось разобраться внутри пар. (далее 2 варианта и более. сначала сложный)

3. в колодце 2 (пока не ушли) делаем пару замыканий по два провода из разных пар. например 4 и 5, 2 и 6.

4. Возвращаемся в колодец 1. размыкаем то что там замкнуто. и тестируем по одному из проводов от "старых" пар на другую пару. Получаем:
1 - нет контакта на 3 и 4 (нет вообще никуда, кстати) значит ето соответсвует номеру 3 во втором колодце.
2 - ето 4... некуда деваться.

теперь вторая "старая" пара: берем 2 и тестируем его с 3 и 4: один из них будет 5-й во вторм колодце. у нас вышел 3, значит 4 - это 2-й во втором колодце.

далее последней старой пары найты который не замыкает на 4-й (да и вообще никуда) или наоборот. если 5-й замыкает на 4-й значит - это 6-й провод во втором колодце.
ну а 6-й первого = 1 второго колодца.

Комбинация была:

1___________________3
2___________________4
3___________________5
4___________________2
5___________________6
6___________________1

проще вариант: во втором колодце замкнуть три провода из разных пар а остальные оставить свободными.

при возврате смотрим в первом колодце какие провода имеют контакт а каие нет. И все. телемаркет

------------------
~~~ "Такое вот хреновое лето..."

Есть другой вариант:

1. В колодце номер 1 провода нумеруются 1,2,3,4,5,6
2. Замыкаются попарно 1-ый со 2-ым и 3-ий с 4-ым
3. Вылезаем из колодца и идем целый километр во второй.
4. Во втором колодце находим два провода, которые не имеют контакта ни с одним другим. Обозначаем их A и B (чтобы не перепутать с концами из 1-ого колодца)
5. Среди оставшихся четырех находим парные (имеющие контакт между собой) и обозначаем их C, D (первая пара) и E, F (вторая пара).
6. Предварительный результат: концы 5 и 6 соответствую концам A и B (осталось уточнить кто кому), концы 1,2,3,4 соответствуют концам C,D,E,F (также осталось разобраться кто куда). Причем при определении 1-ого и 3-ого, 2-ой и 4-ый определяются автооматически, так как они разбиты на пары.
7. Замыкаем B с C и D c E (D и E - как видно, из разных пар)
8. Возращаемся в первый колодец (еще 1 км), размыкаем все.
9. Теперь самое интересное. Проверяем провода 5 и 6. Один из них должен иметь контакт с каким-нибудь из {1,2,3,4}, так как соединены B c C. Допустим, что есть контакт 5-ого с 4-ым (если нет, можно перенумеровать концы внутри множеств {1,2,3,4} и {5,6}, так чтобы 1-ый со 2-ым и 3-ий с 4-ым остались парными.) Тогда 5=B, 4=C.
10. 6=A (так как 5=B, а 5-ый и 6-ой соответствуют A и B)
10. Среди {1,2,3} находим два, имеющие контакт, такие найдуся, потому что соединены D и E. Причем это обязательно будет 3-ий (потому что 4-ый уже определен как С) и, скажем, 2-ой (если нет, меняем номера 1 и 2).
11. 1-ый конец, который не имеет контакта ни со 2-ым ни с 3-м, соответствует концу F. 1=F
12. Так как 1-ый со 2-ым когда-тот были парными и 1-ый оказался F, 2-ой соответствует E. 2=E.
13. Были соединены D и E, контакт у 2 и 3,
2=E, следовательно, 3=D

Итого: после проделанных операций с учетом перенумераций, получаем:
1=F
2=E
3=D
4=C
5=B
6=A

Главное - не запутаться!

Бля, пацаны, ну у вас в натуре клёвый жбан! Я тока глянул: какие провода, какие колодцы... голова ни болта не варит.

Уважаю. Жму руку. Ваш A.

------------------
Я бухаю, но могу ускориться.(с) "Ленинград"

2 Ditrix: начало тоже, но у меня проще. а вариантов до хрена подобных.

------------------
~~~ "Такое вот хреновое лето..."

2Bad и 2Ditrix - всё верно !!! Давай BAD, толкай дальше! Ты ответил первый.

2ditrix: всё правильно

2bad too bad

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

quote:

---

Originally posted by Bad:
easy:

Мы находимся в колодце номер 1. в колодец 2 сходить надо один раз. Итак начем:

1. нумеруем провода в колодце 1 и замыкаем попарно. например замкнуты 1 и 2, 3 и 4, 5 и 6.

2. Идем в колодец 2.
Нумеруем и тестируем парность. например оказалось что замкнуты 3 и 4, 5 и 2, 6 и 1.
замечательно! осталось разобраться внутри пар. (далее 2 варианта и более. сначала сложный)

---

ок, три пары соответствуют трём другим парам

quote:

---

3. в колодце 2 (пока не ушли) делаем пару замыканий по два провода из разных пар. например 4 и 5, 2 и 6.

---

есть пара, соединённая с обеими другими,
и две, соединённые с этой (по одному проводу из каждой).
Может быть комбинация
123456=345261, а может быть это 123456=612534, т.к. эти две пары имеют одинаковые свойства. То же самое с простым вариантом:
знаем пары, знаем соответствие проводов внутри пар, но 12-12, 34-34 или 12-34, 34-12
не знаем.

quote:

---

4. Возвращаемся в колодец 1. размыкаем то что там замкнуто. и тестируем по одному из проводов от "старых" пар на другую пару. Получаем:
1 - нет контакта на 3 и 4 (нет вообще никуда, кстати) значит ето соответсвует номеру 3 во втором колодце.

---

это совсем не понял! 34 в первом колодце принадлежат к одной паре, а все три пары хоть с чем-нибудь да и соединены с другой стороны. А если это 34 с другой стороны, то ты же сам соединил 4 и 5! Или нумеруй буквами, чтобы не путаться, или называй номерами по соответствию с первым колодцем Или я что-то не так понял?

quote:

---

Originally posted by vcd_rus:
[b]2ditrix: всё правильно

2bad too bad

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

---

Как раз вв моем решении я изначально замыкаю только две пары из трех, тем самым соотетствие незамкнутых пар определяется сразу.

2 ditrix & vcd_rus
мда... промашка вышла

надо было в начале токо две пары замкнуть - вышло вы примерно как у ditrix. Поэтому право (или обязанность) вопросящего (или вопрошающего) переходит к ditrix.
А nightmare поторопился

[This message has been edited by Bad (edited 24 January 2002).]

Ну если так, то продолдаю электротехническую тему:

В комнате три лампочки. За пределами комнаты три выключателя, каждый из которых соединен с одной из лампочек в комнате. Находясь у выключателей, вы не видите лампочек. Необходимо, один раз выйдя из комнаты и вернувшись обратно, определить соответствие выключателей и лампочек.

а изначально, все выключутели в положении Off, right?

Но это же невозможно!
Так. Изначально лампочки выключены (раз в условиях молчок).
Допустим, мы вышли из комнаты и включили 1, 2 или 3 лампочки. Вернувшись, мы сможем определиться соответственно в случаях 1 и 2 - с одной лампой, 3 - ни с одной.

простите, но у меня настроение такое....

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

Ах да, есть еще один вариант:

2 Valky: невозможно логически, возможно технически

Нужно находясь в комнате, выкрутить одну из лампочек, скажем это №1 и ЗАМКНУТЬ контакты в патроне накоротко. Потом приходим к выключателям и включаем поочередно выключатели, пока не вырубит пробки. Это выключатель №1. После чего включаем пробки (в случае с автоматами, ждем, пока сами включатся), включаем один из оставшихся и идем спокойно "считывать показания"

Небольшая поправка: так как тулсов, наверное, никаких нет, то лампочку выкручивать не надо (иначе замкнуть нечем).
Разбиваешь лампочку тупым предметом (например, головой) и скручиваешь контакты - К.З. готово.
Далее по плану, описанному Талларной.

[This message has been edited by genpix (edited 24 January 2002).]

Да уж, в находчивости вам не откажешь!

quote:

---

Originally posted by Valky:
Да уж, в находчивости вам не откажешь!

---

A что прикажешь делать?
Ведь задача поставлена некорректно.
Не заданы все условия!
Например: предположим, что в комнате изначально горит одна лампочка (или тилько две лампочки). Тогда задача решается очень просто.
Логического решения нет в случаях, когда все лампочки изначально включены/выключены. Т.е. в общем случае задача не решается.
С другой стороны, если этому электрику разрешается менять провода по своему усмотрению, то задача решается (так же как с колодцем).
Но опять же, в условии это не оговорено (в смысле: есть ли у него инструменты типа нож, отвёртка, изолента и пр.)

PS: а сам то ты знаешь решение?

[This message has been edited by genpix (edited 25 January 2002).]

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

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

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

2) То же самое можно проделать с радио-телефоном или радио-приемником. При замыкании контакта с нагрузкой должен раздаться треск (помехи имеют очень широкий спектр). Неужели в гостях нельзя найти радиотелефон или радиоприемник?

Еще одно уточнение (надеюсь, последнее)

В условии фигурируют: комната, лампочки, выключатели. Ни о чем другом не упоминается. Значит, ничего больше нету.

Надо включить два выключателя, а потом один выключить Будет одна лампочка включена, одна выключена, и одна ещё тёплая

quote:

---

Originally posted by vcd_rus:
Надо включить два выключателя, а потом один выключить Будет одна лампочка включена, одна выключена, и одна ещё тёплая

---

Блин! Умник!
И всё потому, что я давно на люминисцентные лампочки перешёл (они холодные).
Старею, голова - тупеет (или я уже говорил об этом?)

vcd_rus, поздравляю,есть еще Кулибины в русских селениях! Твой ход!

Ну держитесь! Задача сложная, я вроде её решил, но довольно приблизительно, и до конца не уверен во всех деталях:

есть ряд из N людей (компов) произвольной длины (выстроены в одну линию), с идентичным начальным состоянием. Каждый такт, комп может передать соседям слева и справа сообщение, и соответственно принять по сообщению. Самому крайнему я подаю сигнал, и через какое-то время все они одновременно должны выполнить определённое действие (задача была про солдат, которые должны были одновременно выстрелить в воздух). Т.е. задача на синхронизацию. Главная проблема: у каждого компа конечная память, задавайте изначально любой объём, но он будет фиксирован. А N никому неизвестно, и может быть сколь угодно большим.

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

Удачи, надеюсь не совсем запутал

Ну а в чем вопрос то?
Найти алгоритм, по которому стрелять? или что?

Да, надо их синхронизировать, чтобы через какое-то время они одновременно 'стрельнули'
Ещё одно пояснение: т.к. сообщения могут быть любыми, можно считать, что можно передавать по нескольку за раз, главное чтобы ни их число, ни инфа не зависели от N

Ну, vcd_rus, ну погоди! Я уже второй день над задачей голову ломаю, даже во сне приснилась и продолжал обдумывать когда проснулся....

Для начала факты:

ни один комп (солдат) не знает своего места в строю, если только он не стоит на краю. Т.е. никто не знает, какой он номер по порядку. Предположим, что каждый солдат может без ошибки считать до определенного числа (ограниченная память), например до Х=20. Недостаток устраняется быстро - нужно дать приказ передавать сообщение дальше, последнему послать его обратно и каждый начинает считать такты, до тех пор, пока либо не досчитает до 20, либо не придет обратное сообщение. Если счет дошел до 20, значит человек _не_ стоит в последней десятке, если до другого числа - то последние 10 человек могут определить свое место в строю... Аналогично со вторым концом строя... Но так как длина строя может быть больше чем Х, это нам сильно не поможет...

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

Теперь мысли:

Предположим, что после проведения вышеупомянутой операции человек определил, что он не попадает ни в первые, ни в последние Х/2. К нему пришел приказ на стрельбу через 0..Х тактов (больше нельзя - память не позволит)... Проблема в том, что он не может быть уверен, что этот же приказ дошел до людей, находящихся от него на расстоянии, большем, чем 2Х, а так как длина строя превышает это значение, то синхронности не получится.

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

Прошу ногами не бить, если где ошибся, будет очень интересно узнать, есть ли вправду тут решение?

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

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

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

Решение.

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

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

Твой ход

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

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

Правильно!

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

vcd_rus, твой ход

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

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

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

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

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

Ок,проехали

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

Старо

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

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

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

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

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

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

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

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

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

quote:

---

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

---

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

quote:

---

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

---

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

quote:

---

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

---

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

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

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

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

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

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

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

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

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

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