Алгоритмы

Магистр Максимус отправился в опасное путешествие в горы Ордена Магов. Внутри гор великими магами прошлого созданы комнаты, в каждой из которых хранятся магические артефакты. Максимус желает пройти через все n комнат, но, как оказалось, все комнаты заперты, за исключением комнаты 0, в которую Максимус уже вошел. 
В каждой комнате имеется набор уникальных заклинаний, открывающих двери других комнат. Магистр Максимус познал язык великих магов, поэтому он может легко прочитать эти заклинания и отпирать другие комнаты.

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

По известному набору заклинаний, определите сможет ли Максимум получить все артефакты или нет.


Формат входных данных
В первой строке записано число n (2 <= n <= 1000), количество комнат. Далее идет n строк. В i-й строке описываются заклинания, хранящиеся в этой комнате. В каждой из этих строк первое число (m, 0 <= m <= 1000) обозначает количество уникальных заклинаний, которые открывают комнаты, далее записаны m уникальных чисел rooms[i](0 <= rooms[i][j] < n) -  номера комнат, которые открывают эти заклинания (0<=i<n,  1 <= общее количество заклинаний во всех комнатах <= 10000). 

 

Формат выходных данных
Выведите True, если Максимус может посетить все комнаты и найти все магические артефакты, или False в противном случае.

Вы хотите построить лестницу и приготовили n блоков. Лестница строится путем наложения блоков друг на друга.  В i-м ряду лестницы размещается ровно i блоков. 
Определите количество полных рядов лестницы, которую вы сможете построить.



Решите задачу двоичным поиском.

Формат входных данных
Программа получает на вход натуральное число n (1 <= n <= 231 - 1) - количество блоков.

Формат выходных данных
Выведите ответ на задачу.

Переведите {1}  из десятичной системы счисления в двоичную систему счисления.

Для заданного целого положительного числа num, выведите 1, если num является полным квадратом, или 0 в противном случае.
Полный квадрат - это целое число, которое является квадратом целого числа. Другими словами, это произведение некоторого целого числа на само себя.

Решите задачу с помощью бинарного поиска.


Формат входных данных
Программа получает на вход одно целое положительное число num (1 <= num <= 231 - 1).

Формат выходных данных
Выведите 1, если num является полным квадратом, или 0 в противном случае

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

Вы уже выпустили n версий [1, 2, ..., n] и забыли проверить на качество все, кроме последней. Теперь, вы хотите найти первую плохую версию, которая приводит к тому, что все последующие становятся плохими. 

Руководитель отдела качества очень хорошо к вам относится и написал для вас функцию isBadVersion(version), которая определяет является ли версия резила плохой (возвращает True, если версия плохая, и False если хорошая).

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

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

Вы уже выпустили n версий [1, 2, ..., n] и забыли проверить на качество все, кроме последней. Теперь, вы хотите найти первую плохую версию, которая приводит к тому, что все последующие становятся плохими. 

Руководитель отдела качества очень хорошо к вам относится и написал для вас функцию isBadVersion(version), которая определяет является ли версия релиза плохой (возвращает True, если версия плохая, и False если хорошая).

Теперь вам необходимо реализовать функцию для поиска первой плохой версии. Вы должны как можно быстрее определить с какой версии пошел плохой релиз, поэтому количество использования функции isBadVersion(version) должно быть минимальным.

Ваша функция должна вернуть номер первого плохого релиза.
 

Дан одномерный массив, отсортированный по невозрастанию. Дополните функцию binSearch() таким образом, чтобы она возвращала в программу индекс первого элемента равного key. В случае, если такого элемента в массиве нет, функция должна возвращать -1.
 

Дан одномерный массив, отсортированный по невозрастанию. Дополните функцию binSearch() таким образом, чтобы она возвращала в программу индекс первого элемента меньшего или равного key. В случае, если такого элемента в массиве нет, функция должна возвращать -1.
 

Дан одномерный массив, отсортированный по невозрастанию. Дополните функцию binSearch() таким образом, чтобы она возвращала в программу индекс первого элемента меньшего key. В случае, если такого элемента в массиве нет, функция должна возвращать -1.
 

Дан одномерный массив, отсортированный по невозрастанию. Дополните функцию binSearch() таким образом, чтобы она возвращала в программу индекс первого элемента меньшего key. В случае, если такого элемента в массиве нет, функция должна возвращать -1.
 

Дан одномерный массив, отсортированный по невозрастанию. Дополните функцию binSearch() таким образом, чтобы она возвращала в программу индекс последнего элемента равного key. В случае, если такого элемента в массиве нет, функция должна возвращать -1.
 

Дан одномерный массив, отсортированный по невозрастанию. Дополните функцию binSearch() таким образом, чтобы она возвращала в программу индекс последнего элемента большего или равного key. В случае, если такого элемента в массиве нет, функция должна возвращать -1.
 

Дан одномерный массив, отсортированный по невозрастанию. Дополните функцию binSearch() таким образом, чтобы она возвращала в программу индекс последнего элемента большего key. В случае, если такого элемента в массиве нет, функция должна возвращать -1.
 

В городе Лост-Хевен произошла серия загадочных преступлений. Жители напуганы и не знают, кому можно доверять. Местный Шериф позвал на помощь знаменитого детектива Нормана, чтобы тот помог ему найти главаря мафии. 
Норман принялся за дело и опросил всех жителей города. В итоге он теперь знает, кто кого боится. 
Норман знает, что главным подозреваемым будет тот житель города, который удовлетворяет следующим условиям:
1) Подозреваемый никого не боится.
2) Все остальные жители боятся подозреваемого. 
3) Существует ровно один такой человек, который удовлетворяет первым двум условиям.
Вы - программист, который помогает Норману. Норман дал вам информацию в виде списка, кто кого боится.  Помогите Норману определить главного подозреваемого. 

Формат входных данных
В первой строке записано натуральное число N - количество жителей города Лост-Хевен (1 <= N <= 1000). Во второй строке содержится неотрицательное число K (0 <= K <= 104) - количество записей сделанных Норманом после опроса всех жителей города. В следующих K строках записано по два числа (ai, bi) - обозначающие то, что i-й житель a боится жителя b (1 <= ai, bi <= n, ai не равно bi, каждая пара (ai, bi) уникальна).

Формат выходных данных
Выведите номер подозреваемого. Если выявить подозреваемого не представляется возможным, то в ответе укажите число -1.

Дана строка s и символ с, который встречается в s. Для каждого символа из строки s, определите расстояние до ближайшего символа с.
Расстояние между двумя индексами i и j равно abs(i - j), где abs - функция вычисления модуля числа.


Формат входных данных
В первой строке записана непустая строка s, состоящая из маленьких английских букв (длина строки не превышает 104). Во второй строке записан символ c. Гарантируется, что в строке s содержится как минимум один символ c.

Формат выходных данных
Выведите в одной строке через пробел n чисел ai. Число ai - расстояние от символа с индексом i до ближайшего символа c (n равно длине строки s, 0 <= i < n). Числа выводить в порядке следоваения букв в исходной строке.  

Дана последовательность из N чисел. Известно, что сумма всех чисел последовательности не превышает 10⁹. Рассматриваются все её непрерывные подпоследовательности, в которых количество положительных чисел кратных двум кратно K. Найдите такую подпоследовательность с максимальной суммой. 

Формат входных данных
В первой строке записаны два натуральных числа N и K (1 <= N <= 1 000 000, 1 <= K <= 100). Каждая из следующих N строк содержит одно число, не превышающее по модулю 1 000.

Формат выходных данных
Выведите одно число - максимальную сумму подпоследовательности, удовлетворяющей условию задачи. Гарантируется, что как минимум одна такая подпоследовательность существует.

Дан массив целых чисел. Отсортируйте массив по неубыванию количества нечетных цифр в значении каждого элемента массива. При равенстве количества нечетных цифр у двух элементов, числа должны следовать в порядке убывания.


Формат входных данных
Программа получает на вход в первой строке натуральное число n - размер массива. Вторая строка содержит n целых чисел ai - элементы массива (1 <= n <= 103, -104 <= ai <= 104).

Формат выходных данных
Выведите результирующий массив.

Дан массив целых чисел. Отсортируйте массив по неубыванию количества четных цифр в значении каждого элемента массива. При равенстве количества четных цифр у двух элементов, числа должны следовать в порядке убывания.


Формат входных данных
Программа получает на вход в первой строке натуральное число n - размер массива. Вторая строка содержит n целых чисел ai - элементы массива (1 <= n <= 103, -104 <= ai <= 104).

Формат выходных данных
Выведите результирующий массив.

Дан массив целых чисел. Отсортируйте массив по невозрастанию чисел составленных из последних двух цифр каждого значения (в том же порядке следования). При равенстве чисел, составленных из двух последних цифр, числа должны следовать в порядке возрастания.


Формат входных данных
Программа получает на вход в первой строке натуральное число n - размер массива. Вторая строка содержит n целых чисел ai - элементы массива (1 <= n <= 103, -104 <= ai <= 104).

Формат выходных данных
Выведите результирующий массив.

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

Формат входных данных
В первой строке записаны два числа N и M - количество строк и столбцов матрицы соответственно (1 <= N, M <= 50 ). В следующих N строках записаны строки матрицы, в каждой – по M чисел, разделённых пробелами (каждое значение не превышает по модулю 1000). 
 
Формат выходных данных
Программа должна вывести получившуюся матрицу.