Темы --> Информатика --> Алгоритмы
    Задачи на моделирование(78 задач)
    Арифметические алгоритмы(240 задач)
    Алгоритмы поиска(155 задач)
    Алгоритмы сортировки(194 задач)
    Динамическое программирование(355 задач)
    Алгоритмы на графах(319 задач)
    Перебор(154 задач)
    Игры и выигрышные стратегии(33 задач)
    Вычислительная геометрия(216 задач)
    Эвристические методы(30 задач)
    Алгоритмы на строках(45 задач)
    Пересечение множеств(10 задач)
    Жадный алгоритм(71 задач)
    Теория расписаний(5 задач)
    Обработка текста(31 задач)
    Дата и время(14 задач)
---> 1657 задач <---
Источники
    Личные олимпиады(938 задач)
    Командные олимпиады(684 задач)
Страница: << 172 173 174 175 176 177 178 >> Отображать по:
#1859
Волшебный лес
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
263 megabytes

Василиса Премудрая с Иваном-царевичем сбежали от морского царя. Царь немедленно выслал погоню. Уже совсем близко стук копыт, а верный конь Василисы устал нести двоих седоков... Единственное, что спасёт беглецов — чудо!

Сохраняя хладнокровие, Василиса решает в уме сложную задачу. Она хочет сотворить между собой и преследователями волшебный лес. Этот лес будет представлять собой \(n\) рядов деревьев, идущих строго с запада на восток. В каждом ряду будет также \(n\) деревьев, образующих вместе \(n\) рядов, идущих строго с севера на юг. Более того, суммарная высота деревьев в \(i\)-м ряду с запада на восток должна составлять ровно \(a_i\) метров, а суммарная высота деревьев в \(j\)-м ряду с севера на юг — ровно \(b_j\) метров. Наконец, высота каждого дерева должна выражаться целым числом метров. Сотвори такой лес — и преследователи будут без толку плутать по нему, пока волшебство не ослабнет и лес не исчезнет.

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

Помогите Василисе Премудрой и Ивану-царевичу — найдите такие высоты деревьев, что лес будет обладать описанными волшебными свойствами, и при этом максимальная из высот деревьев была бы как можно меньше.

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

В первой строке входного файла задано целое число \(n\) (\(2 \le n \le 1000\)). Во второй строке заданы \(n\) целых чисел \(a_1, a_2, \ldots, a_n\) через пробел — сумма высот деревьев в рядах, идущих с запада на восток (\(0 \le a_i \le 10^6\)). В третьей строке заданы \(n\) целых чисел \(b_1, b_2, \ldots, b_n\) через пробел — сумма высот деревьев в рядах, идущих с севера на юг (\(0 \le b_j \le 10^6\)).

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

Если сотворить волшебный лес с данными параметрами невозможно, выведите «NO» в первой строке выходного файла. Иначе в первой строке выведите «YES», а в следующих \(n\) строках по \(n\) целых неотрицательных чисел через пробел в каждой — высоты деревьев. Сумма чисел в \(i\)-й из последних \(n\) строк должна равняться \(a_i\), а сумма чисел в \(j\)-м столбце должна равняться \(b_j\). Максимальное число в ответе должно быть минимально возможным. Если правильных ответов несколько, можно выводить любой из них.

Примеры
Входные данные
2
1 3
2 2
Выходные данные
YES
1 0 
1 2
Входные данные
2
1 3
2 4
Выходные данные
NO
#1860
Котята с пирожками
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
263 megabytes

Однажды \(n\) котят решили покушать пирожков. Однако котят много, поэтому им непросто выбрать начинку, которая всех порадует. Известно, что группа из не более чем \(k\) котят всегда может прийти к консенсусу, а вот большая группа обязательно разобъётся на две, принципиально несогласные друг с другом. Котята — существа справедливые, поэтому размеры этих групп будут отличаться не более, чем на один.

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

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

В единственной строке входного файла записаны целые числа \(n\) и \(k\) — количество котят и критический размер группы, соответственно (\(1 \le n, k \le 10^{100}\)). Числа записаны без ведущих нулей.

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

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

Примеры
Входные данные
17 4
Выходные данные
5
#1877
Выпуклая оболочка
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
263 megabytes

На плоскости даны \(N\) точек. Вам требуется построить выпуклую оболочку данного множества точек. Если \(N\) нечетно, то оболочку нужно выводить в порядке обхода по часовой стрелке, иначе — против часовой стрелки.

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

Первая строка содержит количество точек \(N\), \(1\le N\le 20\,000\). Каждая из последующих \(N\) строк содержит два целых числа — координаты \(x_i\) и \(y_i\). Все числа по модулю не превосходят \(10^4\).

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

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

Примеры
Входные данные
4
0 0
3 4
3 1
6 0
Выходные данные
3
6 0
3 4
0 0
#1886
Сортировка
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
263 megabytes

Мария Ивановна, учитель средней школы 5 села Уборкино, заполняет классный журнал. Но она неожиданно столкнулась с проблемой: список имен, который у неё есть, не отсортирован. Помогите ей! Список необходимо отсортировать в алфавитном порядке по фамилиям. Люди с одинаковой фамилией должны идти в том же порядке, в котором они идут в исходном списке.

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

Первая строка входного файла содержит натуральное число \(N\) (\(1\leq N\leq 20\,000\)) — количество человек в классе. Далее идут \(N\) строк, содержащих по два слова, записанных через пробел: фамилия и имя ученика. В записи фамилии и имени встречаются только буквы латинского алфавита, причём первая буква всегда большая, а остальные — маленькие. Длина фамилии не менее 1 и не более 20. Длина имени не менее 1 и не более 20.

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

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

Примеры
Входные данные
4
Pupkin Vasya
Ivanov Petya
Iskandeev Semil
Ivanov Roma
Выходные данные
4
Iskandeev Semil
Ivanov Petya
Ivanov Roma
Pupkin Vasya
#1887
Подстрока
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
263 megabytes

Ваша задача — найти все вхождения данной строки в длинный текст.

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

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

Все символы с ASCII кодами 33126 (кроме «*») допустимы и могут встречаться как в строке, так и в тексте. Все пробелы и символы перевода строки во входном файле должны игнорироваться.

Длина строки не превосходит 10000, а длина текста не превосходит 200000 символов.

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

Выведите в выходной файл в возрастающем порядке все точки вхождения данной строки в данный текст. Точка вхождения — это количество символов от начала текста до первого символа вхождения, увеличенное на 1. Если вхождение начинается сразу после звездочки, то точка его вхождения равна 1.

Примеры
Входные данные
aa* bb
aaa
Выходные данные
3
4
Страница: << 172 173 174 175 176 177 178 >> Отображать по:
Выбрано
:
Отменить
|
Добавить в контест