Имя входного файла: input.txt Имя выходного файла: output.txt Максимальное время работы на одном тесте: 1 секунда Максимальный объем используемой памяти: 64 мегабайта
Андрей живет в одном из северных районов Пермского края и даже зимой каждый день ходит в школу, расположенную в соседнем селе, – по будням на обычные уроки, а по выходным — на любимые факультативные занятия по программированию.
Поскольку с современными дорогами в северных районах не очень хорошо, Андрей добирается до школы по замерзшим руслам многочисленных ручьев, протекающих от его родной деревни до соседнего села. Как и все местные жители, Андрей знает наперед, сколько времени займет путь от деревни до села в каждый из коротких зимних дней. Также мальчику известно, сколько дней подряд (максимально) можно пользоваться одним и тем же маршрутом, чтобы не рассердить хозяина леса (об этом в начале зимы Андрею сообщает бабушка).
Андрей только первую зиму учится программировать и не умеет решать задачи, которые составляет жюри областных олимпиад, поэтому он обращается к вам за помощью. Напишите программу, которая позволит мальчику узнать, какой путь выбирать в каждый из дней, чтобы суммарно в течение заданного периода потратить как можно меньше времени на дорогу и не рассердить хозяина леса.
Формат входных данных
Первая строка входного файла содержит два числа: n — количество учебных дней, в течение которых Андрей может пользоваться зимним путем; m — количество различных маршрутов (1 ≤ n ≤ 100, 2 ≤ m ≤ 100).
Вторая строка входного файла содержит m целых чисел ai (1 ≤ i ≤ m), задающих для каждого маршрута максимальное количество дней подряд, когда его можно использовать, чтобы не рассердить сами знаете кого (1 ≤ ai ≤ n).
Следующие m строк содержат по n неотрицательных целых чисел, при этом j-е число i-й строки означает количество единиц времени, которое Андрей потратить используя i-й маршрут в j-й день. Все эти числа не превышают 106. Числа в строках разделяются пробелами.
Формат выходных данных
В первой строке выходного файла выведите одно число — минимальное количество единиц времени, которое он потратит на дорогу. На второй строке выведите n целых чисел, каждое из которых определяет для каждого дня номер маршрута, который должен использовать Андрей в этот день.
Примеры входного и выходного файлов
input.txt output.txt 5 2 9 2 2 1 1 2 2 1 1 3 6 4 1 5 2 3 1 1
Имя входного файла: input.txt Имя выходного файла: output.txt Максимальное время работы на одном тесте: 1 секунда Максимальный объем используемой памяти: 64 мегабайта
В отдаленном будущем в нашем крае планируется создать новый заповедник для сохранения уцелевших диких животных. Для того, чтобы определить количество работников, которые будут обслуживать заповедники, было решено вычислить площадь территории, где встречаются все виды редких животных.
Для каждого представителя фауны известны три точки, ограничивающие область, в которой его можно встретить (точки соединяются прямыми линиями). Очевидно, заповедник будет представлять собой пересечение всех таких областей.
Формат входных данных
Первая строка входного файла содержит число n — количество редких животных, которые пока еще встречаются в Пермском крае (этот список изменяется, поэтому необходимо рассматривать различные варианты в следующем диапазоне: 1 ≤ n ≤ 100).
Следующие n строк содержат по шесть целых чисел – координаты точек X1, Y1, X2, Y2, X3, Y3 (точки перечислены в порядке обхода против часовой стрелки), определяющих область обитания. Все координаты не превышают по модулю 10000. При решении данной задачи можно считать, что территория представляет собой плоскость.
Формат выходных данных
В первой строке выходного файла выведите одно число — площадь территории, которая будет объявлена заповедной, указав в ответе три знака в дробной части.
Примеры входного и выходного файлов
input.txt output.txt 2 0.250 0 0 1 0 0 1 0 0 1 0 1 1
Имя входного файла: input.txt Имя выходного файла: output.txt Максимальное время работы на одном тесте: 1 секунда Максимальный объем используемой памяти: 64 мегабайта
Витя и Маша живут в одном подъезде и учатся в одном классе специализированной школы, где в течение недели проводится так много уроков информатики, что даже хватает времени на изучение программирования. Конечно, таких школ в городе, где живут Маша и Витя, немного, и им приходится долго ехать на автобусе, прежде чем приступить к учебе.
Проводя много времени в дороге, попутчики придумали много интересных способов определения счастливых билетов. Как известно, номера билетов состоят из шести цифр. Однажды Витя выбрал m целых чисел из диапазона от 0 до 999, а Маша – n целых, не выбранных Витей чисел из этого же диапазона. Они решили, что будут считать билет счастливым, если, во-первых, первые три цифры образуют число, выбранное Машей, во-вторых, последние три цифры – число, выбранное Витей, в-третьих, оба числа дают одинаковый остаток при делении на 13. Первой билет всегда покупает Маша, поэтому пока Витя расплачивается, она успевает определить, является ли билет (а значит и весь день) счастливым. Каждый раз проверяется только билет Маши. Как только число встречается в счастливом билете, оно считается потерявшим свои магические свойства и исключается из множества выбранных.
Номера продаваемых билетов, вообще говоря, могут быть произвольными. Для того чтобы Маша в течение нескольких дней подряд покупала счастливые билеты, необходимо, чтобы они доставались ей в определенной последовательности. Напишите программу, которая определяет максимальную длину такой последовательности, а также номера билетов, которые могут соответствовать каждому из дней.
Формат входных данных Первая строка входного файла содержит два целых числа m и n (1 ≤ m, n ≤ 100).
Вторая строка содержит m чисел, выбранных Витей.
Третья строка содержит n чисел, выбранных Машей.
Формат выходных данных
В первой строке выходного файла выведите одно число k — максимальное количество счастливых дней, которые могут идти подряд.
В следующих k строках выведите в порядке возрастания номера билетов, которые должны выпадать в каждый из дней.
Примеры входного и выходного файлов
input.txt output.txt 2 3 2 123 456 014456 14 136 999 136123
Имя входного файла: input.txt Имя выходного файла: output.txt Максимальное время работы на одном тесте: 1 секунда Максимальный объем используемой памяти: 64 мегабайта
Будем называть разнообразностью строки количество символов, которые встречаются в ней ровно один раз. Например, разнообразность строки «INFORMATICS» — 9, поскольку символы «A», «C», «F», «R», «M», «N», «O», «S» и «T» встречаются в ней ровно один раз.
Для заданной строки S найдите подстроку, которая имеет наибольшую разнообразность. Если таких подстрок несколько, то найдите ту, которая минимальна в лексикографическом порядке.
Строка A меньше строки B в лексикографическом порядке, если выполняется одно из условий:
Например, строка «SOL» меньше в лексикографическом порядке строк «SOLVE», «START», «TIME».
Формат входных данных
Входной файл содержит строку, состоящую только из заглавных букв латинского алфавита. Длина строки не превышает 2000 символов.
Формат выходных данных
Выведите в выходной файл подстроку исходной строки, имеющую максимальную разнообразность среди всех ее подстрок. Если таких подстрок несколько, выведите минимальную в лексикографическом порядке.
Примеры входного и выходного файлов
input.txt output.txt ABBAC BAC OLYMP OLYMP AAA A
© Пермский областной Оргкомитет олимпиад школьников по информатике, 2005-2006