21. Почти простые числа

Почти простым числом будем называть число, которое представимо в виде произведения двух простых чисел. По заданному числу , ответьте является ли оно почти простым.

Входные данные
2 ≤ N ≤ 10⁹

Выходные данные
Необходимо вывести строку Yes, если число почти простое, или No, в обратном случае.

Пример

 
6

 
YES

 
8

 
NO

22. Научная проблема

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

Входные данные
2 ≤ N ≤ 10⁹ + 7

Выходные данные
Вывести ответ на задачу.

Пример

 
1

 
3

 
2

 
5

23. Высшая математика

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

Входные данные
1 ≤ a, b, c ≤ 40000

Выходные данные
Вывести “yes” , если треугольник с заданными сторонами является прямоугольным и “no” если не является.

Пример

 
36 77 85

 
yes

 
40 55 69

 
no

24. Взаимнопростые

По заданному числу N, найти количество чисел, которые не больше N и взаимнопростые с N. Взаимнопростыми числами называются числа, НОД которых равен 1.

Входные данные
2 ≤ N ≤ 10⁹ + 7

Выходные данные
Вывести ответ на задачу.

Пример

 
9

 
6

25. Праздничное застолье

Организаторы олимпиады по математике решили устроить праздничный банкет. Было приглашено C участников и приготовлено P плюшек. Каждый участник съел Q плюшек и L плюшек осталось(L < Q). И теперь организаторам интересно, сколько плюшек съел каждый участник.

Входные данные
В первой и единственной строке входного потока дано два натуральных числа — P и L (2 ≤ L ≤ P ≤2³¹).

Выходные данные
Все возможные варианты ответа в возрастающем порядке. Если нет подходящего числа, то вывести «impossible»

Пример

 
10 0

 
1 2 5 10

 
13 2

 
11

 
300 98

 
101 102

 
1000 997

 
impossible

26. Предсказание Панорамикса

Простым числом называется число, которое имеет ровно два различных делителя: единицу и само себя. Например, числа 2, 7, 3 являются простыми, а 1, 6, 4 — нет. Следующим после x простым числом называется наименьшее простое число, большее x. Например, после 2 следующим простым является 3, а после 3 следующим простым является 5. Учтите, что для каждого числа есть ровно одно следующее простое. То есть 5 не является следующим простым для 2. Однажды, холодным апрельским утром Панорамикс предсказал, что скоро освободится Какофоникс из своей смирительной рубашки, и чёрный день наступит для жителей галльской деревни. Этот день, после третьей порции волшебного снадобья, определился друидом очень просто: если в некоторый день Астерикс и Обеликс побьют ровно x римских солдат, где x — простое число, а на следующий день они побьют ровно y римских солдат, где y — следующее после x простое число, то стоит ждать конца света, ибо ничто не сможет сдержать Какофоникса с его адской песней. Вчера галлы побили n римских солдат и оказалось, что число n — простое! Сегодня их жертвами стал отряд из mримлян (m > n). Определите, стоит ли ждать чёрного дня после сегодняшней победы Астерикса и Обеликса?

Входные данные
В первой и единственной строке входного потока дано два натуральных числа — n и m (2 ≤ n < m ≤ 50). Гарантируется, что число n — простое.

Выходные данные
Выведите YES, если число m оказалось следующим простым после n, или NO в противном случае.

Пример

 
3 5

 
YES

 
7 11

 
YES

 
7 9

 
NO

27. Последняя цифра A^B

Требуется написать программу, которая находит цифру, на которую оканчивается число A^B.

Входные данные
Входной файл состоит из единственной строки, содержащей два целых числа A и B, разделенных пробелом (1 ≤ A,B ≤ 10000).

Выходные данные
В выходной файл выведите цифру, на которую оканчивается A^B.

Пример

 
2 2

 
4

 
3 7

 
7

 
24 9

 
4

28. Наилучший делитель

Будем говорить, что число a лучше числа b, если сумма цифр a больше суммы цифр числа b, а в случае равенства сумм их цифр, если число a меньше числа b. Например, число 124 лучше числа 123, так как у первого из них сумма цифр равна семи, а у второго – шести. Также, число 3 лучше числа 111, так как у них равны суммы цифр, но первое из них меньше. Дано число N. Найдите такой его делитель (само число N и единица считаются делителями числа N), который лучше любого другого делителя числа N.

Входные данные
Первая строка входного файла содержит целое число N (1 ≤ N < 2³¹).

Выходные данные
В выходной файл выведите ответ на задачу.

Пример

 
10

 
5

 
239

 
239

29. Отважные воздухоплаватели

Десять математиков летели на воздушном шаре над Тихим океаном. Когда они пересекали экватор, они решили отметить это событие и открыли бутылку шампанского. К сожалению, пробка пробила дыру в воздушном шаре. Водород начал вытекать, а шар — снижаться. Скоро он упадёт в океан, и все воздухоплаватели будут съедены голодными акулами. Но пока ещё не всё потеряно. Один из воздухоплавателей может выпрыгнуть, пожертвовав собой, чтобы его друзья смогли пожить чуть дольше. Осталась только одна проблема — кто будет этим человеком. Есть честный способ решить этот вопрос. Сначала каждый из математиков напишет целое число a_i, не меньшее 1 и не большее 10 000. После чего они найдут волшебное число N, равное количеству положительных делителей произведения a₁*a₂*...*a₁₀. Например, количество положительных целых делителей числа 6 равно 4 (делители 1, 2, 3, 6). Герой (математик, который будет выброшен) определится последней цифрой числа N. Ваша задача — найти эту цифру.

Входные данные
Ввод содержит десять целых чисел, каждое число в отдельной строке.

Выходные данные
Выведите одну цифру от 0 до 9 — последнюю цифру N.

Пример

 
1
2
6
1
3
1
1
1
1
1

 
9

30. Проверка на простоту

Проверьте, является ли число простым.

Входные данные
2 ≤ N ≤ 10⁹

Выходные данные
Необходимо вывести строку prime, если число простое, или composite, если число составное.

Пример

 
5

 
prime

 
7

 
prime

 
9

 
composite

 
2

 
prime

Задача 11. Охрана империи

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

Задача 12. Патруль

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

Задача 13. Сокращение

В этой задаче необходимо было проверить наличие кратных ребер в графе. Известно, что вершин не больше 100, поэтому мы можем использовать матрицу смежности для представления графа. Очевидно, что граф неориентированный. При считывании отмечаем каждое ребро, при этом в матрице ставим не 1, а увеличиваем предыдущее значение количества ребер между планетами. Таким образом если в графе нет кратных ребер, то матрица будет содержать только 1 и 0, а в противном случае еще какие – либо натуральные числа.

Задача 14. Благополучие

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

Задача 15. Банкет

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

По окончании работы алгоритма мы либо обнаружим, что граф не двудолен, либо найдём разбиение вершин графа на две доли.

Задача 16. Династии

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

Задача 17. Императорское путешествие

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

Задача 18. Строительство дорог

Решение основано на системе непересекающихся множеств (DSU) планет. Две планеты принадлежат одному и тому же множеству тогда и только тогда, когда они достижимы друг из друга по уже построенным путям. Введем счетчик текущего количества множеств, изначально равный n. Изначально в каждом множестве находится только одна планета. При считывании пути (x, y) проверим, находятся ли планеты x и y в одном множестве. Если нет, то объединим содержащие их множества и уменьшим счетчик на 1. Как только счетчик станет равным 1 (то есть все планеты будут принадлежать одному множеству), выведем количество считанных путей.

Задача 19. Торговая сеть

В этой задаче необходимо было найти минимальное остовное дерево. Для его поиска можно было воспользоваться описанным выше алгоритмом Крускала либо алгоритмом Прима. Заметим, что ограничения задачи требуют оптимальной реализации за O (M log N).

Задача 20. Карта империи

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

* Более полная информация о том как решать данные задачи расположена тут. 

3.12.11 з 10.00 по 15.00 відбудеться Другий Відкритий Кубок Олександрії з програмування серед школярів. До участі були запрошені школярі 7-11 класів з Кіровоградської, Вінницької, Хмельницької, Полтавської областей. 

Олімпіада проводиться окремо серед учнів 7-9 класів, 10-х класів, та 11-х класів.  Участь в змаганні можлива за попередньою реєстрацією. 

11. Охрана империи

За много тысяч световых лет от нашей планеты существовала космическая империя Брума. Долгое время она была образцом спокойствия, жители этой планеты были весьма невозмутимы и неиссякаемы на богатство. Ничтожное количество планет могли сравниться с ней … но всё безнадёжно. Можно было только позавидовать благородству этих безмятежных и миролюбивых горожанин, их плодородию и душевному богатству. Но всё изменилось с приходом последнего императора, который рассеял страх и трепет во все дома обитателей. Его коварству не было предела, он был подобием протобестии.  За время его правительства в империи начались массовые беспорядки, народ был повергнут в высшую степень беспредела … Горожане не могли вынести всего этого и вынуждены были прибегнуть к тому, чтобы покинуть родные дома и планету, чтобы отправится в вечное странствие по космосу.  Они были огорчены и разбиты… и вынуждены избрать нового правителя. Они возложили надежду и новые силы на своего новоизбранного императора Синдерона. Перед ним постыла миссия восстановить империю во всей её красе. 

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

Формат входных данных

В первой строке задается число N (0 ≤ N ≤ 100). В следующих N строках содержится по N чисел, каждое из которых является единичкой или ноликом. Причем, если в позиции (i,j) квадратной матрицы стоит единичка, то между i-й и j-й планетами существует торговая магистраль, а если нолик, то не существует.

Формат выходных данных

Выведите одно число - количество необходимых отрядов.

Примеры

 12. Патруль

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

Формат входных данных

 Входные данные включают число n ( 1 ≤ n ≤ 100) – количество планет, а затем n строк по n чисел, каждое из которых равно 0 или 1, – существует ли маршрут между планетами.

Формат выходных данных

Выведите список планет, между какими необходимо патрулировать пространство (в любом порядке).

Примеры

13. Сокращение

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

Формат входных данных

Сначала вводятся  числа n ( 1≤n≤100) – количество планет и m ( 1≤m≤10 000) – количество патрулей. Затем следует m пар чисел – маршруты патрулей.

Формат выходных данных

Выведите  «YES», если количество патрулей изменится, и «NO» в противном случае.

Примеры

14. Благополучие

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

Формат входных данных

            В первой строке входных данных содержатся два числа: N и S (1  N  S  N), где N – количество планет, а S – номер столицы. В следующих N строках записано по N чисел – карта империи, в которой 0 означает отсутствие сообщения между вершинами, а 1 – его наличие. 

Формат выходных данных

Выведите одно целое число – искомое количество планет.

Примеры

15. Банкет

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

Формат входных данных

Если способ рассадить гостей существует, то выведите YES в первой строке и номера гостей оторые будут сидеть за первым столом. В противном случае в первой и единственной строке выведите NO.

Формат выходных данных

Если способ рассадить гостей существует, то  выведите YES в первой строке и номера гостей которые будут сидеть за первым столом. В противном случае в первой и единственной строке выведите NO.

Примеры

16. Династии

Во время проведения банкета стало известным, что в империи пребывает немалое количество династий, о количестве которых должно быть ведомо только Синдериону. Для того, чтобы владеть такой информацией он внедрил в дело своих разведчиков, которые предоставили данные о том, кто с кем состоит в одной династии. Теперь император просит Вас ответить на его вопрос , располагая предоставленными данными, сколько династий существует в его империи ?

Формат входных данных

В первой строке задается число известных родственных связей K и число N (0 ≤ N ≤ 100). В следующих N строках содержится 2 числа – номера жителей, которые находятся в одной династии.

Формат выходных данных

Выведите одно число - количество династий в империи.

Примеры

17. Императорское путешествие

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

Формат входных данных

В первой строке – количество планет 1≤N≤2500. В последующих N-1 строках по два целых числа – номера, соединенных планет.

Формат выходных данных

Вывести одно число – искомое количество планет.

Примеры

18. Строительство дорог

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

Формат входных данных

Первая строка содержит два числа: число планет N (1≤N≤10000) и количество дорог в плане M (1≤M≤50000). Далее идет M строк, каждая содержит два числа x и y (1≤x,y≤N) - номера планет, которые соединяет очередная дорога в плане.

Формат выходных данных

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

Примеры

19. Торговая сеть

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

Формат входных данных

Первая строка входного файла содержит два натуральных числа n и m - количество планет и дорог в империи соответственно (1≤n≤80000, 0≤m≤100000). Следующие m строк содержат описание дорог по одному на строке. Дорога номер i описывается тремя натуральными числами bi, ei и wi - номера ее концов и ее длинна соответственно (1≤bi,ei≤n, 0≤wi≤1000000000).

Формат выходных данных

Выведите одно число - стоимость содержания дорожной сети империи.

Примеры

20. Карта империи

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

Формат входных данных

В первой строке вводится единственное число N (1 N N строках по N чисел задается карта (j-ое число в i-ой строке соответствует длинне пути с планеты i на планету j). Все числа по модулю не превышают 100.

Формат выходных данных

Выведите N строк по N чисел – матрицу кратчайших расстояний между парами планет. j-ое число в i-ой строке должно быть равно длиннекратчайшего пути с планеты i на планету j

Примеры