ХКОИС
ХРРЦ
Регистрация
Забыли пароль?
Логин:
Пароль:
Поиск
Справочные сведения о системе образования Хабаровского края
Новости образования Хабаровского края
Информация и документы из министерства образования и науки Хабаровского края
Хабаровская краевая заочная физико-математическая школа
РЕГИОНАЛЬНАЯ ОЛИМПИАДА ШКОЛЬНИКОВ
Подготовка к олимпиадам по информатике
Подготовка к олимпиадам по информатикеЗадачи прошедших олимпиад > 2013 год. Задачи, рекомендованные для муниципального тура.
2013 год. Задачи, рекомендованные для муниципального тура.
Задачи муниципального тура олимпиады школьников по информатике и ИКТ
(Хабаровский край, 2013-2014 учебный год)
 
Задача 1. Робот-пылесос (100 баллов)
Шагающий робот-пылесос работает по программе, составленной его хозяином. Программа состоит из набора команд, задающих направление движения (Вперед-F, Назад-B, Влево-L, Вправо-R) аргументами которых является количество шагов (число от 1 до 19).
Нужно написать программу, которая будет формировать данные для отображения маршрута робота по комнате размером N x M шагов для предварительной проверки правильности программы управления роботом. Перед началом работы робот стоит в углу, из которого может двигаться только вперед (в длину) или вправо (в ширину) и начинает в нем пылесосить. Робот может повторно пылесосить те участки, в которых уже убирался.
Входные данные: Целые числа N – длина и M – ширина комнаты в шагах робота (0<N<20, 0<M<20). Целое число K<10 – количество команд в программе. Последовательность из K команд, каждая из которых состоит из латинской буквы (F,B,L,R) и целого числа от 1 до 19. Каждая буква и число вводятся в отдельной строке. Гарантируется, что программа управления роботом составлена так, что робот не упрется ни в одну из стен комнаты.
Выходные данные: Таблица из M строк и N столбцов, в которой цифрой 1 отмечены участки комнаты размером 1 x 1 шаг, в которых пылесосил робот, а  цифрой 0 участки, в которых он не был.
Примеры входных и выходных данных:
Входные данные
Выходные данные
Входные данные
Выходные данные
5
4
4
F
2
R
3
B
2
L
2
11100
10100
10100
11100
Пояснения:
Комната 5 х 4 шагов. Программа из 4 команд.
Робот пропылесосил квадрат в углу, где стоял. Сделал 2 шага вперед, потом 3 шага вправо, потом 2 шага назад, и 2 шага влево
6
5
5
F
5
B
3
R
3
B
2
L
2
111111
101000
101000
111000
000000
 
7
6
6
F
6
R
1
B
4
R
2
B
2
L
2
1111111
1011111
1010000
1110000
0000000
0000000
7
6
6
F
1
R
1
B
1
R
4
F
6
L
5
1100001
1100001
1000001
1000001
1000001
1111111
7
6
6
F
5
R
1
B
3
R
4
L
2
B
2
1111110
1011110
1010000
1110000
0010000
0010000
7
6
6
F
2
R
1
B
2
R
4
F
6
L
3
1110000
1110000
1000001
1000001
1000001
1111111
7
6
6
F
5
R
1
B
3
R
4
L
2
F
2
1111110
0011110
0010000
0011100
0010000
0010000
7
6
6
F
2
R
1
B
2
R
4
F
5
L
4
1110000
1110010
1000010
1000010
1000010
1111110
7
6
6
F
5
B
3
R
2
F
3
B
3
L
3
1111110
0010000
0011110
0010000
0010000
0010000
7
6
6
F
3
R
1
B
3
R
3
F
6
L
2
1111000
1111000
1000001
1000001
1111111
0000000
 
Возможное решение:
Комната представляется как целочисленный массив соответствующей размерности, первоначально заполненный нулями. Начальному положению робота соответствует элемент с координатами 1, 1 — квадрат из которого начинается уборка. В этом элементе должно быть установлено значение 1.  В цикле считываются буквы команд и количество шагов. Для заданного количества шагов в цикле в соответствии с буквой, задающей направление, выполняется заполнение элементов массива единицами. По завершении считывания и обработки данных, массив построчно выводится на экран.
 
Программа приведена ниже.
 
program robot;
var
   room:array[1..19,1..19] of integer;
   i,j,k,l1,l2,n,m,p:integer;
   c:char;
begin
readln(n);
readln(m);
for i:=1 to n do
    for j:=1 to m do
    room[i,j]:=0;
l1:=1;
l2:=1;
room[1,1]:=1;
readln(k);
for i:=1 to k do
    begin
    readln(c);
    readln(p);
    for j:=1 to p do
        begin
        case c of
    'F': l1:=l1+1;
    'B': l1:=l1-1;
    'R': l2:=l2+1;
    'L': l2:=l2-1;
         end;
         room[l1,l2]:=1
         end
    end;
for j:=1 to m do
    begin
    for i:=1 to n do
        write(room[i,j]);
    writeln
    end
end.
 

Задача 2. Дамы сдавали багаж (100 баллов)
 
Авиационная компания для удешевления услуг аэропортов ввела для пассажиров правило, согласно которому каждый из них может провезти бесплатно только одно место (сумку, коробку, чемодан и т.п.) багажа весом до M килограммов включительно. Сверхнормативный багаж независимо от количества дополнительных мест оплачивается по установленной авиакомпанией цене за каждый килограмм. Если пассажир сдает в багаж одно место, но его вес превышает установленный предел в M килограммов, то за весь этот багаж берется оплата также как за дополнительный багаж.
Два пассажира собираются лететь одним авиарейсом. Вещи, которые они везут с собой, упакованы в N запечатанных пакетов. Вес каждого пакета известен. Вынимать или перекладывать вещи из пакетов нельзя.
Необходимо написать программу, которая поможет пассажирам распределить пакеты по двум чемоданам, сдаваемым как бесплатный багаж, и, если не избежать перевеса, определить вес пакетов, которые должны быть упакованы в оплачиваемые чемоданы. Считаем все пустые чемоданы невесомыми. Раскладка должна быть сделана так, чтобы доплаты за багаж не было, либо, если этого не избежать, доплата была минимальной.
Входные данные: Целые числа M – максимальный вес одного бесплатного места багажа, N – количество пакетов с вещами,  (0<M<25, 0<N<10). Последовательность из N целых чисел от 1 до 50, соответствующих весу пакетов с вещами.
Выходные данные: Последовательность целых чисел разделенных пробелом и соответствующих номерам пакетов помещаемых в первый бесплатный чемодан или 0, если чемодан невозможно упаковать как бесплатный багаж. С новой строки вес первого бесплатного чемодана.
С новой строки последовательность целых чисел разделенных пробелом и соответствующих номерам пакетов помещаемых во второй бесплатный чемодан или 0, если чемодан невозможно упаковать как бесплатный багаж. Если все вещи уместились в первый чемодан, то в последовательности для второго чемодана также выводится 0. С новой строки вес второго бесплатного чемодана.
С новой строки, целое число — вес багажа, за который нужно сделать доплату, либо 0 если такого багажа нет.
Примеры входных и выходных данных:
Входные данные
Выходные данные
Входные данные
Выходные данные
21
1
22
0
0
0
0
22
Весь багаж оплачивается полностью из-за превышения веса
21
6
17
16
5
4
10
7
1 4
21
2 3
21
17
Два чемодана упакованы до предела, осталось 17 кг дополнительного багажа
23
4
10
13
11
12
1 2
23
3 4
23
0
Весь багаж поместился в 2 чемодана без перевеса
 
11
7
12
1
2
3
1
2
13
2 3 4 5 6
9
0
0
25
Первый чемодан упакован полностью, второй нельзя упаковать как бесплатный, оплачивается 25 кг
23
5
6
8
10
14
5
1 3 5
21
2 4
22
0
 
12
7
2
3
4
5
6
7
8
1 2 6
12
3 7
12
11
 
15
6
9
8
7
11
4
10
2 3
15
4 5
15
19
10
5
5
6
3
2
4
 
1 3 4
10
2 5
10
0
17
6
15
16
16
2
4
5
1 4
17
2
16
25
21
2
22
23
0
0
0
0
45
ВНИМАНИЕ! Возможны другие подходящие расклады по бесплатным чемоданам, при этом ответ будет правильным если:
1.     вес каждого из бесплатных чемоданов не превышает предельного,
2.     каждый пакет может лежать не более чем в одном чемодане,
3.     общий вес груза в бесплатных чемоданах и перевеса должен быть равен сумме весов пакетов,
4.     перевес должен быть таким же, как в представленных примерах (выделено жирным).
5.     ответ, соответствующий приведенным выше условиям, но имеющий другие варианты раскладов по сравнению с тестами оценивается полным баллом.
 
Возможное решение:
Задача сводится к разбиению множества имеющихся пакетов на все возможные тройки не пересекающихся подмножеств и выбора такого разбиения, которое наилучшим образом удовлетворяет условию задачи.
Все возможные разбиения N предметов на тройки непересекающихся подмножеств можно получить, перебрав все возможные N разрядные числа в системе счисления по основанию 3. Для удобства решения считаем, что цифра 0 в i-том разряде – соответствует i-тому пакету, не попавшему в бесплатный багаж, 1 – попаданию i-того пакета в первый бесплатный чемодан, а 2 – попаданию i-того пакета во второй бесплатный чемодан.
Самой плохой является ситуация, когда нельзя упаковать ни один чемодан так, чтобы их вес не превышал предельный. Ей соответствует число, состоящее из одних 0, а перевес будет равен весу всего багажа.
Получим все остальные разбиения путем последовательного увеличения числа на 1. Для каждого вычислим вес бесплатных чемоданов и перевес. Если вес бесплатных чемоданов не выше предельного, то сравниваем перевес. Выбираем и запоминаем тот расклад, при котором перевес меньше.
Выводим ответ в соответствии с условиями задачи.
Текст программы приведен ниже.
program bagazh;
var
   a,a1:array [1..9] of integer;
   p:array [1..9] of integer;
   i,j,k,l,n,m,p1,p2,p3,p4,pm:integer;
begin
readln(m);
readln(n);
p4:=0;
for i:=1 to n do
    begin readln(p[i]); p4:=p4+p[i]; a[i]:=0 end;
a[n+1]:=0; pm:=p4; a1:=a;
repeat
      p1:=0; p2:=0;
      for i:=1 to n do
          begin
          if a[i]=1 then p1:=p1+p[i];
          if a[i]=2 then p2:=p2+p[i]
          end;
      p3:=p4-p1-p2;
      if (p1<=m)and(p2<=m)and(p3<pm) then
         begin pm:=p3; a1:=a end;
         i:=1;
      while a[i]=2 do
            begin a[i]:=0; i:=i+1 end;
      a[i]:=a[i]+1
until (a[n+1]=1) or (pm=0);
p1:=0; p2:=0;
for i:=1 to n do
          begin
          if a1[i]=1 then p1:=p1+p[i];
          if a1[i]=2 then p2:=p2+p[i]
          end;
if p1=0 then write(0)
        else
for i:=1 to n do
    if a1[i]=1 then write(i,' ');
    writeln; writeln(p1);
if p2=0 then write(0)
        else
for i:=1 to n do
    if a1[i]=2 then write(i,' ');
writeln; writeln(p2);
writeln(pm)
end.
 

Задача 3. Шахматное поло (100 баллов)
 
Уставшие от умственного труда шахматисты решили развлечься, сыграв в поло (конная игра в мяч с использованием специальных клюшек) на шахматной доске. Для этого на шахматной доске 8х8 клеток установлены черный и белый кони. Ход коня состоит из движения по вертикали (вверх или вниз) и по горизонтали (вправо или влево) в любой последовательности, при этом если в одном направлении смещение происходит на 1 клетку, то в другом на 2 и наоборот (Траектория «Кочерга»). Коней нельзя устанавливать в диагональные клетки, соседние с угловыми.
В некоторую клетку поля бросается фишка (мяч). Фишка не может попасть на занятую конем клетку или вылететь за пределы доски потому, что изготовлена с использованием нанотехнологий. Очки начисляются следующим образом:
1.     если мяч попал в клетку, через которую может пройти только один из коней при совершении одного хода, соответствующий игрок получает 2 очка, а второй 0,
2.     если через клетку с мячом при совершении одного хода могут пройти оба коня, то каждый игрок получает по 1 очку,
3.     если ни один конь не проходит при совершении одного хода через клетку с мячом, очки не начисляются.
Партия (чакка) состоит из серии бросаний фишки. Перемещение коней по шахматной доске на другую позицию в течение всей партии не производится.
Напишите программу, которая по протоколу игры, содержащему сведения о положении коней и клетках в которые попадал мяч, определит счет чакки.
 
Входные данные: Маленькая латинская буква от a до h, затем с новой строки цифра от 1 до 8 – позиция белого коня. С новой строки маленькая латинская буква от a до h, затем с новой строки цифра от 1 до 8 – позиция черного коня.
С новой строки целое число N – количество бросаний фишки в партии (0<N<20).
Затем последовательность вводимых в отдельных строках маленьких латинских букв от a до h  и цифр от 1 до 8 соответствующих N позициям фишки в игре.
 
Выходные данные: Целое число – количество очков набранных игроком белым конем, двоеточие, количество очко набранных игроком черным конем.
 
Примеры входных и выходных данных:
 
 
Входные данные
Выходные данные
Входные данные
Выходные данные
a
1
f
4
4
d
3
e
5
c
5
b
2
2:4
d
3
c
8
5
d
4
e
2
c
7
h
1
g
4
4:2
d
3
e
7
5
a
1
a
8
d
5
e
5
f
5
2:4
f
1
h
5
5
e
1
g
1
g
3
a
2
c
8
5:1
b
4
c
3
5
a
2
a
3
a
4
a
5
a
6
7:3
d
5
d
6
5
c
3
c
4
c
5
e
6
e
8
5:5
g
4
h
6
5
d
5
g
5
h
8
c
7
f
3
f
6
4:4
b
3
a
6
6
d
1
d
2
d
4
d
5
c
3
c
6
 
 
 
 
 
6:2
b
1
h
7
6
a
8
b
7
c
6
h
1
g
2
f
3
0:0
f
1
d
5
6
e
1
e
2
e
3
e
4
d
3
f
3
7:5
Возможное решение:
Зададим массив 8х8 и заполним его нулями. Введем координаты первого коня. Перейдем от букв к цифрам. Заполним поля, через которые может пройти конь числами, отличными от 0 (например, 2). Для определения полей можно написать сложные логические выражения, либо заметить, что квадрат расстояние от центра поля, где стоит конь до центров полей, через которые он может пройти по «кочерге» не превышает 5 (12+22). Используя такое же правило для ходов второго коня, преобразуем массив. Доступные второму коню поля, помеченные 0, заполним другим числом (например, -2), а поля уже помеченные числом 2 третьим (например, 1).
Будем вводить координаты фишки, и начислять игрокам очки, используя значения в соответствующих ячейках массива.
Текст программы приведен ниже.

 

Program polo;
var
a:char;
i,j,k,l,m,n,p:integer;
desk:array [1..8,1..8] of integer;
begin
readln(a);
i:=pos(a,'abcdefgh');
readln(j);
readln(a);
k:=pos(a,'abcdefgh');
readln(l);
readln(n);
for p:=1 to 8 do
    for m:=1 to 8 do
    if sqr(p-i)+sqr(m-j)<6 then desk[p,m]:=2
                           else desk[p,m]:=0;
for p:=1 to 8 do
    for m:=1 to 8 do
    if sqr(p-k)+sqr(m-l)<6 then
       if desk[p,m]=2 then desk[p,m]:=1
                      else desk[p,m]:=-2;
k:=0;
l:=0;
for p:=1 to n do
    begin
    readln(a);
    i:=pos(a,'abcdefgh');
    readln(j);
    case desk[i,j] of
    2: k:=k+2;
    1: begin
       k:=k+1;
       l:=l+1;
       end;
   -2: l:=l+2
    end;
    end;
writeln(k,':',l)
end.

 

 

 

Задача 4. Тонкое место (100 баллов)
Девочка Маша связала очень длинную цепь из отрезков проволочек разной толщины, сделанных из одинакового материала. Первая проволочка завязывается кольцом, в нее продевается вторая и тоже завязывается кольцом и так далее. Старшеклассник Вася помогал Маше  смотать цепь. Он увидел, что звенья цепи имеют разную толщину, и захотел найти самое слабое, сделанное из самой тонкой проволочки. Оказалось, что таких звеньев может быть несколько. Помогите Васе выяснить шансы, что разрыв может произойти в конкретном звене цепочки.
Напишите программу, которая по номеру звена в цепочке и последовательности значений толщины проволочек, из которых она сделана, определит, может ли цепочка разорваться именно в этом звене или нет, и если может то каков шанс, что это звено разорвется.
Входные данные: Целое число N – номер выбранного Васей звена цепочки (0<N<1000000). Последовательность положительных целых чисел, вводимых с новой строки – толщина проволоки для очередного звена в сотнях микронов (0<Di<100). С новой строки число 0 – означающее, что ввод данных закончен. Гарантируется, что длина цепочки не менее N звеньев.
Выходные данные: Сообщение SN>SMin — если выбранное звено не относится к самым тонким, где SN – целое число равное толщине выбранного звена, а SMin — целое число, соответствующее минимальной толщине проволоки. В противном случае сообщение вида 1:M, где M – количество звеньев, имеющих минимальную толщину и с новой строки SMin.
Примеры входных и выходных данных:
Входные данные
Выходные данные
Входные данные
Выходные данные
12
10
11
30
21
22
11
9
12
9
12
10
9
11
0
1:3
9
4
21
2
12
4
5
6
2
23
12
12
24
11
7
0
4>2
7
4
5
4
5
4
7
4
6
4
5
4
0
1:6
4
6
8
8
6
6
6
4
4
6
4
4
8
0
1:4
4
3
7
7
7
7
7
7
7
7
7
7
1
0
7>1
5
8
6
8
6
3
8
7
8
6
9
7
0
1:1
3
1
2
5
6
6
5
7
6
8
5
8
6
0
1:1
2
11
10
7
30
21
22
11
9
12
9
9
7
0
1:2
7
3
4
5
2
4
5
6
5
3
2
2
2
5
0
1:4
2
8
1
2
3
4
5
6
7
1
2
3
4
5
0
1:2
1
 
Возможное решение:
Вначале рассмотрим первые звенья цепочки. Введем номер звена и первое число. Если было выбрано первое звено, запомним его толщину. Считаем первое звено самым тонким.
Зададим начальные значение счетчиков звеньев и количества самых тонких из них. Введем следующее значение толщины. Далее в цикле пока введенное значение не ноль будем увеличивать счетчик введенных данных, если он совпадет с номером искомого звена, запомним его толщину. Если введенная толщина совпадает с самой тонкой, увеличим счетчик тонких на 1. Если введенная толщина меньше текущего значения, то считаем ее самой тонкой и устанавливаем счетчик самых тонких равным 1.
После окончания ввода данных рассматриваем полученные результаты и выводим нужные сообщения.
Текст программы приведен ниже.
program tcep;
var
   i,j,k,sk,n,m:integer;
begin
readln(n);
readln(i);
m:=1;
j:=i;
if n=1 then sk:=i;
readln(i);
k:=1;
while i<>0 do
begin
k:=k+1;
if k=n then sk:=i;
if i=j then m:=m+1;
if i<j then begin j:=i; m:=1 end;
readln(i)
end;
if sk<>j then writeln(sk,'>',j)
         else begin writeln('1:',m); writeln(j) end
end.
Copyright © 2005–2017 ХабЦНИТ ТОГУ Отправить письмо
Создание сайтов в Хабаровске