OK, решено. По другим задачкам есть мысли?

Задача 4.

InToTheSorrow, верно.

Задача 1: такая последовательность есть. Например, известно, что с повышением номера числа, количество простых чисел уменьшается... Можно в конце концов найти такую, которая бы включала в себя только составные числа.
Например... Ну не знаю, можно попробовать начать с числа 2012! (факториал)

Задача 3: ответ на эту задачу следует напрямую из доказательства 2-ой задачи, ведь если у нас высота очень малая, то расширяя основание, медиану можно сделать сколь угодно большой.

Аромат,
> известно, что с повышением номера числа, количество простых чисел уменьшается
"Известно"? А доказать? :)
На что делится число (2012!+1)?

> расширяя основание, медиану можно сделать сколь угодно большой
Ну, примерно так, да.

Васе очень нравится быть дежурным по своему пионерскому отряду. Но по санитарным нормам пионер не может быть дежурным более двух дней подряд. Тогда Вася договорился со своим другом Петей, чтобы тот иногда сменял его. Но Петя очень уважает своего друга и хочет, чтобы Вася как можно чаще был дежурным. Поэтому Петя никогда не соглашается дежурить больше одного дня подряд.
Сколькими способами ребята могут составить расписание своих дежурств на N дней?

Вход: натуральное число N, не превышающее 146.
Выход: натуральное число - количество способов.
Пример: вход - 5, выход - 7.
Пояснение к примеру: ВВПВВ, ВВПВП, ВПВВП, ВПВПВ, ПВВПВ, ПВПВВ, ПВПВП.

Опишите решение, не предусматривающее перебор вариантов, или программу, работающую в пределах 1 секунды.

64-разрядная целая арифметика без проблем сосчитает результат при N примерно до 155. Но 146 - уж очень в тему. )

А что ты улыбаешься? Для ровного счета, очевидно же.

Всем оживления темы, посоны!

Нeктo нaхoдится в oднoм из гoрoдoв А или В, надo придумaть вoпрoс для пеpвого встречнoгo, пpичeм нектo нe знaет лoжeн oтвeт нa eгo вoпpoc или иcтинeн, нo пo oтвeту надo тoчнo oпрeдeлить, в кaком из гoрoдoв oн нaхoдитcя.

Давайте, ребятки, я в вас верю :3

То есть, хочешь сказать, что и про города ничего неизвестно? Типа и в том, и в другом городе могут как соврать, так и правду сказать? Такой вот лютый рандом?
upd. Что бы вы ответили, если бы я вас спросил, в каком из городов А или Б мы находимся? :)
updupd. Работает, конечно, только при условии, что отвечающий гарантированно либо всегда врет, либо говорит правду. Если он может и то, и другое, то... ДА И НЕ ВЫЯСНИТЬ ТОГДА!

Вроде бы исходная задача такова:
Жители города А всегда говорят правду. Жители города Б всегда врут. Жители обоих городов часто наведываются друг к другу в гости. Вы находитесь в одном из этих городов. Какой вопрос следует задать первому встречному, чтобы определить своё местонахождение?

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

Могу доказать, что в такой постановке задача не решается.
Доказательство. "Первый встречный" может сам оказаться не местным, а решающим ту же самую задачу. Соответственно, никакой дополнительной информацией он не располагает. Единственное преимущество двух незнаек перед одним - наличие двух тел. Его невозможно применить, т. к. не предполагаются контакты с третьими лицами или какие-либо перемещения. Стало быть, два незнайки экивалентны одному. А сам по себе один человек ничего не определит. Вот.

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

Тоже вариант. Был такой сериал "десятое королевство", там герою задали классическую задачку.
Перед ним было две двери, у каждой двери по охраннику, один из них всегда врет, другой всегда говорит правду. За одной дверью плюшка, за другой - КРОВЬКИШКИ. Мужик подумал, открыл от фонаря одну дверь и кинул туда охранника. :) Узрел эффект и выбрал другую дверь, соответственно. Ок.

Sauvage привел нам занимательные рассуждения про двух людей, решающих одну задачу. Можно еще дополнить: скажем, первый встречный окажется немым. Или иностранцем. Или двухлетним ребенком. Или крысой.
Буквоедствовать можно по-разному (:
Разницу постановок, алсо, лично я так и не увидел)

"Вы скажете правду, если находитесь в городе А?"
Или, другой вариант:
"Вы скажете правду, если находитесь в городе В?"