Темы
Информатика(2656 задач)
--->
9 задач
<---
В одном городе недавно запустили автобусную сеть. Однако, плата за проезд для жителей этого города показалась чрезмерной. И несознательные граждане, вместо того, чтобы покупать билет, стали договариваться с водителем и ездить за полцены. Конечно, городская казна понесла серьезные убытки, и было решено взять на работу нескольких контролёров. По уставу, каждый контролёр должен стоять на одном месте и останавливать подозрительные автобусы с целью проверки билетов.
Для повышения эффективности труда контролёров начальство хочет, чтобы через каждую точку, в которой находится контролёр, проходили маршруты всех автобусов. С другой стороны, нельзя ставить нескольких контролёров в одной точке, чтобы они не отвлекались от выполнения своих обязанностей. Наконец, третья сторона, независимый профсоюз, требует от городской администрации принять на работу максимальное количество контролёров.
Для простоты предположим, что действие происходит на координатной плоскости. Каждый автобус ездит по границе прямоугольника c ненулевыми сторонами, вершины которого имеют целочисленные координаты, а стороны параллельны осям координат. Требуется выяснить, какое максимальное число контролёров удастся принять на работу, если городское управление милиции, в свою очередь, требует, чтобы каждый контролёр находился в точке с целочисленными координатами.
На первой строке входного файла находится число \(n\) (1 ≤ \(n\) ≤ \(10^4\)) – количество маршрутов. Далее следуют \(n\) строк, на каждой из которых находятся две пары целых чисел – координаты двух противоположных вершин прямоугольника, по которому проходит данный маршрут. Все координаты не превосходят \(10^8\) по абсолютной величине.
Выведите в выходной файл одно число – максимальное количество контролёров, которые смогут обрести работу благодаря этому мероприятию.
1 0 0 1 1
4
В марсианских сутках \(N\) часов. У марсиан Ятеп и Ашам есть часы со стрелками, которые работают почти так же, как земные – большая стрелка делает один оборот в час, а маленькая – один оборот в сутки. Ятеп и Ашам поссорились и решили не разговаривать, пока стрелки часов не совпадут. Определите точный момент времени, когда это случится.
Во входном файле задано число тестов \(K\) (0 ≤ \(K\)<\(10^4\)), далее для каждого теста указаны целые числа \(N\), \(A\), \(B\) и \(C\) (1<\(10^9\), 0 ≤ \(A\), 0 ≤ \(B\) < \(10^9\)). Числа \(A\), \(B\) и \(C\) означают, что Ятеп и Ашам поссорились в \(A\)+\(B\)/\(C\) часов.
Для каждого теста выведите искомое время в том же формате: числа \(A\), \(B\) и \(C\), такие, что искомое время равно \(A\)+\(B\)/\(C\) (0 ≤ \(A\), 0 ≤ \(B\), дробь \(B\)/\(C\) – несократимая).
2 12 11 0 1 12 0 0 1
0 0 1 1 1 11
Рассмотрим две строки \(α\) и \(β\). Их конкатенацией называется строка, получающаяся в результате приписывания к строке \(α\) строки \(β\). Эта строка обозначается \(αβ\). Например, конкатенацией строк `ab' и `ac' будет строка `abac'. Очевидно, что это определение естественным образом распространяется на конкатенацию произвольного количества строк. Так, конкатенацией нуля строк будет пустая строка, а конкатенацией одной строки будет она сама.
Рассмотрим некоторое множество \(W\), состоящее из строк. Назовём его замыканием множество \(W\)*, состоящее из тех и только тех строк, которые можно получить в результате конкатенации нуля и более строк из множества \(W\). Таким образом, множество \(W\)* содержит пустую строку, и если строка α принадлежит множеству \(W\)*, а строка \(β\) принадлежит множеству \(W\), то строка \(αβ\) принадлежит множеству \(W\)*. Более того, все элементы множества \(W\)* можно представить в таком виде, то есть \(W\)* является пересечением всех множеств с указанными выше свойствами. Например, если \(W\)={a,ab}, то \(W\)* состоит из всех строк, в которых перед каждой буквой `b' идёт хотя бы одна буква `a'.
Задано некоторое множество строк \(W\). Требуется найти множество \(X\), такое, что \(W\)*=\(X\)* и множество \(X\) имеет минимальное возможное число элементов. В случае, если таких множеств несколько, подходит любое из них. Например, если \(W\)={a,aabb,ab,ac,b,bac}, то единственным множеством, удовлетворяющим условиям задачи будет множество {a,ac,b}.
Входной файл состоит из набора строк, каждая из которых является элементом множества \(W\). Каждая строка из множества \(W\) встречается во входном файле хотя бы один раз. Суммарная длина всех строк во входном файле не превосходит \(10^4\). Количество строк во входном файле не превосходит \(10^4\). После каждой строки из множества \(W\) во входном файле идёт перевод строки (пара символов с ASCII кодами 13 и 10). Строки состоят из символов с ASCII кодами от 33 до 126 включительно.
Выведите в выходной файл элементы одного из множеств \(X\), удовлетворяющих условиям задачи. Каждая строка множества \(X\) должна быть выведена ровно один раз. Строки должны идти в лексикографическом порядке (лексикографический порядок используется в словарях, в этом порядке строка `ab' меньше строки `aba' и строка `ab' меньше строки `ac'). После каждой строки множества \(X\) должен идти один перевод строки.
a aabb ab ac b bac
a ac b
Идёт 2163 год. Мишу, который работает в отделении таможни при космодроме города Нью-Питер, вызвал в кабинет шеф.
Как оказалось, недавно Министерство Налогов и Сборов выделило отделению определённую сумму денег на установку новых аппаратов для автоматического досмотра грузов. Естественно, средства были выделены с таким расчётом, чтобы грузы теперь находились на таможне ровно столько времени, сколько требуется непосредственно на их досмотр.
В руках шефа каким-то образом оказались сведения о надвигающейся ревизии – список из \(N\) грузов, которые будут контролироваться Министерством. Для каждого груза известны время его прибытия, отсчитываемое с некоторого момента, хранимого в большом секрете, и время, требуемое аппарату для обработки этого груза. Шеф дал Мише задание по этим данным определить, какое минимальное количество аппаратов необходимо заказать на заводе, чтобы все грузы Министерства начинали досматриваться сразу после прибытия. Необходимо учесть, что конструкция тех аппаратов, которые было решено установить, не позволяет обрабатывать два груза одновременно на одном аппарате. Напишите программу, которая поможет Мише справиться с его задачей.
На первой строке входного файла задано число \(N\) (0 ≤ \(N\) ≤ 50 000). На следующих \(N\) строках находится по 2 целых положительных числа \(T_i\) и \(L_i\) – время прибытия соответствующего груза и время, требуемое для его обработки (1 ≤ \(T_i\) ≤ \(10^6\), 1 ≤ \(L_i\) ≤ \(10^6\)).
В выходной файл выведите одно число – наименьшее количество аппаратов, которое нужно установить, чтобы не вызвать подозрений у Министерства.
3 3 2 4 2 5 2
2
5 13 4 15 1 11 5 12 3 10 3
3
Строки формируются по правилу: S1 = a, Si = Si-1 + chr(i) + Si-1. Необходимо по данной строке найти максимальное i, такое что данная строка является подстрокой Si
Учёные любят присваивать идентификаторы всему живому. Поэтому они обозначают динозавров I эпохи кодом `a'. Динозавры II эпохи, как произошедшие от динозавров I эпохи, именуются кодом `aba'. Ящеры III эпохи – `abacaba', и вообще если \(C\)(\(n\)) – код динозавров эпохи \(n\), то \(C\)(\(n\)+1)=\(C\)(\(n\))+\(S\)(\(n\)+1)+\(C\)(\(n\)) , где \(S\)(\(n\)+1) – символ очередной (\(n\)+1-ой) эпохи. Символ первой эпохи – `a' , символ второй эпохи – `b', затем `c', `d', …, `x', `y', `z'. После букв учёные почему-то перешли на цифры, и обозначили эпохи с XXVII по XXXVI соответственно `0', `1', …, `9' .
После XXXVI эпохи динозавры вымерли, и уже утверждённое название XXXVII эпохи (`α') отдали астрономам для нового кратера на Марсе.
Астрономы (в знак благодарности) нашли какую-то отдалённую звезду с огромной статуей динозавра, похожего на земные аналоги. Экспедиция, посетившая указанную звезду, нашла под статуей надпись, очевидно, с кодом этого динозавра. Впрочем, часть надписи стёрлась. Теперь учёные хотят максимально завысить древность находки. Для этого нужно определить, в коде динозавров какой эпохи – самой древней из подходящих – встречается данный образец (как подстрока). Такую задачу не по силам решить даже астрономам.
На первой и единственной строке входного файла находится непустая строка, состоящая из символов `a', …, `z', `0', …, `9'. Длина строки не превосходит 100.
Выведите два числа – номер эпохи и смещение образца от начала кода. Если же статуя изображает неземного динозавра (или код инопланетян отличается от земного), выведите в выходной файл число 0.
a
1 0
bae
5 13