|
Задачи районной олимпиады по информатике (2007 - 2008 уч.год)
Во всех задачах
Имя входного файла:
| input.txt
| Имя выходного файла:
| output.txt
| Ограничение по времени:
| 1 секунда
| Ограничение по памяти:
| 64 мегабайта
|
1. Сумма и произведение цифр
Дано четырехзначное число. Найти сумму и произведение цифр данного числа.
Входные данные:
Одно целое четырехзначное число N (1000≤N≤9999).
Входные данные:
Вывести в первой строке сумму цифр числа N, а во второй строке произведение цифр числа N.
Пример:
input.txt
| output.txt
| 1234
| 10
24
|
2. Бутявки
Мир наш, как это всем хорошо известно, развивается. Строятся города, люди улетают в космос, вымирают цивилизации… Так вот, пока нас тут не было, существенно увеличилась мировая популяция бутявок. Каждая из бутявок по-прежнему имеет свой рост, а заниматься мы с вами будем всё тем же — искать бутявок с заданным ростом.
Входные данные:
Первая строка входного файла содержит натуральные числа N и K (1≤K, N≤10000). Во второй строке N натуральных чисел не превышающий 2*109 — рост каждой из N бутявок соответственно. В третьей строке K натуральных чисел, задающие бутявкин рост, который мы будем искать.
Выходные данные:
Для каждого из K запросов выведите в отдельную строку файла YES, если бутявка с таким ростом встречается среди заданных и NO в противном случае.
Пример:
input.txt
| output.txt
| 3 4
1 6 9
7 9 10 1
| NO
YES
NO
YES
|
3. Упорядоченные буквы.
Дана строка, содержащая цифры, прописные и строчные латинские буквы длиной не более 250 символов. Если буквы в строке упорядочены по алфавиту, то вывести 0; в противном случае вывести номер первого символа строки, нарушающего алфавитный порядок.
Входные данные:
строка из латинских строчных и заглавных символов и цифр.
Выходные данные:
Вывести 0, если буквы в строке упорядочены по алфавиту или номер первого символа строки, нарушающего алфавитный порядок, если буквы в строке упорядочены не по алфавиту.
Пример:
input.txt
| output.txt
| abcd12
| 0
| Ab23dc
| 6
|
4. Малыш играет в "Морской бой"
Малыш играет в "Морской бой". Поле для игры представляет собой квадрат 10 x 10 клеток. На поле отмечены клетки, в которые Малыш уже стрелял. Однако пока он не попал ни в один корабль противника. Требуется определить максимальную длину корабля, который может поместиться в небитых клетках этого поля. Корабль представляет из себя прямоугольник ширины 1 и располагается горизонтально или вертикально. (Гарантируется, что на поле есть хотя бы одна небитая клетка.)
Входные данные:
Входной файл содержит 10 строк по 10 чисел в каждой, числа разделены пробелами. Число 1 означает, что в соответствующую клетку стреляли, число 0 – что в клетку не стреляли.
Выходные данные:
вывести одно число от 1 до 10 – максимальную возможную длину корабля.
Пример
input.txt
| output.txt
| 0 0 0 0 0 0 0 0 0 1
0 0 0 0 0 0 0 0 1 0
0 0 0 0 0 0 0 1 0 0
0 0 0 0 0 0 1 0 0 0
0 0 0 0 0 1 0 0 0 0
0 0 0 0 1 0 0 0 0 0
0 0 0 1 0 0 0 0 0 0
0 0 1 0 0 0 0 0 0 0
0 1 0 0 0 0 0 0 0 0
1 0 0 0 0 0 0 0 0 0
| 9
|
5. Минимумы на отрезке
Дано N чисел. Для каждых K подряд идущих чисел найти минимальное среди них.
Входные данные:
В первой строке даны числа N и K (1≤N≤150000, 1≤K≤10000, K≤N) разделенные пробелом. Во второй строке записано N целых чисел через пробел. Числа находятся в диапазоне от -32768 до 32767.
Выходные данные:
Для каждых К подряд идущих чисел вывести минимальное из них.
Пример.
input.txt
| output.txt
| 11 3
8 764 1 3 85 2 4 5 77 1 5
| 1 1 1 2 2 2 4 1 1
|
6. Лабиринт
Как известно, из любого лабиринта можно заведомо найти выход, если начать егообходить его от входа, а затем двигаться, все время касаясь левой (или правой – на выбор) стены рукой.
Однако со времен фараоновых гробниц лабиринты строили весьма умные люди, это правило было им известно, и они старались сделать так, чтобы при подобном обходе лабиринта «посетитель» заведомо не попал в самые интересные места, — скажем, в те комнаты, где хранятся главные сокровища.
Например, в лабиринте, схематично изображенном на рисунке, найти выход очень просто, а вот клад — попросту невозможно.
Итак, по имеющемуся плану лабиринта нужно определить, есть ли в нем недоступные области. Причем, обходить лабиринт можно любым способом. Недоступные области могут находиться и одна внутри другой.
Входные данные
В первой строке входного файла задано одно целое число N — размер лабиринта (лабиринт у нас квадратный, 3 ≤ N ≤ 100). Далее N строк содержат по N символов, описывающих сам лабиринт: стенки изображаются звездочками, пустоты — пробелами. Считается, что вход в лабиринт располагается в самой первой строке (мы ведь всегда можем развернуть карту так, как нам удобнее).
Выходные данные
В выходной файл нужно вывести одно число — количество недоступных областей лабиринта. Недоступные области считаются различными, если из одной нельзя попасть в другую
Пример
Input.txt
| output.txt
| 7
***,***
*.....*
*.***.*
*.*..*.*
*.***.*
*.....*
*******
| 1
|
7. Удаление простых чисел из массива.
Дан массив из N (1≤N≤10000) натуральных чисел в интервале от 1 до 100000. Удалить из массива все простые числа и вывести его содержимое.
Входные данные:
В первой строке одно число N. Во второй строке расположены N чисел, разделенных пробелами..
Выходные данные:
Вывести в одной строке через один пробел массив после удаления из него простых чисел.
input.txt
| output.txt
| 8
1 2 3 4 5 6 7 8
| 1 4 6 8
| 5
7 7 7 7 7
|
|
8. Острова
В океане есть архипелаг из N прямоугольных островков. Стороны прямоугольников расположены параллельно осям координат. Чтобы переходить с острова на остров, не замочив ног, Робинзону, потерпевшему кораблекрушение на архипелаге, приходится носить с собой длинную доску. Напишите программу, вычисляющую минимальную длину доски, с помощью которой Робинзон сможет попасть с любого острова на любой другой. Переходить на нужный остров можно, используя в качестве промежуточных пунктов путешествия остальные острова. Длина доски, необходимая для перехода с одного острова на другой, равна расстоянию между ближайшими точками этих островов.
Входные данные:
В первой строке входного файла содержится одно целое число N (2≤N≤50) – количество островков. Далее следует N строк, каждая строка содержит четыре целых числа x1, y1, x2, y2, разделенных пробелами – координаты противоположных углов прямоугольного острова (0<x1,x2,y1,y2<1000).
Выходные данные:
Вывести одно число с точностью 10-3 – минимальную длину доски для путешествия.
Пример
input.txt
| output.txt
| 3
1 3 3 4
3 1 4 2
5 3 6 4
| 1.414
|
Дополнение:Каталог Prolems (скачать)
|
|
|
