Темы --> Информатика --> Алгоритмы --> Алгоритмы поиска --> Бинарный поиск --> Бинарный поиск в массиве
---> 24 задач <---
Источники
    Личные олимпиады(938 задач)
    Командные олимпиады(684 задач)
Страница: << 1 2 3 4 5 >> Отображать по:
#1664
Суперсумма
  
ограничение по времени на тест
5.0 second;
ограничение по памяти на тест
64 megabytes

Дано \(N\) натуральных чисел. Требуется для каждого числа найти количество вариантов разбиения его на сумму двух других чисел из данного набора.

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

В первой строке дано число \(N\) ( 1 ≤ \(N\) ≤ 10000). Далее заданы \(N\) натуральных чисел, не превосходящих \(10^9\). Для каждого числа количество разбиений меньше 231.

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

Вывести \(N\) чисел – количество разбиений, в порядке, соответствующем исходному.

Примеры
Входные данные
5 
3
3
2
2
1
Выходные данные
2
2
0
0
0
#1771
Свечки
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes
На круглом торте расположены свечки, заданные двумя координатами. Разрезы торта заданы уравнениями прямых. Требуется определить, есть ли на каком-либо кусочке торта более одной свечки.

Мише исполнилось \(n\) лет. Праздничный торт, испеченный по этому случаю, имеет форму круга радиуса \(r\) с центром в начале координат. На торте стоят \(n\) свечек. Мишина мама разделила торт на части, сделав \(m\) прямолинейных разрезов. Каждый гость взял один из получившихся кусков.

Миша хочет узнать, не досталось ли кому-нибудь из его гостей более одной свечки. Помогите ему это выяснить.

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

Первая строка входного файла содержит целые числа \(n\), \(m\) и \(r\) (1 ≤ \(n\) ≤ 10000, 0 ≤ \(m\) ≤ 1000, 1 ≤ \(r\) ≤ 2000).

Следующие n строк содержат пары целых чисел \(x_i\), \(y_i\) – координаты точек, где расположены свечки. Гарантируется, что эти точки лежат внутри круга, размерами свечек следует пренебречь. Никакие две свечки не совпадают.

Последние \(m\) строк содержат описание разрезов – тройки целых чисел \(a_i\), \(b_i\), \(c_i\). Такая тройка соответствует разрезу, который задается уравнением \(a_i\) \(x\) + \(b_i\) \(y\) + \(c_i\) = 0. Ни один разрез не проходит через свечку. Никакие два разреза не совпадают. Числа ai, bi, ci не превышают 10000 по модулю.

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

Если одному из гостей досталось более одной свечки, выведите в выходной файл слово «YES», иначе выведите слово «NO».

Примеры
Входные данные
3 2 3
2 2
1 -1
-2 0
2 -1 0
0 1 -1
Выходные данные
NO
Входные данные
3 2 3
2 2
1 -1
-2 0
1 1 -1
0 1 -1
Выходные данные
YES
Входные данные
4 2 10
1 1
1 -1
-1 1
-1 -1
0 1 0
1 0 0
Выходные данные
NO
#2532
Ханты-Мансийск — Париж
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
256 megabytes

В 2050 году руководство Глобальной Телефонной Сети (ГТС) приняло решение о новой системе тарификации коротких текстовых сообщений. Теперь цена отправки одного сообщения зависит от количества совпадающих цифр в начале номеров телефонов отправителя и получателя. Если первые \(c\) цифр телефонов совпадают, а \((c+1)\)-я цифра различается, то стоимость сообщения составляет \((10-c)\) кредитов (\(0\le c\le9\)). Все номера телефонов — десятизначные. При этом ГТС разрешает каждому абоненту отправлять сообщение только в пределах часового пояса своего проживания или часовых поясов, отличающихся от него на 1 час.

Школьник Поликарп из Ханты-Мансийска (время +2 часа от московского) успешно решил все задания первого тура олимпиады школьников по информатике. Теперь он желает сообщить об этом в Париж (время −2 часа от московского) своему учителю — профессору де Коде́ру. Так как Ханты-Мансийск и Париж находятся не в соседних часовых поясах, Поликарп не может послать сообщение напрямую. Поэтому он пользуется тем, что у него есть друзья, которые проживают в Ханты-Мансийске, Париже, а также в промежуточных часовых поясах — в Дубае (время +1 час от московского), Москве и Калининграде (время −1 час от московского). Друзья Поликарпа по цепочке доставят профессору де Коде́ру столь важную информацию. Поликарп хочет организовать передачу информации таким образом, чтобы минимизировать суммарные расходы по отправке всех сообщений.

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

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

Первые две строки входного файла содержат телефонные номера Поликарпа и профессора де Коде́ра. Далее следуют 5 блоков данных, описывающих друзей Поликарпа, живущих в Ханты-Мансийске, Дубае, Москве, Калининграде и Париже, соответственно. Каждый блок начинается со строки, содержащей одно число \(n_i\) (\(1\le n_i\le100\,000\)) — количество друзей Поликарпа в соответствующем городе, после которой следуют \(n_i\) строк — номера телефонов друзей. Все номера телефонов состоят ровно из 10 цифр. Гарантируется, что сумма всех \(n_i\) не превосходит 100 000. Все номера телефонов во входных данных различны.

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

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

Система оценивания

  • Решения, корректно работающие при сумме \(n_i\), не превосходящей 500, будут оцениваться из 40 баллов.
  • Решения, корректно работающие при сумме \(n_i\), не превосходящей 5 000, будут оцениваться из 60 баллов.

    • Примеры
    Входные данные
    2099013166
7043239909
1
0258442145
1
0000000000
1
0000000001
1
0000000002
1
0147571204
    Выходные данные
    22 5
2099013166
0000000000
0000000001
0000000002
7043239909
    Входные данные
    4261802325
7967612531
1
8176476745
1
3084033164
1
1737248630
1
9447552231
1
2848478213
    Выходные данные
    40 5
4261802325
3084033164
1737248630
9447552231
7967612531
    #2859
    Раскраска кубиков
      

    На день рождения Пете подарили коробку кубиков. На каждом кубике написано некоторое целое число. Петя выложил все \(n\) своих кубиков в ряд, так что числа на кубиках оказались расположены в некотором порядке \(a_1\), \(a_2\), ..., \(a_n\). Теперь он хочет раскрасить кубики в разные цвета таким образом, чтобы для каждого цвета последовательность чисел на кубиках этого цвета была строго возрастающей. То есть, если кубики с номерами \(i_1\), \(i_2\), ...., \(i_k\) покрашены в один цвет, то \(a_{i_1} \lt a_{i_2}\lt ... \lt a_{i_k}\). Петя хочет использовать как можно меньше цветов. Помогите ему!

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

    Первая строка входного файла содержит число \(n\) - количество кубиков у Пети (\(1\le n \le 250000\)). В следующей строке записано \(n\) чисел \(a_1\), \(a_2\), ..., \(a_k\), \(-2^{31}\le a_i \le 2^{31} - 1\).

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

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

    Примеры
    Входные данные
    10
2 3 1 3 2 1 2 2 4 3
    Выходные данные
    5
1 1 2 2 3 4 4 5 1 3
    #2973
    Арифметическая прогрессия
      
    Источники: [ Командные олимпиады, ВКОШП, 2010, Задача A ]
    ограничение по времени на тест
    3.0 second;
    ограничение по памяти на тест
    256 megabytes

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

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

    Теперь Петя хочет восстановить исходную последовательность по этим карточкам. К сожалению возможно, что это можно сделать несколькими способами, но Петю устроят любые \(n\) чисел, образующие арифметическую прогрессию.

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

    Напомним что последовательность \(a_1, a_2, \ldots, a_n\) называется арифметической прогрессией, если \(a_i = a_{i-1} + d\) для всех \(i\) от 2 до \(n\) и некоторого \(d\). Число \(d\) называется разностью арифметической прогрессии.

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

    В первой строке входного файла находится целое число \(n\) (\(1 \le n \le 100\,000\)). В следующей строке находится \(2n\) целых чисел по модулю не превосходящих \(10^9\) — числа, написанные на карточках, перечисленные в произвольном порядке. Гарантируется, что можно выбрать \(n\) из них так, чтобы они образовывали арифметическую прогрессию.

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

    В первой строке выходного файла выведите \(a_1\) и \(d\) — первый элемент и разность найденной арифметической прогрессии. Если \(d = 0\), число \(a_1\) должно встречаться среди заданных чисел \(n\) раз.

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

    Страница: << 1 2 3 4 5 >> Отображать по:
    Выбрано
    :
    Отменить
    |
    Добавить в контест