Реферат: Районная олимпиада школьников по программированию Сибгиу, 2007

Районная олимпиада школьников по программированию СибГИУ, 2007

А. Головоломка


Максимальное время: 0,5 с.

Максимальная память: 8 MB


В коробке 33 находится восемь подвижных квадратов, пронумерованных от 1 до 8, и одно пустое место. Любой квадрат, прилегающий к пустому месту, можно передвинуть на это место, при этом пустое место окажется в позиции, занимаемой до этого квадратом.

Составить программу, расставляющую квадраты в порядке их номеров.

Примечание:

По условиям тестов, требуемое количество ходов не превышает 15.

^ Входной файл содержит исходное расположение пронумерованных квадратов, разделенных пробелами, по три в каждой строке. Пустое место отмечается цифрой “0”.

^ Выходной файл:

Первая строка содержит количество шагов.

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



Пример:

Input.txt

1 2 3

0 4 6

7 5 8

Output.txt

3

2 2

3 2

3 3

^ Б. Двоичная система


Максимальное время: 0,3 с.

Максимальная память: 8 MB


Составить программу для перевода числа N (0  N  231-1) из десятичной системы счисления в двоичную систему счисления.

Входной файл содержит исходное число, представленное в десятичной системе счисления.

^ Выходной файл должен содержать исходное число, представленное в двоичной системе счисления.

Пример:

Input.txt

1981

Output.txt

11110111101

^ В. Квадрат числа


Максимальное время: 0,3 с.

Максимальная память: 8 MB


Дано натуральное число N. На интервале от 1 до N найти все такие числа, запись которых совпадает с последними цифрами записи их квадрата.

^ Входной файл содержит натуральное число N (1  N  10000).

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

Пример:

Input.txt

30

Output.txt

1 5 6 25

^ Г. Массив


Максимальное время: 1 с.

Максимальная память: 10 MB


Задан одномерный массив натуральных чисел размером N. Определить количество неповторяющихся чисел заданного массива.

Входной файл

Первая строка содержит натуральное число N (1  ^ N  50000).

Вторая строка содержит N целых чисел Mi, разделенные пробелами (1  i  N; |Mi|  109). Гарантируется, что количество неповторяющихся чисел не превышает 500.

Выходной файл должен содержать:

 в первой строке - количество неповторяющихся чисел;

 во второй строке - все неповторяющиеся числа, разделенные между собой одним пробелом, в порядке их первого вхождения в исходный массив.

Пример:

Input.txt

10

4 2 3 2 5 4 1 5 1 3

Output.txt

5

4 2 3 5 1

^ Д. Матрица


Максимальное время: 0,5 с.

Максимальная память: 10 MB


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

^ Входной файл

В первой строке содержаться два целых числа M и N - число строк и столбцов матрицы соответственно, разделенные пробелом (1  M, N  100).

В последующих M строках записывается исходная матрица. Элементы матрицы разделяются пробелами и не превышают по абсолютному значению 10000.

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

Пример:

Input.txt

4 4

1 2 4 7

3 4 7 8

2 3 5 6

4 5 6 5

Output.txt

4 5 7 8

3 4 6 7

2 3 5 6

1 2 4 5

^ Е. Одинаковые числа


Максимальное время: 0,3 с.

Максимальная память: 8 MB


Задан массив из пяти произвольных целых чисел. Если среди них одинаковы 5 чисел, то вывести 1, иначе, если одинаковы 4 числа, то вывести 2, иначе, если одинаковы 3 числа, то вывести 3, иначе, если одинаковы 2 числа, то вывести 4, иначе вывести число 5.

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

Выходной файл должен содержать целое число от 1 до 5.

Пример 1:

Input.txt

1 1 1 1 1

Output.txt

1


Пример 2:

Input.txt

1 2 3 4 5

Output.txt

5

Ж. Слова


Максимальное время: 0,3 с.

^ Максимальная память: 8 MB


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

^ Входной файл

Содержит две строки, в каждой из которых записано по одному предложению. Слова в предложении разделены пробелами (возможно несколькими). В конце предложения ставится точка. Длина строки не превышает 255 символов.

^ Выходной файл должен содержать самое длинное общее слово или сообщение "совпадений нет" (без кавычек), если общих слов нет.

Пример:

Input.txt

В лесу зимой родилась елочка.

Маленькая елочка мерзнет зимой.

Output.txt

елочка

З. Сумма


Максимальное время: 0,5 с.

^ Максимальная память: 8 MB


Составить программу нахождения суммы всех целых чисел, лежащих между 1 и N, включая границы.

Входной файл содержит целое число N (|N|  10000).

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

Пример 1:

Input.txt

2

Output.txt

3

Пример 2:

Input.txt

-3

Output.txt

-5

^ И. Треугольник


Максимальное время: 0,3 с.

Максимальная память: 8 MB


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

^ Входной файл состоит из трех строк, каждая из которых содержит координаты концов одного отрезка - четыре целых числа, по модулю не превышающие 1000, которые записываются в формате "X1Y1X2Y2".

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

Пример 1:

Input.txt

0 0 4 3

0 0 4 0

4 0 4 3

Output.txt

6.000


Пример 2:

Input.txt

0 0 4 3

0 -3 4 0

4 0 4 3

Output.txt

IMPOSSIBLE

^ К. Японский календарь


Максимальное время: 0,3 с.

Максимальная память: 8 MB


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

В качестве отсчета может быть взят 1984 год - год зеленой крысы.

Составить программу, которая для заданного года N определяет его название по старояпонскому календарю.

Входной файл содержит заданный год N (0  N  2100).

Выходной файл должен содержать две строки: название подцикла и название года.

Пример:

Input.txt

1984

Output.txt

зеленый

крыса



Страница из