Информатика

Сначала Антону Витальевичу показалось, что объявить приз на самую упоротую задачу – очень хорошая идея. Но когда его просто завалили этими задачами, он понял, что не успеет проверить их все к Новому Году. Поэтому он, пообещав хорошую оценку в журнал, дал Вам задание написать проверяющую эти задачи программу. (Ваш вопрос «А почему вы не можете сделать этого сами?» остался без ответа).

Задача – это набор текста, содержащего русские слова, заглавные латинские символы и числа, разделённые знаками препинания, специальными символами и пробелами. Упоротость задачи можно выразить целым неотрицательным числом, зависящим от многих факторов. Во-первых, чем длиннее задача, тем она упоротее, поэтому за каждое русское словоупоротость увеличивается на 1. Но если задача слишком длинная, то она из упоротой превращается в скучную. Поэтому, если количество слов превышает 50, то за каждое лишнее слово упоротость уменьшается на 2. Во-вторых, чем больше исходных данных, то есть латинских символов, тем задача упоротее, так что за каждый латинский символ упоротость умножается на 2. В-третьих, чем больше чисел нам дано сразу, тем задача скучнее, поэтому за каждое число упоротость делится на 10. Но если число отделено от латинского символа только пробелами, знаками препинания или специальными символами, то оно считается ограничением и вместо деления на 10 просто увеличивает упоротость на 30. В-четвёртых, знаки препинания – это всегда скучно, так что из-за них упоротость уменьшается на округлённый вверх двоичный логарифм их общего количества. Специальные символы и пробелы на упоротость никак не влияют. Если в результате получается нецелое число, оно округляется вниз.

Общая длина задачи не более 2*10^9 символов.
Русские слова - слова, состоящие из символов, не являющихся заглавными латинскими буквами, числами, знаками препинания и специальными символами.
Двоичным логарифмом нуля считать ноль.
К знакам препинания относятся , . ! ? ( ) : 

К специальным символам относятся & * = + - / ><
 

Дана задача. Вам необходимо подсчитать её общую упоротость.
 

Формат ввода

Дан текст с единственным символом переноса в конце.
 

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

Вывести единственное число – общую упоротость задачи.

Пример

Ввод:

2 N 2 N 2 N 2 N 2
 

Вывод:

2400

(с) Даниил Кирионенко, 9и

И вот вновь наступил Новый Год, и Васе снова понадобилось наряжать ёлку. Но, памятуя о своих прошлогодних неудачах (Вы о них знаете, если решали прошлогодний контест), он купил в магазине брендовые ударопрочные шарики. К сожалению, на ёлку в результате денег почти не осталось, и её пришлось покупать у какого-то индуса. Поэтому ёлка имеет форму полного двоичного дерева глубины N – на верхушке только одна ветка, и под каждой веткой, кроме самых нижних, снизу растёт ровно две. В самом низу, соответственно, под ветками только Васин немытый пол.

Но когда Вася приступил к украшению, он понял, что совершил страшную ошибку. Ударопрочные шарики были одноцветными и скучными, поэтому Вася не мог развесить их как попало, как он делал это раньше. Пришлось ему разрабатывать алгоритм украшения. Для начала он соотнёс каждому цвету его индекскрасоты – параметр от 0 до 10⁹. Чем он больше, тем более красивым кажется Васе шар этого цвета. Потом он случайным образом развесил шарики у пола (на каждую ветку Вася всегда вешает только один шар). Для всех остальных веток Вася смотрел на их нижних соседей, определял, какой из висящих на этих ветках шариков красивее, и вешал на эту ветку точно такой же.

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

Нижние ветви пронумерованы от 1 до 2^(N- 1), более верхним Вася из лени решил номера не давать. Вася подаёт на вход два вида запросов. В первом он заменяет какой-либо шар в нижнем уровне с номером k на шар цвета c, и хочет узнать, на скольких слоях веток (кроме нижнего) ему придётся перевесить шары, чтобы ёлка по-прежнему подходила под описанный выше алгоритм. Во втором он хочет узнать цвет самого красивого шара в секторе от l до r. К сектору относятся все ветки нижнего слоя с номерами от l до r включительно, а также все находящиеся над ними ветки.То есть, если N = 3, то к секторуот 1 до 2 относятся ветки 1 и 2, а также третья ветка, находящаяся между ними чуть выше.

Формат ввода

В первой строке задана глубина ёлки N (N<= 15) и количество запросов M (M<= 10⁷). Во второй строке задана первоначальная развеска нижних шариков, представленная их индексами красоты. В следующих M строках заданы запросыдвух типов (первый обозначен цифрой 1, а второй, как ни странно, 3). Описание запросов дано выше.

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

Нужно вывести Mстрок, содержащих ответы на запросы.

Пример

Ввод:

4 5

1 1 2 3 100 7 11 3

3 1 8

3 2 4

1 5 4

3 1 8

1 5 9
 

Вывод:

100

3

3

11

1

 

(c) Даниил Кирионенко, 9и

int main()
{
       string s;
       vector <int> arr = { 70, 109, 108, 96, 37, 100, 114, 113, 41, 56, 96, 61, 59 };
       for(int i = 0; i < arr.size(); i++)
       {
             int x = s[i];
             cout << (x ^ arr[i]) << " ";
       }
       return 0;
}

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

 

1 2 3 4 5 6 7 8 9 10 11 12 13

 

?

 

 

Входные данные пусты

 

 

Выведите одну строку – ответ на задачу.

(c) Егор Курбатов, 10и

Вилли - сильный шахматист, но удача улыбается ему только в определенное время года. Получая приглашение сыграть в определенном турнире, Вилли хочет, чтобы сразу отображалось время года, в которое будет проходить турнир. Для этого он хочет написать программу. Сделайте это за него. 
Напишите программу, которая получает с клавиатуры номер месяца и выводит название соответствующего ему времени года (winter, spring, summer, autumn) или сообщение об ошибке (error).

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

 

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

 

В первой строке входного файла задано целое число R - количество заменяемых последовательностей и целое число N - количество строк в исходном тексте (1<=N<=1000). Далее следуют R пар строк, описывающих возможные замены. Первая строка каждой пары содержит заменяемую последовательность, а вторая - заменяющий символ, являющийся большой или маленькой английской буквой. Различным заменяемым последовательностям соответствуют разные английские буквы (большие и маленькие буквы различаются). В следующих N строках записан текст,  подлежащий сжатию. В этом тексте, также как и в заменяемых последовательностях, отсутствуют буквы английского алфавита.

 

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

 

Символы перевода строки не заменяются (т.е. замены возможны только внутри строк). Длина каждой строки входного файла не превосходит 255 символов.

 

8 10

рхиватор

b

замен

D

ены

F

зам

G

быт

h

про

d

сжат

f

ом называется

g

Архиватором называется программа, предназначенная для сжатия данных за счет удаления 

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

архиватора текстов на русском языке. В таких текстах многие знаки стандартной таблицы 

символов не встречаются, поэтому они могут быть использованы для замены часто 

повторяющихся последовательностей символов. 

 

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

алфавита, а также исходный текст, который следует сжать. Поскольку в исходном тексте эти 

последовательности могут накладываться друг на друга, результат сжатия существенно зависит 

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

 

Аbg dграмма, предназначенная для fия данных за счет удаления 

изhочной информации. В этой задаче вашей целью является разработка dстейшего 

аbа текстов на русском языке. В таких текстах многие знаки стандартной таблицы 

символов не встречаются, поэтому они могут hь использованы для Dы часто 

повторяющихся последовательностей символов. 

 

Заданы последовательности, которые могут hь DF некоторыми символами английского 

алфавита, а также исходный текст, который следует fь. Поскольку в исходном тексте эти 

последовательности могут накладываться друг на друга, результат fия существенно зависит 

от порядка D. Ваша задача состоит в том, чтобы получить fый текст наименьшей длины.

 

В то время, пока обороняющиеся отвлеклись на Блейза, Корвин начал штурм города. Для того, чтобы его армия вошла в город, ему нужно пробить брешь в стене. В его распоряжении есть целый флот, из которого он собирается обстреливать стены города. Стена являются линией из n сегментов, пронумерованных от 1 до n. 

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

Но Джерард не только согласился отвести свой флот из бухты Амбера, благодаря чему флоту Корвина удалось добраться до Амбера с целым и невредимым флотом, но и предоставил ему журнал с m записями, в котором в i-ой записи указано, что были перестроены сегменты с li по ri, а также сказано, насколько изменилась укрепленность всех сегментов (укрепленность каждого сегмента на отрезке [li; ri] изменяется на одно и тоже значение ti).

Корвин m раз предлагает выстрелить по сегментам стены с l по r из p кораблей. Известно, что брешь будет пробита, если на отрезке [l; r] есть хотя бы один сегмент с укрепленностью меньше p. Вы должны ответить ему, будет ли пробита брешь (вывести "YES"), или нет (вывести "NO"). 

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

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

В первой строке дано число n -  количество операций с деревом. 1 <= n <= 100000.

Далее дается n строк – операции с деревом. В каждой строке находится одна из следующих операций:

1) insert x – добавить в дерево ключ x. Если ключ x уже в дереве, то ничего делать не нужно.

2) delete x – удалить из дерева ключ x. Если ключа x в дереве нет, то ничего делать не нужно.

3) exists x – если ключ х есть в дереве, то выведите “true”, иначе “false”.