Темы
    Информатика(2656 задач)
---> 304 задач <---
Источники --> Личные олимпиады --> Всероссийская олимпиада школьников
    Муниципальный этап(80 задач)
    Окружная олимпиада(18 задач)
    Региональный этап(109 задач)
    Заключительный этап(97 задач)
Страница: << 17 18 19 20 21 22 23 >> Отображать по:
#1668
Блохи
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes
Блохи сидят на клетках шахматного поля и ходят конем. Должны собраться в одной из клеток. Определить сумму длин кратчайших путей.

На клеточном поле, размером \(N\)x\(M\) (2 ≤ \(N\), \(M\) ≤ 250) сидит \(Q\) (0 ≤ \(Q\) ≤ 10000) блох в различных клетках. "Прием пищи" блохами возможен только в кормушке - одна из клеток поля, заранее известная. Блохи перемещаются по полю странным образом, а именно, прыжками, совпадающими с ходом обыкновенного шахматного коня. Длина пути каждой блохи до кормушки определяется как количество прыжков. Определить минимальное значение суммы длин путей блох до кормушки или, если собраться блохам у кормушки невозможно, то сообщить об этом. Сбор невозможен, если хотя бы одна из блох не может попасть к кормушке.

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

В первой строке входного файла находится 5 чисел, разделенных пробелом: \(N\), \(M\), \(S\), \(T\), \(Q\). \(N\), \(M\) - размеры доски (отсчет начинается с 1); \(S\), \(T\) - координаты клетки - кормушки (номер строки и столбца соответственно), \(Q\) - количество блох на доске. И далее \(Q\) строк по два числа - координаты каждой блохи.

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

Содержит одно число - минимальное значение суммы длин путей или -1, если сбор невозможен.

Примеры
Входные данные
2 2 1 1 1
2 2
Выходные данные
-1
#1669
Отчет
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes
Заданы две последовательности чисел: объем продукции и процент брака. Требуется найти наибольшую подпоследовательность, в которой объем продукции растет, а процент брака падает.

Один из цехов завода производит продукцию в течение \(N\) месяцев. Начальнику цеха было поручено составить отчет о росте производительности данного цеха и об уменьшении доли некачественной продукции в процентном соотношении (точность доли процента до одного знака после запятой, например, 2/7=0.(285714) ≈ 28.6%). При этом в отчет должна войти информация как можно за большее число месяцев \(K\) (\(K\) ≤ \(N\)) работы цеха. Начальник цеха решил, что он включит в отчет данные только по тем месяцам (не обязательно взятым подряд, но обязательно в хронологическом порядке), по которым наблюдается строгий рост количества производимой продукции и строгий спад доли бракованных товаров по сравнению с данными предыдущего месяца, вошедшего в отчет. Определить, какое максимальное количество месяцев удовлетворяет этим условиям и сколько есть возможных вариантов составления отчета.

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

Первая строка файла содержит число \(N\) (1 ≤ \(N\) ≤ 40) - количество месяцев работы цеха. Далее следует N строк, содержащих целые числа \(v_i\) (1 ≤ \(v_i\) ≤ 10000) и \(b_i\) (1 ≤ \(b_i\) ≤ \(v_i\)); \(v_i\) - объем продукции, произведенной цехом за \(i\)-ый месяц; \(b_i\) - количество бракованной продукции в \(i\)-ом месяце.

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

Первая строка файла содержит число \(K\) - количество месяцев, по которым будет включена в отчет информация о работе цеха. Вторая строка содержит число \(P\) - количество возможных вариантов составления отчета с максимальным содержанием.

Примеры
Входные данные
10
313 100
313 106
442 106
442 104
475 104
475 102
539 102
539 109
682 109
682 111
Выходные данные
5
32
#1670
Точки
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes
Заданы точки на окружности. Требуется выбрать две из них, чтобы сумма расстояний по окружности до всех остальных была минимальна.

На окружности расположено N точек. Их положение определяется углом φ между осью OX и радиусом, проведенным от центра окружности к этой точке. Угол задается в градусах. Никакие две точки на окружности не совпадают. Требуется среди данных точек найти такие, что сумма расстояний по окружности от каждой из этих точек до всех остальных была минимальна. Расстояние по окружности пропорционально минимальному углу, между радиусами, проведенными к этим точкам, поэтому сумму расстояний следует вычислять как сумму углов.

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

Первая строка файла содержит целое число N (1 ≤ N ≤ 360) - количество точек. Далее следует N строк: каждая строка содержит целое число φ (1 ≤ φ ≤ 360), определяющее положение точки на окружности.

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

Первая строка файла содержит число K - количество точек, удовлетворяющих условию задачи. Далее следует K строк, содержащих номера этих точек в порядке считывания данных из файла. Номера точек требуется вывести в порядке возрастания номеров.

Примеры
Входные данные
4
5
95
185
275
Выходные данные
4
1
2
3
4
#1671
г. Киров
  
ограничение по времени на тест
5.0 second;
ограничение по памяти на тест
64 megabytes
Заданы точки (станции). Для каждой станции известно расстояние от начала координат (Москва) и зона. Зоны имеют одинаковую длину. Требуется определить координаты г. Кирова, от которого расходятся зоны.

Через г. Киров проходит железнодорожная дорога (считать, что она не имеет ответвлений), расстояние на которой отсчитываются от г. Москвы. Новый министр железнодорожного транспорта с целью придания единообразия приказал переименовать все небольшие станции. После этого станции стали иметь названия - такой-то километр от г. Москвы - например, 910 км. Местный заместитель министра, с целью увеличения поступлений в местный бюджет, все пригородные станции распределил по зонам (стоимость проезда до всех станций в одной зоне одинакова, независимо от расстояния), с одинаковой протяженностью L. Если станция находится на границе двух зон, то она может быть отнесена к любой из них в зависимости от настроения кассира, продающего билеты.

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

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

В первой строке числа N (0 < N < 201), L, затем, для каждой станции расстояние от г. Москвы и номер зоны. (Все расстояния < 1000000001)

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

Расстояние от г. Москвы до г. Кирова (одно из возможных) или -1, если задача не имеет решения.

Примеры
Входные данные
1 10
910 1
Выходные данные
0
Входные данные
2 10
910 1
800 15
Выходные данные
-1
#1672
Спутник
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes
Требуется выполнять две операции: прибавить к ячейке X число Y и определять сумму с L по R.

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

С этой целью его траектория была разбита на равные интервалы. Они пронумерованы от 1 до N. По запросу с Земли о количестве живых форм в интервале с L по R (L ≤ R) - спутник должен, пролетая над ними (L, L+1, …,R-1, R интервалами) произвести подсчет и затем, в ответ на запрос, отправить полученные данные. Но количество организмов постоянно изменяется: в некоторое время в X интервале на Y единиц.

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

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

Во входном файле первым записано число N (1 ≤ N ≤ 213 = 8192). Затем записана последовательность событий:

Событие

Параметры

Описание

1

X, Y

Изменение количества организмов в интервале с номером X на Y единиц.(-215 ≤ Y ≤ 215-1 = 32767)

2

L, R

Запрос суммарного количества организмов с L по R интервал.

0

  

Завершение работы.

Количество событий не превосходит 100000.

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

В выходной файл записывать только ответы на запросы.

Примеры

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

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

2

1 1 4

2 1 1

2 1 1

0

4

4

4

2 1 4

1 1 3

1 4 2

2 2 4

2 1 2

1 4 -2

1 2 8

2 1 4

0

0

2

3

11
Страница: << 17 18 19 20 21 22 23 >> Отображать по:
Выбрано
:
Отменить
|
Добавить в контест