Темы --> Информатика
    Язык программирования(952 задач)
    Алгоритмы(1657 задач)
    Структуры данных(279 задач)
    Интерактивные задачи(17 задач)
    Другое(54 задач)
---> 199 задач <---
Источники --> Личные олимпиады --> Всероссийская олимпиада школьников
    Муниципальный этап(80 задач)
    Окружная олимпиада(18 задач)
    Региональный этап(109 задач)
    Заключительный этап(97 задач)
Страница: << 1 2 3 4 5 6 7 >> Отображать по:
#19
Треугольная реформа
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

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

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

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

Формат входных данных

В первой строке входных данных задается число N (3 ≤ N ≤ 20) — количество вершин многоугольника, образующего границу Полигонии. В следующих N строках находятся по 2 целых числа, по абсолютной величине не превосходящих 10 000 — координаты вершин в порядке обхода многоугольника против часовой стрелки. Гарантируется, что никакие три последовательные вершины многоугольника не лежат на одной прямой, и он не имеет самопересечений и самокасаний. Также гарантируется, что никакие две диагонали, содержащиеся внутри многоугольника, не лежат на одной прямой.

Формат выходных данных

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

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

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

Если искомых разбиений несколько, выведите любое из них.

Примеры

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

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

Рисунок к тесту

4
0 0
1 0
1 1
0 1

2
1
1 1 0 0

 1

10
-6 0
0 2
6 0
3 3
6 4
2 4
0 6
-2 4
-6 4
-3 3

4
3
2 4 -2 4
0 2 3 3
-3 3 0 2

 2
#20
Уроки физкультуры
  

Сегодня в 5-А классе праздник — урок физкультуры. Традиционно ребята в это время после небольшой разминки играют в футбол. Коля очень любит футбол, но сегодня, проходя мимо учительской, он случайно услышал, что несколько самых сильных школьников из 5-А во время урока физкультуры должны помочь разгружать новые парты. Что же делать? Ведь Коля предпочитает поиграть в футбол!

В голове Коли моментально созрел план. Коля знает, что в 5-А классе N школьников. Он хочет воспользоваться тем, что учитель физкультуры Иван Петрович на уроках вместо обычной расстановки школьников в шеренгу по росту практикует расстановку «по силе». Для этого Иван Петрович сначала расставляет N школьников по росту, а затем (N – 1) раз проходит вдоль шеренги слева направо, каждый раз начиная с самого левого (первого) школьника и заканчивая предпоследним школьником справа. Проходя мимо школьника, который стоит на i-м месте (1 ≤ i ≤ N – 1), Иван Петрович просит его помериться силой с соседом справа, который стоит на (i + 1)-м месте. Если школьник, стоящий левее, оказывается сильнее своего соседа справа, то они меняются местами. Если же силы школьников оказываются равны, либо слева стоит более слабый школьник, то школьники остаются на своих местах. После этого Иван Петрович просит помериться силой школьников, стоящих на местах (i + 1) и (i + 2), и т. д., заканчивая каждый проход школьниками, которые стоят на местах (N – 1) и N. При любом сравнении «по силе» все школьники, включая Колю, показывают свою реальную силу, так как не хотят прослыть слабаками.

Для увеличения шансов поиграть в футбол, Коля хотел бы оказаться как можно левее в получившейся шеренге. Силу каждого из своих одноклассников он знает. По предыдущим занятиям Коля заметил, что если присесть «завязывать шнурки» при каком-либо из проходов учителя, то Иван Петрович во время такого прохода не будет просить Колю мериться силой ни с соседом слева, ни с соседом справа, и, тем более, не будет просить мериться силой соседей Коли, так как они не стоят рядом. Однако, чтобы сохранить силы для игры в футбол, Коля не может присесть более k раз.

Требуется написать программу, которая определит, как нужно действовать Коле, чтобы после проведения расстановки «по силе» оказаться в шеренге как можно левее.

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

В первой строке входных данных задаются три целых числа: N — число школьников в классе, p — место Коли в шеренге по росту, и k — количество приседаний, которое Коля может сделать, не потеряв при этом способность играть в футбол (2 ≤ N ≤ 100 000, 1 ≤ p ≤ N, 1 ≤ k ≤ N – 1).

Во второй строке задаются целые числа a1, a2, ..., aN (1 ≤ ai ≤ 109). Число ai показывает силу школьника, который стоит на i-м месте по росту. Школьник, который стоит на i-м месте в расстановке по росту, сильнее школьника, который стоит j-м месте в расстановке по росту, если ai > aj.

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

В первой строке выведите самую левую позицию в шеренге, в которой может оказаться Коля после построения школьников «по силе». Во второй строке выведите любую из возможных стратегий Коли, приводящую к этому результату. Стратегия выводится в виде строки из (N – 1) символов, j-й символ этой строки должен быть равен символу «+», если на j-м проходе Коле необходимо присесть, и символу «-» — в противном случае.

Примечание

Решения, корректно работающие при N ≤ 3000, будут оцениваться, исходя из 70 баллов.

Примеры
Входные данные
10 5 6
10 1 8 3 6 5 4 7 2 9
Выходные данные
5
---++++++
#21
Электрички на перегонах не меняют
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
256 megabytes

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

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

Требуется написать программу, которая назначит каждой станции тарифный номер.

1

4 станции, 3 перегона: 1-4, 2-4, 3-4

Маршруты: 1-4-2, 2-4-3, 3-4-1.


Ответ: решения нет

2

5 станций, 4 перегона: 1-5, 2-5, 3-5, 4-5

Маршруты: 1-5-2, 2-5-3, 3-5-4, 4-5-1.


Ответ: решение есть; например, следующее: номер станции: 1 2 3 4 5

тарифный номер: 1 4 1 5 3


Замечание: тарифные номера разных станций могут совпадать.
Входные данные

В первой строке входных данных содержатся два целых числа: N — количество станций (2 ≤ N ≤ 100 000), и M — количество перегонов между ними (1 ≤ M ≤ N – 1). В последующих M строках записаны пары целых чисел a, b (a ≠ b, 1 ≤ a ≤ N, 1 ≤ b ≤ N), означающие наличие перегона между станциями a и b. За ними в отдельной строке записано единственное целое положительное число K — количество маршрутов электричек. В последующих K строках идут описания маршрутов электричек, по одному на строке. Каждое описание представляет собой последовательность целых чисел — номеров всех станций маршрута в порядке одного из двух возможных направлений следования электрички. Описание маршрута заканчивается числом 0.

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

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

В первую строку  выведите «NO», если искомого назначения тарифных номеров не существует. В противном случае в первую строку выведите «YES», а в следующей строке — N целых положительных чисел, где i-е число — тарифный номер i-й станции. Тарифный номер каждой станции должен находиться в диапазоне от 1 до N.

Если существует несколько решений, необходимо вывести любое из них.

Система оценивания

Тесты к этой задаче состоят из четырёх групп. Баллы за каждую группу ставятся только при прохождении всех тестов группы и всех тестов предыдущих групп.

  • Группа 1 (20 баллов): N, K <= 20
  • Группа 2 (30 баллов): N, K <= 2000
  • Группа 3 (50 баллов): без дополнительных ограничений
Примеры
Входные данные
6 5
1 2
5 2 
5 6
4 5
3 2
6
1 2 0
5 6 0
3 2 1 0
5 2 3 0
4 5 2 0
6 5 4 0
Выходные данные
YES
2 3 4 1 2 3
#22
Ударим мостом по бездорожью
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
256 megabytes

Профиль Уральских гор задается ломаной (x1, y1), (x2, y2), …, (xN, yN), для координат вершин которой верны неравенства x1 < x2 < … < xN. Начальные и конечные точки профиля расположены на уровне моря (y1 = yN = 0).

На горном профиле заданы две различные точки A и B, между которыми требуется проложить дорогу. Эта дорога будет проходить по склонам гор и проектируемому горизонтальному мосту, длина которого не должна превышать L. Оба конца моста находятся на горном профиле. Дорога заходит на мост с одного конца и выходит с другого. Мост не может содержать точек, расположенных строго под ломаной (строительство тоннелей не предполагается).

Возможные примеры расположения моста

1

Невозможное расположение моста

2

Достоверно известно, что строительство такого моста в данной местности возможно, причем позволит сократить длину дороги из точки A в точку B. Требуется написать программу, которая определит такое расположение горизонтального моста, что длина дороги от точки A до точки B будет наименьшей.

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

Первая строка входных данных содержит два целых числа N и L — количество вершин ломаной (2 ≤ N ≤ 100 000) и максимальную длину моста (1 ≤ L ≤ 106) соответственно. Вторая строка  содержит координаты точки A, третья строка — координаты точки B. Точки A и B различны.

Последующие N строк содержат координаты вершин ломаной (x1, y1), (x2, y2), …, (xN, yN). Координаты вершин ломаной, а также точек A и B, задаются парой целых чисел, не превосходящих по абсолютному значению 106. Гарантируется, что x1 < x2 < … < xN и y1 = yN = 0, а также, что точки A и B принадлежат ломаной.

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

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

В примере в первой строке указана длина дороги от точки A до точки B с учётом построенного моста. Её не нужно выводить.

Примечание

Решения, корректно работающие при N ≤ 2000, будут оцениваться, исходя из 80 баллов.

Примеры
Входные данные
5 3
1 1
3 1
-1 0
0 2
2 0
4 2
5 0
Выходные данные
2.000000000
1.00000 1.00000
3.00000 1.00000
#23
То березка, то рябина…
  

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

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

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

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

В первой строке вводятся два целых числа: K — количество различных видов деревьев (1 ≤ K ≤ 100 000), и P — требуемое количество подряд идущих деревьев разных видов (2 ≤ P ≤ K). Последующие K строк  входных данных содержат целые числа ai, задающие количество закупленных саженцев деревьев i-го вида  (1 ≤ ai ≤ 109), по одному числу в каждой строке.

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

Выведите единственное число — максимальное количество деревьев, посадка которых в ряд в некотором порядке достигает эстетического совершенства.

Примеры
Входные данные
3 3
1
200 
1
Выходные данные
4
Страница: << 1 2 3 4 5 6 7 >> Отображать по:
Выбрано
:
Отменить
|
Добавить в контест