Задача A. Наибольшее число цепочек

Автор:А. Баранов   Ограничение времени:1 сек
Входной файл:input.txt   Ограничение памяти:2 Мб
Выходной файл:output.txt  

Условие

Пусть имеется множество всех возможных цепочек, состоящих из конечного числа звеньев. Из указанных цепочек необходимо построить последовательность такую, чтобы каждая следующая цепочка в ней была ровно на d звеньев больше предыдущей, а суммарная длина всех входящих в нее цепочек равнялась n. Максимально возможное количество цепочек, из которых может состоять такая последовательность, обозначим за A(n, d).

Требуется вычислить значения A(n, d) для всех натуральных n, не превосходящих заданного m, при некотором фиксированном d.

Формат входного файла

Входной файл "input.txt" содержит два натуральных числа: d и m.

Формат выходного файла

Выходной файл "output.txt" должен содержать последовательность значений A(n, d), расположенных в порядке возрастания величины n = 1, 2, …, m.

Ограничения

d ≤ m ≤ 105

Примеры тестов

Входной файл (input.txt) Выходной файл (output.txt)
1
1 10
1 1 2 1 2 3 2 1 3 4
2
2 10
1 1 1 2 1 2 1 2 3 2

Задача B. Составные блоки

Автор:А. Баранов   Ограничение времени:1 сек
Входной файл:input.txt   Ограничение памяти:2 Мб
Выходной файл:output.txt  

Условие

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

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

Совпадающие между собой ребра (в которых две и более ячейки соприкасаются друг с другом) полагаются тождественными и рассматриваются как одно общее ребро. Так, например, блок размером 2 × 2 × 2 состоит из 8-ми ячеек и содержит в себе 54 ребра.

Требуется определить, существует ли прямоугольный блок, состоящий из m кубических ячеек и при этом имеющий ровно n ребер.

Формат входного файла

Во входном файле "input.txt" содержатся два натуральных числа: m и n.

Формат выходного файла

Выходной файл "output.txt" должен содержать одно из следующих значений:

1 — если заданный блок существует;

0 — в противном случае.

Ограничения

0 < m < 232, 0 < n < 264

Примеры тестов

Входной файл (input.txt) Выходной файл (output.txt)
1
8 54
1
2
6 43
0

Задача C. Нули в окончании числа

Автор:А. Баранов   Ограничение времени:1 сек
Входной файл:input.txt   Ограничение памяти:2 Мб
Выходной файл:output.txt  

Условие

Обозначим за P(A, B) результат произведения всех натуральных чисел от A до B включительно.

Для заданных значений A, B и q требуется определить количество нулевых разрядов, которыми оканчивается q-ичная запись числа P(A, B).

Формат входного файла

Входной файл "input.txt" содержит три натуральных числа: A, B и q.

Формат выходного файла

Выходной файл "output.txt" должен содержать одно единственное число, указывающее количество нулевых разрядов.

Ограничения

0 < A ≤ B < 264, 2 ≤ q < 232

Примеры тестов

Входной файл (input.txt) Выходной файл (output.txt)
1
1 100 10
24
2
9 75 120
17

Задача D. Представление дробей

Автор:А. Баранов   Ограничение времени:1 сек
Входной файл:input.txt   Ограничение памяти:2 Мб
Выходной файл:output.txt  

Условие

Пусть имеется некоторая простая дробь, заданная своим числителем A и знаменателем B.
Требуется преобразовать указанную дробь, представив ее в одном из следующих форматов:

Если дробная часть равна нулю, результат записывается как целое число.
В противном случае полученную дробь следует привести к несократимому виду
так, чтобы <числитель> был меньше, чем <знаменатель>.

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

Формат входного файла

Во входном файле "input.txt" содержатся два натуральных числа: A и B.

Формат выходного файла

Выходной файл "output.txt" должен содержать дробь A / B,
отформатированную в соответствии с условием задачи.

Ограничения

0 < (A, B) < 264

Примеры тестов

Входной файл (input.txt) Выходной файл (output.txt)
1
1736744720710
5067073484375
11977549798 / 34945334375
2
57295346800
351486000
163 ( 7822 / 878715 )
3
10298463668
40000000
257.4615917
4
1675223508
13509867
124

Задача E. Возведение большого числа в степень

Автор:А. Баранов   Ограничение времени:1 сек
Входной файл:input.txt   Ограничение памяти:2 Мб
Выходной файл:output.txt  

Условие

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

Формат входного файла

Первая строка входного файла "input.txt" представляет собой десятичную запись числа A.
Следующая строка содержит показатель степени n.

Формат выходного файла

Выходной файл "output.txt" должен содержать результат возведения в степень,
представленный в десятичной системе счисления.

Ограничения

0 ≤ A ≤ 1050, 0 < n ≤ 1000

Примеры тестов

Входной файл (input.txt) Выходной файл (output.txt)
1
10203756485819806252197658031528043601970
2
104116646421909761950282879573175588809976767764774752111453905887721451787880900
2
55786
17
490827381405222212342433355512086149590506305271663102056527621790991920279453696

Задача F. Сжатие бинарной строки

Автор:А. Баранов   Ограничение времени:1 сек
Входной файл:input.txt   Ограничение памяти:2 Мб
Выходной файл:output.txt  

Условие

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

Пусть имеется некоторая бинарная последовательность (состоящая из нулей и единиц), разбитая на блоки фиксированной длины. При этом заранее известно, что каждый такой блок содержит в себе ровно n нулей и m единиц.

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

Несложно показать, что размер полученного алфавита обратно пропорционален значению |n − m|. Так, в предельном случае, когда n (или m) равно нулю, алфавит будет состоять всего-лишь из одного символа. В свою очередь, чем меньше размер алфавита, тем меньшее число бит будет требоваться для представления номеров содержащихся в нем символов.

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

Формат входного файла

В первой строке входного файла "input.txt" записаны два целых неотрицательных числа n и m. Далее следует текстовая строка, состоящая из n нулей и m единиц.

Формат выходного файла

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

Ограничения

0 < (n + m) ≤ 2 ⋅ 104

Примеры тестов

Входной файл (input.txt) Выходной файл (output.txt)
1
8 24
00000001101111111111111111111111
000000000000000000000010
2
24 8
01000100000011001000001101000000
011000111110100111000100

Задача G. Очередь в поликлинике

Автор:А. Баранов   Ограничение времени:1 сек
Входной файл:input.txt   Ограничение памяти:8 Мб
Выходной файл:output.txt  

Условие

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

За отдельно взятые сутки была собрана статистика, состоящая из моментов времени ti, указанных в талоне каждого i-го пациента, и времени mi, которое было затрачено на его прием.
Требуется определить максимальную длину очереди, которая имела место за текущие сутки, а также время окончания приема последнего пациента.

При решении задачи следует полагать, что все ti и mi указывают время в минутах и могут принимать только целочисленные значения. Число минут в сутках полагается равным tmax.

Также известно, что пациентам, которые не успели пройти прием в течение суток, очередь автоматически продлевается на следующий день.
В качестве окончания приема для всех таких пациентов указывается максимально допустимое время t = tmax.

Формат входного файла

В начале входного файла "input.txt" содержится пара натуральных чисел tmax и n, за которыми следует ровно n записей, представленных в виде пар положительных целых чисел ti и mi. При этом полагается, что все они упорядочены по возрастанию ti.

Формат выходного файла

Выходной файл "output.txt" должен содержать два значения: максимальную длину очереди и время завершения последнего приема.

Ограничения

0 < tmax ≤ 106, 0 < (ti, mi) ≤ tmax, ti < ti + 1

Примеры тестов

Входной файл (input.txt) Выходной файл (output.txt)
1
1440 10
1 1
2 1
3 2
54 2
349 1
720 2
1024 2
1175 2
1193 1
1205 3
0 1208
2
1440 10
1 1
2 4
6 134
79 12
136 5
214 173
345 15
1075 2
1093 114
1205 3
2 1210

Задача H. Число комнат в лабиринте

Автор:А. Баранов   Ограничение времени:1 сек
Входной файл:input.txt   Ограничение памяти:2 Мб
Выходной файл:output.txt  

Условие

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

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

Для некоторого заданного лабиринта требуется определить общее число закрытых комнат.

Формат входного файла

Во входном файле "input.txt" построчно хранится двумерный массив символов, представляющий собой карту лабиринта. Свободные клетки в нем обозначаются пробелами (ASCII 32), в то время как все остальные выступают в качестве непроходимых участков.

Формат выходного файла

Выходной файл "output.txt" должен содержать полученное число комнат.

Ограничения

0 < (n, m) ≤ 5000

Примеры тестов

Входной файл (input.txt) Выходной файл (output.txt)
1
xxxxxxxxx    xxx xx xxxxxxxxxxxx
xxxxxxxxx    xxx xx xxxxxxxxxxxx
xxxxxxxxx    xxx                
xxxxxxxxx    xxxxxxxxx   xxxxxxx
xxx          xxxxxxxxx   xxxxxxx
xxx   xxx    xxxxxxxxx          
xxx          xxxxxxxxx          
xxxxxx  xxx  xxxxxxxxx   xxxxxxx
xxxxxx  xxx  xxxxxxxxx   xxxxxxx
xxxxxx                   xxxxxxx
xxxxxxxxxxxxx            xxxxxxx
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
1
2
xxx   xxx       xxxx  0000000000
xxx   xxx   xx  xxxx  0000000000
xxx   xxx   xx                  
xxxxxxxxx   xxxxxxxx  aaa    iii
            xxxxxxxx  aaa       
xxx   xxx   xxaa    aa    000iii
              aa    aa    000iii
iiiiii   aaa  aaaaaaaa    000iii
iiiiii   aaa  aaaaaaaa    000iii
000iii                          
000000   000  00000000    000000
000000   0000000000000    000000
3

Задача I. Префиксные основы

Автор:А. Баранов   Ограничение времени:1 сек
Входной файл:input.txt   Ограничение памяти:2 Мб
Выходной файл:output.txt  

Условие

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

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

Формат входного файла

В начале входного файла "input.txt" хранится натуральное число n. Далее следует набор из n слов, состоящих из цифр и букв латинского алфавита (регистр их написания неважен). При этом каждое слово располагается в отдельной строке.

Формат выходного файла

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

Ограничения

Полагается, что длина отдельно взятого слова лежит в диапазоне от 1 до 5000.

0 < n ≤ 105.

Размер входного файла не превосходит 10 МБ.

Примеры тестов

Входной файл (input.txt) Выходной файл (output.txt)
1
10
abcd11112345
y4141
abcd1111
abcdy
yyyy
abcdabcdabcd
A1111
A1111
11114141
AbcD
1111 5
2345 1
4141 2
a 9
bcd 7
y 6
2
10
111123abcd
y4141A
abcd1111
y4141a
abcdy
AbCdA
AbCd1111
abcd
A1111
aA
1111 4
23abcd 1
4141a 2
a 9
bcd 5
y 3

Задача J. Генератор палиндромов

Автор:А. Баранов   Ограничение времени:1 сек
Входной файл:input.txt   Ограничение памяти:2 Мб
Выходной файл:output.txt  

Условие

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

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

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

Формат входного файла

В заголовке входного файла "input.txt" содержатся две строки S и T, состоящие из цифр и строчных букв латинского алфавита.
За ними следует натуральное число n.

Формат выходного файла

Выходной файл "output.txt" должен содержать все оставшиеся палиндромы, расположенные в лексикографическом порядке.

В случае если их число равно нулю, выходной файл следует оставить пустым.

Ограничения

0 < |T| ≤ |S| ≤ 100,

0 < n ≤ 2 ⋅ 104

Примеры тестов

Входной файл (input.txt) Выходной файл (output.txt)
1
abcbac
aca
15
aca
acbbca
acbca
acca
b
baab
bab
bacab
baccab
bb
bcaacb
bcacb
bcb
bccb
c
2
123243
21a
50
22
23132
232
2332
23432
242
3
313
32123
3223
323
32423
33
343
4

Задача K. Число вхождений подстроки

Автор:А. Баранов   Ограничение времени:1 сек
Входной файл:input.txt   Ограничение памяти:2 Мб
Выходной файл:output.txt  

Условие

Пусть имеется текстовая строка S, состоящая из произвольных печатных символов (ASCII 32-126). Требуется определить общее число ее подстрок, совпадающих с некоторым заданным образцом T.

Для решения задачи следует воспользоваться алгоритмом Кнута-Морриса-Пратта.

Формат входного файла

В заголовке входного файла "input.txt" содержится строка T, выступающая в роли образца. Далее следует строка S, в которой необходимо выполнить поиск.

Формат выходного файла

Выходной файл "output.txt" должен содержать число найденных подстрок.

Ограничения

0 < |T| ≤ 5 ⋅ 104, 0 ≤ |S| ≤ 2 ⋅ 107

Примеры тестов

Входной файл (input.txt) Выходной файл (output.txt)
1
ABCDEF
123 AB ABCDEFABCDEF ABCDEF45ABCDEFuZ
4
2
ABCABC
ZEt AB ABCABCABCABC ABC45-ABCABCABC+
5

Задача L. Сортировка записей

Автор:А. Баранов   Ограничение времени:1 сек
Входной файл:input.txt   Ограничение памяти:8 Мб
Выходной файл:output.txt  

Условие

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

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

При сравнении отдельных полей необходимо придерживаться следующих правил: вещественные значения должны быть упорядочены по возрастанию; знаковые целые — по убыванию; беззнаковые — по возрастанию; символьные значения — по убыванию своих позиций в таблице ASCII; упорядочение строк производится по возрастанию (в лексикографическом порядке).

Формат входного файла

В первой строке входного файла "input.txt" содержится пара натуральных чисел n и m, указывающих общее количество таких записей и число их полей. Во второй строке содержится массив из m символьных значений (разделенных пробелами), указывающих тип каждого поля в соответствии со следующей таблицей:

Далее следует массив из m целых чисел pi, устанавливающих приоритеты указанных полей. Начиная с четвертой строки располагается массив записей. При этом значение каждого поля занимает ровно одну строку.

Формат выходного файла

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

Ограничения

n ≤ 2 ⋅ 104, m ≤ 10, 0 ≤ pi < 10

Примеры тестов

Входной файл (input.txt) Выходной файл (output.txt)
1
5 4
i s d c
2 9 7 0
-1
QWERTY
3.90000
a
-9
ASUS
0.47000
t
75
QWERTY
0.10000
x
9
ASKOLD
8.05000
b
0
ASUS
-0.00075
y
3
4
1
2
0
2
5 4
i u d c
9 8 1 3
-1
48
-3.50000
a
-9
15
0.90000
w
-9
10
4.70000
b
-1
48
-0.70000
z
-1
48
1.56000
p
3
4
0
2
1

Задача M. Сжатый префиксный словарь

Автор:А. Баранов   Ограничение времени:1 сек
Входной файл:input.txt   Ограничение памяти:4 Мб
Выходной файл:output.txt  

Условие

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

  1. на начальном этапе алгоритма создадим пустой словарь T и заведем счетчик k = 0;
  2. будем двигаться по заданной строке, читая ее символы слева направо;
  3. находясь в начале очередного суффикса строки S, выберем наименьший непустой его префикс, который отсутствует в словаре T;
  4. выбранный на предыдущем этапе префикс добавим в словарь, указав в качестве числового кода его порядковый номер k;
  5. увеличим счетчик k на единицу;
  6. дальнейший поиск продолжается с позиции, следующей после указанного префикса.

Если при попытке добавления очередной подстроки число записей в словаре превысит некоторое заданное n, словарь должен быть очищен. Счетчик k при этом обнуляется. Последний считанный символ (в окончании текущего префикса) возвращается в поток, и процедура возобновляется с той же позиции, в которой она остановилась.

В качестве ответа требуется вывести содержимое такого словаря на момент окончания входной строки.

Формат входного файла

В первой строке входного файла "input.txt" записано натуральное число n.
Далее следует строка S, для которой необходимо построить словарь.

Формат выходного файла

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

Ограничения

10 ≤ n ≤ 5000, 0 < |S| ≤ 2 ⋅ 107

Примеры тестов

Входной файл (input.txt) Выходной файл (output.txt)
1
50
BaNaNAbaNAnaBaNaNAba
a 1
ab 4
aba 9
an 3
ana 5
b 0
ba 7
n 2
na 6
nan 8
2
10
12uitNp3zxrv45swe6qa
4 2
5 3
6 7
a 9
e 6
q 8
r 0
s 4
v 1
w 5

Задача N. Раскрытие скобок

Автор:А. Баранов   Ограничение времени:1 сек
Входной файл:input.txt   Ограничение памяти:2 Мб
Выходной файл:output.txt  

Условие

Исходная строка, содержащая некоторое арифметическое выражение, состоит из набора символьных идентификаторов (выступающих в роли операндов), знаков операций ('+', '-', '*') и круглых скобок. Между ними также допускается наличие разделителей из произвольного числа пробелов. При этом знак минуса может обозначать как бинарную, так и унарную операцию. Между любыми двумя знаками операций всегда присутствуют либо скобки, либо операнды. Для записи операндов здесь используются строчные буквы латинского алфавита.

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

На выходе каждое такое слагаемое должно быть записано в следующем формате.

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

Каждому символу алфавита здесь должен соответствовать ровно один множитель.

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

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

Формат входного файла

Входной файл "input.txt" содержит единственную строку с арифметическим выражением.

Формат выходного файла

Выходной файл "output.txt" должен содержать все полученные слагаемые, приведенные к требуемому виду и разделенные символами '+' либо '-'
(в зависимости от знаков стоящих перед ними коэффициентов).

Если полученное выражение тождественно равно нулю, в выходной файл выводится 0.

Ограничения

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

Число открывающихся скобок ограничено и не превосходит 20.

Примеры тестов

Входной файл (input.txt) Выходной файл (output.txt)
1
- a * b * (b+a) +b*c + b*(a + c)
2*b*c+a*b-a*b^2-a^2*b
2
 (a + b) - b -(a - b) -b 
0

Задача O. Два кольца на плоскости

Автор:А. Баранов   Ограничение времени:1 сек
Входной файл:input.txt   Ограничение памяти:2 Мб
Выходной файл:output.txt  

Условие

Кольцо представляет собой область плоскости, ограниченную двумя окружностями.

Пусть имеются два кольца, каждое из которых задается координатами своего центра (xi, yi), а также внутренним qi и внешним ri радиусами.

Требуется определить площадь их пересечения.

Формат входного файла

Во входном файле "input.txt" содержится набор вещественных значений, определяющих положение исходных колец: x1, y1, q1, r1, x2, y2, q2, r2.

Формат выходного файла

Выходной файл "output.txt" должен содержать площадь их пересечения, указанную с точностью до 5-го знака после запятой.

Ограничения

0 ≤ q1 ≤ r1, 0 ≤ q2 ≤ r2

Примеры тестов

Входной файл (input.txt) Выходной файл (output.txt)
1
-2.16000 -2.45000  1.27000  2.35000
 1.00000  0.19000  3.00000  4.00000
2.24485
2
-3.64000 -2.75000  1.00000  2.95000
 5.00000 -3.19000  2.00000  4.00000
0.00000

Задача P. Три подвижные частицы

Автор:А. Баранов   Ограничение времени:1 сек
Входной файл:input.txt   Ограничение памяти:2 Мб
Выходной файл:output.txt  

Условие

Пусть имеются три частицы, положение которых в момент времени t = 0 задается двумерными координатами: (x1, y1), (x2, y2) и (x3, y3).

Полагается, что в течение всего последующего времени каждая i-я частица, независимо от остальных,
совершает прямолинейное движение с некоторой постоянной скоростью (ui, vi).

Требуется определить наиболее ранний момент времени T ≥ 0, когда они окажутся на одной прямой.

Формат входного файла

Входной файл "input.txt" содержит последовательность целых чисел:
x1, y1, u1, v1, x2, y2, u2, v2, x3, y3, u3, v3.

Формат выходного файла

Выходной файл "output.txt" должен содержать значение T, указанное с точностью до 5-го знака после запятой.

В случае если подходящее решение не может быть найдено, в выходной файл необходимо вывести  − 1.

Ограничения

Все входные значения являются целыми десятичными числами.

 − 104 ≤ (xi, yi, ui, vi) ≤ 104.

Примеры тестов

Входной файл (input.txt) Выходной файл (output.txt)
1
 2500  2500 -3000 -3000
-1000     0  1000  4000
    0 -1000  4000  3000
 0.48990
2
-1097   236  1000  1000
  200   178  1500   500
    0  -500 -1240   356
-1

Задача Q. Ловушка для подвижных частиц

Автор:А. Баранов   Ограничение времени:1 сек
Входной файл:input.txt   Ограничение памяти:2 Мб
Выходной файл:output.txt  

Условие

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

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

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

Определим кольцо, как область, заключенную между двумя окружностями с общим центром (x0, y0) и разными радиусами: r2 > r1 > 0. В этом случае исходное множество частиц можно условно разбить на три группы:

  1. частицы, попадающие во внутренний круг с центром в точке (x0, y0) и радиусом r1 > 0;
  2. частицы, заключенные между двумя окружностями с радиусами r1 и r2;
  3. частицы, лежащие за пределами внешнего круга с радиусом r2 > r1.

Рассмотрим поведение указанных частиц на временном интервале от 0 до T.

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

Требуется написать программу, которая по известному начальному положению частиц, исходным компонентам скорости и параметрам кольцевой области, производит расчет их траекторий в течение заданного промежутка времени. В качестве ответа вывести координаты положения частиц в равноотстоящие моменты времени tk = k ⋅ (T / m), где k = 1, 2, …, m.

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

Формат входного файла

В первой строке входного файла "input.txt" содержатся параметры расчетной области: x0, y0, r1, r2. Во второй строке указано значение T, задающее длину временного интервала, и число его подынтервалов m. Далее следует натуральное число n и последовательность из 4 × n вещественных чисел, задающих начальные координаты и скорости каждой из частиц: xi, yi, ui, vi, где i = 1, 2, …, n.

Формат выходного файла

Выходной файл "output.txt" должен содержать координаты положения частиц в моменты времени tk (k = 1, 2, …, m), расположенные в том же порядке, что и во входном файле. Все значения должны быть указаны с точностью до 5-го знака после запятой.

Ограничения

Полагается, что ни одна из частиц в начальный момент времени не лежит на границе кольца.

2 ≤ r1 ≤ (r2 − 2) ≤ 10, 0 < T ≤ 20, 0 < m ≤ 10,

ui2 + vi2 ≤ 25, 0 < n ≤ 4000

Примеры тестов

Входной файл (input.txt) Выходной файл (output.txt)
1
 1.62400  4.86000  2.01152  4.21450
10.00000  4
 5
 2.24501 -2.75130 -0.46250  1.00000
-1.39080  6.92500  0.02731 -1.75240
-7.10643  2.32470  0.10561  0.27435
 2.07640  4.96800 -0.04658  0.94071
 3.00000  3.75400 -1.04060 -1.04520
 1.08876 -0.25130
-1.32252  2.54400
-6.84240  3.01057
 1.79231  6.39753
 0.09054  3.90417

-0.67633 -0.22719
 2.36153  1.88787
-6.57838  3.69645
 0.85566  4.23718
 1.22695  6.69642

-2.86015 -1.90584
 4.61717  4.01900
-6.31435  4.38232
 1.39629  4.06765
 3.58175  4.57937

-5.04397 -3.58449
 4.04359  7.86965
-6.05033  5.06820
 3.19249  5.59017
 0.69049  3.16606

Задача R. Треугольник в параллелепипеде

Автор:А. Баранов   Ограничение времени:1 сек
Входной файл:input.txt   Ограничение памяти:2 Мб
Выходной файл:output.txt  

Условие

Пусть имеется параллелепипед со сторонами, параллельными осям координат: D = { (x, y, z): xmin ≤ x ≤ xmax, ymin ≤ y ≤ ymax, zmin ≤ z ≤ zmax} и некоторый треугольник T, заданный координатами своих вершин: (x1, y1, z1), (x2, y2, z2), (x3, y3, z3).

Требуется определить площадь той части треугольника T, которая имеет общие точки с параллелепипедом D.

Формат входного файла

В начале входного файла "input.txt" записаны координаты двух наиболее удаленных вершин параллелепипеда: (xmin, ymin, zmin), (xmax, ymax, zmax).

Далее следуют координаты вершин треугольника: (x1, y1, z1), (x2, y2, z2), (x3, y3, z3).

Формат выходного файла

Выходной файл "output.txt" должен содержать площадь, указанную с точностью до 5-го знака после запятой.

Ограничения

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

xmin ≤ xmax, ymin ≤ ymax, zmin ≤ zmax.

Примеры тестов

Входной файл (input.txt) Выходной файл (output.txt)
1
-1.00000 -1.00000 -1.00000
 1.00000  1.00000  1.00000

-1.25000  0.56000  1.28090
-1.30000 -1.29010 -0.75000
 0.60790 -1.30700  1.30600
0.97386
2
-1.50000 -1.50000  1.00000
 0.50000  0.00000  1.50000

-3.70980  0.67000  3.20000
-4.60000 -1.86010  3.80250
 1.00000 -1.25000  4.10900
0.00000

Задача S. Пересечение двух пластин

Автор:А. Баранов   Ограничение времени:1 сек
Входной файл:input.txt   Ограничение памяти:2 Мб
Выходной файл:output.txt  

Условие

Пусть имеются две круглые плоские пластины, произвольным образом расположенные в трехмерном пространстве. Каждая такая пластина однозначно задается ортогональным к ней вектором (Nxi, Nyi, Nzi), своим центром (Cxi, Cyi, Czi) и радиусом Ri.

Требуется определить наличие пересечения между указанными пластинами. Будем считать, что пластины пересекаются, если у них имеется как минимум одна общая точка.

Формат входного файла

В начале входного файла "input.txt" хранится набор вещественных значений, задающих первую пластину:
Nx1, Ny1, Nz1, Cx1, Cy1, Cz1, R1.
Далее следует такой же набор, задающий вторую пластину:
Nx2, Ny2, Nz2, Cx2, Cy2, Cz2, R2.

Формат выходного файла

Выходной файл "output.txt" должен содержать:

1 — если заданные пластины пересекаются;

0 — в противном случае.

Ограничения

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

Примеры тестов

Входной файл (input.txt) Выходной файл (output.txt)
1
 0.59914  0.43486 -0.67224
 1.37001 -4.96720 -5.08104
 8.89915

 0.68033 -0.72560 -0.10314
 6.58011  2.42032  2.03280
 7.03841
1
2
 0.31968  0.82015 -0.47448
 0.37001 -8.76004 -5.38004
 8.01551

 0.24587 -0.88474  0.39594
 8.94060  7.42032 -0.33687
 9.03937
0

Problem T. Comparison of topologies

Author:Baranov A.A.   Time limit:1 sec
Input file:input.txt   Memory limit:256 Mb
Output file:output.txt  

Statement

Consider a set of rings on the plane. Each of these rings can be described by coordinates of its center (x, y), internal and external radius: q, r. It is known that any two circles bounding different rings do not cross each other.

Let us define a continuous mapping on this set that includes the next operations:

It is assumed that during these operations the bounding circles shouldn't intersect. Also, any ring shouldn't become singular (circle or point) during resizing. In other words, this mapping must keep the basic topological properties of the initial set.

Your program must, given two sets of the rings M1 and M2, determine whether there exist a continuous mapping to obtain M2 from M1 or not. It is assumed that order of rings in these sets may be different.

Input file format

Input file contains integer n — number of rings in the each set, followed by 4 × n floating point numbers xi, yi, qi, ri — parameters of the rings of M1, and then followed by another 4 × n numbers — similar parameters of the rings of M2,

Output file format

Output file must contain a single integer 1 — if M2 can be obtained by continuous mapping from M1 or 0 — otherwise.

Constraints

All input values have no more than 3 digits after the decimal point.

 − 105 < xi, yi < 105, 0 < qi < ri < 105, 1 ≤ n ≤ 2000

Sample tests

No. Input file (input.txt) Output file (output.txt)
1
 3
 0.000  0.000  1.000  2.000
 0.000  0.000  0.500  1.500
 5.000 -7.000  1.000  2.000
 0.000  0.000  1.000  6.000
-5.000  9.000  0.500  2.000
 0.000  0.000  0.500  1.500
1
2
 3
 0.000 -2.500  4.790  6.800
 0.000 -2.180  3.260  4.000
 9.810  2.630  1.000  1.500
 0.000 -8.500  2.000  6.800
-0.940 -4.000  0.500  1.500
-3.970 -8.970  1.000  1.500
0

1.361s 0.020s 59