Темы
    Информатика(2609 задач)
---> 22 задач <---
Источники --> Личные олимпиады --> Индивидуальная олимпиада по информатике и программированию (ИОИП)
Страница: 1 2 3 4 5 >> Отображать по:
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes

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

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

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

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

Первая строка входного файла содержит число n (1 n 100000) вопросов в тесте. Вторая строка входного файла содержит n целых чисел a1, a2, . . . , an — номера правильных вариантов ответов на каждый из вопросов. Третья строка входного файла содержит n целых чисел b1, b2, . . . , bn — номера вариантов, выбранных тестируемым. Для чисел ai и bi верны неравенства 1 ai, bi 10.

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

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

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

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

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

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

Кроме этого, будем считать, что продажа и покупка будет осуществляться только с акциями одного типа. На начало этого периода вы располагаете суммой в x рублей. Для каждого из дней известна цена ai (от ask — цена предложения), по которой можно купить одну акцию, и цена bi (от bid — цена спроса), по которой можно одну акцию продать. При этом в соответствии с действующими правилами торгов на бирже разрешается продавать и покупать только целое число акций (например, если у вас есть 5 рублей, а акция стоит 2 рубля, то вы можете купить не более двух акций).

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

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

Первая строка входного файла содержит два целых числа n и x (1 n 100000, 1 x 106).

Вторая строка входного файла содержит n целых чисел a1, . . . , aт. Третья строка входного файла содержит n целых чисел b1, . . . , bт. Для каждого индекса i (1 i n) выполняются неравенства 1 bi ai 1000.

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

В первой строке выходного файла выведите максимальную сумму, которой вы можете обладать по окончании рассматриваемого периода. Во второй строке выведите два числа — номер дня d1, в который следует купить акции, и номер дня d2, в который эти акции следует продать (должно выполняться неравенство d2 > d1). При этом подразумевается, что покупается столько акций, сколько их можно купить на x рублей, а потом они все продаются. Если в найденной вами стратегии продавать и покупать акции не требуется, то выведите выведите во второй строке «-1 -1».

Если существует несколько вариантов оптимальной стратегии, то выведите любой из них

Примеры
Входные данные
5 1000
2 3 1 4 3
1 2 1 2 3
Выходные данные
3000
3 5
Входные данные
5 1000
10 9 8 7 6
9 8 7 6 5
Выходные данные
1000
-1 -1
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes

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

Петя пытается добиться того, чтобы последовательность чисел, написанных на карточках стала строго монотонной (возрастающей или убывающей). Для этого ему разрешается совершать следующие действия: выбрать два числа l и r, такие что 1 l r n и перевернуть каждую из карточек от карточки номер l до карточки номер r.

Напомним, что последовательность c1, . . . , cn называется строго возрастающей, если выполняются неравенства c1 < c2 < < cn, и строго убывающей, если выполняются неравенства c1 > c2 > … > cn.

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

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

Первая строка входного файла содержит целое число n (1 n 100000). Каждая из последующих n строк описывает одну карточку и содержит два числа — ai написано на ее лицевой стороне, а bi — на оборотной. Все числа ai и bi находятся в диапазоне от 1 до 109.

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

В первой строке выходного файла выведите минимальное число действий, которое должен совершить Петя. Если Петина цель недостижима, то выведите в выходной файл число -1.

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

В первом примере для достижения цели Петя может перевернуть карточки со второй по третью.

В третьем примере можно, например, первым действием перевернуть карточки со второй по шестую, а вторым — четвертую карточку.

Примеры
Входные данные
3
3 4
1 2
4 1
Выходные данные
1
Входные данные
3
1 2
4 1
3 4
Выходные данные
-1
Входные данные
6
1 2
3 2
2 3
4 5
6 5
5 6
Выходные данные
2
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes

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

Один из плакатов, подготовленных в рамках этого проекта, выполнен в весьма абстрактном стиле. Плакат имеет форму прямоугольника высотой h и шириной w, который изначально полностью покрашен в белый цвет. На плакате изображены несколько прямоугольников разных цветов.

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

Так как во Флатландии повсеместно внедрены информационные технологии, то подготовка плаката велась с помощью специальной программы. В этой программе (как и во многих других) цвета представляются в так называемом RGB-формате. Это означает, что цвет кодируется тремя целыми числами, каждое из которых находится в пределах от 0 до 31 (обычно используются значения от 0 до 255, но оборудование, используемое для печати, обладает ограниченными возможностями цветопередачи). Эти числа обозначают интенсивность красной, зеленой и синей компонент цвета (0 соответствует отсутствию соответствующей компоненты, а 31 — ее максимальной интенсивности).

Таким образом, черный цвет кодируется как (0; 0; 0), а белый — как (31; 31; 31).

Цвета различных областей плаката определяются следующим образом. Изначально весь плакат заполняется белым цветом (таким образом, исходно все точки имеют цвет (31; 31; 31)), после чего выполняется рисование прямоугольников, заданных в описании плаката. При рисовании прямоугольника цветом, который кодируется как (r; g; b), новые цвета точек, находящихся внутри этого прямоугольника, определяются так: если до рисования точка имела цвет (r1; g1; b1), то после того, как прямоугольник будет нарисован, ее цвет будет равен ((r1+r) mod 32; (g1+g) mod 32; (b1+b) mod 32).

Например, на рисунке приведен плакат, который получается из белого листа размера 10 # 10 изображением двух прямоугольников: цвета (12; 0; 12) с координатами левого нижнего угла (0; 0) и правого верхнего (5; 5), а затем цвета (0; 12; 0) с координатами левого нижнего угла (4; 4) и правого верхнего (6; 6).


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

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

Первая строка входного файла содержит число n прямоугольников, изображенных на плакате (0 n 1500). Вторая строка входного файла содержит два целых числа w и h — соответственно, ширину и высоту плаката (1 w, h 109). Каждая из последующих n строк описывает один из прямоугольников, изображенных на плакате, и содержит семь целых чисел: x1, y1, x2, y2, r, g, b. Первые два из них — координаты левого нижнего угла прямоугольника, третье и четвертое — координаты правого верхнего угла. Для этих чисел выполняются неравенства 0 x1 < x2 w, 0 y1 < y2 h. Пятое, шестое и седьмое числа задают цвет прямоугольника — они равны, соответственно, красной, зеленой и синей компонентам цвета (0 r, g, b 31).

Система координат введена таким образом, что левый нижний угол плаката имеет координаты (0; 0), а правый верхний — (w, h).

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

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

Примеры
Входные данные
2
10 10
0 0 5 5 12 0 12
4 4 6 6 0 12 0
Выходные данные
4
11 11 11 1
11 31 11 24
31 11 31 3
31 31 31 72
Входные данные
0
7 8
Выходные данные
1
31 31 31 56
Входные данные
2
10 10
0 0 5 5 20 21 22
4 4 6 6 15 16 17
Выходные данные
4
2 4 6 1
14 15 16 3
19 20 21 24
31 31 31 72
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
256 megabytes

Как и у каждого мальчика, у Феди есть игрушечные машинки. Однако ему повезло больше, чем обычному мальчику — все $n$ его машинок являются радиоуправляемыми. Целыми днями он может устраивать различные автогонки и играть с друзьями.

Из всех видов гонок Федя предпочитает гонки по прямой. В данном формате соревнования трасса имеет форму прямой и является бесконечной (соревнования идут до тех пор, пока Феде это не надоест). Изначально каждая из $n$ машинок находится на некотором расстоянии от старта — имеет фору $x_i$ метров. По команде все машинки начинают свое движение от старта, при этом каждая машинка движется во время гонки с постоянной скоростью $v_i$ метров в секунду. Все машинки движутся в одном направлении — удаляются от старта.

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

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

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

В первой строке входного файла содержится единственное число $n$ — количество машинок на трассе (2 $\leq$ n $\leq$ 100). Каждая из следующих $n$ строк содержит по два целых числа $x_i$ и $v_i$ — расстояние от старта (в метрах) и скорость машинки $i$ (в метрах в секунду) соответственно (1 $\leq x_i, v_i \leq$ 1000).

Исходно никакие две машинки не находятся в одной точке. Гарантируется, что хотя бы один обгон во время гонки произойдет.

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

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

Примечание

Пояснение для первого примера:

На рисунке точкой A обозначено место обгона.

Примеры
Входные данные
2
1 3
4 2
Выходные данные
3.00000
Входные данные
2
12 20
2 21
Выходные данные
10.00000

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