Темы --> Информатика --> Алгоритмы
    Задачи на моделирование(78 задач)
    Арифметические алгоритмы(240 задач)
    Алгоритмы поиска(155 задач)
    Алгоритмы сортировки(194 задач)
    Динамическое программирование(355 задач)
    Алгоритмы на графах(319 задач)
    Перебор(154 задач)
    Игры и выигрышные стратегии(33 задач)
    Вычислительная геометрия(216 задач)
    Эвристические методы(30 задач)
    Алгоритмы на строках(45 задач)
    Пересечение множеств(10 задач)
    Жадный алгоритм(71 задач)
    Теория расписаний(5 задач)
    Обработка текста(31 задач)
    Дата и время(14 задач)
---> 1657 задач <---
Источники
    Личные олимпиады(938 задач)
    Командные олимпиады(684 задач)
Страница: << 101 102 103 104 105 106 107 >> Отображать по:
#924
Рисование
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes

Дано \(N\) точек на плоскости, их надо покрасить в черный и белый цвета.

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

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

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

В первой строке задано число \(2 \leq N \leq 300\). В следующих \(N\) строках заданы координаты точек.

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

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

Примеры
Входные данные
4
0 0
1 0
1 1
0 1
Выходные данные
12
Входные данные
3
0 0
0 1
0 2
Выходные данные
4
#932
Почтальон
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

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

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

Помогите почтальону составить такой маршрут.

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

Сначала записано число N — количество площадей в городе (2≤N≤1000). Далее следуют N строк, задающих улицы. В i-ой из этих строк находится число mi — количество улиц, выходящих из площади i. Далее следуют \(m_i\) пар натуральных чисел: в j-ой паре первое число — номер площади, в которую идет j-ая улица с \(i\)-ой площади, а второе число — длина этой улицы.

Между двумя площадями может быть несколько улиц, но не может быть улицы с площади на нее саму.

Все числа во входном файле не превосходят 100000

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

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

Если решения нет, выведите в выходной файл одно число –1.

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

Примеры
Входные данные
4
2  2 1  2 2
4  1 2  4 4  3 5  1 1
2  2 5  4 8
2  3 8  2 4
Выходные данные
5
1 2 3 4 2 1
#936
Экономический кризис
  

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

Центробанк Флатландии планирует выделить N пакетов помощи. Каждый пакет характеризуется его суммой Ai.

Банки предоставили запросы на помощь. На данный момент поступило M запросов. Каждый запрос характеризуется его продолжительностью Bi дней.

Законы Флатландии требуют, чтобы при возвращении пакета помощи банк каждый день возвращал центробанку одинаковую целую сумму флатландских рублей. Таким образом, пакет с суммой A и продолжительностью B можно выделить только в случае если A делится на B.

По известной информации о пакетах помощи и запросах подсчитайте количество возможных пар пакет-запрос.

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

Первая строка содержит целое число N – количество пакетов помощи (1 ≤ N ≤ 100 000). Вторая строка содержит N целых чисел: a1, a2, . . . , an (1 ≤ ai ≤ 106).

Вторая строка содержит целое число N – количество запросов (1 ≤ M ≤ 100 000). Вторая строка содержит N целых чисел: b1, b2, . . . , bn (1 ≤ bi ≤ 106).

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

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

Комментарий к примеру

Пары могут быть следующие: (3, 1) дважды как (a1, b1) и (a1, b2), (3, 3), (4, 1) дважды, (4, 2), (5, 1) дважды, (6, 1) дважды, (6, 2) и (6, 3).

Примеры
Входные данные
4
3 4 5 6
4
1 1 2 3
Выходные данные
12
#941
Не в билетах счастье, а в их количестве
  

Люди, покупающие какие-либо билеты, часто пытаются понять, на сколько счастливый билет им попался. При этом определения счастья бывают различные. В общественном транспорте Кирова для нумерации билетов используются числа от 1 до n. Витя считает билет счастливым, если его номер делится на сумму его цифр. Помогите Вите определить количество счастливых билетов.

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

На вход подается число n (1 ≤ n ≤ 1012).

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

Выведите количество счастливых билетов в диапазоне от 1 до n.

Примеры
Входные данные
100
Выходные данные
33
#942
Ключ к успеху
  

Организаторы TВ-Шоу “Ключ к успеху” подготовили ряд призов для победителей. Если победитель набрал X очков, он должен выбрать призов в точности на X у.е. От предыдущих шоу у организаторов остались N призов стоимостью a1,a2,... ,an< у.е. соответственно. К сожалению, не известно, сколько именно очков наберет победитель очередной игры. Организаторы решили купить еще M призов, чтобы максимизировать минимальную сумму очков, которую уже нельзя будет набрать имеющимися призами.

Например, если уже имеются призы в 2, 3 и 9 у.е., а покупается 2 приза, то купить надо призы стоимостью 1 и 7 долларов. Тогда победитель сможет набрать себе призы при любом счете от 1 до 22 очков.

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

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

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

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

Примеры
Входные данные
2 2
2 3
Выходные данные
1
7
Страница: << 101 102 103 104 105 106 107 >> Отображать по:
Выбрано
:
Отменить
|
Добавить в контест