WWW.NET.KNIGI-X.RU
БЕСПЛАТНАЯ  ИНТЕРНЕТ  БИБЛИОТЕКА - Интернет ресурсы
 

«ЗКШ 2014. День 7. Дивизион 1 Россия, Долгопрудный, 4 марта 2014 года Задача A. XOR-максимизация Имя входного файла: input.txt Имя ...»

ЗКШ 2014. День 7. Дивизион 1

Россия, Долгопрудный, 4 марта 2014 года

Задача A. XOR-максимизация

Имя входного файла: input.txt

Имя выходного файла: output.txt

Ограничение по времени: 1.5 секунд

Ограничение по памяти: 256 мегабайт

Дана некоторая последовательность, состоящая из N чисел. Обозначим i-тое число последовательности за ai. Вас просят ответить на M запросов, каждый задается парой чисел lj и rj. Ответом

на запрос является максимальное возможное значение операции XOR всех чисел последовательности, индексы которых представляют собой некоторый подотрезок отрезка [lj ; rj ]. Мы считаем [x; y] подотрезком отрезка [l; r], если l x y r.

Формат входного файла Первая строка входного файла состоит из двух разделенных одиночным пробелом целых чисел N и M (1 N 15000, 1 M 10000).

Далее, на второй строке следуют N целых чисел i-е из которых есть ai (0 ai 220 ). Числа в последовательности нумеруются с нуля.

Далее в M строках следуют описания запросов в виде lj rj (0 lj, rj N ).

Сами числа lj и rj определяются следующим образом:

lj = min{(lj + lastans) (mod N ), (rj + lastans) (mod N )} + lastans) (mod N ), (r + lastans) (mod N )} rj = max{(lj j Здесь lastans - последнее выведенное Вами число. Изначально lastans равняется нулю.

Формат выходного файла Для каждого запроса выведите ответ на него на отдельной строке.

Примеры input.txt output.txt Note

Разберем стандартный тест:



1. Так как lastans изначально равняется нулю, получаем отрезок [0; 1], которому соответствует последовательность (1, 4). Вся последовательность является ответом — 1 XOR 4 = 5.

2. lastans = 5. Получаем отрезок с концами (0 + 5) mod 3 = 2 и (1 + 5) mod 3 = 0. Последовательность, которая ему соответствует равна (1, 4, 3). На подотрезке [1; 2] получаем XOR равный 7.

3. lastans = 7. Получаем отрезок с концами (1 + 7) mod 3 = 2 и (0 + 7) mod 3 = 1. Последовательность, которая ему соответствует равна (4, 3). Вся последовательность является ответом — 4 XOR 3 = 7.

Страница 1 из 8 ЗКШ 2014. День 7. Дивизион 1 Россия, Долгопрудный, 4 марта 2014 года Задача B. Количество треугольников Имя входного файла: input.txt Имя выходного файла: output.txt Ограничение по времени: 1 секунда Ограничение по памяти: 256 мегабайт Здесь была я Легенда про Байтландию Есть прямоугольная решетка, параллельная осям координат. Левый нижний угол имеет координаты (0, 0), а правый верхний — (N, M ). Требуется найти количество треугольников внутри решетки в точках с целыми координатами с площадью ровно S.

Формат входного файла В единственной строке ввода находятся три целых числа N, M и S (1 N, M 70, ·M 1 S N 2 ) — размеры решётки и требуемая площадь.

Формат выходного файла Выведите одно целое число — количество треугольников с площадью ровно S внутри решетки в точках с целыми координатами.

Примеры input.txt output.txt

–  –  –

Рассмотрим некоторую матрицу из N строк и M столбцов, элементы которой являются строчными буквами байтландского (а по непонятному совпадению, еще и английского) алфавита.

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

Она может быть вычислена следующим образом:

1. Рассмотрим некоторый путь из левой верхней клетки (1, 1) в правую нижнюю клетку (N, M ). Каждый раз в этом пути выбирается направление или клеткой вниз, или клеткой вправо.

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

2. Запишем все буквы в клетках, которые мы проходили в этом пути в том порядке, в котором их проходили. Получим некоторую строку S. Обозначим за f (S) количество путей в матрице, которые образуют строку S.

3. Значение вероятности некоторой строки S равно сумме значений вероятности всех путей, которые образуют строку S.

4. Удачливостью матрицы называется величина суммы произведений f (S) на вероятность строки S, по всем возможным строкам S.

Можно показать, что удачливость матрицы с N строками и M столбцами, умноженная на 2N +M есть целое число. Найдите это число по модулю 109 + 7.

Формат входного файла Первая строка входного файла содержит числа N и M (1 N, M 300), разделенные одиночным пробелом - количество строк и столбцов в матрице. Далее следуют N строк по M маленьких латинских букв, задающих матрицу.

Формат выходного файла Выведите значение удачливости матрицы, умноженное на 2N +M по модулю 109 + 7.

Примеры input.txt output.txt abc ccc Note

Рассмотрим все возможные пути в тестовом примере:

1. Вправо, вправо, вниз. Получаем строку «abcc». Вероятность этого пути равна 1. 4

2. Вправо, вниз, вправо. Получаем строку «abcc». Вероятность этого пути равна 1. 4

3. Вниз, вправо, вправо. Получаем строку «accc». Вероятность этого пути равна 1. 2 Таким образом получаем: f (”abcc”)·( 1 + 4 )+f (”accc”)· 1 = 3. Домножая на 2N +M, как требуется 5, то есть, на 32), получаем 48 — ответ тестового примера.

в условии задачи (то есть, на 2

–  –  –

По мнению студента Владислава все числа чётные. Просто некоторые чуть более чётные, чем другие. Степень чётности числа — это сколько раз это число можно делить на два, пока оно не перестанет быть целым.

Например, у нечётных чисел степень равна нулю, у числа 6 — 1, а у числа 72 — 3. Заметим, что у числа 0 степень бесконечна.

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

Владислав решил не сам решать эту задачу, а перепоручить её Владимиру. Так не оставим же в беде Владимира и поможем ему найти ответ.

Формат входного файла В единственной строке входного файла находятся два числа l и r (0 l r 101000 ) — границы отрезка.

Формат выходного файла В выходной файл выведите одно число x. x должен удовлетворять неравенству l x r и обладать наибольшей степенью чётности на данном интервале. Если таких чисел несколько выведите наибольшее из них.

Примеры input.txt output.txt

–  –  –

Два старых добрых друга Абрахам Лемпель и Якоб Зив обожают читать длинные условия задач. Поэтому по вечерам они пишут условия с большими, размашистыми легендами, наполняют их картинками, поясняющими примерами и посылают друг другу для прочтения. Однако канал передачи данных между товарищами настолько медленный, что условия приходится ждать неделю, не меньше. Для решения проблемы был придуман способ уменьшения объема передаваемых данных, то есть метод сжатия сообщений без потерь.

Сжатое сообщение представляет собой один или несколько блоков, каждый из которых имеет один из двух типов: блок-символ или блок-строка. Процесс распаковки сжатого сообщения есть последовательная обработка его блоков. Пусть S это часть распакованной строки известная на текущий момент. Изначально S –– пустая строка. Блок-символ представляет собой один символ c и означает, что к текущей распакованной строке следует приписать в конце этот самый символ.

Псевдокод этой операции:

Блок-строка представляет собой пару целых положительных чисел (l, r), и означает, что мы должны к S добавить r символов из самой S, начиная с l-го по счету с конца символа. Отметим, что копирование происходит по одному символу, так что r может превосходить l.

Псевдокод этой операции:

Обработав все блоки сжатого сообщения, получившаяся строка S будет распакованным сообщением.

Известно, что блок первого типа можно описать 9-ю битами, а блок второго типа — 20-ю битами.

Размер сжатого сообщение есть сумма размеров каждого из его блоков.

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





Формат входного файла Первая строка содержит число T (1 T 20), где T – количество сообщений для сжатия.

Далее идут T строк, каждая из которых содержит одно непустое сообщение. Сообщение состоит только из маленьких латинских букв. Длина сообщения не превосходит 1000.

–  –  –

Note В первом сообщении после первых четырех блоков-символов S = abac, затем мы начиная с 4-го с конца символа (то есть с a), копируем 3 символа в конец S, и получаем abacaba Во втором примере после первого блока-символа S = a, затем мы 6 раз копируем символы по очереди из S, начиная с первого с конца (и единственного) символа.

S S + S[1] = qq S S + S[2] = qqq...

S S + S[6] = qqqqqqq Страница 6 из 8 ЗКШ 2014. День 7. Дивизион 1 Россия, Долгопрудный, 4 марта 2014 года Задача F. Распродажа Имя входного файла: input.txt Имя выходного файла: output.txt Ограничение по времени: 1.5 секунд Ограничение по памяти: 256 мегабайт Владелец байтландского магазина игрушек «Цацка» решил устроить распродажу. Если обычно цена некоторой игрушки была равна X, то во время распродажи её цена будет равна числу, которое состоит из цифр числа X записанных в обратном порядке. Например, если до распродажи цена игрушки равнялась 654321 рублей, то во время распродажи она будет стоить 123456 рублей, а игрушка, которая стоила 1000 рублей, будет стоить всего 1 рубль.

В магазине имеются игрушки с ценами от S до F включительно, причем на каждую цену имеется ровно одна игрушка. Владелец магазина хочет узнать, у скольких игрушек стоимость на время распродажи поменяется незначительно, а именно, сколько из них изменят свою цену не больше, чем на K рублей. Например, для начальной цены в 321 рубль при распродаже произойдет изменение на |321 – 123| = 198 рублей, а при начальной цене в 35 рублей изменение будет на |35 - 53| = 18 рублей.

Формат входного файла В первой единственной строке ввода записаны три целых числа S, F, K (1 S F 108, 0 K 108 ) –– ценовой диапазон игрушек в магазине и приемлемое изменение цены.

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

Примеры input.txt output.txt Страница 7 из 8 ЗКШ 2014. День 7. Дивизион 1 Россия, Долгопрудный, 4 марта 2014 года Задача G. Тонкий расчёт Имя входного файла: input.txt Имя выходного файла: output.txt Ограничение по времени: 1 секунда Ограничение по памяти: 256 мегабайт Девочка Нина очень красива и умна. Поэтому немудрено, что у неё есть много друзей-мальчиков.

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

Более формально у Нины есть N друзей. Друг с номером i хочет провести время с Ниной весь период времени с момента starti до f inishi включительно. Причём Нина, чтоб не обидеть своих друзей, в каждый момент времени может уделять своё внимание не более чем одному другу. Если Нина решила, что не может провести с другом весь желаемый отрезок времени, то она не будет проводить с ним вообще никакого времени, чтоб не давать ложных надежд. Если Нина закончила видеться с каким-то другом в момент времени t, то она может начать уделять внимание следующему уже в момент t + 1.

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

Не все друзья Нины одинаково полезны. Некоторые хорошо решают дифференциальные уравнения, некоторые могут покормить, а некоторые ну так, пригодятся. Поэтому всех своих друзей делит на две категории: «полезные» и «не очень». В первую очередь Нина хочет максимизировать количество «полезных» друзей, с которыми проведёт время. Если же есть несколько способов это сделать, то она максимизирует общее количество друзей, с которыми она проведёт время.

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

Формат входного файла В первой строке входного файла находится целое число N — количество друзей Нины (1 N 105 ).

Во второй строке входного файла находится строчка из ровно N символов. Если i-й символ строки равен «0», то значит, что i-й мальчик не очень полезен Нине, а если «1» — то полезен.

Других символов в строке нет.

В следующих N строках содержится по два неотрицательных целых числа starti и f inishi — описание моментов времени в условных единицах от какой-то точки отсчёта (0 starti f inishi 108 ).

Мальчики нумеруются в порядке ввода.

Формат выходного файла В выходной файл выведите два числа — количество «полезных» мальчиков в удачном расписании и количество «не очень полезных».

Примеры input.txt output.txt

Похожие работы:

«ЕЖЕКВАРТАЛЬНЫЙ ОТЧЕТ Публичное акционерное общество "НОВАТЭК" Код эмитента: 00268-E за 3 квартал 2016 г. Адрес эмитента: 629850 Россия, Ямало-Ненецкий автономный округ, Пуровский район, г. Тарко-Сале, Победы 22 а Информация, содержащ...»

«СУЩНОСТНАЯ ОСНОВА ПОНЯТИЯ "ИННОВАЦИОННАЯ СРЕДА": ЕЕ ОСНОВНЫЕ СОСТАВЛЯЮЩИЕ И НАПРАВЛЕНИЯ РАЗВИТИЯ Т.Е. Шишкова, научно-методический центр по инновационной деятельности высшей школы им. Е.А. Лурье Тверского государственного университета В статье даны различные трактовки понятия "инновационн...»

«Региональный отчет по результатам исследования читательской грамотности "Тяни-Толкай" В декабре 2014/2015 учебного года в Новосибирской области проведено исследование динамики читательской грамотности учащихся основной школы с использованием диагностической методики, получившей необычное название "Тяни-Толкай". Из опыта известно...»

«АННОТАЦИЯ К ПРОГРАММЕ ПОДГОТОВКИ СПЕЦИАЛИСТОВ СРЕДНЕГО ЗВЕНА ПО СПЕЦИАЛЬНОСТИ 38.02.05 Товароведение и экспертиза качества потребительских товаров базовой подготовки Общие положения Федеральны...»

«Сообщение о существенном факте “Сведения о решениях общих собраний” 1. Общие сведения 1.1. Полное фирменное наименование эмитента Закрытое акционерное общество (для некоммерческой организации – "Гражданские самолеты Сухого" наименование) 1.2. Сокращенное ф...»

«Гиперболические группы по Громову М. Вербицкий Гиперболические группы по Громову: лемма Морса Миша Вербицкий 29 ноября, 2012 НМУ Гиперболические группы по Громову М. Вербицкий Кратчайшие в метрическом прострастве (повторение) Определение: Пусть : [0, ]...»

«ОАО Мобильные Телесистемы филиал в Республике Марий Эл Салон-магазин Красный город, Республика Марий Эл, г.Йошкар-Ола, ул.Советская, д.154 (8-800-333-0890), WWW.MARI-EL.MTS.RU MAXI Plus Пакеты минут по выгодной ц...»

«Капитальный ремонт многоквартирных домов в Республики Крым, формирование фондов капитального ремонта многоквартирных домов. Постановлением Совета Министров Республики Крым от 30 ноября 2015 года №753 утверждена региональная программа капитального ремонта общего имущества в мно...»








 
2017 www.ne.knigi-x.ru - «Бесплатная электронная библиотека - электронные матриалы»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.