Войти в систему

Home
    - Создать дневник
    - Написать в дневник
       - Подробный режим

LJ.Rossia.org
    - Новости сайта
    - Общие настройки
    - Sitemap
    - Оплата
    - ljr-fif

Редактировать...
    - Настройки
    - Список друзей
    - Дневник
    - Картинки
    - Пароль
    - Вид дневника

Сообщества

Настроить S2

Помощь
    - Забыли пароль?
    - FAQ
    - Тех. поддержка



Пишет flaass ([info]flaass)
@ 2009-07-28 18:08:00


Previous Entry  Add to memories!  Tell a Friend!  Next Entry
головоломка
http://vic-gorbatov.livejournal.com/2417.html

На каждый из следующих вопросов точно один из предложенных вариантов ответа верен.

1. Первый вопрос, ответ на который – B, это вопрос
(A) 2
(B) 3
(С) 4
(D) 5
(E) 6

2. Единственные два последовательных вопроса с идентичными ответами – вопросы
(A) 2 и 3
(B) 3 и 4
(С) 4 и 5
(D) 5 и 6
(E) 6 и 7

3. Последний вопрос с таким же ответом, как этот, – вопрос
(A) 10
(B) 9
(С) 8
(D) 7
(E) 6

4. Количество вопросов с ответом A –
(A) 0
(B) 1
(С) 2
(D) 3
(E) 4

5. Ответ на этот вопрос такой же, как и ответ на вопрос
(A) 10
(B) 9
(С) 8
(D) 7
(E) 6

6. Количество вопросов с ответом A равно количеству вопросов с ответом
(A) B
(B) C
(С) D
(D) E
(E) ни одному из вышеуказанных

7. В алфавите ответ на этот вопрос и ответ на следующий вопрос
(A) различаются на 4
(B) различаются на 3
(С) различаются на 2
(D) различаются на 1
(E) совпадают

8. Количество вопросов, ответы на которые – гласные, –
(A) 2
(B) 3
(С) 4
(D) 5
(E) 6

9. Количество вопросов, ответы на которые – согласные, –
(A) простое
(B) факториал
(С) квадрат
(D) куб
(E) кратно 5

10. Ответ на этот вопрос –
(A) A
(B) B
(С) C
(D) D
(E) E

По ссылке не ходите, там есть ответ.

Это - один из непредвиденных уловов предыдущей записи.

Сейчас поеду в электричке, засеку время.


(Добавить комментарий)


[info]w_bf@lj
2009-07-28 09:11 (ссылка)
flaass, мне три задачи на прошлой работе дали, чтоб решил... типа испытания при вступлении.
Это одна из них, не осилил часа за три, хитрая,чертяка, а я методов не знаю.

Если хочешь - вторая задача из трех, кстати, про поезд:

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

Я долго думал :(
Если интересно - подкину потом еще одну.
(для читеров- игрок голый, зубы и ногти вырваны, вагоны обиты мягким впитывающим материалом, лампа за бронестеклом и не греется)

(Ответить) (Ветвь дискуссии)


[info]ext_92325@lj
2009-07-28 09:23 (ссылка)
Это хорошая задача.
Я её умею решать довольно тупо за O(n^2) (n -- число вагонов), но не умею доказывать, что быстрее нельзя.

Чем-то похожая на неё задача: есть связанный список (singly linked list, назад идти нельзя), в котором, возможно, есть цикл. Не меняя сам список и используя только O(1) дополнительной памяти, найти цикл и его первый элемент (первый элемент с двумя входящими рёбрами). Времени даётся O(n) (при этом n заранее не известно), список хорошо бы читать один раз. ;)

(Ответить) (Уровень выше) (Ветвь дискуссии)


[info]w_bf@lj
2009-07-28 09:30 (ссылка)
Ох, не математик я и не программист, дай подумать...
За (n^2)+n переходов...
А насчет списка - видимо близко, да...

(Ответить) (Уровень выше)


[info]anna_frid@lj
2009-07-28 10:14 (ссылка)
Пардон, конечно, но как можно вообще убедиться в том, что вагоны начали повторяться? Что это не идут все новые и новые, совершенно случайно повторяющие оставленный порядок лампочек?

(Я вообще решаю такие вещи довольно плохо, может, я чего-то не понимаю?)

(Ответить) (Уровень выше) (Ветвь дискуссии)


[info]ext_92325@lj
2009-07-28 10:28 (ссылка)
Ну вот можно.
Как маленькая подсказка — тут, пожалуй, принципиально, что по вагонам можно ходить и вперёд, и назад.

(Ответить) (Уровень выше) (Ветвь дискуссии)


[info]anna_frid@lj
2009-07-28 10:49 (ссылка)
А, спасибо! Тогда действительно просто.

(Ответить) (Уровень выше)


[info]flaass@lj
2009-07-28 14:20 (ссылка)
Дык, будет O(n), если удваивать длины вылазок. В памяти-то мы не ограничены.

(Ответить) (Уровень выше) (Ветвь дискуссии)


[info]ext_92325@lj
2009-07-28 15:50 (ссылка)
Красиво, я так делать не догадался. :-)

(Ответить) (Уровень выше)


[info]flaass@lj
2009-07-28 12:16 (ссылка)
Вначале лампы выключены или включены неизвестно как?

(Ответить) (Уровень выше) (Ветвь дискуссии)


[info]w_bf@lj
2009-07-28 12:25 (ссылка)
Рандом. Ну и, как сказано выше, можно ходить вперед и назад и с особым цинизмом считать количество ходов в ту и другую сторону.

(Ответить) (Уровень выше) (Ветвь дискуссии)


[info]sergey_koroteev@lj
2009-07-28 13:50 (ссылка)
Тогда, как вариант, такое решение: погасить в первом вагоне фонарик, идти вперёд, до первого погашенного и считать вагоны. Как встретится погашенный, включить его, вернуться обратно на отсчитанное до этого число вагонов (должны вернуться в самый первый) и проверить, включен ли там фонарь. Если да, то, значит, мы прошли весь состав и знаем сколько в нём вагонов. Если нет, то нам по пути просто встретился вагон, где тоже был погашен фонарь, поэтому возвращаемся к нему и идем дальше, продолжая отсчетов вагонов, как будто его не было на пути. Так движемся пока снова не встретим вагон с погашенным фонарем, после чего повторяем процедуру с возвращением. Все эжто повторяется до тех пор, пока мы все таки не увидим ,что фонарь в первом вагоне снова стал зажжённым

(Ответить) (Уровень выше)