Для транспортирования материалов из цеха А в цех В используется конвейер. Материалы упаковываются в одинаковые контейнеры и размещаются на ленте один за одним в порядке изготовления в цехе А. Каждый контейнер имеет степень срочности обработки в цехе В. Для упорядочивания контейнеров по степени срочности используют накопитель, который находится в конце конвейера перед входом в цех В. Накопитель работает пошагово, на каждом шаге возможны следующие действия:
накопитель перемещает первый контейнер из ленты в цех В;
накопитель перемещает первый контейнер из строки в склад (в складе каждый следующий контейнер помещается на предыдущий);
накопитель перемещает верхний контейнер из склада в цех В.
Напишите программу, которая по последовательности контейнеров определит, можно ли упорядочить их по степени срочности пользуясь описанным накопителем.
Входной файл в первой строке содержит количество тестов N. Далее следует N строк, каждый из которых описывает отдельный тест и содержит целое число K (1 ≤ K ≤ 10000) — количество контейнеров в последовательности и K действительных чисел — степеней срочности контейнеров в порядке их поступления из цеха А (меньшим числам соответствует большая степень срочности).
Каждая строка выходного файла должна содержать ответ для одного теста. Необходимо вывести 1, если необходимое упорядочивание возможно, или 0 в противном случае.
2 2 2.9 2.1 3 5.6 9.0 2.0
1 0
В городе введено движение автобусов. Все автобусы имеют циклические маршруты. Некоторые маршруты имеют общие остановки. Когда два или больше автобусов встречаются на одной остановке, водители обмениваются всеми новостями, которые им известны на данный момент (после того как они отъедут от остановки, все будут знать одинаковые новости).
Водители начинают движение своих автобусов одновременно, и в это время каждый из водителей знает одну новость, которую не знает ни один из других.
Движение автобусов синхронизировано в том смысле, что время, необходимое для переезда от одной остановки до следующей, одинаково для всех автобусов.
Существует D водителей (и, соответственно, D автобусов), которые пронумерованы от 1 до D, и S остановок, которые имеют номера от 1 до S.
Напишите программу, которая определит, может ли каждый водитель знать все новости своих коллег, если длительность нахождения на маршруте неограниченна.
Входной файл в первой строке содержит число тестов N. Далее следует N блоков информации, каждый из которых соответствует одному тесту. Первая строка блока содержит два целых числа D (1 D 100) и S (1 S 250). Каждая из следующих D строк описывает маршрут одного из автобусов таким образом: первое число — количество остановок на данном маршруте Mi, после чего Mi разных целых чисел, которые задают последовательность остановок маршрута. Движение автобуса начинается с остановки, которая указана первой.
Каждая строка выходного файла должна содержать ответ для одного теста. Необходимо вывести 1, если каждый водитель узнает все новости, или 0 в противном случае.
2 1 3 3 1 2 3 2 2 2 1 2 2 2 1
1 0
Достаточно популярна лотерея, которая проводится по таким правилам: из набора N шариков случайно выбираются K шариков, которые являются выигрышными. Выигрывают игроки, которые предвидели выбор именно этих шариков. Нетрудно подсчитать количество C вариантов выбора K шариков из набора N шариков.
Напишите программу которая определит, какое именно количество шариков необходимо брать из набора N шариков, если количество вариантов выбора есть C.
Входной текстовый файл содержит в единственной строке два числа — N и C (1≤N≤500000).
Единственная строка выходного файла должна содержать число K — количество шариков, которые надо брать.
15 5005
6