ЗАДАЧА №691 Номера автобусов
(Время: 1 сек. Память: 16 Мб Сложность: 16%)
Однажды Вася очень долго просидел на остановке, прежде чем дождался своего автобуса. Чтобы как-то занять время, он решил записывать на листочке государственные регистрационные номера проходящих мимо автобусов, следующих по другому маршруту, нежели нужен был Васе. При этом производилась запись лишь основного номера, без учета региональной принадлежности. В итоге Васе удалось записать N таких номеров.
Основная часть государственного регистрационного номера состоит из 6 символов: трех букв и трех цифр. Сначала идет буква, затем 3 цифры и еще 2 буквы заканчивают запись. В качестве цифр могут использоваться любые цифры от 0 до 9, а в качестве букв только прописные буквы, обозначения которых присутствуют как в английском, так и в русском алфавите, т.е. только следующие символы: A, B, C, E, H, K, M, O, P, T, X, Y. Например, «P204BT» - правильный номер, а «X182YZ» и «ABC216» - нет.
Ваша задача заключается в проверке правильности проделанной Васей работы. А именно, нужно определить, какие из номеров соответствуют принятому стандарту, а какие нет.
Входные данные Первая строка входного файла INPUT.TXT содержит единственное натуральное число N – количество записанных Васей номеров (N ≤ 50). Далее следует N строк с записями номеров автобусов. Длины строк от 1 до 300 и содержат только символы с кодами ASCII от 33 до 127 (не содержат пробелов, специальных и русских символов).
Выходные данные В выходной файл OUTPUT.TXT выведите N строк, в i-й строке должно содержаться «Yes», если соответствующая i-я запись номера верна и «No» в противном случае.
begin
foreach var s in ReadSeqString(ReadlnInteger) do
Println((s = s.MatchValue('[ABCEHKMOPTXY]\d{3}[ABCEHKMOPTXY]{2}')) ? 'Yes' : 'No')
end.
Здесь представляется удобным использовать регулярное выражение, соответствующее “правильному” госномеру. Критерием правильности будем считать совпадение исходной строки с полученной после сопоставления с регулярным выражением. Регулярное выражение построено по схема “буква” - три цифры - две “буквы”, где каждая “буква” должна быть одной из допустимых.
Сопоставление производится в цикле для каждой строки из входной последовательности. По результату сопоставления выводится Yes или No.
ЗАДАЧА №231 Распаковка строки
(Время: 1 сек. Память: 16 Мб Сложность: 25%)
Будем рассматривать только строчки, состоящие из заглавных английских букв. Например, рассмотрим строку AAAABCCCCCDDDD. Длина этой строки равна 14. Поскольку строка состоит только из английских букв, повторяющиеся символы могут быть удалены и заменены числами, определяющими количество повторений. Таким образом, данная строка может быть представлена как 4AB5C4D. Длина такой строки 7. Описанный метод мы назовем упаковкой строки.
Напишите программу, которая берет упакованную строчку и восстанавливает по ней исходную строку.
Входные данные Входной файл INPUT.TXT содержит одну упакованную строку. В строке могут встречаться только конструкции вида nA, где n — количество повторений символа (целое число от 2 до 99), а A — заглавная английская буква, либо конструкции вида A, то есть символ без числа, определяющего количество повторений. Строка содержит от 1 до 80 символов.
Выходные данные В выходной файл OUTPUT.TXT выведите восстановленную строку. При этом строка должна быть разбита на строчки длиной ровно по 40 символов (за исключением последней, которая может содержать меньше 40 символов).
begin
var s := '';
foreach var w in ReadlnString.MatchValues('\d*[A-Z]') do
begin
var l := w.Length;
s += l = 1 ? w : w[:l].ToInteger * w[l]
end;
s.Batch(40, c -> c.JoinIntoString).PrintLines
end.
При помощи регулярного выражения разбираем строку на элементы вида «буква» или «число»«буква». Формируем выходную строку s, в которую заносим либо найденную букву, либо “число” такик букв. Затем с помощью s.Batch(40) разрезаем полученную строку на 40-символьные последовательности, каждую из которых снова объединяем в строку. Последовательность строк выводим с помощью PrintLines.
ЗАДАЧА №838 Шаблон программы
(Время: 1 сек. Память: 16 Мб Сложность: 30%)
Многие команды, участвующие в командных соревнованиях по программированию, используют так называемый «шаблон программы». Он набирается в самом начале соревнования и содержит общее для всех решений - например, открытие и закрытие входных и выходных файлов.
Трехкратный чемпион мира по версии AMC команда Dream Team – не исключение. Во многом их успехи связаны с тем, что они очень тщательно готовятся к соревнованиям, продумывая даже очень мелкие детали. Например, перед последним финалом они во время пробного тура рассчитали, сколько джоулей энергии потратится на набор шаблона.
Организаторы финала использовали весьма странные клавиатуры — жесткость различных клавиш была различной. Таким образом, на нажатие разных клавиш требовалось различное количество энергии.
Эксперименты, проведенные командой Dream Team во время пробного тура, показали следующее. На набор строчной буквы английского алфавита требуется количество энергии, равное сумме цифр ее порядкового номера в алфавите (буквы нумеруются с единицы). На нажатие клавиши «Shift» требуется 10 джоулей энергии (таким образом набор заглавной буквы английского алфавита требует на 10 джоулей больше, чем набор соответствующей ей строчной буквы), нажатие клавиши «Пробел» требует 4 джоуля энергии. Набор цифры x требует (13 – x) джоулей энергии, набор точки – 5 джоулей, точки с запятой – 7 джоулей, запятой – 2 джоуля. Знак равенства, плюс, минус, одинарная и двойная кавычка требуют по 3 джоуля энергии. Закрывающая и открывающая круглые скобки требуют по 1 джоулю, а фигурные, квадратные и угловые (т.е. символы < и >) – по 8. При этом для всех упомянутых знаков препинания на клавиатуре, используемой на финале, существуют отдельные клавиши, и другой возможности набрать соответствующий символ нет. Нажатие клавиши «Enter» (перевод строки) оказалось настолько легким, что энергозатраты на него можно считать нулевыми.
Ваша задача – написать программу, которая по тексту шаблона вычислит энергозатраты на его набор.
Входные данные Входной файл INPUT.TXT содержит шаблон программы, энергетические затраты на набор которого необходимо вычислить. Он содержит только цифры, пробелы, строчные и заглавные буквы английского алфавита, точки, запятые, знаки равенства, плюсы, точки с запятыми, двойные кавычки (“), одинарные кавычки (‘), закрывающие и открывающие круглые, фигурные и квадратные скобки. Его размер не превышает 20000 байт.
Выходные данные В выходной файл OUTPUT.TXT выведите ответ на задачу.
begin
var D := new Dictionary<char, integer>;
var k: integer;
for var i := 1 to 26 do
begin
k := i div 10 + i mod 10;
D.Add(Chr(Ord('A') + i - 1), k + 10);
D.Add(Chr(Ord('a') + i - 1), k);
end;
for var i := 0 to 9 do
D.Add(Chr(Ord('0') + i), 13 - i);
var s := ' .,;+-="''()<>[]{}'+#13#10;
var a := Arr(4,5,2,7,3,3,3,3,3,1,1,8,8,8,8,8,8,0,0);
for var i := 1 to s.Length do
D.Add(s[i], a[i-1]);
var r := ReadAllText('input.txt');
r.Select(c -> D[c]).Sum.Print
end.
Алгоритм решения тут очень простой. Создается таблица, в которой каждому символу сопоставляется числовое значение (“энергия в джоулях”). Читаются друг за другом исходные символы, каждый символ заменяется выбранным из таблицы числовым значеним и эти значения суммируются. После исчерпания входных символов накопленная сумма выводится в качестве результата.
В качестве “таблицы” в приведенной программе выбрана стандартная коллекция Dictionary (словарь). Ключом является символ, значением - энергия в джоулях. Словарь удобен тем, что в нем поиск по ключу быстрый (бинарный), а значение выбирается путем указания ключа в качестве индекса - в программе это D[c].
Основная часть программы - это заполнение словаря, само же решение занимает две строки. Словарь вначале пополняется символами латиницы (в обоих регистрах), затем символами цифр и последними - всеми прочими знаками, которые пришлось просто перечислить.