ХКОИС
ХРРЦ
Регистрация
Забыли пароль?
Логин:
Пароль:
Поиск
Справочные сведения о системе образования Хабаровского края
Новости образования Хабаровского края
Информация и документы из министерства образования и науки Хабаровского края
Хабаровская краевая заочная физико-математическая школа
РЕГИОНАЛЬНАЯ ОЛИМПИАДА ШКОЛЬНИКОВ
Подготовка к олимпиадам по информатике
Подготовка к олимпиадам по информатикеЗадачи прошедших олимпиад > 2011 год. Задачи, рекомендованные для муниципального тура.
2011 год. Задачи, рекомендованные для муниципального тура.

 

Задача 1. «Что общего?» (100 баллов)
 
            Дано два натуральных числа A и B. Написать программу, которая будет находить и распечатывать все общие делители этих чисел в порядке убывания их значений.
Входные данные:
Два натуральных числа A и B (0<A<1000, 0<B<1000).
Выходные данные:
Общие делители заданных чисел в порядке убывания их значений.
 
Тестовые примеры входных и выходных данных
Входные данные
Выходные данные
10
12
2
1
225
15
15
5
3
1
13
17
1
196
28
28
14
7
4
2
1
45
225
45
15
9
5
3
1
 
Указания к решению
 
            Задачу можно решить перебором в порядке убывания в цикле всех значений счетчика, начиная от меньшего из двух чисел до 1. Если текущее значение счетчика является делителем каждого из заданных чисел, то его выводят на печать.


Задача 2. «Подводная лодка — шпионка» (100 баллов)
            Автоматическая подводная лодка — шпионка оснащена устройством, удерживающим ее на одном из четырех курсов (S-юг, N-север, W-запад, E-восток) с задаваемой относительно воды скоростью. В районе действия подводной лодки дрейфует буй. Буй находится под водой и движется только под действием течения. Спутник-шпион определяет параметры подводного течения, измеряя проекции скорости движения буя на направления к сторонам света.
            Лодка отплыла от буя и стала плавать под водой в соответствии с заданным алгоритмом, последовательно задающим временные интервалы и скорость движения лодки относительно воды в определенном направлении.
Необходимо написать программу, определяющую расстояние от лодки до стартовой точки после завершения шпионской миссии. Для этого представлен обработанный протокол движения лодки и буя, в котором перечислены данные о движении лодки и буя в последовательные интервалы времени. В течение каждого интервала параметры движения лодки и буя не изменяются.
Входные данные:
Целое число N – количество интервалов. 0<N<6.
N последовательностей данных со следующим содержанием: продолжительность интервала (с), направление движения лодки (символ S, N, W или E), скорость движения лодки (м/с), проекция скорости движения буя в северном направлении (м/с), проекция скорости движения буя в восточном направлении (м/с). При движении буя  на юг или на запад соответствующие проекции скорости имеют отрицательную величину.  Скорости течения и движения лодки не превышают 30 км/ч, время наблюдения не более 12 часов. Ввод данных можно выполнять в столбец.
Выходные данные:
Число – расстояние лодки от начального пункта в метрах с точностью до одного знака после запятой.
Тестовые примеры входных и выходных данных
Входные данные
Выходные данные
2
100 S 5 1 0
1000 S 2 0 1
2600.0
4
100 N 3 1 1
300 S 2 3 0
200 W 4 0 1
150 E 3 1 1
855.8
4
150 E 3 1 1
200 W 4 0 1
300 S 2 3 0
100 N 3 1 1
855.8
4
350 E 3 2 -3
240 W 3 4 -2
300 S 2 -3 2
1000 N 3 -8 -3
6032.0
4
100 E 3 2 -3
100 S 3 -4 -2
100 W 3 -2 2
100 N 3 4 3
0.0
 
Указания к решению
 
Для определенности будем считать, что в начальный момент лодка имеет координаты x=0, y=0.
После ввода очередной серии данных следует увеличить x и y на смещение от подводного течения, соответственно на величины проекций скорости на меридиан или на параллель, умноженных на продолжительность текущего интервала. Затем, следует определить, в каком направлении двигалась лодка относительно воды и изменить соответствующую координату на величину скорости лодки, умноженную на длину интервала времени. Знак изменения координаты определяется направлением движения лодки.
После завершения  обработки последовательностей данных нужно вычислить . Это и будет искомое расстояние.
Файл «Подводная лодка.xls» может использоваться для генерации дополнительных тестов.
Программа на Паскале, соответствующая описанному решению, приведена ниже.
Program apl;
var x,y,v1,vx,vy,t:real;
n,i:integer;
s:char;
begin
readln (n);
x:=0;
y:=0;
for i:=1 to n do
begin
readln(t);
readln(s);
readln(v1)
readln(vy);
readln(vx);
x:=x+t*vx;
y:=y+t*vy;
case s of
'N': y:=y+t*v1;
'S': y:=y-t*v1;
'E': x:=x+t*v1;
'W': x:=x-t*v1
end;
end;
writeln(sqrt(x*x+y*y):10:1);
end.
Задача 3. «Оптимистический прогноз или мат в два хода» (100 баллов)
 
В крестики-нолики играют на клеточном поле размером 5 x 5. Игроки ходят по очереди. Первый ход делают крестики. Считается, что крестики (нолики) выиграли, если на поле найдется по горизонтали, вертикали или диагонали цепочка, состоящая подряд из 5 крестиков (ноликов).
Имеется частично заполненное крестиками и ноликами поле. Пусть игровая ситуация, возникающая после очередного хода игрока, называется предвыигрышной, если в случае любого ответного хода соперника, найдется следующий ход, являющийся победным.
Написать программу, проверяющую, может ли игрок, делающий очередной ход, создать для себя предвыигрышную ситуацию или, по аналогии с шахматами, объявить мат в два хода.
Входные данные:
Пять строк, каждая из которых содержит 5 символов из числа нулей «Ø», крестиков «+» или звездочек «*», означающих пустую клетку. Гарантируется, что входные данные являются корректными.
Выходные данные:
Если игрок, делающий очередной ход, может создать предвыигрышную для себя ситуацию, то выводятся: слово «Yes», затем через пробел символ («Ø» или «+»), указывающий какой игрок делает ход, затем через пробел, разделенные пробелом номера строки и столбца клетки, в которую должен быть сделан очередной ход.
Если предвыигрышную ситуацию для игрока, делающего очередной ход, создать невозможно, то выводится слово «No».
Тестовые примеры входных и выходных данных
Входные данные
Выходные данные
*000*
****+
**0++
**+0*
+++*0
Yes 0 1 1
*000*
****+
**0+*
**+0*
+++*0
No
+*00*
*+0*0
*0+**
0****
*+++*
Yes + 5 5
+*000
*+0**
+0+**
0****
*+++*
No
+*00*
*+0**
+0+**
0****
*++**
No
 
Указания к решению
 
            Для удобства обработки данных рекомендуется перейти от текстовых строк к двумерному числовому массиву, поставив крестикам в соответствие 1, ноликам (-1), а пустым клеткам 0.
Сначала следует определить, какой игрок делает очередной ход. Для этого следует подсчитать количество знаков «+» и «0» (найти сумму значений всех элементов массива). Если их поровну, сумма равна 0, то ход «+», если «0» на один меньше, сумма равна (-1), то ходят «0». Другие ситуации не являются корректными и не должны рассматриваться. В тестовых примерах данные должны быть корректными.
            Для игрока, делающего очередной ход ситуация, приводящая к обязательному выигрышу его следующим ходом возможна в следующем случае. В главных диагоналях, вертикалях или горизонталях имеются не менее двух различных цепочек из четырех знаков игрока, делающего ход (для крестиков и для ноликов сумма элементов цепочки будет соответственно равна 4 и -4), с пустыми клетками в разных местах.
            Решить задачу можно организовав перебор всех возможных ходов игрока (поочередно ставить нужный знак во все пустые клетки). Для каждой позиции проверять, является ли она предвыигрышной, то есть, существует не менее двух цепочек, которые можно закончить разными ходами. После тестирования очередной позиции нужно удалять (обнулять) соответствующий элемент массива. Если была найдена предвыигрышная позиция – проверка прекращается.
 


Задача 4. «Три буквы» (100 баллов)
На доске в одну строку написано решение примера на сложение двух целых чисел. Cлева от знака равенства «=» записаны два целых числа, разделенных символом «+», справа записано целое число являющееся их суммой.
В записи равенства некоторые цифры от 1 до 9 заменили одной из трех букв — «A», «B» или «C». Каждая буква заменяет одинаковые цифры. Разные буквы соответствуют разным цифрам. Буквами могли заменить не все соответствующие им цифры.
            Напишите программу, проводящую обратную замену букв на цифры, получающую верное равенство.
Входные данные:
Три строки, соответствующие первому и второму слагаемым и их сумме, содержащие цифры и символы «A», «B», «C». Длина каждой строки от 1 до 5 символов.
Гарантируется, что входные данные являются корректными.
Выходные данные:
В первой строке выводятся разделенные пробелами значения цифр, соответствующих символам «A», «B», «C» соответственно.
Во второй строке выводится строка, соответствующая восстановленной записи примера.
Если возможно несколько вариантов решения задачи, то выводится любой из них.
Верный ответ может отличаться от эталона. При проверке следует убедиться, что получено верное равенство!
Тестовые примеры входных и выходных данных
Входные данные
Выходные данные (вариант)
A54C
C2A
ABB4
3
6
1
3541+123=3664
6ABC
11BB
766B
5
3
2
6532+1133=7665
442CC
AA8B1
56AA4
1
8
3
44233+11881=56114
C00AB
BA07
CB2A8
2
1
4
40021+1207=41228
9A0002B
CC00045
BC500066
7
1
8
9700021+8800045=18500066
Указания к решению
Можно организовать три вложенных цикла с параметрами a, b, c, изменяющимися от 1 до 9. Для каждой тройки, не удовлетворяющей условию, что хотя бы две цифры совпадают (можно проверять равенство (a-b)*(b-c)*(a-c)=0), следует вычислить значения каждого из трех чисел, заменив буквы цифрами. Если сумма двух первых чисел будет равна третьему, то найдено искомое решение.
По условию задачи данные в тестовых примерах должны быть корректными, то есть для них обязательно должна существовать соответствующая тройка цифр.
Copyright © 2005–2017 ХабЦНИТ ТОГУ Отправить письмо
Создание сайтов в Хабаровске