1. Является ли число степенью двойки Написать тело функции bool isExp (int32_t a) которая получает положительное число и возвращает true если это число является степенью двойки, т.е. pow(2, n) = a, n- натуральное число. Время выполнения функции не должно зависеть от a. Решение: 2. Арбуз Арбуз весит 100 кг и в нем 99% воды. Через какое-то время в нем стало 98% воды. Сколько стал весить арбуз? Решение: В самом начале в арбузе был 1% сухого вещества, то есть 1 кг. Сухое вещество испариться не может. А значит, когда его стало 2%, его вес не изменился (остался 1 кг). В результате, 2% = 1кг. Соответственно, 100% = 50кг. Ответ: 50 кг. 3. И снова о монетах На столе стоят 10 одинаковых стаканов. В каждом из них по 10 одинаковых монет. Известно, что в одном стакане все монеты поддельные (весят на коэффициент k отлично от настоящих — k известно и одинаково для каждой из поддельных монет). Необходимо с помощью ВСЕГО ЛИШЬ ОДНОГО взвешивания определить, в каком стакане поддельные монеты. Решение: 1) Вообще говоря, о типе весов ничего не сказано. Рассмотрим вариант электронных весов. Занумеруем мысленно каждый стакан. Положим на электронные весы 1 монету из первого стакана, 2 монеты из второго, и т.д., до 10 монет из 10-го стакана. Вес одной подлинной монеты х грамм. Вес одной поддельной монеты k*х грамм. На весах получили сумму: Sigma по n=1..10 от n*(k^l[n]*x)^n, где l — десятимерный вектор, каждая координата которого принадлежит {0,1}, причем, с ограничением, Sigma по n=1..10 от l[n] = 1. Таким образом, получив сумму, мы всегда взаимно однозначно определим, вектор l. Номер его единичной координаты — номер стакана с поддельными монетами. 2) Вероятно, задача имеет решение также с чашечными весами. 4. Задачка про жадных пиратов Как трем жадным пиратам поделить золото, чтобы ни один из них не считал, что у него меньше, чем у любого другого, даже если любые двое из них в сговоре? Решение: Обозначим пиратов: П1, П2, П3. 1) П1 делит все золото на 3 равных, по его мнению, кучки: А, В, С. 2) П2 выбирает наибольшую кучку, пусть это будет А. 3.1) Если П2 думает, что 2 наибольших кучки не совпадают, то П2 отделяет от А кучку, делая ее такого же размера как и вторая по величине. Т.о. А поделена на А1 (кучка такого же размера как и вторая по величине) и А2 (остаток). 3.2) Если П2 думает, что 2 наибольших кучки совпадают, то пираты выбирают в следующем порядке: П3, П2, П1. 4) П3 выбирает кучку между А1 и двумя другими (В, С). 5) П2 выбирает кучку с ограничением, что: если П3 не выбрал А1, то он должен ее выбрать. 6) П1 выбирает последнюю кучку (не А2). Кучка А1 должна быть выбрана либо П3, либо П2. Назовем пирата, выбравшего А1, ПА, другого — ПВ. 7) ПВ делит А2 на 3 равные кучки. 8) ПА выбирает кучку, являющуюся частью А2. 9) П1 выбирает кучку, являющуюся частью А2. 10) ПВ выбирает последнюю оставшуюся кучку. Пояснение почему все пираты думают, что другой не получил больше золота. Без потери общности, мы можем сопоставить пиратов с кучкаи следующим образом: пираты: ПА ПВ П1 кучки: А1 В С А21 А23 А22 — ПА получил А1 и наибольшую кучку от А2. Для него: A1 >= B, A1 >= C. Т.о. ни один из пиратов не получил золота больше, чем он. — ПВ получил В и кучку от А2. Для него: B >= A1, B >=C. Также, он поделил А2 на 3 такие кучки, что между собой они равны. — П1 получил С и кучку от А2. Для него: C >= A1, C = B. П1 считает, что ПВ не получит больше, чем он, потому что П1 выбрал свою кучку от А2 раньше ПВ. П1 считает, что ПА не получит больше, чем он, потому что для П1: С = А, А = А1 + А2; поэтому С больше, чем А1 и кучка от А2, которую получил ПА. (Даже если ПА взял целую А2, у П1 не будет меньше золота, чем у него) 5. Хирургия Трём хирургам необходимо последовательно прооперировать в полевых условиях больного, страдающего заразным заболеванием. Сами хирурги тоже больны, причём все — разными болезнями. В распоряжении хирургов есть лишь две пары стерильных перчаток. Подскажите план операции, после которой ни хирурги, ни больной не заразятся друг от друга. (Помогать друг другу во время операций хирурги не должны. Оперировать одной рукой нельзя.) Решение: Первый хирург может надеть сразу две пары перчаток. Затем второй хирург наденет ту пару, которая была внешней во время первой операции. А третий хирург будет делать операцию опять в двух парах перчаток, причём внешняя останется внешней, а пара перчаток, бывшая во время первой операции внутренней, останется внутренней, но будет вывернута наизнанку.
