1 Требуется отгадать число от 1 до $n,n>10$, задавая лишь вопросы, на которые можно отвечать "да" или "нет"; при этом отвечающий может один раз солгать. Придумайте алгоритм, гаранированно позволяющий сделать это быстрее, чем за $\lceil \log_2n \rceil +1$ шагов.
2 Зададим числовую последовательность $a_n$ следующим образом. Пусть $a_1$ и $a_2$ - произвольные натуральные числа. Число $a_n$ получается приписыванием к $a_{n-1}$ числа $a_{n-2}$ справа. Предложите алгоритм, вычисляющий по данным $a_1$ и $a_2$ $i$-ю цифру числа $a_n$ и оцените его временную сложность. Ограничение по памяти: О(1)
3 В полукруге есть $n$ неизвестных нам точек. Разрешается задавать вопросы вида "каково расстоние от точки Х до ближайшей из этих точек?". Если расстояние оказываается нулевым, точка считается угаданной. Докажите, что хотя бы одну из этих точек можно угадать не более чем за $2n+1$ вопрос.
4 Квадратная матрица $n \times n$ заполнена натуральными числами. Предложите алгоритм, находящий два элемента этой матрицы, не лежащих ни в одной строке, ни в одном столбце, с максимально возможным произведением. Ограничение по времени $O(n^2)$, по памяти $О(n)$.
5 В социальной сети зарегистрироано n человек. Каждый участник может подписываться на сообщения других участников, причем если человек A подписан на B, то из этого не следует, что B подписан на A. Известно, что среди зарегистрированных пользователей есть знаменитость - человек, на которого подписаны все n-1 других пользователей, но он сам не подписан ни накого. При помощи одного запроса к серверу вы можете определить, подписан ли человек А на сообщения человека B. Предложите алгоритм, позволяющий найти знаменитость за не более чем n запросов к серверу.
6 В корридоре длины L находятся n роботов, i-й из которых изначально расположен в позиции $x_i$ (все позиции различны, $0 \leq x_i \leq L$). Все роботы движутся с единичной скоростью вдоль коридора, i-й робот движется со скоростью $v_i\ (\pm 1)$. При столкновении робота с границей корридора или с другим роботом направление вектора скорости робота меняется на протиоположное. Прошло t единиц времени:
(a) Требуется найти множество точек, в которых находятся роботы (без учета порядка: не важно, какой робот находится в какой точке; точки в множестве не должны повторятся)
(б) Дл каждого робота i необходимо указать его финальное положение $y_i$ в коридоре
Предложите эффективный алгоритм решения этих задач
7 Трое игроков по очереди вынимают от 1 до m (m > 1) камней из кучи (количество камней им изначально известно). Игрок, вынувший последний камень, проигрывает. Докажите, что если изначально куча была достаточно велика, то любые два игрока, договорившись, сумеют привести третьего к проигрышу.
8 Предложите алгоритм, находящий значения P(n+1), P(n+2),...,P(2n) неизвестного многочлена n-й степени P(x), если даны его значения P(0), P(1),...,P(n). Ограничение по времени - $O(n^2)$
9 Трудоемкость алгоритма А описывается следующим соотношением (T(n)- время решения задачи размерности n)
$T(n) \leq T(\lfloor \sqrt{n} \rfloor) + 1,\ T(1) = C_1(const)$
Найдите асимптотически как можно меньшую функцию, удовлетворяющую этому соотношению. Ответ предоставьте в $O$-нотации, докажите, что функция удовлетворяет данному соотношению.
10 Палиндромом называется строка, которая одинаково читается слева направо и справа налево. Рассмотрим некоторую строку S, состоящую из маленьких латинских букв. Какое минимальное количество букв (возможно нуль) нужно в ней удалить, чтобы она не являлась палиндромом? Предлоите алгоритм решения задачи, докажите его корректность, оцените трудоемкость.
11 Дан массив из n целых чисел. Предложите алгоритм, сортирующий их по остатку при делении на 5 за время O(n) (в каком порядке будут расположены числа, имеющие один и тот же остаток, неважно). Ограничение по дополнительной памяти O(n).
12 За столом сидят n старателей, перед каждым из которых находится кучка золотого песка. Каждую минуту происходит следующее: по общей команде каждый из них перекладывает в свою кучку половину песка из кучки левого соседа и половину из кучки правого соседа. Опишите асимптотическое поведение кучек (а) при n=3 (б) при произвольном n.
13 Даны два массива целых чисел $a[1..n],b[1..k]$, причем все элементы $b$ различны. Предложите алгоритм, находящий набор индексов $i_1 < i_2 < \dots <i_k$ с минимальной разностью $i_k - i_1$, для которого набор $a[i_1],...,a[i_k]$ является перестановкой элементов массива b. Ограничение по времени - O(nk), по дополнительной памяти - O(n).
14 Дана матрица $n \times n$, каждая строка и каждый столбец которой упорядочены по возрастанию ($a_{ki} < a_{kj},\ i<j$). Предложите алгоритм, находящий два элемента этой матрицы, сумма которых наиболее близка к заданному числу q. Ограничение по дополнительной памяти - O(n). Изменять исходную матрицу нельзя.
15 Даны n отрезков $[a_i, b_i]$. Назовем индексом вложенности отрезка $[a_i, b_i]$ количество отрезков, которые его содержат. Предложите алгоритм, определяющий, есть ли в наборе отрезок с индексом вложености, превышающим 1000. Ограничение по времени $O(n log(n))$, по дополнительной памяти - O(n).
16 В графстве имеется несколько городов, соединенных дорогами, причем из каждого города выходит ровно 3 таких дороги. Инквизитор странствует по графству, искореняя ересь. Выехав из города Э, он едет по дорогам, причем после каждого посещенного им города он поворачивает либо направо, либо налево по отношению к дороге, по которой приехал, и никогда не сворачивает в ту сторону, в которую он свернул перед этим. Докажите, что рано или поздно брат Франсуа вернется в город Э.
17 В множестве из n человек каждый может знать или не знать другого (если А знает B, отсюда не следует, что B знает A). Все знакомства заданы булевой матрицей $n \times n$. В этом множестве может найтись или не найтись знаменитость - человек, который никого не знает, но которого знают все. Предложите алгоритм, который бы находил в множестве знаменитость или говорил, что ее в этом множестве нет. Сложность по времени O(n), сложность по памяти O(1).
18 Назовем двумерный массив действительных чисел $A[1..n][1..n]$ возрастающим, если для любых $k,l \ A[i][j] \geq A[i][j],\ i \leq l,\ j \leq l$. Задача поиска в квадратном возрастающем массиве формулируется так: для заданного возрастающего массива $A[1..n][1..n]$ и некоторого числа Х определить, встречается ли число Х в массиве А. Покажите, что не существует алгоритма, решающего эту задачу менее чем за n сравнений.
19 Дан числовой массив данных n. Предложите алгоритм, находящий максимальное значение сумм отрезков этого массива. Ограничение по времени - O(n), по дополнительной памяти - О(1)
20 Известно количество секунд, прошедшее с начала некоторых суток. Напишите программу, которая запишет текущее время в формате электронных часов. Формат: h:mm:ss, количество минут и секунд при необходимости дополняются нулями.
Ограничение по времени: 1 секунда
Ограничение памяти: 64 Мб
Формат ввода: n-целое, положительное, не превышает $10^7$ - номер текущей секунды
21 Задача - выбрать 2 носка, максимально похожих друг на друга. Причем один из них должен быть левым, а второй - правым. Носки тем более похожи, чем меньше разницы в свете.
В наличии имеется N ($1 \leq N \leq 100000$) левых носков и M ($1 \leq M \leq 100000$) правых. Про каждый носок известне его цвет (целое число от 1 до $10^7$). Помогите Глебу выбрать один левый и один правый носок, чтобы разница в их цвете была как можно меньше. Разницей светов можно считать разноть чисел, задающих эти цвета.
Формат ввода: В первой строке - целое число N. Во второй N целых чисел - цвета левых носков, номера цветов идут в возрастающем порядке (цвета никаких 2 левых носков не совпадают). В третьей строке - число правых носков M. В четвертой M целых чисел в возрастающем порядке.
Формат вывода: Цвет левого и цвет правого носков, которые максимально похожи друг на друга. Если несколько, то любой вариант.
Ограничение по времени - 1 секунда
Ограничение по памяти - 64 Мб
22 Дано натуральное n ($1 \leq n \leq 10^{18}$). Найдите количество пар неотрицательных целых чисел $(x,y)$, удовлетворяющих соотношению $x^2 + y^3 = n$. В ответе укажите одно число - количество пар.
Python - 5 секунд - 64 Mb
23 Две строки S и T будем называть похожими, если можно переобозначить одинаковые буквы строки S и таким образом получить строку Т. Например, строки abacaba и xyxzxyx - похожие. А строки abacaba и pqpqpqp похожими не являются.
Вам даны два числа L и K. Определите количество пар различных строк, каждая из которых имеет длину L, содержит K различных символов, строки в паре похожие.
Гарантируется, что числа L и K подобраны таким образом, что ответ не превышает $10^{18}$
Формат ввода. В единственной строке входных данных записаны два целых числа $L$ и $K$ ($1 \leq L, K \leq 50$).
Формат вывода. В единственной строке выведите одно число - количество пар похожих строк.
ПРимер. Ввод 5 2. Вывод 15
1 секунда - 64 Мб
24
25
26 Дан массив длины n из нулей и единиц. Найдите в нем подмассив максимальной длины, в котором количество единиц равно количество нулей. Ограничение O(n) по времени и O(n) по дополнительной памяти.
In [ ]:
a = [1,0,0,0,1,1,1,0,1,1]
b = [-1]*len(a)
c = [-1]*len(a)
d = [-1]*len(a)
e = [-1]*len(a)
i = 1
print '****************'
print 'a=',a
print 'b=',b
print 'c=',c
print 'd=',d
print 'e=',e
#если в а заменить все нули на -1, то в b будут стоять суммы о a[0] до a[i]
b[0] = 2*a[0]-1
while i in range(1,10):
b[i] = b[i-1] + 2*a[i]
i+=1
print '****************'
print 'a=',a
print 'b=',b
print 'c=',c
print 'd=',d
print 'e=',e
i = 0
k = 0
while i in range(0,10):
while k in range(0,10):
if b[i] == k:
d[k] = i
if c[k] == -1:
c[k] = i
print '****************'
print 'a=',a
print 'b=',b
print 'c=',c
print 'd=',d
print 'e=',e
In [ ]: