📌Ответ на задачу "Деревенский дурачок"

"Дурачок" был не так глуп: он понимал, что, пока он будет выбирать 50-ти центовую монету, люди будут предлагать ему деньги на выбор, а если он вы­берет пятидолларовую купюру, предложения денег прекратятся, и он не будет получать ничего.

📌Задача "Простые числа"
Сложность: 28%

Необходимо вывести все простые числа от M до N включительно.

🔻Входные данные
Входной файл INPUT.TXT содержит два натуральных числа M и N, разделенных пробелом (2 ≤ M ≤ N ≤ 10(6))

🔻Выходные данные
В выходной файл OUTPUT.TXT выведите все простые числа от M до N в порядке возрастания, по одному в строке. Если таковых чисел нет, то следует вывести «Absent».

📌Решение задачи "Простые числа"

Масса олимпиадных задач связаны с простыми числами, в частности с их поиском и определением простоты. Поэтому, прежде чем начинать разбор данной задачи, поговорим сначала о том, как определить простоту конкретного числа. Известно, что если число n составное, то один из его делителей не превосходит значения sqrt(n), поэтому при проверке на делимость числа n достаточно перебрать всевозможные делители от 2 до sqrt(n). Это можно оформить в виде следующей функции:

bool IsPrime(int n){
int i;
for i=2..sqrt(n)
if(n mod i = 0) return false;
return true;
}
Описанную выше функцию можно ускорить вдвое, если проверять делимость только на нечетные числа, а делимость на 2 рассмотреть отдельно. Так же когда уже известны все простые числа, не превосходящие sqrt(n), то еще более разумно проверять делимость только на них, тогда скорость возрастет в ln(sqrt(n)) раз. Следующий фрагмент программы демонстрирует заполнение массива p[i] простыми числами от 2 до n:

📌Логическая задача "Кольцо вокруг Земли"

Образно представьте себе нашу планету, плотно стянутую кольцом по всему ее экватору. После увеличения длины окружности кольца на 10 метров, между кольцом и поверхностью земли образовался зазор определенной величины. Как Вы считаете, сможет ли человек пройти, или хотя бы протиснуться в этот зазор?
Известно, что экватор имеет длину приблизительно равную 40 075 километров.

📌Решение задачи "Кольцо вокруг Земли"

Для решения данной задачи достаточно элементарных знаний геометрии. Изначально может показаться, что увеличение длины кольца на 10 метров, по сравнению с его длиной L= 40 075 000м будет способствовать образованию практически незаметного зазора. Зная формулу определения радиуса окружности и известную величину ее длины (L), определяем величину, на которую увеличится радиус (в нашем случае это будет величина зазора) при увеличении длины окружности (кольца) на 10м.
ΔR = (L+10м) / (2π) — L / (2π) = (40075000м+10м) / (2х3,14) — 40075000м / (2х3,14) = 1,592м
В такой зазор человек сможет не только протиснуться, но и даже пройти, немного нагнувшись.

📌Задача "Разложение на простые множители"
Сложность: 27%

Требуется вывести представление целого числа N в виде произведения простых чисел.

🔻Входные данные
Входной файл INPUT.TXT содержит натуральное число N (2 ≤ N ≤ 2(31)-1).

🔻Выходные данные
В выходной файл OUTPUT.TXT выведите список простых множителей числа N в порядке неубывания, разделенных знаком «*».

📌Решение задачи "Разложение на простые множители"

Для решения данной задачи можно найти все простые числа, не превосходящие sqrt(n), а далее делить на каждое из них число n пока оно делится, изменяя значение n. Но на самом деле вовсе не обязательно осуществлять поиск простых делителей, достаточно это проделывать со всеми числами от 2 до sqrt(n) в порядке возрастания. При этом, каждый раз при изменении значения n следует бежать до нового значения sqrt(n) для того, чтобы в итоге в n оказалось единственное простое число. Описанный выше алгоритм можно представить в следующей форме:

📌Логическая задача "Коробки с конфетами"

Пете и Коле купили по коробке конфет. В каждой коробке находится 12 конфет. Петя из своей коробки съел несколько конфет, а Коля из своей коробки съел столько конфет, сколько осталось в коробке у Пети. Сколько конфет осталось на двоих у Пети и Коли?

Ответ на задачу "Коробки с конфетами"

12 конфет.

Задача "Подстроки из одинаковых букв"
Сложность: 32%

В заданной строке, состоящей из малых английских букв, необходимо найти пару самых длинных подстрок, состоящих из одних и тех же букв (возможно, в разном порядке). Например, в строке twotwow это будут подстроки wotwo и otwow.

Входные данные
Входной файл INPUT.TXT содержит исходную строку, длиной от 1 до 100 символов.

Выходные данные
Выходной файл OUTPUT.TXT должен содержать единственное число – длину подстрок в максимальной паре, или 0, если таких подстрок в строке нет.

Логическая задача "О лифте"

Человек живет на 17-м этаже. На свой этаж он поднимается на лифте только в дождливую погоду или тогда, когда кто-нибудь из соседей с ним едет в лифте. Если погода хорошая и он один в лифте, то он едет до 9-го этажа, а дальше до 17-го этажа идет пешком по лестнице... Почему?

Ответ на задачу "О лифте"

Этот человек - лилипут, и до кнопки 17-го этажа дотягивается только зонтиком или просит кого-нибудь нажать на эту кнопку.

Задача "Степень - 2"
Сложность: 45%

Для натуральных чисел A и N требуется вычислить значение AN.

Входные данные
Входной файл INPUT.TXT в первой строке содержит числа A и N, разделенные пробелом. (1 ≤ A ≤ 9, 1 ≤ N ≤ 7000)

Выходные данные
В выходной файл OUTPUT.TXT выведите одно число – результат возведения в степень, без лидирующих нулей.

Решение задачи "Степень - 2"

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

Логическая задача "Школьный инспектор"

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

Ответ на задачу "Школьный инспектор"

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

Задача "Подпись"
Сложность: 44%

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

Учтите, что на Марсе принято подписываться полными именами, а они у марсиан могут быть достаточно длинными.

Входные данные
Входной файл INPUT.TXT содержит две строки, в которых записаны полные имена друзей. Имена, как ни странно, состоят из букв английского алфавита, из которых только первая – прописная. Длина имен от 1 до 1000 символов.

Выходные данные
В выходной файл OUTPUT.TXT выведите кратчайшую строку, в которой встречаются имена Миши и Маши одновременно. Буквы, с которых имена начинаются в этой строке нужно сделать большими. Если существует несколько решений, выведите то, которое меньше в алфавитном порядке (следует считать, что любая буква в верхнем регистре меньше, чем любая буква в нижнем регистре).

​​Решение задачи "Подпись"

В силу небольших ограничений на длину строк мы можем перебрать всевозможные варианты соединений, которые могут быть получены из данных имен. Сделаем это следующим образом: будем убирать по одному символу справа из первого имени и приписывать к нему второе, при этом каждый раз будем проверять: имеется ли в образующейся таким образом строке первое имя в качестве подстроки, если это так, то данная строка удовлетворяет необходимому условию (заканчиваться она будет вторым именем по построению), останется только преобразовать первую букву первого имени в заглавную (следует помнить, что может быть несколько вариантов вхождения первой строки в получившуюся). При встрече очередной строки, начинающейся и заканчивающейся нашими именами, будем сравнивать ее с ранее найденной, на текущий момент самой короткой. Если текущая окажется более подходящей (короче или в случае равенства длины лексикографически меньше), то ее следует запомнить. После перебора всех вариантов сокращения первой строки следует поменять строки местами, для чего удобно описать отдельную функцию search(a,b) , которая будет сокращать первую строку, приписывая вторую. Следует так же отметить, что в процессе сравнения нужно преобразовывать все символы либо в верхний, либо в нижний регистр. В начале в качестве самой короткой строки можно считать строку, состоящую из суммы исходных имен, которая очевидно обладает необходимым свойством. По завершению поиска в качестве ответа просто останется вывести ту строку, в которой мы хранили текущий наикратчайший вариант.

Алгоритмическая реализация вышеописанной идеи:

Логическая задача "Два шнура"

У Вас есть два шнура (фитиля). Каждый шнур, подожженный с конца, полностью сгорает дотла ровно за один час, но при этом горит с неравномерной скоростью. Как при помощи этих шнуров и зажигалки отмерить время в 45 минут?

Ответ на задачу "Два шнура"

Необходимо поджечь первый шнур одновременно с обоих концов - получаем 30 минут. Одновременно с первым шнуром поджигаем второй шнур с одного конца, и когда первый шнур догорит (30 минут),- поджигаем второй шнур с другого конца (оставшиеся 15 минут).