Воскресные задачки

← →
Vasya.ru © (2005-02-27 00:59) [0]

Прошлые задачки оказались легкими для местных мастеров, выкладываю еще 2 задачи чуть посложнее

1. Кодировка.
Общеизвестны два самых простых метода кодировки: метод подстановки и метод перестановки. Первый заключается в том, что каждую букву в исходном слове мы заменяем на какую-то (возможно другую) букву. Например из слова HEHE , заменив E на O, а H на T, мы получаем слово TOTO. Второй состоит в том, что буквы в слове переставляются в произвольном порядке (например OMON -> NOOM). Оба метода легко дешифруются и поэтому чаще всего применяются совместно - то есть сначала к слову применяется первый, а затем второй. Нужно определить, можно ли таким преобразованием получить из одного слова другое.
Прим. слова состоят только из больших латинских букв, не длинее 100 символов

2. Мартышка и орехи.
Мартышка, в кармане которой лежит K орехов, бегает по N-этажному зданию. Бросая орехи из окон здания, она решила экспериментально определить ореховый коэффициент - минимальный этаж, начиная с которого орехи разбиваются. Бросив орех с какого-то выбранного ею этажа, она наблюдает за тем, разбился он или нет. Если он разбился, он уже не пригоден для дальнейших экспериментов, а если нет - она спускается и подбирает его. Затем она выбирает еще этаж и бросает оттуда и т.д. Требуется найти минимальное количество попыток, за которое мартышка гарантированно решает свою задачу при любом ореховом коэффициенте. Обратите внимание, что здание может оказаться недостаточно высоким, и орехи не будут разбиваться вообще.

← →
DiamondShark © (2005-02-27 01:18) [1]

По второй могу пока сказать, что не больше N/2.
Точнее не могу -- спать охота.

← →
QuasiLamo © (2005-02-27 01:19) [2]

в одном месте собрали 2005 самых умных ученых, чтобы подвергнуть испытанию. Им сказали, что их поставят в ряд друг за другом, на каждого из них наденут колпаки(либо красный, либо синий). При этом самый первый ученый будет смотреть в затылок второму, второй в затылок третьему и т.д. Таким образом, первый будет видеть всех, последний - никого из своих соратников. Каждый ученый в отдельности не сможет без посторонней помощи узнать цвет своего колпака, проще говоря, он его не увидит. Напоследок им сказали, что задача каждого из них будет состоять в том, чтобы правильно выкрикнуть цвет колпака, надетого на нем. Считается, что каждый из ученых в процессе испытания будет слышать то, что кричит любой из его соратников. Право голоса в процессе испытания каждому из ученых дается один раз, и выкрикнуть он может только одно из двух слов: "красный" или "синий", и это будет считаться цветом его колпака. Если ученый правильно назвал цвет своего колпака, значит, он справился с задачей.
А теперь, собсно вопросы:
1. Какая тактика должна быть выбрана учеными, чтобы максимальное количество назвало правильный цвет своих колпаков?
2. Сколько гарантированно правильных ответов будет получено при этом?

← →
QuasiLamo © (2005-02-27 01:27) [3]

Vasya.ru © (27.02.05 0:59)
2. вроде, если я прально понял условия, (log(N) по осн. 2) - минимальное количество попыток при наихудшем стечении обстоятельств(при использовании бинарного поиска). Я вот только не пойму, зачем дано K?

← →
GuAV © (2005-02-27 01:40) [4]

1.
type TLetterCount = array["A".."Z"] of Byte; function CountLetters(const S: string): TLetterCount; var C: Char; I: Integer; begin FillChar(Result, SizeOf(Result), 0); for C := Low(Result) to High(Result) do for I := 1 to Length(S) do if S[I] = C then Inc(Result[C]); end; function CompareLettersCount(const L1, L2: TLetterCount): Boolean; var C: Char; I, J: Integer; begin J := 0; for I := 1 to 100 do begin for C := Low(TLetterCount) to High(TLetterCount) do begin if L1[C] = I then Inc(J); if L2[C] = I then Dec(J); end; if J <> 0 then begin Result := False; Exit; end; end; Result := True; end; function CanBeConverted(const S1, S2: string): Boolean; begin Result := CompareLettersCount(CountLetters(S1), CountLetters(S2)); end; procedure TForm1.Button1Click(Sender: TObject); begin Caption := BoolToStr(CanBeConverted(Edit1.Text, Edit2.Text), True); end;

QuasiLamo © (27.02.05 1:27) [3]
Я вот только не пойму, зачем дано K?
Орехов должно хватить. Так, если К = 1, то нужно идти только сверху по одному вниз, т.е. ответ равен N. Если 1 < K << N то cложнее...

← →
GuAV © (2005-02-27 01:48) [5]

GuAV © (27.02.05 1:40) [4]
только сверху по одному вниз
наоборот, снизу вверх.

← →
Alex_Petr © (2005-02-27 02:03) [6]

QuasiLamo © (27.02.05 1:19) [2]
Гарантированно: 2004.
Красный: четное количество красных, синий - нечетное.

← →
GuAV © (2005-02-27 02:11) [7]

1.
Немного оптимизировал
function CountLetters(const S: string): TLetterCount;
var I: Integer;
begin
FillChar(Result, SizeOf(Result), 0);
for I := 1 to Length(S) do
if S[I] in ["A".."Z"] then
Inc(Result[S[I]]);
end;

2.
Про мавпу - искать бинарным поиском до последнего ореха, а потом по одному вверх ?

← →
GanibalLector © (2005-02-27 02:15) [8]

2 QuasiLamo © (27.02.05 01:19) [2]
Это уже было,правда в другой интерпритации.Jack128 баловался!

← →
QuasiLamo © (2005-02-27 05:37) [9]

GanibalLector © (27.02.05 2:15) [8]
Alex_Petr © (27.02.05 2:03) [6]
это из олимпиадных заданий

← →
Vasya.ru © (2005-03-02 16:26) [10]

GuAV © (27.02.05 2:11) [7]
2.
Про мавпу - искать бинарным поиском до последнего ореха, а потом по одному вверх ?

Бинарный поиск - не самое быстрое решение, так например при N = 10, K = 2 бинарным поиском понадобится сделать 5 бросков орехов, а можно сделать за 4

решение для 2 я видел в нете, там для 100 этажей и 2 стёклышек
там говорится и обобщение на K стёкол
есть что-нибудь другое?

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

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

Fay © (02.03.05 17:48) [12]
Не понял тебя. Задача мартышки не разбить орех, а найти этаж, начиная с которого орехи разбиваются.
default © (02.03.05 17:26) [11]
Ссылку не вспомнишь?

Vasya.ru © (02.03.05 18:02) [14]
" Вы находитесь в 100-этажном здании, а в руках у Вас две стеклышка. Вы знаете, что выбросив стекло с этажа H или выше, оно разобьется, упав на землю. Если же Вы выбросите его с этажа H-1 или ниже, с ним ничего при падении не случится. Вы можете спуститься на нижний этаж, подобрать стекло, если оно не разбилось и использовать его заново. Каков алгоритм, с помощью которого можно определить число H за минимальное число шагов?

Ответ: Решение Константина Кнопа:
Замечание 1.
Можно было бы формулировать задачки и почетче.
Следствие.
Эта задача допускает несколько разных пониманий.

Я приведу решение, которое относится вот к какому пониманию: 1) шагом называется одна попытка бросания стеклышка 2) ищется алгоритм, который ЗАВЕДОМО укладывается в некое число шагов, независимо от того, каким именно окажется число H. Иными словами, если обозначить f(H) число шагов, необходимое для того, чтобы алгоритм закончил работу в случае, когда "ответом" служит H, то ищется алгоритм, минимизирующий max f(H) по всем H от 1 до 100.
Почти очевидно, что этот алгоритм должен быть в общих чертах следующим: сначала кидается первое стеклышко с этажей a1 < a2 < ... < ak - до тех пор, пока оно не разобьется. После этого (известно, что для этажа a_m стеклышко еще не разбивалось, а для этажа a_{m+1} уже разбилось) запасного стеклышка уже нет, поэтому второе стеклышко приходится кидать подряд по всем этажам от 1+a_m до a_{m+1}-1 включительно. Такой алгоритм требует (m+1) шагов для первого стеклышка и не более чем (a_{m+1}-1-a_m) шагов для второго стеклышка (худшим случаем, очевидно, будет тот, когда второе стеклышко придется кидать со всех этажей, то есть оно не разобьется вплоть до (a_{m+1}-1)-го этажа.
Если мы хотим, чтобы max f(H) по всем H был ограничен сверху величиной N, то это требует соблюдения неравенств
a_{m+1}-1-a_m + m + 1 <= N
при всех m. Так как a_0=0, то это означает, что
a_1 <= N,
a_2 - a_1 <= N-1,
a_3 - a_2 <= N-2,
.................
a_N - a_{N-1} <= 1
При этом алгоритм позволяет полностью "пройти" здание, в котором a_N этажей (и не больше, потому что если первое стеклышко не разбилось даже при N-м шаге, то все попытки уже исчерпаны).
Выписанную систему неравенств можно почленно сложить и получить почти очевидное неравенство
a_N <= N(N+1)/2.
Поскольку нам нужно пройти 100-этажный дом, то необходимо выполнение неравенства 100 <= N(N+1)/2, а так как хочется минимизировать N, то нужно взять наименьшее из натуральных значений N, удовлетворяющих этому неравенству, то есть N=14.
На этом доказательное теоретизирование заканчивается и начинается голая практика.
Все вышесказанные рассуждения приводят к очень естественному и простому алгоритму бросаний: кидаем стеклышко последовательно с 14-го, 27-го, 39-го, 50-го, 60-го, 69-го, 77-го, 84-го, 90-го, 95-го, 99-го и 100-го этажей, пока оно не разобьется. Как только стеклышко разбилось, кидаем второе стеклышко по всем промежуточным этажам от последней "удачной" пробы и выше. Это гарантирует, что для любого H результат будет получен не более чем на 14-м ходу. Доказательство оптимальности представлено выше.

Замечание 2.
100 - "неправильная" высота дома для данной задачи. Было бы более красиво взять, скажем, 120-этажный дом.
Замечание 3.
Мне неизвестен алгоритм, который решает эту задачу в другом понимании - когда требуется минимизировать СРЕДНЕЕ число шагов-попыток (при естественном допущении, что все H равновероятны в качестве ответа). Иными словами, я не умею минимизировать сумму f(H) по всем H от 1 до 100.
Замечание 4.
Задача допускает обобщение (не очень сложное) на три, четыре и большее число стеклышек. Там в алгоритме естественно возникают биномиальные коэффициенты C_N^3, C_N^4 и т.п."

Воскресные задачки Найти похожие ветки