Темы --> Информатика
    Язык программирования(952 задач)
    Алгоритмы(1657 задач)
    Структуры данных(279 задач)
    Интерактивные задачи(17 задач)
    Другое(54 задач)
---> 2656 задач <---
Источники
    Личные олимпиады(938 задач)
    Командные олимпиады(684 задач)
Страница: << 338 339 340 341 342 343 344 >> Отображать по:
#3397
Парк аттракционов
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
256 megabytes

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

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

Время перемещения участников между автоматами, а также между автобусом и павильоном считается равным нулю. Каждый из участников в любой момент времени может как играть на автомате, так и ждать своей очереди, например, гуляя по парку. Для каждого из \(M\) (\(M \leq N\)) автоматов известно время игры на нём \(t_i\) (\(1 \leq i \leq M\)). Прервать начатую игру на автомате невозможно. Автобус привозит всех участников олимпиады в парк одновременно в нулевой момент времени.

Требуется написать программу, которая по заданным числам \(N\), \(M\) и \(t_i\) определяет оптимальное расписание игры на автоматах для каждого из участников.

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

В первой строке входного файла содержатся два числа: \(N\) и \(M\) (\(1 \leq M \leq N \leq 100\)). Во второй строке заданы \(M\) целых чисел \(t_i\) (\(1 \leq t_i \leq 100\)), каждое из которых задаёт время игры на \(i\)-м автомате (\(1 \leq i \leq M\)). Числа в строке разделяются одиночными пробелами.

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

В первой строке необходимо вывести одно число — минимально возможное время отправления автобуса из парка аттракционов. Далее необходимо вывести \(N\) расписаний игр на автоматах, по одному для каждого из участников. Каждое расписание описывается в (\(M + 1\)) строках, первая из которых — пустая, а далее следуют \(M\) строк, описывающих автоматы в порядке их посещения этим участником. Посещение автомата описывается двумя целыми числами: номером автомата \(j\) (\(1 \leq j \leq M\)) и временем начала игры участника на этом автомате.

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

Подзадачи и система оценки

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

Подзадача 1 (20 баллов)

\(M = 1\), \(1 \leq N \leq 100\), \(t_1\) лежит в пределах от 1 до 100.

Подзадача 2 (20 баллов)

Все \(t_i\) равны 1, \(N = M\).

Подзадача 3 (20 баллов)

Все \(t_i\) равны 1, \(N > M\).

Подзадача 4 (20 баллов)

Числа \(t_i\) лежат в пределах от 1 до 100, \(N = M\).

Подзадача 5 (20 баллов)

Числа \(t_i\) лежат в пределах от 1 до 100, \(N > M\).

Примеры
Входные данные
2 1
2
Выходные данные
4

1 0

1 2
Входные данные
3 2
2 1
Выходные данные
6

1 0
2 2

1 2
2 4

2 0
1 4
#3398
Велогонка
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
256 megabytes

Велосипедисты, участвующие в шоссейной гонке, в некоторый момент времени, который называется начальным, оказались в точках, удалённых от места старта на \(x_1\), \(x_2\), ..., \(x_n\) метров (\(n\) – общее количество велосипедистов). Каждый велосипедист двигается со своей постоянной скоростью \(v_1\), \(v_2\), ..., \(v_n\) метров в секунду. Все велосипедисты двигаются в одну и ту же сторону.

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

Требуется написать программу, которая по заданному количеству велосипедистов \(n\), заданным начальным положениям велосипедистов \(x_1\), \(x_2\), ..., \(x_n\) и их скоростям \(v_1\), \(v_2\), ..., \(v_n\), вычислит момент времени \(t\), в который расстояние \(l\) между лидирующим и замыкающим велосипедистом будет минимальным.

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

Первая строка входного файла содержит целое число \(n\) – количество велосипедистов.

В последующих n строках указаны по два целых числа: \(x_i\) – расстояние от старта до \(i\)-го велосипедиста в начальный момент времени (\(0 \leq x_i \leq 10^7\)) и \(v_i\) – его скорость (\(0 \leq v_i \leq 10^7\)).

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

В выходной файл необходимо вывести два вещественных числа: \(t\) – время в секундах, прошедшее от начального момента времени до момента, когда расстояние в метрах между лидером и замыкающим будет минимальным, \(l\) – искомое расстояние.

Числа t и l должны иметь абсолютную или относительную погрешность не более \(10^{–6}\), что означает следующее. Пусть выведенное число равно \(x\), а в правильном ответе оно равно \(y\). Ответ будет считаться правильным, если значение выражения \(|x – y| / max(1, |y|)\) не превышает \(10^{–6}\).

Подзадачи и система оценки

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

Подзадача 1 (20 баллов)

\(2 \leq n \leq 50\), \(0 \leq  x_i \leq 1000\), \(0 \leq v_i \leq 1000\). Гарантируется, что существует ответ, в котором \(t\) – целое число, не превышающее 1000.

Подзадача 2 (20 баллов)

\(2 \leq n \leq 200\).

Подзадача 3 (30 баллов)

\(2 \leq n \leq 2000\)

Подзадача 4 (30 баллов)

\(2 \leq n \leq 10^5\)

Примеры
Входные данные
3
0 40
30 10
40 30
Выходные данные
1 30
Входные данные
5
90 100
100 70
100 70
110 60
120 35
Выходные данные
0.5 5.000000000000
#3400
Распил бревен
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
256 megabytes

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

Для каждой заготовки измеряется несколько сечений. Каждое из них задано в виде ломаной, представленной координатами ее вершин (\(x_0, y_0\)), (\(x_1, y_1\)), ..., (\(x_N, y_N\)) в порядке их следования. Координаты вершин ломанной удовлетворяют следующим условиям:

\(x_0 < x_1 < x_2 < \dots < x_N\);

\(x_i = 0\) для некоторого \(0 < i < N\);

\(y_0 = y_N = 0\);

\(y_0 = y_N = 0\);

для всех \(i\) от 1 до (\(N – 1\)) выполнено условие \(y_i > 0\).

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

основание треугольника лежит на оси абсцисс;

основание симметрично относительно начала координат;

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

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

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

Первая строка входного файла содержит целое число \(K\) – количество измеренных сечений.

Далее следуют описания каждого из \(K\) сечений. В первой строке описания сечения содержится число \(N_K\) – количество звеньев ломаной. За ней следуют (\(N_K + 1\)) строк, каждая из которых содержит пару целых чисел \(x_i\) и \(y_i\) – координаты вершин ломаной сечения в порядке их следования.

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

Выходной файл должен содержать одно вещественное число – наибольшую возможную площадь треугольника. Эта площадь должна иметь абсолютную или относительную погрешность не более \(10^{–6}\), что означает следующее. Пусть выведенное число равно \(x\), а в правильном ответе оно равно \(y\). Ответ будет считаться правильным, если значение выражения \(|x – y| / max(1, |y|)\) не превышает \(10^{–6}\).

Подзадачи и система оценки

Данная задача содержит пять подзадач.

Подзадача 1 (20 баллов)

\(K = 1\), \(N_1 \leq 15\), координаты вершин по модулю не превышают 20.

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

Подзадача 2 (10 баллов)

\(1 \leq K \leq 20\), сумма \(N_i \leq 2000\), координаты вершин по модулю не превышают \(10^4\). Гарантируется, что полученный в качестве ответа треугольник является прямоугольным.

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

Подзадача 3 (20 баллов)

\(1 \leq K \leq 20\), сумма \(N_i \leq 2000\), координаты вершин по модулю не превышают \(10^4\).

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

Подзадача 4 (10 баллов)

\(1 \leq K \leq 1000\), сумма \(N_i \leq 10^5\), координаты вершин по модулю не превышают \(10^9\). Гарантируется, что полученный в качестве ответа треугольник является прямоугольным.

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

Подзадача 5 (40 баллов)

\(1 \leq K \leq 1000\), сумма \(N_i \leq 10^5\), координаты вершин по модулю не превышают \(10^9\).

Каждый тест для данной подзадачи оценивается отдельно.

Примеры
Входные данные
2
5
-6 0
-3 5
-2 4
0 6
2 3
5 0
5
-6 0
-2 3
-1 6
0 6
1 6
7 0
Выходные данные
25.0
#3402
Шахматные баталии
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes

Недавно Петя начал играть в шахматы.

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

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

Фигуры ходят следующим образом:

король - на любую соседнюю по вертикали, горизотнали или диагонали клетку;

ферзь - на любое расстояние по вертикали, горизонтали или диагонали;

ладья - на любое расстояние по вертикали или горизонтали;

слон - на любое расстояние по диагонали;

конь - в форме буквы "Г": на 1 клетку по горизонтали и на 2 по вертикали, или наоборот, на 1 клетку по вертикали и 2 по горизонтали.

Вам даны позиции одной белой и одной черной фигуры.

Определите, бьют ли фигуры друг друга, и, если бьют, выведите какая из них бьет какую.

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

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

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

B - слон, N - конь, R - ладья, Q - ферзь, K - король.

Второй символ задает горизонталь (от \(a\) до \(h\)). Третий символ задает вертикаль (от 1 до 8).

Гарантируется, что фигуры стоят на различных клетках шахматной доски.

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

В выходной файл выведите одно слово - ответ на задачу.

В случае, если ни одна фигура не бьет другую, выведите "NONE".

В случае, если обе фигуры бьют друг друга, выведите "BOTH".

В случае, если белая фигура бьет черную, а черная не бьет белую, выведите "WHITE".

В случае, если черная фигура бьет белую, а белая не бьет черную, выведите "BLACK".

Примеры
Входные данные
Ka1
Rg1
Выходные данные
BLACK
Входные данные
Qf3
Qh5
Выходные данные
BOTH
#3403
Сумма цифр
  
Темы: [Цикл for]
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes

Задано натуральное число \(A\). Необходимо представить его в виде суммы двух неотрицательных целых чисел \(B\) и \(C\) так, чтобы сумма цифр десятичных представлений чисел \(B\) и \(C\) была как можно больше.

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

Входной файл содержит целое число \(A\) (\(1 \le A \le 10^{18}\)).

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

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

Примеры
Входные данные
4
Выходные данные
4
2 2
Входные данные
28
Выходные данные
19
9 19
Страница: << 338 339 340 341 342 343 344 >> Отображать по:
Выбрано
:
Отменить
|
Добавить в контест