ХКОИС
ХРРЦ
Регистрация
Забыли пароль?
Логин:
Пароль:
Поиск
Справочные сведения о системе образования Хабаровского края
Новости образования Хабаровского края
Информация и документы из министерства образования и науки Хабаровского края
Хабаровская краевая заочная физико-математическая школа
РЕГИОНАЛЬНАЯ ОЛИМПИАДА ШКОЛЬНИКОВ
Подготовка к олимпиадам по информатике
Подготовка к олимпиадам по информатикеЗадачи прошедших олимпиад > 2009 год. Задачи, рекомендованные для муниципального тура.
2009 год. Задачи, рекомендованные для муниципального тура.
Задания для проведения муниципального этапа Всероссийской олимпиады школьников по информатике в 2009/2010 учебном году в Хабаровском крае
 
Задача 1. «Арифметика без скобок» (100 баллов)
Арифметическое выражение записано только с использованием латинских букв и знаков четырех арифметических операций (+, -, /, *), буквы в выражении не повторяются. Задаются числа, соответствующие значениям каждой из букв, необходимо вычислить значение выражения.
Входные данные:
Строка, задающая правильно составленное арифметическое выражение, без пробелов и других символов, не предусмотренных условием.
Числа, значения которых должны соответствовать каждой из букв.
Выходные данные:
Число, соответствующее значению выражения, заданного строкой для данного набора значений.
Пример входных и выходных данных:
Входные данные
Выходные данные
Примечание
a+b-c*d/e
2
4
5
10
25
4
 
Было задано выражение 2+4-5*10/25
a*b-c/d+e
3
4
7.2
2
5
13.4
 
Было задано выражение 3*4-7.2/2+5
 
Указания к решению:
Пусть длина строки N символов, тогда в ней будет (N+1)/2 букв и (N-1)/2 знаков арифметических операций. Введем в массив числа, соответствующие буквам. Для удобства обработки, получим из входной строки другую строку (можно использовать массив). В эту строку запишем только знаки операций. Далее задача решается в два прохода. На первом проходе слева направо выполняются операции умножения и деления, при этом изменяются элементы массивов со значениями правого и левого операндов: правый получает значение результата выполненного действия, а левый – 0, знак выполненной операции заменяется на знак предыдущей операции, а если самая первая операция была умножение или деление, то на «+». На втором проходе вычисляется результат последовательного выполнения действий сложения и вычитания.
Примеры:
1. исходное выражение 3*4-7.2/2+5, после первого прохода 0+12-0-3.6+5, после второго прохода получим 13.4;
2. исходное выражение 2+4-5*10/25, на первом проходе сначала 2+4-0-50/25, потом 2+4-0-0-2, после второго прохода получим 4.
 
Задача 2. «Складываем дроби» (100 баллов)
Арифметическое выражение состоит из обыкновенных дробей и арифметических операций сложения и вычитания. Найти значение выражение в виде несократимой обыкновенной дроби.
Входные данные:
N – число дробей.
N пар целых положительных чисел, задающих числитель и знаменатель каждой дроби.
Строка из N-1 знаков «+» или «-».
Выходные данные:
Пара целых чисел, соответствующих числителю и знаменателю вычисленного значения выражения. Знак дроби задается знаком ее числителя.
Пример входных и выходных данных:
Входные данные
Выходные данные
Примечание
3
2 3
1 2
5 6
+-
1 3
Было задано выражение 2/3+1/2-5/6
Результат 1/3
3
1 2
3 4
1 8
--
-3 8
 
Было задано выражение 1/2-3/4-1/8
Результат -3/8
 
Указания к решению:
Задача решается в соответствии с правилами выполнения действий над обыкновенными дробями. Числитель и знаменатель выводимого результата не должны иметь общих делителей кроме 1. Следует учитывать, что при больших значениях числителя или знаменателя возможно переполнение целых данных, поэтому решения, предусматривающие поиск наименьшего общего кратного и сокращение дробей после каждой операции следует оценивать из полного количества баллов, а не выполняющих эти действия из половины баллов.
 
Задача 3. «Всегда посту» (100 баллов)
На КПП режимного объекта ведется учет количества людей находящихся на объекте. Для того, чтобы запутать шпионов и предателей, система учета закодирована. Каждой сотне соответствует знак W, десятку - знак Y, единице – знак M. Вход и выход людей на объект происходит группами. Для каждой группы постовой формирует записку, соответствующую либо числу вошедших на объект, либо числу вышедших из него. В начале записки стоит знак «>», если люди входили и «<», если выходили. Символы W, Y,M в записке могут стоять в произвольном порядке.
Написать программу, обрабатывающую записки и выдающую после каждой обработки сообщение минимальной длины в описанной выше системе обозначений о том, сколько человек находится на объекте. Символы должны быть сгруппированы в порядке убывания величин соответствующих им чисел.
Вначале на объекте находится 2 человека (постовой и дежурный). Данные являются корректными (не может выйти людей больше, чем было на объекте и остаться меньше 2). Максимальное число людей на объекте не превышает 999 человек. Программа заканчивает работу после ввода строки «=».
Входные данные:
Строки, соответствующие запискам постового.
Строка «=».
Выходные данные:
Строки, соответствующие количеству людей на объекте после обработки очередной записки.
Пример входных и выходных данных:
Входные данные
Выходные данные
Примечание
>MMMYYMMMMMM
<MMY
>YYYYYYYYYMM
=
YYYM
YMMMMMMMMM
WYM
Было 2, вошли 29, на объекте 31
Вышли 12, на объекте19
Вошли 92, на объекте 111
Завершение работы программы
 
Указания к решению:
Количество людей на объекте хранится в числовой переменной и первоначально равно 2. После ввода строки в зависимости от того, какой символ стоит в ее начале, прибавляются или отнимаются числа, соответствующие считанным из сообщения символам. После обработки сообщения формируется строка, соответствующая количеству сотен, десятков и единиц в переменной и выводится на экран.
 
Задача 4. «В две шеренги становись» (100 баллов)
В помещение по одному входят люди, каждому из них дается жетон с порядковым номером. Люди выстаиваются в одну шеренгу по росту, если у двух человек одинаковый рост, то впереди стоит тот, кто вошел раньше. Строй перестраивается в две шеренги, при этом, в передней шеренге оказывается каждый второй. Перечислить номера жетонов людей, оказавшихся в задней шеренге в порядке убывания их роста.
Входные данные:
N – число людей.
N значений роста людей.
Выходные данные:
Номера жетонов людей, оказавшихся в задней шеренге в порядке убывания их роста.
Пример входных и выходных данных:
Входные данные
Выходные данные
Примечание
5
175
164
175
188
156
4
3
5
188 175 175 164 156
  4    1     3     2     5
 
Указания к решению:
Заведем два массива, один для хранения данных о росте, другой для хранения номеров жетонов. Одновременно с вводом значений роста i-того человека, присвоим i-элементу массива номеров жетонов значение i. Отсортируем массив роста людей по убыванию любым способом. При сортировке одновременно с перестановкой значений роста двух людей будем переставлять соответствующие им элементы с номерами жетонов. Тогда порядок следования номеров жетонов будет соответствовать порядку расстановки людей в одну шеренгу.
По окончании выведем на печать значения элементов массива номеров жетонов, стоящие на нечетных местах.
Copyright © 2005–2017 ХабЦНИТ ТОГУ Отправить письмо
Создание сайтов в Хабаровске