Школа программиста
Резервная копия - VPS Hoster 

Забыли пароль?
[задачи] [курсы] [олимпиады] [регистрация]
Логин:   Пароль:    
Скрыть меню
О школе
Правила
Олимпиады
Фотоальбом
Гостевая
Форум
Архив олимпиад
Архив задач
Состояние системы
Рейтинг
Курсы
Новичкам
Работа в системе
Алгоритмы
Курсы ККДП
Дистрибутивы
Ссылки

HotLog


 
[Положение] [Расписание] [Архив] [Содержание] [Задачи] [Рейтинг]

Задачи олимпиады "Тринадцатая командная олимпиада"

Задача A. Все, что движется

(Время: 1 сек. Память: 16 Мб)

Дано поле N×M и объекты на нем в моменты времени T и T+1. Каждый объект представлен одной английской буквой и в любой момент времени может занимать ровно одну клетку поля.

Объект движется, если в два последовательных момента времени его положения различаются.

Найдите все, что движется.

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

В первой строке входного файла INPUT.TXT записаны два целых числа N и M (1 ≤ N, M ≤ 100). В следующих N строках по M символов – поле в момент времени T. Каждый символ либо является точкой «.», и это означает, что в этом месте поля ничего нет, либо английская буква, обозначающая то, что в этом месте находится объект. Никакие два различных объекта не обозначены одним и тем же символом.

Далее идет пустая строка.

В следующих N строках находится описание того же поля в момент времени T+1 в том же формате. Множество объектов, находящихся на поле в момент времени T, равно множеству объектов в момент времени T + 1.

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

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

Примеры

INPUT.TXTOUTPUT.TXT
12 2
.A
..

A.
..
1
A
23 3
x.O
.X.
.o.

x.O
.X.
.o.
0

Задача B. Орфография

(Время: 1 сек. Память: 16 Мб)

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

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

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

Входной файл INPUT.TXT содержит целое число K - номер лишней буквы, а затем через один или несколько пробелов записано слово S, состоящее из английских букв верхнего регистра. Гарантируется, что номер буквы не превышает длину слова. Длина слова не более 80 символов.

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

В выходной файл OUTPUT.TXT выведите исправленное слово.

Примеры

INPUT.TXTOUTPUT.TXT
14 MISTSPELLMISSPELL
22       ABCAC

Задача C. Простые числа - 2

(Время: 1 сек. Память: 16 Мб)

Знаете ли вы, что такое простое число? Простое число – это натуральное число, имеющее ровно два различных натуральных делителя: единицу и самого себя. Все остальные числа, кроме единицы, называются составными. Например, числа 2, 3, 5, 7, 11 являются простыми. А числа 4, 6, 10 – составными.

Требуется из заданного набора чисел выбрать одно, имеющее максимальное количество простых делителей. Например, 30 имеет три простых делителя (2, 3 и 5), а 40 – только два (2 и 5).

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

Первая строка входного файла INPUT.TXT содержит число N – количество чисел в наборе. Во второй строке теста содержится N чисел, разделенных пробелом. Все числа во входных данных целые, принимающие значения от 2 до 1024.

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

В выходной файл OUTPUT.TXT выведите число с максимальным количеством простых делителей. Если таких чисел несколько, выведите наименьшее из них.

Примеры

INPUT.TXTOUTPUT.TXT
110
3 5 7 9 11 13 15 17 19 21
15
211
2 4 6 8 10 13 39 105 200 201 143
105

Задача D. Bizons

(Время: 1 сек. Память: 16 Мб)

Как-то раз широко известная в узком кругу команда «Bizons» приехала в город Барнаул для участия в олимпиаде. Первым делом им надо было поселиться в отеле, но ребята так долго были в пути, что очень проголодались. Поэтому было принято решение заглянуть в кафе по пути в отель, но, так как участникам команды скучно ходить по одним и тем же местам, они договорились выбрать такой маршрут, в каждой точке которого они окажутся ровно один раз. По счастливой случайности у одного из участников команды в смартфоне оказалась карта города, которая представляет собой прямоугольное поле, состоящее из N строк и M столбцов. Каждая клетка этого поля принимает одно из следующих значений:

«#» – данная клетка находится в ремонте (проход по ней запрещен);

«.» – пустая клетка;

«S» – клетка, из которой ребята хотят начать свой маршрут;

«H» – клетка, в которой находится отель;

«C» – клетка, в которой располагается кафе;

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

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

Первая строка входного файла INPUT.TXT содержит целые числа N и M (1 ≤ N, M ≤ 100). Каждая из последующих N строк содержит по M символов в соответствии с условием задачи. Гарантируется, что на карте присутствует ровно один символ «S», ровно один символ «H» и ровно один символ «C».

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

В выходной файл OUTPUT.TXT выведите «Yes», если команде «Bizons» удалось добраться до отеля указанным способом, иначе выведите «No».

Примеры

INPUT.TXTOUTPUT.TXT
11 3
SCH
Yes
23 3
S#.
H#.
..C
No

Задача E. Клетки в кругу

(Время: 1 сек. Память: 16 Мб)

Дан действительный радиус круга R и размер клетки L на клеточной бумаге. Известно, что центр круга находится на пересечении линий. Требуется найти число целых клеток, лежащих внутри круга. 0 ≤ R ≤ 25000, 1 < L < 100.

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

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

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

В единственную строку выходного файла OUTPUT.TXT нужно вывести одно натуральное число — количество клеток, целиком лежащих в кругу.

Пример

INPUT.TXTOUTPUT.TXT
15 160

Задача F. Слова

(Время: 1 сек. Память: 16 Мб)

Пусть даны два слова, состоящие из строчных английских букв. Если в этих словах различное число гласных букв, то более красивым считается слово, содержащее больше гласных (гласными буквами считаются буквы a, e, i, o, u). Если же число гласных в двух словах одинаково, более красивым считается то из слов, которое является лексикографически наименьшим.

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

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

Первая строка входного файла INPUT.TXT содержит натуральное число N (N ≤ 104) — количество слов. Далее следует N непустых строк – слова, состоящие не более чем из 100 строчных английских букв.

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

В выходной файл OUTPUT.TXT выведите N cтрок – слова, упорядоченные по красоте.

Пример

INPUT.TXTOUTPUT.TXT
15
abcd
efgh
uggu
ziii
fooo
fooo
ziii
uggu
abcd
efgh

Задача G. Дорога

(Время: 3 сек. Память: 16 Мб)

В Древнем государстве Оссия было два города, между которыми была проложена дорога длиной S метров. Через каждый метр стояли столбики, на каждом из которых по некоторому принципу (этот секретный принцип был известен только древним монахам Шамбалы) было написано по букве (а алфавит там у них был английский). Однажды князь-король Василий I решил, что человек, когда он едет по этой дороге, слишком редко вспоминает о нем. Он решил это исправить. Для этого он повелел на некоторых столбиках вместо буквы написать «Здесь был Вася». По его представлению, человек, проехав любой участок дороги длиной K метров, должен обязательно хоть раз увидеть такую надписью Иными словами, среди каждых K идущих подряд столбиков должен оказаться хоть один, на котором буква заменена на надпись. При этом, чтобы не слишком раздражать монахов (а они люди обидчивые), Василий I приказал выбрать для надписи такие столбики, чтобы среди стертых букв оказалось как можно меньше различных букв английского алфавита.

Помогите боярам выполнить приказ своего повелителя.

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

В первой строке входного файла INPUT.TXT написано одно целое число K (1 ≤ K ≤ 100 000). Во второй строке – без пробелов написано S заглавных английских букв в той последовательности, в которой ими помечены столбики вдоль дороги. Гарантируется, что K ≤ S ≤ 100 000.

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

В первой строке выходного файла OUTPUT.TXT выведите N – минимальное количество различных букв английского алфавита, которые хотя бы на одном столбике придется стереть, чтобы написать «Здесь был Вася». В следующих N строках выведите те заглавные буквы английского алфавита, которые потребуется хоть раз стереть. Буквы можно выводить в любом порядке. Если ответов с минимальным N несколько, можно вывести любой из них.

Примеры

INPUT.TXTOUTPUT.TXT
12
ABA
1
A
22
ABBAA
2
A
B

Задача H. Жук

(Время: 1 сек. Память: 16 Мб)

Петя нашел в Интернете по адресу http://buglab.ru игру-головоломку "Жук", в которой от участников требуется построить для жука лабиринт таким образом, чтобы жук как можно дольше искал выход.

Жук всегда начинает свое движение с левого верхнего угла, а выход всегда находится в правом нижнем. Жук движется не оптимально, а следующим образом: он идет туда, где еще не был, либо был там реже. Т.е. проходя каждую клетку лабиринта, жук запоминает: сколько раз он был в этой клетке и при обдумывании направления своего движения в какой то конкретный момент он смотрит: сколько раз он был в клетке снизу, сколько справа, сколько слева и сколько сверху и движется туда, где он был меньше раз. Если таких направлений несколько и одно из них совпадает с текущим направлением движения, то он не меняет направления, иначе он движется согласно следующим приоритетам: вниз, направо, вверх, налево. Т.е. если минимальное число посещений сразу справа и слева (а двигался он при этом вверх или вниз), то жук идет направо, т.к. у "направо" приоритет выше. Следует заметить, что двигаясь по данному алгоритму жук всегда достигнет выхода в том случае, когда выход существует.

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

Конструктор лабиринта

- кнопка запуска жука Ходы: 0

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

Входной файл INPUT.TXT в первой строке содержит разделенные пробелом целые числа N и M - количество строк и столбцов в лабиринте (4 ≤ N, M ≤ 100). Далее следует N строк, содержащих данные лабиринта построчно. Каждая строка содержит M символов - клетки лабиринта текущей строки, где символ "@" обозначает присутствие стены, а символ пробела - пустое пространство. Гарантируется, что граница лабиринта окружена стеной. Предполагается, что жук начинает свое движение из координаты (2, 2) и заканчивает в координате (M-1, N-1), подразумевается, что в этих координатах нет стен. Гарантируется, что если выход из лабиринта существует, то жук сможет выйти из него, сделав не более 107 шагов.

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

В выходной файл OUTPUT.TXT выведите количество движений жука, если спасительный маршрут для жука существует, и -1 в противном случае.

Примеры

¹INPUT.TXTOUTPUT.TXT
16 6
@@@@@@
@    @
@    @
@ @ @@
@ @  @
@@@@@@
20
28 30
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
@   @    @ @@@@ @  @ @@@@ @@ @
@ @ @@ @  @ @     @ @ @      @
@   @  @ @ @@  @@        @@ @@
@             @           @ @@
@ @  @@ @ @   @@@  @  @   @  @
@     @   @  @    @   @ @@   @
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
630
34 4
@@@@
@ @@
@@ @
@@@@
-1


Красноярский краевой Дворец пионеров, (c)2006 - 2018, ICQ: 151483, E-mail: admin@acmp.ru