Темы --> Информатика
    Язык программирования(952 задач)
    Алгоритмы(1657 задач)
    Структуры данных(279 задач)
    Интерактивные задачи(17 задач)
    Другое(54 задач)
---> 72 задач <---
Источники --> Личные олимпиады --> Всероссийская олимпиада школьников --> Региональный этап
    2009(8 задач)
    2010(8 задач)
    2011(8 задач)
    2012(8 задач)
    2013(8 задач)
    2014(8 задач)
    2015(8 задач)
    2016(8 задач)
    2017(8 задач)
    Московская областная олимпиада(13 задач)
    Кировская открытая областная олимпиада(21 задач)
    Санкт-Петербург(3 задач)
Страница: << 2 3 4 5 6 7 8 >> Отображать по:
#1666
Супермногоугольники
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

На плоскости задано N (1 ≤ N ≤ 30) супермногоугольников (без пересечений и самопересечений). Каждый супермногоугольник задаётся координатами своих Ki (3 ≤ Ki ≤ 30, 1 ≤ i ≤ N) вершин в порядке обхода против часовой стрелки. Все координаты — целые числа из диапазона -32000..32000. Требуется соединить супермногоугольники М отрезками так, чтобы:

  1. Oтрезок соединяет только пару супермногоугольников.

  2. Суммарная длина отрезков была минимальна.

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

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

В первой строке число N. В следующих N строках. Число Ki и Ki пар чисел – координаты вершин.

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

В первой строке число М и сумма длин найденных отрезков с точностью 10-3. В следующих М строках числа L1 X1 Y1 L2 X2 Y2 – номера супермногоугольников и координаты концов отрезков с точностью 10-3.

Примеры

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

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

2

3 1 0 2 0 1 1

4 6 5 7 5 7 6 6 6

1 6.364

1 1.500 0.500 2 6.000 5.000

3

3 0 0 1 0 0 1

4 5 5 6 5 6 6 5 6

3 0 5 1 6 0 6

2 8.000

3 1.000 6.000 2 5.000 6.000

1 0.000 1.000 3 0.000 5.000
#1667
Текст
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes
Требуется перевернуть слова, состоящие из латинских букв, не трогая остальные.

Дан текст, состоящий из слов, знаков препинания и других символов. Словом в тексте считается последовательность символов из прописных и строчных букв латинского алфавита. Требуется перевернуть (записать в обратном порядке) все слова текста, оставив знаки препинания и другие символы, включая буквы русского алфавита, без изменений. В строке не более 255 символов, строк в файле не более 1000.

Примеры
Входные данные
Thisisveryveryverylongword
Выходные данные
drowgnolyrevyrevyrevsisihT
Входные данные
This test is very! easy and short.
But it's  ,. mo:re difficult than first.
Выходные данные
sihT tset si yrev! ysae dna trohs.
tuB ti's  ,. om:er tluciffid naht tsrif.
#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
#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
Страница: << 2 3 4 5 6 7 8 >> Отображать по:
Выбрано
:
Отменить
|
Добавить в контест