ХКОИС
ХРРЦ
Регистрация
Забыли пароль?
Логин:
Пароль:
Поиск
Справочные сведения о системе образования Хабаровского края
Новости образования Хабаровского края
Информация и документы из министерства образования и науки Хабаровского края
Хабаровская краевая заочная физико-математическая школа
РЕГИОНАЛЬНАЯ ОЛИМПИАДА ШКОЛЬНИКОВ
Подготовка к олимпиадам по информатике
Подготовка к олимпиадам по информатикеЗадачи прошедших олимпиад > 2008 год. Задачи, рекомендованные для школьного тура
2008 год. Задачи, рекомендованные для школьного тура
Задания для проведения школьного этапа Всероссийской олимпиады школьников по информатике в 2008/2009 учебном году в Хабаровском крае
 
Задача 1. (100 баллов)
 
«Цепочки домино»
 
На столе выложены в цепочку четыре костяшки из одного набора домино. Следует определить, является ли эта цепочка правильной и если да, то можно ли ее замкнуть. Например, [3|2], [2|5], [5|1], [1|3] – правильная и замыкаемая цепочка, а [3|2], [6|6], [3|1], [1|1] — неправильная. Напишите программу, в которой нужно ввести четыре пары чисел от 0 до 6, каждая из которых соответствует костяшке домино, а результатом выполнения программы будет одно из сообщений: «правильная цепочка замкнется», «правильная цепочка не замкнется» или «цепочка неправильная».
 
Решение. Пусть костяшкам соответствуют переменные a1, b1, a2, b2, a3, b3, a4, b4, где a количество точек на левой половинке домино, b – на правой. Цепочка, составленная из костяшек разложенных в порядке ввода данных, является правильной, если логическое выражение (b1=a2) and (b2=a3) and (b3=a4) будет иметь значение «истина». Для того чтобы она могла замкнуться необходимо выполнение условия b4=a1. Решение может быть записано следующим образом:
 
if (b1=a2) and (b2=a3) and (b3=a4) then
                        if b4=a1 then writeln(‘правильная цепочка замкнется’)
                                   else writeln(‘правильная цепочка не замкнется’)
            else writeln(‘цепочка неправильная’)
 
Тестовые примеры 
 
Входные данные Выходные данные
1 2, 2 4, 4 6, 6 1
3 2, 2 6, 6 1, 1 0
3 3, 4 4, 0 0, 0 3
1 2, 2 2, 2 3, 2 4
«правильная цепочка замкнется»
«правильная цепочка не замкнется»
«цепочка неправильная»
«цепочка неправильная»
 
 
Задача 2. (100 баллов)
 
 «Счастливы вместе»
 
Для участников олимпиады школьников по информатике проводится лотерея. Каждый участник получает билет с четырехзначным номером. По условию лотереи выигрышными являются билеты сразу двух участников, если при этом сумма первых двух цифр билета первого участника равна сумме последних двух цифр билета второго или наоборот. Например: 4571 и 1890 – счастливая пара, так как 4+5=9 и 9+0=9, 7712 и 3031 – счастливая пара, так как 1+2=3 и 3+0=3. Напишите программу, в которой вводятся два четырехзначных целых числа, а выводится сообщение «Счастливы вместе», если для введенной пары номеров выполняется условие выигрыша, и сообщение «Повезет в другой раз» в противном случае.
Ограничение: использовать в решении этой задачи функции и процедуры преобразования чисел в строки и наоборот недопустимо.
 
Решение. Необходимо используя операции целочисленного деления и нахождения остатка от целочисленного деления найти четыре суммы цифр, а затем сравнить их попарно, если значения хотя бы одной из двух пар равны – условие выполняется, в противном случае – нет.
Пусть n, m – введенные номера билетов. Вычислим n1:= (n div 1000)+((n div 100) mod 10) – сумму первых двух цифр числа n и n2:=((n div 10) mod 10)+(n mod 10) – сумму последних двух цифр числа n (скобки расставлены для наглядности). Аналогично находятся m1 и m2 – соответствующие суммы для числа m. Условие «Счастливы вместе» выполняется, если истинным является выражение (n1=m2) or (n2=m1).
 
Тестовые примеры 
 
Входные данные Выходные данные
4315, 2411
4782, 9183
9213, 1129
1223, 3322
4498, 3399
6588, 8734
«Счастливы вместе»
«Счастливы вместе»
«Счастливы вместе»
«Повезет в другой раз»
«Повезет в другой раз»
«Повезет в другой раз»
 
 
Задача 3. (100 баллов)
 
«Канал связи»
 
Совсем недавно две школы Хабаровска решили провести между своими зданиями новый канал связи с использованием оптико-волоконной линии для проведения совместных видеоуроков. По каналу связи данные передаются в двоичном виде, то есть с помощью «0» и «1». Однако оказалось, что поскольку школы находятся далеко друг от друга, в канале связи иногда возникают помехи, из-за которых «1» может быть прочитана как «0» или наоборот. Для устранения проблемы решено было каждый сигнал передавать трижды, то есть вместо «1» передавать «111», а вместо «0» — «000». При приеме такого сообщения каждая тройка цифр преобразуется в ту цифру, которая встречается в этой тройке не менее двух раз. Например, «110001» -> «10». Напишите программу, которая будет восстанавливать исходный сигнал, переданный по каналу связи. Входные данные: строка, состоящая из «0» и «1», представляющая сообщение, полученное по каналу связи. Длина сообщения кратна трем. Выходные данные: строка, состоящая из «0» и «1», представляющая исходное сообщение.
 
Решение. Решение сводится к считыванию сообщения по три символа с подсчетом количества, например, единиц. Если количество единиц в тройке больше одной, то на выход записывается «1», в противном случае — «0».
 
Тестовые примеры  
 
Входные данные Выходные данные
110010001000111
10001
101010101010101
10101
111011010101000
11010
110000000000000111011010101000
1000011010

Задача 4. (100 баллов)
 
«Самый активный абитуриент»
 
В стране Х каждый выпускник школы получает аттестат с уникальным номером. Так же как и в нашей стране, выпускники школ страны Х могут подавать документы на конкурс сразу в несколько вузов. После окончания приема документов приемные комиссии всех вузов объединяют списки номеров аттестатов абитуриентов в один общий список. Требуется найти номер аттестата абитуриента, подавшего документы в наибольшее число вузов. Входные данные: N – количество записей в общем списке. Список из N чисел – номеров абитуриентов. Выходные данные: номер самого активного абитуриента. Если таких абитуриентов несколько, указать любого.
Пример:
N=10
2, 67, 3, 8, 5, 67, 6, 7, 67, 5
Ответ: 67
 
Решение. Задача заключается в формировании числового массива номеров аттестатов и нахождении в нем числа, встречающегося максимальное количество раз. Для организации поиска более простым путем рекомендуется отсортировать массив, тогда все одинаковые номера будут расположены рядом. Задача сведется к поиску в массиве самой длинной последовательности стоящих рядом одинаковых чисел.
 
Тестовые примеры
 
Входные данные Выходные данные
15
77, 12, 23, 12, 34, 655, 877, 23, 34, 231, 4554, 787, 32, 12, 41
12
10
123, 654, 123, 654, 777, 123, 654, 888, 654, 123
654 или 123
15
1, 2, 3, 7, 8, 9, 4, 5, 6, 14, 25, 36, 74, 96, 85
Любое из введенных чисел
Copyright © 2005–2017 ХабЦНИТ ТОГУ Отправить письмо
Создание сайтов в Хабаровске
весы электронные торговые