Темы --> Информатика --> Алгоритмы
    Задачи на моделирование(78 задач)
    Арифметические алгоритмы(240 задач)
    Алгоритмы поиска(155 задач)
    Алгоритмы сортировки(194 задач)
    Динамическое программирование(355 задач)
    Алгоритмы на графах(319 задач)
    Перебор(154 задач)
    Игры и выигрышные стратегии(33 задач)
    Вычислительная геометрия(216 задач)
    Эвристические методы(30 задач)
    Алгоритмы на строках(45 задач)
    Пересечение множеств(10 задач)
    Жадный алгоритм(71 задач)
    Теория расписаний(5 задач)
    Обработка текста(31 задач)
    Дата и время(14 задач)
---> 1657 задач <---
Источники
    Личные олимпиады(938 задач)
    Командные олимпиады(684 задач)
Страница: << 305 306 307 308 309 310 311 >> Отображать по:
#112902
Transformation Sequence
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
256 megabytes

Для каждой пары чисел \(x\) и \(y\) из диапазона \(0,1,2,\ldots,N-1\) определим расстояние \(D(x,y)\) как \(min(|x-y|,N-|x-y|)\). Для перестановки \(T\) можно построить набор чисел \(D_i=D(i,T_i)\). Ваша задача состоит в обратном: по заданному набору чисел восстановить корректную перестановку, а среди таких требуется выбрать лексикографически минимальную.

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

В первой строке входных данных содержится число \(N\) - размер перестановки. В следующей строке содержатся числа \(D_0,D_1,\ldots,D_{N-1}\).

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

В случае, если такой перестановки не существует, выведите «No Answer». В противном случае выведите искомую оптимальную перестановку.

Система оценки

  • В 30% тестовых примеров выполнено \(N \le 50\)
  • В 60% тестовых примеров выполнено \(N \le 500\)
  • В 100% тестовых примеров выполнено \(N \le 10\,000\)
#112910
Cheese
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
512 megabytes

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

Рисунок соответствует первому тесту. Пунктирной линией показан разрез Степана.

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

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

Первая строка входного файла содержит одно целое число N — количество вершин в многоугольнике. Каждая из следующих N строк содержит два числа x i и y i — координаты i -й вершины. Следующая строка содержит одно число M — количество перчинок. Каждая из следующих M строк содержит два числа x i и y i — координаты i -й перчинки.

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

Все перчинки расположены в различных точках и внутри многоугольника (они не расположены на стороне или снаружи многоугольника).

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

Выведите одно число — удвоенную максимальную площадь (это число всегда целое). Если отрезать кусок без перца невозможно, выведите 0.

Примечание

Система оценки:

  1. 12 баллов. 4 ≤ N ≤ 300 , 1 ≤ M ≤ 300 .
  2. 39 баллов. 4 ≤ N ≤ 3000 , 1 ≤ M ≤ 3000 .
  3. 49 баллов. 4 ≤ N ≤ 300 000 , 1 ≤ M ≤ 300 000 .

Во всех подзадачах координаты от - 10 9 до 10 9 .

Примеры
Входные данные
5
0 1
3 0
4 2
2 3
0 3
3
2 1
3 1
3 2
Выходные данные
4
#112922
Алканы
  
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт

Алканы (также насыщенные углеводороды, парафины, алифатические соединения) — ациклические углеводороды линейного или разветвленного строения, содержащие только простые связи. Алканы являются насыщенными углеводородами и содержат максимально возможное число атомов водорода. Каждый атом углерода в молекулах алканов находится в состоянии sp3-гибридизации — все четыре гибридные орбитали атома С идентичны по форме и энергии, четыре связи направлены в вершины тетраэдра под углами . Cвязи C–C представляют собой σ-связи, отличающиеся низкой полярностью и поляризуемостью.

Ничего не поняв, вы обратились к однокласснику за помощью. Он сказал вам забыть всё, что было написано в учебнике, и объяснил, что алканы — углеводороды. То есть соединения, состоящие из атомов углерода и водорода, не содержащие связей водород–водород, причём каждый углерод соединен ровно с четырьмя другими атомами, а каждый водород соединен ровно с одним другим атомом. При этом алкан является связным соединением, а также молекула алкана не является цикличной (для каждых двух атомов существует единственный способ добраться из одного в другой по связям между атомами). Также он сказал, что связи между атомами всегда соединяют два различных атома.

Запомнив всё это, вы пошли к Александру Евгеньевичу, и он дал вам задание: для данного соединения определить, является ли оно алканом.

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

В первой строке содержатся два числа N и M (1 ≤ N ≤ 100 000, 0 ≤ M ≤ 100 000) — количество атомов и соединений между атомами соответственно.

Следующая строка состоит из N символов. Если i-й символ — «C», то i-й атом — атом углерода. Если i-й символ — «H», то i-й атом — атом водорода. Гарантируется, что каждой символ этой строки — либо «C», либо «H».

В следующих M строках содержатся описания соединений между атомами. В i-й из них содержатся номера двух атомов, связанных i-м соединением.

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

Выведите «YES», если соединение является алканом, и «NO», если не является.

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

Входные данные
8 7
HHHCCHHH
1 4
2 4
3 4
4 5
5 6
5 7
5 8
Выходные данные
YES
Входные данные
2 1
CH
1 2
Выходные данные
NO

Соединение в первом примере является молекулой этана. Ниже представлена его структурная формула.

#113073
Выбор заявки
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

Дана лекционная аудитория, в которой несколько профессоров хотят прочесть свои лекции. Для составления расписания профессора подали заявки, вида [\(s_i, f_i\)) – время начала и конца лекции. Лекция считается открытым полуинтервалом, то есть какая-то лекция может начаться в момент окончания другой, без перерыва. Составьте расписание занятий так, чтобы выполнить максимальное количество заявок.

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

В первой строке вводится натуральное число \(N\), не более 1000 – общее количество заявок. Затем вводится \(N\) строк с описаниями заявок - по два числа в каждом \(s_i\) и \(f_i\).

Гарантируется, что \(s_i < f_i\). Время начала и окончания лекции – натуральное число, не превышает 1440 (в минутах с начала суток :) )

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

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

Пояснения к примерам

Во втором примере можно выполнить вторую и третью заявки.

Примеры
Входные данные
1
5 10
Выходные данные
1
Входные данные
3
1 5
2 3
3 4
Выходные данные
2
#113074
Проблема сапожника
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

В некоей воинской части есть сапожник. Рабочий день сапожника длится \(N\) минут. Заведующий складом оценивает работу сапожника по количеству починенной обуви, независимо от того, насколько сложный ремонт требовался в каждом случае. Дано \(k\) сапог, нуждающихся в починке. Определите какое максимальное количество из них сапожник сможет починить за один рабочий день.

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

В первой строке вводятся число \(N\) (натуральное, не превышает 1000), и число \(k\) (натуральное, не превышает 500). Затем идет \(k\) чисел – количество минут, которые требуются чтобы починить \(i\)-й сапог (времена – натуральные числа, не превосходят 100).

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

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

Пояснение к примерам

В первом примере можно починить либо первый и второй, либо второй и третий сапоги.

Примеры
Входные данные
10 3
6 2 8
Выходные данные
2
Входные данные
3 2
10 20
Выходные данные
0
Входные данные
100 4
2 6 7 8
Выходные данные
4
Страница: << 305 306 307 308 309 310 311 >> Отображать по:
Выбрано
:
Отменить
|
Добавить в контест