Темы --> Информатика --> Алгоритмы
    Задачи на моделирование(78 задач)
    Арифметические алгоритмы(240 задач)
    Алгоритмы поиска(155 задач)
    Алгоритмы сортировки(194 задач)
    Динамическое программирование(355 задач)
    Алгоритмы на графах(319 задач)
    Перебор(154 задач)
    Игры и выигрышные стратегии(33 задач)
    Вычислительная геометрия(216 задач)
    Эвристические методы(30 задач)
    Алгоритмы на строках(45 задач)
    Пересечение множеств(10 задач)
    Жадный алгоритм(71 задач)
    Теория расписаний(5 задач)
    Обработка текста(31 задач)
    Дата и время(14 задач)
---> 35 задач <---
Источники --> Личные олимпиады --> Московская олимпиада школьников --> 10-11 классы
    2004(7 задач)
    2005(7 задач)
    2006(8 задач)
    2007(8 задач)
    2008(8 задач)
    2011(5 задач)
    2012(14 задач)
    2013(14 задач)
    2014(14 задач)
    2015(14 задач)
    2016(15 задач)
Страница: << 1 2 3 4 5 6 7 >> Отображать по:
#994
Сплоченная команда
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes
Дано N чисел. Требуется выбрать подмножество с максимальной суммой так, чтобы максимальный элемент подмножества не превосходил суммы двух минимальных.

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

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

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

В первой строке входного файла записано целое число \(N\) (\(1 \le N \le 30\,000\)). В последующих \(N\) строках записано по одному целому числу \(P_i\) (\(0 \le P_i \le 60\,000\)), представляющему собой ПП соответствующего игрока.

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

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

Примеры
Входные данные
4
1
5
3
3
Выходные данные
3 11
3
4
2
Входные данные
5 
100
20
20
20
20
Выходные данные
2 120
2
1
#995
Сократи векторы
  

На плоскости задано N векторов. Есть 3 правила:

1) вектора на непересекающихся прямых можно сложить

2)  вектора на одной прямой можно сложить (результат исходит из начала одного из векторов)

3) в любой точке можно породить два одинаковых по длине, но разнонаправленных вектора

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

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

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

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

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

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

3) В любой точке плоскости можно породить два противоположно направленных отрезка равной (в том числе и нулевой) длины:

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

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

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

В первой строке входного файла записано число N – количество заданных векторов (1 < N ≤ 1000). В каждой из следующих N строк через пробел записаны четыре числа, обозначающие координаты начала и конца каждого из векторов соответственно. Все координаты – целые числа, по модулю не превосходящие 1000.

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

В первой строке входного файла следует записать число M – количество векторов в полученной системе (1 ≤ M ≤ N). В каждой из следующих M строк через пробел должны находиться четыре числа, обозначающие координаты начала и конца каждого из векторов соответственно. Все координаты – вещественные числа, записанные с 6 цифрами после точки.

Примеры
Входные данные
3
1 1 1 3
3 3 3 1
5 1 7 1
Выходные данные
1
3.000000 3.000000 5.000000 3.000000
Входные данные
2
2 4 5 10
-2 -4 -5 -10
Выходные данные
1
2.000000 4.000000 2.000000 4.000000
#997
Квадрат
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes
Требуется в каждую клетку квадратной таблицы размером NxN поставить ноль или единицу так, чтобы в любом квадрате размера KxK было ровно S единиц.

Требуется в каждую клетку квадратной таблицы размером NxN поставить ноль или единицу так, чтобы в любом квадрате размера KxK было ровно S единиц.

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

Во входном файле записаны три числа — N, K, S (1N100, 1KN, 0SK2).

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

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

Примеры
Входные данные
3 2 1
Выходные данные
0 0 0
0 1 0
0 0 0
Входные данные
4 2 2
Выходные данные
1 0 0 1
0 1 1 0
1 0 0 1
0 1 1 0
#998
Поле чудес
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes
Барабан совершает несколько оборотов. Дана последовательность чисел, на которые указывает стрелка. Требуется определить сколько всего чисел на барабане (найти максимальную подпоследовательносьть, из повторов которой состоит последовательность).

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

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

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

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

Во входном файле записано сначала число N — количество чисел, которое назвал ведущий (2N30000). Затем записано N чисел, на которые указывала стрелка в процессе вращения барабана. Первое число всегда совпадает с последним (в конце стрелка указывает на тот же сектор, что и в начале). Числа, записанные в секторах барабана, — натуральные, не превышающие 32000.

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

Выведите минимальное число секторов, которое может быть на барабане.

Примеры
Входные данные
13
5 3 1 3 5 2 5 3 1 3 5 2 5
Выходные данные
6
Входные данные
4
1 1 1 1
Выходные данные
1
#999
Юный поджигатель
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes
Дан граф на клетчатом поле, вершины которого могут находится в целых клетках и соединяться по линиям сетки или по диагонали клеток (в случае пересечения двух клеток там также создается вершина). Необходимо найти вершину, расстояние от которой до самой дальней минимально.

На клеточном поле введена система координат так, что центр координат находится в точке пересечения линий сетки и оси направлены вдоль линий сетки.

На этом поле выложили связную фигуру, состоящую из спичек. Использовались спички двух типов:

  • Спички длины 1 выкладывались по сторонам клеток.
  • Спички длины выкладывались по диагоналям клеток.

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

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

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

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

Во входном файле записано сначала число N — количество спичек (1N40). Затем идет N пятерок чисел вида X1, Y1, X2, Y2, T, задающих координаты концов спички и время ее сгорания при условии, что она будет подожжена с одного конца (гарантируется, что каждая спичка имеет длину 1 или , все спички образуют связную фигуру, и положение никаких двух спичек не совпадает). Все координаты — целые числа, по модулю не превышающие 200, время сгорания — натуральное число, не превышающее 107.

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

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

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