Алгоритмы

166 задачвместе с подтемами
Число у задачи — рейтинг сложности, слово рядом — насколько она трудна по сравнению с другими задачами такого же типа. Шкалы задач с ответом и задач с кодом между собой не сравниваются. Рядом — счётчики попыток: ✓ успешные, ✗ неуспешные.
РейтингЛюбойдо 800800–11991200–15991600+Без рейтинга
СначалаПодходящиеНовыеПопулярныеПростыеСложные
31922#31922
Даны два простых числа p и q. Надо расшифровать сообщение состоящее из последовательности чисел оканчивающееся нулем с помощью алгоритма RSA.

Входные данные
В первой строке вводятся p и q (3<=p,q<10), далее вводится длина N (N<10) и сообщение состоящее из натральных чисел не превышающее 10.

Ввод Вывод
3 7
1 11 12 16 17 6 7 8 18 0 0		 1234567890

Арифметические алгоритмы (Теория чисел)МЦКО-10. RSA
✓ 0✗ 121 400средняяВойти и решать
RSA. Расшифровать сообщение#31921
Даны два простых числа p и q. Надо расшифровать сообщение состоящее из последовательности чисел оканчивающееся нулем с помощью алгоритма RSA.

Входные данные
В первой строке вводятся p и q (3<=p,q<10) и сообщение состоящее из натуральных чисел оканчивающееся нулем.

Ввод Вывод
3 7
1 11 12 16 17 0		 1 2 3 4 5

Арифметические алгоритмы (Теория чисел)МЦКО-10. RSA
✓ 0✗ 251 300средняяВойти и решать
RSA. Зашифровать большое числовое сообщение#31920
Даны два простых числа p и q. Надо зашифровать сообщение длинной N с помощью алгоритма RSA.

Входные данные
В первой строке вводятся p и q (3<=p,q<100), далее вводится сообщение состоящее из цифр.

Ввод Вывод
3 7
12345678901234567890		 1 11 12 16 17 6 7 8 18 0 1 11 12 16 17 6 7 8 18 0

"Длинная" арифметикаМЦКО-10. RSA
✓ 0✗ 271 300средняяВойти и решать
Про любовь...#29478
Паук и паучиха плывут по озеру на двух веточках. Плавать они не умеют, поэтому смогут встретиться только тогда, когда веточки соприкоснутся.


 

Считая, что веточки имеют форму отрезков, и что они плывут с постоянными скоростями, определите, сколько осталось ждать встречи несчастным членистоногим.

 
Входные данные
Входной файл содержит 12 чисел: x1, y1, x2, y2, x3, y3, x4, y4, v1x, v1y, v2x, v2y. Координаты вершин первого отрезка: (x1, y1) и (x2, y2), координаты вершин второго отрезка: (x3, y3) и (x4, y4), скорость первого отрезка (v1x, v1y), скорость второго отрезка (v2x, v2y). Все числа целые и не превосходят по модулю 104. В начальный момент времени веточки не соприкасаются. Гарантируется, что веточки имеют ненулевую длину.
 
Выходные данные
Выведите в выходной файл время до ближайшего момента, когда веточки соприкоснутся, с ошибкой не более 10−4. Если веточки не соприкоснутся никогда, выведите число -1.
 
Ввод Вывод
0 0 -1 3
4 4 7 7
3 0
0 -1
 1.6
0 0 -1 3
4 4 7 7
1 0
0 -3
 -1
 
Тернарный поиск
✓ 11✗ 1001 300средняяВойти и решать
Архимедова спираль#29477
Дима недавно поступил на работу в НИИ Плоских Кривых. Как следует из названия этого научно- исследовательского института, он занимается различными исследованиями в области плоских кривых. Недавно Димин начальник Георгий столкнулся с весьма интересной кривой, которая, как выяснилось после некоторого исследования, известна под названием Архимедовой спирали. Архимедова спираль плоская кривая, изображающая траекторию точки M, которая равномерно движется вдоль луча OK с началом в O, в то время как сам луч OK равномерно вращается вокруг точки O (см. рисунок). Другими словами, расстояние до начала координат ρ = OM линейно зависит от угла поворота φ луча OK. При этом повороту луча OK на один и тот же угол соответствует одно и то же приращение расстояния ρ. 
 
Движение точки M можно задать с помощью ряда параметров:
 
• начального угла поворота α луча OK (измеряется в градусах против часовой стрелки относительно положительного направления оси OX);
 
• угловой скорости вращения ω луча OK (измеряется в градусах за единицу времени);
 
• начального расстояния R от точки M до начала координат (точки O);
 
• скорости движения V точки M по лучу OK.
 
Если, задав эти параметры, не ограничить время движения точки M, то получится бесконечная кривая, исследовать которую достаточно трудно. Поэтому Дима решил ограничиться исследованием некоторой части этой кривой той, которая получается при движении точки M от нулевого момента времени до момента времени T. Задача, которую решает Дима состоит в поиске прямоугольника минимальной площади со сторонами, параллельными осям координат, в который ее можно вписать.
 
Требуется написать программу, которая найдет искомый прямоугольник

 
Входные данные
Входной файл содержит четыре целых числа: ω (1 ≤ ω ≤ 100), V (1 ≤ V ≤ 100), R (0 ≤ R ≤ 100) и T (1 ≤ T ≤ 1000). В этой задаче считается, что начальный угол поворота α равен нулю.
 
Выходные данные
В первой строке выходного файла выведите два вещественных числа — координаты левого нижнего угла искомого прямоугольника, а во второй строке — координаты правого верхнего угла искомого прямоугольника.
 
Ответ будет считаться правильным, если значение каждой из координат будет отличаться от истинного значения не более чем на 10-5.
Тернарный поиск
✓ 9✗ 261 200средняяВойти и решать
Шаблон с ? и *#28419
Шаблоном называется строка, состоящая из английских букв (a, ..., z, A, ..., Z) и символов ? и *. Каждый из символов ? разрешается заменить на одну произвольную букву, а каждый из символов * – на произвольную (возможно пустую) последовательность букв. Про любую строку из букв, которую можно получить из шаблона такими заменами, будем говорить, что она удовлетворяет этому шаблону.
 
Имеются два шаблона. Требуется найти строку минимальной длины, которая удовлетворяет обоим шаблонам, либо выдать сообщение, что такой строки не существует.
 
Входные данные
Заданные шаблоны записаны в первых двух строках входных данных. Длина каждого шаблона не превосходит 80 символов.

Выходные данные
Выведите строку минимальной длины, удовлетворяющую обоим шаблонам, либо сообщение "No solution!"
 
Примеры
№ Входные данные Выходные данные
1
AB?
*BC
 ABC
Динамическое программирование
✓ 21✗ 1741 200средняяВойти и решать
Расстояние между точками#28346
На окружности заданы N точек, надо найти пару точек, расстояние между которыми (по хорде окружности) максимально. 

Входные данные
В первой строке задано N (1 <= N <= 100 000).
В следующей строке даны N пар вещественных чисел. Сначала описывается координата x, потом – y.

Выходные данные
Вывести два числа – номера точек, расстояние между которыми максимально. Сначала идет наименьшее число, потом наибольшее.
 
Ввод Вывод
3
1.4142 1.4142
0 2
-1.4142 -1.4142		 1 3

 
"Два указателя"геометриясортировки
✓ 1✗ 4191 400средняяВойти и решать
Trapped in the Haybales#28323
Фермер Джон получил груз из N больших стогов сена (1≤N≤4000) и разместил эти стога в различных точках дороги, ведущей к его амбару. К несчастью, он совсем забыл, что Беси пасётся вдоль этой дороги и может оказаться в ловушке из этих стогов.
Каждый стог с номером j имеет размер Sj и уникальную позицию Pj, задающую его положение вдоль одномерной дороги. Беси начинает движение в некоторой позиции, где не было стога и может передвигаться свободно вдоль дороги, вплоть до позиции, где размещён стог сена, но она не может перейти эту позицию. В качестве исключения, если она движется в некотором направлении D единиц расстояния, она набирает достаточно скорости, чтобы протаранить любой стог сена с высотой строго меньше, чем D. Конечно, после того, как она сделает это, перед ней открывается пространство с другими стогами сена, которые она тоже может протаранить.
 
Беси может выйти на свободу как после самого левого, так и после самого правого стога сена. Пожалуйста, определите общую длину дороги, состоящую из тех позиций, из которых Беси не сможет выбраться. Например, если Беси не может выбраться если она начинает с позиции между стогами в позициях 1 и 5, тогда ответ будет 4 (поскольку эти позиции ограничивают область размером 4).
 
ФОРМАТ ВВОДА:
Первая строка ввода содержит NN. Каждая из последующих NN строк описывает стог и содержит два целых числа, определяющих его размер и позицию, каждое в диапазоне 1…109.

ФОРМАТ ВЫВОДА:
Выведите целое число, определяющее длину части дороги из которой Беси не сможет сбежать.
 
Ввод Вывод
5
8 1
1 4
8 8
7 15
4 20
 14
Задачи на моделирование
✓ 3✗ 61 200средняяВойти и решать
Генерация ПСП#27312

Самой инновационной разработкой "British Scientists, Inc" является способ нахождения решения для любой задачи, которую возможно решить с помощью тильда-омега-лямбда-исчисления (то есть, для никакой). Для этого они перебирают все возможные скобочные последовательности длины x, где х - первая цифра секретной константы, использующейся во многих разработках компании. Если x нечётное, они просто прибавляют к нему единицу. Потом они используют продвинутые алгоритмы, использующие нейролингвистическое программирование и вычисленные по спирали Фибоначчи числа Каталана гуголдцатого порядка для определения местонахождения термов. Но эти алгоритмы уже реализованы и запатентованы. 

Ваша же задача - реализовать алгоритм перебора. 


Входные данные
На вход подаётся первая цифра секретной константы - x (\(1 <= x <= 9\)). 
 

Выходные данные
Нужно вывести все ПСП длины x (или x+1, если \(x \% 2 ==1\)) в лексикографическом порядке.

 

Примеры
№ Входные данные Выходные данные
1 1
( )
[ ]
{ }
Рекурсивный переборСтроки
✓ 8✗ 4501 200средняяВойти и решать
27309#27309
Вы должны реализовать алгоритм или структуру данных, эффективно реализующих следующие запросы:
1)Добавление в массив элемента
2)Извлечение k-того по величине элемента массива (первым по величине будет считаться наименьший элемент)
Гарантируется, что каждый элемент встречается в массиве всего один раз
 
Входные данные:
В первой строке указано натуральное число n, за ним следует n целых чисел. 
Далее вводится натуральное m - количеств запросов.
В каждой из следующих m строк содержится слово "add" или "get" и целое число k.
Все численные значения по модулю не превосходят 1000. 
В первом случае вы должны дополнить массив элементом со значением k. Иначе - вывести k-тый элемент отсортированного текущего массива (индексация с единицы).
 
Выходные даннные: 
Вы должны ответить на запрос извлечения k-того элемента массива, а именно вывести его значение на экран.

(c) Ибрахим Ахмад, 2017
Двоичное дерево поискаПорядковые статистики
✓ 0✗ 41 300средняяВойти и решать
Тандемный префикс#27306
Егор Кубратов очень огорчен задачами с codeforces и олимпиады Иннополиса, поэтому теперь он сам придумывает задачи и сам же их решает. Сегодня он придумал следующую задачу:
 
“Тандемный префикс – это подстрока, образованная конкатенацией двух непустых, не обязательно одинаковых префиксов строки и не являющаяся префиксом строки*. Вам необходимо найти длиннейший тандемный префикс данной строки. Если вариантов несколько, выведите тот, вхождение которого самое раннее. Если тандемного префикса не существует, то выведите -1”
 
*Имеется в виду, что тандемный префикс не является подстрокой, начинающейся в первом символе строки. То есть по составу букв он может являться каким-то префиксом, но только если начинается не в первой позиции. Например, в строке “aaa” подстрока [2;3] является тандемным префиксом.
 
Входные данные
В первой строке дана строка, состоящая из строчных латинских букв. Длина строки не превышает 105.
 
Выходные данные
Выведите ответ, если он существует. Иначе выведите -1.
 
Ввод Вывод
abcabac aba

Подстроки abca и abcab являются конкатенациями двух префиксов, но они сами являются префиксами, что противоречит определению тандемного префикса, поэтому aba – единственный тандемный префикс данной строки.

(с) Курбатов Е., 2017
Z-функция. Префикс-функциястроковые суфф. структуры
✓ 1✗ 91 300средняяВойти и решать
Кедор и Гихаил#27305
Меллерт Гихаил сегодня был в прекрасном настроении до того, как его одноклассник Фусков Кедор не заговорил о политике. Гихаил очень сильно разозлился, поэтому придумал задачу по информатике для Кедора, чтобы тот начал решать и наконец-то заткнулся. 
Задача была такая:  “Существует n логических функций, которые зависят от одного и того же множества переменных. Даны n чисел, битовое представление которых определяет таблицу истинности для каждой функции. Вам необходимо найти такой порядок расположения функций, чтобы из каждой функции логически следовала любая из последующих или сказать, что это  невозможно. Если ответ существует, то необходимо найти лексикографически минимальный порядок. Можно показать, что размер множества переменных, от которого зависят функции, не влияет на решение задачи”.
 Кедор – ваш лучший друг, а Гихаил – заклятый враг, поэтому вы решили помочь с решением задачи, а затем вместе с Кедором возобновить разговоры о политике, чтобы Гихаил от злости улетел на Луну.
 
Входные данные
В первой строке дано число n (1 <= n <= 10) – кол-во функций. 
Во второй строке дано n чисел в диапазоне [0; 10^9] – таблицы истинности функций, переведенные в десятичную систему счисления. 
Выходные данные
Если порядок существует, в первой строке выведите “YES”, во второй лексикографически минимальную перестановку из всех возможных. Если порядка нет, то выведите “NO”.

Пример
Ввод Вывод
3
3 1 7
 YES
2 1 3
2
1 2
NO
 

(с)  Курбатов Е., 2017
 
битмаскиПереборРазбор случаев
✓ 3✗ 171 200средняяВойти и решать
Building a Ski Course#27301
Фермер Джон помогает превратить его большое поле в лыжный маршрут для предстоящих Му-олимпийских игр. Поле имеет размеры M x N (1 <= M,N <=100) и его целевое финальное состояние описывается решеткой из M x N символов таких как:
 
RSRSSS
RSRSSS
RSRSSS
 
Каждый символ описывает состояние снега на этом участке R – грубый, S – гладкий (организаторы считают, что в таком случае - чередования грубых и гладких участков, гонка будет интересней).
 
Для выполнения этой задачи ФД планирует модифицировать свой трактор так, чтобы тот мог «отштамповать» любой фрагмент размером B x B (B<=M,B<=N) грубым снегом или гладким снегом.
ФД хочет сделать B как можно большим. С B=1 он может подготовить поле, штампуя индивидуально квадраты в соответствии с заданным финальным состоянием. Однако для бОльших значений B может оказаться невозможным выполнить задачу. Каждый квадрат поля должен быть обработан трактором. Невозможно оставить ячейку поля в исходном состоянии.
 
Помогите ФД определить максимально возможное значение B, которое он сможет успешно использовать.
 
INPUT FORMAT:
 
* Строка 1: Два разделённых пробелом целых числа M и N.
 
* Строки 2..M+1: M строк ровно по N символов (каждый R или S),
        описывающих желаемое финальное состояние поля.

 
OUTPUT FORMAT:
 
* Строка 1: Максимальное значение B, которое ФД может использовать, чтобы создать нужное поле.
 
 
Ввод Вывод
3 6
RSRSSS
RSRSSS
RSRSSS
 3


 
OUTPUT DETAILS:
 
ФД может отштамповать R колонках 1-3, затем S в колонках 2-4, затем R в колонках 3-5, и наконец,  S в колонках 4-6.
 
Двумерные массивыКонструктив
✓ 0✗ 41 200средняяВойти и решать
Fencing the Herd#27299
Фермер Джон нуждается в вашей помощи. Он решил построить изгородь в форме прямой, чтобы ограничить движение своих коров. Он рассматривает несколько вариантов размещения изгороди и с вашей помощью хочет определить наиболее подходящий. Подходящим считается вариант, когда все коровы находятся по одну сторону изгороди. Изгородь не считается подходящей, если хоть одна корова расположена на изгороди. ФД будет задавать вам вопросы про варианты изгороди, на которые вы должны отвечать YES, если изгородь подходит и NO, в противном случае.
 
Кроме того, ФД может добавить новых коров в стадо. С того момента, как корова добавлена, она должна быть по одну сторону от изгороди со всеми другими коровами.
 
Входные данные 
Первая строка ввода содержит N (1 <= N <= 100000) и Q (1 <= Q <= 100000) разделённые одним пробелом. Это, соответственно, начальное количество коров в стаде и количество запросов.
Следующие N строк описывают начальное положение стада. Каждая строка содержит два целых числа x и x (разделённые пробелом), представляющие позицию очередной коровы.
Оставшиеся Q строк содержат запросы, либо добавляющие новую корову в стадо, либо проверяющие изгородь на применимость. Строка вида 1 x y означает, что новая корова добавляется в стадо на позицию x y. Строка вида 2 A B C означает, что ФД хочет проверить изгородь, описываемую прямой Ax+By=C.
Все позиции коров уникальны (-109 <= x, x <= 109). Кроме того, -109 <= A, B <= 109 и -1018 <= C <= 1018. Никогда не будет изгороди с A = B = 0.
 
Выходные данные
Для каждой изгороди выведите YES, если она подходит и NO, в противном случае.
 
Ввод Вывод
3 4
0 0
0 1
1 0
2 2 2 3
1 1 1
2 2 2 3
2 0 1 1
YES
NO
NO
 
Прямая 2x + 2y = 3 оставляет начальные 3 коровы по одну сторону. Однако корова (1,1) на другой стороне, поэтому после её добавления такая изгородь уже не подходит. Прямая Y=1 не подходит, поскольку коровы (0,1) и (1,1) находятся на ней.
 
Предупреждение: ввод-вывод для этой задачи очень большой. В С++ можно использовать scanf или ios_base::sync_with_stdio(false). В Java надо не использовать java.util.Scanner. Не делайте flush вывода (например? используя std::endl) после каждого запроса.
Вычислительная геометрия
✓ 0✗ 11 300средняяВойти и решать
Modern Art #3#27225
Недавно вошла в моду корова-художница Picowso.
Picowso рисует особым образом. Она начинает на чистом холсте N×N, представленной матрицей N×N нолей, где ноль означает пустую ячейку холста. Затем она рисует до 9 прямоугольников на холсте, каждый одним из 9 цветов (последовательно пронумерованных 1…9). Например, она может начать рисовать прямоугольник цветом 2, получая такое промежуточное состояние холста:
 
2220 
2220 
2220 
0000
Затем она может нарисовать прямоугольник цветом 7:
 
2220 
2777 
2777 
0000
Затем она может нарисовать прямоугольник цветом 3:
 
2230 
2737 
2777 
0000
Каждый прямоугольник имеет стороны, параллельные сторонам холста и самый большой прямоугольник может быть размером с весь холст, а самый маленький размером в одну ячейку. Каждый цвет из 1…9 используется ровно один раз, хотя впоследствии любой цвет может полностью покрыть некоторые из ранних цветов.
 
По заданному конечному положению холста вычислите сколько из ещё видимых цветов могли быть первым нарисованным цветом.
 
ФОРМАТ ВВОДА:
 
Первая строка ввода содержит N, размер холста (1≤N≤10). Следующие N строк описывают финальную картинку холста, каждая содержит по N чисел в интервале 0…9. Гарантируется, что такой ввод был получен рисованием как описано выше с использованием различных цветов.

ФОРМАТ ВЫВОДА:
 
Выведите количество цветов, которые могли быть использованы первым, из всех цветов, которые видны на финальном рисунке.
 
Ввод Вывод
4
2230
2737
2777
0000
 1
Двумерные массивыКонструктив
✓ 4✗ 181 200средняяВойти и решать
COWBASIC#27217
Беси изобрела новый язык программирования, но поскольку нет компилятора, она нуждается в Вашей помощи для исполнения её программ.
COWBASIC - это простой, элегантный язык. У него две основные черты: сложение и циклы. Для решения проблемы переполнения, Беси выполняет все операции сложения по модулю 109+7. MOO-цикл исполняет блок кода фиксированное количество раз. Циклы и сложения могут быть вложенными.
 
Вам дана COWBASIC-программа, определите результат её выполнения - число, которое она вернёт.
 
ФОРМАТ ВВОДА:
 
Вам дана COWBASIC-программа длиной не более 100 строк, каждая строка длиной не более 350 символов. COWBASIC-программа это список операторов.
Имеется три типа операторов:
 
<переменная> = <выражение>
 
<литерал> MOO {
  <список операторов>
}
 
RETURN <переменная>
Имеется три типа выражений:
 
<литерал>
 
<перменная>
 
( <выражение> ) + ( <выражение> )
 
Литерал - это положительное целое число не более 100,000.
 
Переменная - это строка не более 10 маленьких латинских букв.
 
Гарантируется, что переменная никогда не будет использована или возвращена оператором RETURN прежде, чем она будет определена. Гарантируется, оператор RETURN будет только один раз в последней строке программы.
 
ФОРМАТ ВЫВОДА:
 
Выведите одно положительное целое число - значение переменной, возвращённой оператором RETURN.
ОЦЕНИВАНИЕ
 
в 20% тестов MOO-циклы не вложены.
В других 20% всех тестов программу будет иметь только одну переменную. MOO-циклы могут быть вложенными
В остальных тестах нет никаких ограничений.
 
Ввод Вывод Примечание 
x = 1
10 MOO {
  x = ( x ) + ( x )
}
RETURN x
 1024 Эта COWBASIC-программа вычисляет 210 
n = 1
nsq = 1
100000 MOO {
  100000 MOO {
    nsq = ( nsq ) + ( ( n ) + ( ( n ) + ( 1 ) ) )
    n = ( n ) + ( 1 )
  }
}
RETURN nsq
 4761 Эта программа вычисляет (105∗105+1)2 (по модулю 109+7).
.

 
"Длинная" арифметикаЗадача на реализацию
✓ 1✗ 31 200средняяВойти и решать
Consonant Fencity#27117
There are two kinds of sounds in spoken languages: vowels and consonants. Vowel is a sound, produced with an open vocal tract; and consonant is pronounced in such a way that the breath is at least partly obstructed. For example, letters a and o are used to express vowel sounds, while letters b and p are the consonants (e.g. bad, pot).

Some letters can be used to express both vowel and consonant sounds: for example, y may be used as a vowel (e.g. silly) or as a consonant (e.g. yellow). The letter w, usually used as a consonant (e.g. wet) could produce a vowel after another vowel (e.g. growth) in English, and in some languages (e.g. Welsh) it could be even the only vowel in a word.
In this task, we consider y and w as vowels, so there are seven vowels in English alphabet: a, e, i, o, u, w and y, all other letters are consonants.

Let’s define the consonant fencity of a string as the number of pairs of consecutive letters in the string which both are consonants and have different cases (lowercase letter followed by uppercase or vice versa). For example, the consonant fencity of a string CoNsoNaNts is 2, the consonant fencity of a string dEsTrUcTiOn is 3 and the consonant fencity of string StRenGtH is 5.

You will be given a string consisting of lowercase English letters. Your task is to change the case of some letters in such a way that all equal letters will be of the same case (that means, no letter can occur in resulting string as both lowercase and uppercase), and the consonant fencity of resulting string is maximal.

Input
The only line of the input contains non-empty original string consisting of no more than 106 lowercase English letters.

Output
Output the only line: the input string changed to have maximum consonant fencity.
 
Input Output
consonants CoNsoNaNts
destruction dEsTrUcTiOn
strength StRenGtH
КонструктивСтроки
1 300средняяВойти и решать
МАРШРУТЫ#27073
В государстве Чудаков N городов ( 2 <=N <= 16 ), обозначаемых заглавными латинскими буквами, начиная с A, по порядку. Между некоторыми из них проложены дороги, которые могут быть как односторонними, так и двусторонними, причем не обязательно, что из каждого города можно проехать в любой другой.

В государстве всего один маршрут автобуса – 'Ч', который совершает только один рейс каждый день. Выходя из некоторого города, он совершает ровно N переездов между городами так, чтобы вернуться в тот, из которого выехал. Других ограничений на его маршрут нет. В течение дня автобус может несколько раз проезжать один и тот же город или дорогу. В каждом городе существуют автобусные парки, из которых могут выезжать автобусы маршрута 'Ч'. Так что, хотя автобус каждый день возвращается в город, из которого стартовал в этот день, на следующий день начало маршрута 'Ч' может быть из любого другого города. Но рейс каждый день только один.

Маршрут обозначается N буквами, начиная с города, из которого происходит выезд. Например, BCDCE – допустимый маршрут для государства из 5 городов ссоответствующими дорогами: выехать из B, проехать в C, затем в D, вернуться в C, проехать в E и вернуться в изначальный город B (последний пункт маршрута, совпадающий с первым, в маршруте не указывается).

Маршрут автобуса меняется каждый день так, что список маршрутов по дням расположен в словарном порядке и содержит все возможные маршруты. Когда список кончается, его обход начинается сначала. В первый день введения маршрута 'Ч' автобус шёл по первому по порядку маршруту. Выведите его маршрут на день K работы маршрута. Пример: В государстве четыре города: A, B, C, D. Наличие дорог между ними задано матрицей, где элемент равен 1, если из города, соответствующего строке, в город, соответствующий столбцу, есть дорога, и 0 – иначе (на главной диагонали нули – дорог, ведущих назад в тот же город, не бывает).

 
откуда/куда A B C D
A 0 0 1 1
B 1 0 1 1
C 0 1 0 0
D 0 1 1 0


Полное расписание маршрутов в таком государстве выглядит так:
ADCB
BADC
BCBC
BCBD
BDBC
BDBD
CBAD
CBCB
CBDB
DBCB
DBDB
DCBA

Таким образом, например, маршрут на день 30 – это BDBD.

Формат входных данных
В первой строке указывается количество городов N ( 2<= N <= 16 ). Далее следует N строк по N элементов (цифр), разделенных пробелом, содержащих матрицу, задающую дороги между городами. Далее следует строка содержащая целое число D – номер дня, маршрут которого требуется определить ( 1<= D <= 264 ).

Формат выходных данных
В единственной строке указывается маршрут, т.е. порядок посещения городов, например BDBD (см. предыдущий пример).
 
Ввод Вывод
3
0 1 1
1 0 1
1 1 0
4		 BCA

 
Комбинаторика
✓ 0✗ 41 200средняяВойти и решать
Capybara. Канатная дорога#27068
Побывав недавно в лесу, Вася решил построить на деревьях канатную дорогу. Он хочет, чтобы дорога была как можно более длинной, но он плохо помнит высоты деревьев в лесу. К счастью, он уверен, что правильно помнит высоты всех деревьев, кроме, возможно, одного из них.

Известно, что лес состоит из n деревьев, стоящих в ряд и пронумерованных слева направо числами от 1 до n. Высота i-го дерева, по воспоминаниям Васи, равна hi. Канатная дорога длины k должна опираться на k (1 <= k <= n) деревьев i1, i2, . . . , ik (i1 < i2 < . . . < ik), таких что их высота возрастает, то есть, hi1 < hi2 < . . . < hik.
Петя тоже был в лесу, и у него есть q предположений о том, где именно ошибается Вася. Его i-е предположение задаётся числами ai и bi , означающими, что, по мнению Пети, высота дерева
с номером ai на самом деле равна bi . Обратите внимание, Петины предположения независимы между собой.

Ваша задача состоит в том, чтобы для каждого предположения Пети найти максимальную длину канатной дороги, которую можно построить с опорой на эти деревья.
Отметим, что в рамках данной задачи длиной дороги Вася считает количество опорных деревьев в ней.
 
Формат входных данных
Первая строка входных данных содержит два числа n и m (1 <= n, m <= 400 000) — количество деревьев в лесу и количество предположений Пети соответственно.
В следующей строке содержатся n целых чисел hi (1 <= hi <= 109 ) — высоты деревьев по предположению Васи.

Каждая из следующих m строк содержит по два целых числа ai и bi (1 <= ai <= n, 1 <= bi <= 109 ).

Формат выходных данных
Для каждого предположения Пети выведите в отдельной строке одно число — максимальную длину канатной дороги.

Ввод Вывод
4 4
1 2 3 4
1 1
1 4
4 3
4 5		 4
3
3
4
4 2
1 3 2 6
3 5
2 4		 4
3
Замечание
Рассмотрим первый пример. Первое Петино предположение совпадает с предположением Васи.
Согласно его второму предположению, высоты деревьев были (4, 2, 3, 4), третьему (1, 2, 3, 3), а по четвёртому предположению — (1, 2, 3, 5).
Динамическое программированиедп
✓ 1✗ 411 300средняяВойти и решать
Линейная классификация#27044

В машинном обучении часто возникает задача линейной классификации объектов, когда классы объектов разделяются между собой линейной поверхностью. Например, у нас есть информация о количестве дней с момента регистрации аккаунта в социальной сети и количество отправленных сообщений за последний
день, а также информация о том, является ли этот аккаунт спам-ботом. Возраст аккаунта мы можем взять за X координату точки, а количество сообщений  за Y
коордианату. Задача классификации состоит в том, чтобы провести какую-либо прямую так, чтобы объекты одного типа находились по одну сторону этой прямой, а объекты другого типа  по другую.
 
При наличии такой прямой мы сможем пронозировать тип даже незнакомого объекта по известному возрасту аккаунта и количеству отправленных сообщений в зависимости от того, с какой стороны от прямой оказался объект. Естественно, в реальных данных могут быть ошибки измерений или необычные объекты и провести такую прямую не всегда возможно, потому что, например, объект первого типа может случйно попасть в скопление объектов второго типа и отделить его прямой невозможно.
 
Вам необходимо по информации о параметрах и типе объектов определить, существует ли прямая, которая однозначно разделеят классы объектов. Прямая не должна проходить ни через один объект.
 
Формат входных данных
В этой задаче входной файл содержит несколько тестовых блоков.
В первой строке задано число T  количество тестовых блоков (1 <= T <= 100).
Каждый тестовый блок состоит из числа N  количество описанных объектов (1 <= N <= 2000).
В следующих N строках содержится описания объектов, состоящие из трех целых чисел X, Y , Type (0 <= X, Y <= 107 , 0 <= Type <= 1).

Формат выходных данных
Выведите T слов "YES" или "NO" по одному в строке для каждого из тестовых блоков. "YES" необходимо выводить если разделение на классы возможно, "NO"  если невозможно.

Система оценки
Решения, верно работающие при T <= 10, N <= 100, будут набирать не менее половины баллов.

Ввод Вывод
2
6
1 1 1
1 2 1
1 3 0
2 1 1
2 2 0
3 1 0
6
1 3 0
2 2 0
1 2 1
3 1 1
2 1 1
1 1 0		 YES
NO

Вычислительная геометрия
✓ 2✗ 241 200средняяВойти и решать
Поделиться
Класснуть