Темы --> Информатика
    Язык программирования(952 задач)
    Алгоритмы(1657 задач)
    Структуры данных(279 задач)
    Интерактивные задачи(17 задач)
    Другое(54 задач)
---> 2656 задач <---
Источники
    Личные олимпиады(938 задач)
    Командные олимпиады(684 задач)
Страница: << 237 238 239 240 241 242 243 >> Отображать по:
#1783
Игра с графом
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes

Петя и Вася играют в очередную интересную игру. У них есть лист бумаги, на котором изображены \(n\) кружочков, помеченных числами от 1 до \(n\). Участники по очереди рисуют стрелочки, соединяющие кружочки. При этом стрелочку из кружочка a в кружочек \(b\) разрешено проводить, если выполнены два условия:

1. еще нет стрелочки из \(a\) в \(b\);

2. нельзя дойти по стрелочкам из \(b\) в \(a\).

Например, в позиции на рис. 1 можно поставить одну из трех стрелочек (рис. 2).

Проигрывает тот, кто не может сделать ход.

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

Входные данные

Входной файл содержит одно число \(n\) (1 ≤ \(n\) ≤ 100).

Выходные данные

Выведите в выходной файл число возможных позиций без ведущих нулей.

Пояснение к примеру

Примеры
Входные данные
3
Выходные данные
25
#1784
Про любовь...
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes

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

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

Входные данные

Входной файл содержит 12 чисел: \(x_1\), \(y_1\), \(x_2\), \(y_2\), \(x_3\), \(y_3\), \(x_4\), \(y_4\), \(v_{1x}\), \(v_{1y}\), \(v_{2x}\), \(v_{2y}\). Координаты вершин первого отрезка: (\(x_1\), \(y_1\)) и (\(x_2\), \(y_2\)), координаты вершин второго отрезка: (\(x_3\), \(y_3\)) и (\(x_4\), \(y_4\)), скорость первого отрезка (\(v_{1x}\), \(v_{1y}\)), скорость второго отрезка (\(v_{2x}\), \(v_{2y}\)). Все числа целые и не превосходят по модулю \(10^4\). В начальный момент времени веточки не соприкасаются. Гарантируется, что веточки имеют ненулевую длину.

Выходные данные

Выведите в выходной файл время до ближайшего момента, когда веточки соприкоснутся, с ошибкой не более \(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
#1785
Спички детям не игрушка!
  
Темы: [Хеш]
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes

Вася любит решать головоломки со спичками. Чаще всего они формулируется следующим образом: дано изображение \(A\), составленное из спичек; переложите в нем минимальное количество спичек так, чтобы получилось изображение \(B\).

Например, из номера текущего командного чемпионата школьников Санкт-Петербурга по программированию, можно получить ромб с диагональю, переложив всего три спички.

Головоломки, которые решает Вася, всегда имеют решение. Это значит, что набор спичек, используемый в изображении \(A\), совпадает с набором спичек, используемым в изображении \(B\). Кроме того, в одном изображении никогда не встречаются две спички, у которых есть общий участок ненулевой длины (то есть спички могут пересекаться, но не могут накладываться друг на друга).

Вася устал решать головоломки вручную, и теперь он просит вас написать, программу, которая будет решать головоломки за него. Программа будет получать описания изображений \(A\) и \(B\) и должна найти минимальное количество спичек, которые надо переложить в изображении \(A\), чтобы полученная картинка получалась из \(B\) параллельным переносом.

Входные данные

В первой строке входного файла содержится целое число \(n\) – количество спичек в каждом из изображений (1 ≤ \(n\) ≤ 1000).

В следующих n строках записаны координаты концов спичек на изображении \(A\). Спичка номер \(i\) описывается целыми числами \(x_{1i}\), \(y_{1i}\), \(x_{2i}\), \(y_{2i}\) – координатами ее концов. Следующие \(n\) строк содержат описание изображения \(B\) в таком же формате. Набор длин этих спичек совпадает с набором длин спичек с изображения \(A\).

Все координаты по абсолютной величине не превосходят \(10^4\). Все спички имеют ненулевую длину, то есть \(x_{1i}\) ≠ \(x_{2i}\) или \(y_{1i}\) ≠ \(y_{2i}\).

Выходные данные

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

Примеры
Входные данные
5
0 0 1 2
1 0 0 2
2 0 2 2
4 0 3 2
4 0 5 2
9 -1 10 1
10 1 9 3
8 1 10 1
8 1 9 -1
8 1 9 3
Выходные данные
3
#1786
Лабиринт
  

Открыв глаза, Принц Персии обнаружил, что находится на верхнем уровне подземного лабиринта Джаффара. Лабиринт состоит из \(h\) уровней, расположенных строго друг под другом. Каждый уровень представляет собой прямоугольную площадку, разбитую на \(m\) × \(n\) участков. На некоторых участках стоят колонны, поддерживающие потолок, на такие участки Принц заходить не может.

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

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

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

Входные данные

В первой строке входного файла содержатся натуральные числа \(h\), \(m\) и \(n\) – высота и горизонтальные размеры лабиринта (2 ≤ \(h\), \(m\), \(n\) ≤ 50). Далее во входном файле приведены \(h\) блоков, описывающих уровни лабиринта в порядке от верхнего к нижнему.

Каждый блок содержит \(m\) строк, по \(n\) символов в каждой: «.» (точка) обозначает свободный участок, «o» (строчная латинская буква «o») обозначает участок с колонной, «1» обозначает свободный участок, в котором оказался Принц в начале своего путешествия, «2» обозначает свободный участок, на котором томится Принцесса.

Символы «1» и «2» встречаются во входном файле ровно по одному разу: символ «1» – в описании самого верхнего уровня, а символ «2» – в описании самого нижнего.

Соседние блоки разделены одной пустой строкой.

Выходные данные

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

Примеры
Входные данные
3 3 3
1..
oo.
...

ooo
..o
.oo

ooo
o..
o.2
Выходные данные
60
#1787
Число
  

По заданным числам \(a\), \(b\), \(c\) и \(d\), найдите наименьшее натуральное число \(n\), большее \(ac\), которое нельзя представить в виде произведения двух натуральных чисел \(u\) и \(v\), таких что \(a\) ≤ \(u\) ≤ \(b\) и \(c\) ≤ \(v\) ≤ \(d\).

Входные данные

Входной файл содержит одну строку, состоящую из натуральных чисел \(a\), \(b\), \(c\), \(d\) (1 ≤ \(a\) ≤ \(b\) ≤ \(10^6\), 1 ≤ \(c\) ≤ \(d\) ≤ \(10^6\)).

Выходные данные

Выведите в выходной файл искомое число \(n\).

Примеры
Входные данные
1 2 1 2
Выходные данные
3
Входные данные
1 2 3 5
Выходные данные
7
Страница: << 237 238 239 240 241 242 243 >> Отображать по:
Выбрано
:
Отменить
|
Добавить в контест