Темы --> Информатика --> Алгоритмы
    Задачи на моделирование(78 задач)
    Арифметические алгоритмы(240 задач)
    Алгоритмы поиска(155 задач)
    Алгоритмы сортировки(194 задач)
    Динамическое программирование(355 задач)
    Алгоритмы на графах(319 задач)
    Перебор(154 задач)
    Игры и выигрышные стратегии(33 задач)
    Вычислительная геометрия(216 задач)
    Эвристические методы(30 задач)
    Алгоритмы на строках(45 задач)
    Пересечение множеств(10 задач)
    Жадный алгоритм(71 задач)
    Теория расписаний(5 задач)
    Обработка текста(31 задач)
    Дата и время(14 задач)
---> 1657 задач <---
Источники
    Личные олимпиады(938 задач)
    Командные олимпиады(684 задач)
Страница: << 297 298 299 300 301 302 303 >> Отображать по:
#112550
Интервалы
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
256 megabytes

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

Поиск решения можно проводить с помощью двухмерной модели. В этой модели ось Ох расположена на уровне пола, источник света считается точкой с целочисленными координатами ( b x , b y ) . Трубы представляют собой окружности. Центр i -й окружности имеет целочисленные координаты ( с x , c y ) , радиус r i также целый. Так как трубы сделаны из твердого материала, окружности не пересекаются. Трубы не отражают и не пропускают свет. Вы должны написать программу, которая найдет непересекающиеся интервалы на оси Ох , которые уже защищены от света благодаря имеющимся трубам.

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

Входной файл состоит из набора сразу нескольких тестов. Общее число строк в файле не превосходит 20000 . В первой строке каждого теста содержится положительное целое число N ≤ 10000 — обозначающее количество труб. Во второй строке расположены два целых числа b x и b y , разделенных пробелом. Каждая из следующих N строк содержит 3 целых числа через пробел с x , c y и r i , причем c y + r i < b y . Последний тест содержит единственную строку, содержащую N = 0 .

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

Для каждого теста выведите набор искомых интервалов по одному в строке. Интервал описывается двумя вещественными координатами. Ответ будет считаться правильным, если его относительная и абсолютная погрешности не будут превосходить \(10^{-6}\). Интервалы должны быть отсортированы в порядке возрастания координаты x . В конце каждого набора интервалов выводите пустую строчку.

Примечание

Картинки иллюстрируют тест из условия.

Примеры
Входные данные
1
300 300
300 150 90
6
300 450
70 50 30
120 20 20
270 40 10
250 85 20
220 30 30
380 100 100
0
Выходные данные
75.00 525.00

0.72 78.86
88.50 133.94
181.04 549.93
#112551
Призы
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes

Андрей Сергеевич работает воспитателем в детском саду. Недавно он придумал новую веселую игру, для участия в которой все дети разбились на n команд. В качестве призов для участников игры Андрей Сергеевич подготовил d конфет.

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

Теперь перед Андреем Сергеевичем стоит непростая задача: надо распределить конфеты. При этом должны выполняться следующие условия:

  • Все участники одной команды должны получить поровну конфет: пусть участники команды, занявшей i -е место получат по a i конфет;
  • Каждый ребенок должен получить хотя бы одну конфету: a i > 0 ;
  • Участники команды, занявшей более высокое место, должны получить больше конфет: если i < j , то a i > a j
  • Все конфеты должны быть распределены: a 1 x 1 + a 2 x 2 + ... a nx n = d
Помогите Андрею Сергеевичу раздать детям конфеты, или сообщите,что это невозможно.

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

Первая строка содержит два целых числа n и d ( 1 ≤ n ≤ 100 , 1 ≤ d ≤ 10 6 ). Вторая строка содержит n целых чисел x 1 , ..., x n ( 1 ≤ x i ≤ 100 для всех i от 1 до n ).

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

Если разделить конфеты возможно, то в первой строке выведите YES , а во второй выведите n целых чисел: a 1 , a 2 , ..., a n . Если разделить конфеты указанным способом нельзя, выведите NO .

Примеры
Входные данные
2 100
2 1
Выходные данные
YES
49 2
Входные данные
2 6
2 1
Выходные данные
NO
#112553
Строки Фибоначчи
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
256 megabytes

Алла очень любит палиндромы. Все потому, что её имя является палиндромом. Напомним, что строку называют палиндромом тогда, когда она одинаково читается как слева направо, так и справа налево.

Однажды в школе учитель рассказал Алле про так называемые строки Фибоначчи. Строки Фибоначчи определяются следующим образом:

  • f 0 = a
  • f 1 = b
  • f n = f n −1 f n −2 для каждого n ≥ 2 — конкатенация двух предыдущих строк Фибоначчи
Таким образом, первые пять строк Фибоначчи: « a » , « b » , « ba » , « bab » , « babba » .

Аллу сразу заинтересовал вопрос — какой максимально длинный палиндром встречается в k -й строке Фибоначчи. Помогите Алле решить эту задачу.

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

Первая строка входного файла содержит одно целое число k (0 ≤ k ≤ 80) — номер строки Фибоначчи.

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

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

Примеры
Входные данные
2
Выходные данные
1
Входные данные
4
Выходные данные
4
#112554
Подстрока
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes

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

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

В первой строке даны два целых числа n и k (1 ≤ n ≤ 100000, 1 ≤ k ≤ n ) , где n – количество символов в строке. Во второй строке n символов – данная строка, состоящая только из строчных латинских букв.

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

В выходной файл выведите два числа – длину искомой подстроки и номер её первого символа. Если решений несколько, выведите любое.

Примеры
Входные данные
3 1
abb
Выходные данные
2 1
Входные данные
5 2
ababa
Выходные данные
4 1
#112555
Бег по эскалатору
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes

Пусть N человек бегут вниз по эскалатору, причем i -ый пробегает одну ступеньку за t i секунд. По технике безопасности бега по эскалатору, на эскалаторе запрещены "обгоны", то есть если A в процессе бега догнал человека B , который бежит с более низкой скоростью, то далее, до конца эскалатора, человек A бежит со скоростью человека B . Однако ступени эскалатора таковы, что на них может помещаться несколько человек одновременно. Ваша задача написать программу, которая рассчитает, когда закончит свой бег по эскалатору каждый бегущий человек.

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

В первой строке записано число N ( 1 ≤ N ≤ 10 5 ). В следующих N строках перечислены пары чисел t i , w i ( 1 ≤ t i , w i ≤ 10 6 )- время пробега одной ступени и количество ступеней до конца эскалатора. Гарантируется что изначально всем людям осталось бежать различное количество ступеней.

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

В i -ой строке выведите время в секундах, через которое i -ый человек сойдет с эскалатора

Примеры
Входные данные
3
2 10
3 11
1 12
Выходные данные
20
33
33
Страница: << 297 298 299 300 301 302 303 >> Отображать по:
Выбрано
:
Отменить
|
Добавить в контест