ХКОИС
ХРРЦ
Регистрация
Забыли пароль?
Логин:
Пароль:
Поиск
Справочные сведения о системе образования Хабаровского края
Новости образования Хабаровского края
Информация и документы из министерства образования и науки Хабаровского края
Хабаровская краевая заочная физико-математическая школа
РЕГИОНАЛЬНАЯ ОЛИМПИАДА ШКОЛЬНИКОВ
Подготовка к олимпиадам по информатике
РЕГИОНАЛЬНАЯ ОЛИМПИАДА ШКОЛЬНИКОВИнформатика и ИКТ > Задания 2007-2008 учебного года (с решениями)
Задания 2007-2008 учебного года (с решениями)
Задача 1. (100 баллов)
 
«Цепочки домино – II»
 
На столе выложены три костяшки из одного набора домино в произвольном порядке. Следует определить, можно ли из этих костяшек составить правильную цепочку. Например, из костяшек [3|2], [6|2], [3|1], можно составить правильную цепочку [1|3], [3|2], [2|6], а из набора [3|2], [6|6], [3|1] правильная цепочка не составится. Напишите программу, в которой нужно ввести три пары чисел от 0 до 6, каждая из которых соответствует костяшке домино, а результатом выполнения программы будет сообщение «можно построить цепочку», если можно переложить и повернуть костяшки так, что получится правильная цепочка или «невозможно» в противном случае. Выводить на печать саму цепочку не требуется.
 
Решение. Задача может быть решена «в лоб». В этом случае следует составить логическое выражение, получающее значение «истина», если цепочка правильная. Пусть костяшкам соответствуют переменные a1, b1, a2, b2, a3, b3, где a количество точек на левой половинке домино, b – на правой. Рассмотрим возможные комбинации поворотов трех костяшек:
 
a1
b1
a2
b2
a3
b3
a1
b1
b2
a2
a3
b3
a1
b1
a2
b2
b3
a3
a1
b1
b2
a2
b3
a3
b1
a1
a2
b2
a3
b3
b1
a1
b2
a2
a3
b3
b1
a1
a2
b2
b3
a3
b1
a1
b2
a2
b3
a3
 
Правильная цепочка может быть составлена из костяшек разложенных в порядке ввода данных, если хотя бы в одной из строк приведенной выше таблицы одновременно значение во второй ячейке будет равно значению в третьей, а значение в четвертой ячейке будет равно значению в пятой. Получим логическое выражение
 
(b1=a2) and (b2=a3) or (b1=b2) and (a2=a3) or (b1=a2) and (b2=b3) or (b1=b2) and (a2=b3) or (a1=a2) and (b2=a3) or (a1=b2) and (a2=a3) or (a1=a2) and (b2=b3) or (a1=b2) and (a2=b3)
 
Оно будет истинным, если можно получить верную цепочку поворотами костяшек. Следует рассмотреть случаи, когда порядок костяшек изменяется. Заметим, что перестановка крайних костяшек на результат не влияет, так как получится та же последовательность, только в противоположном направлении. Достаточно рассмотреть перестановки соседних костяшек. Компактную запись решения можно получить, если использовать логическую функцию:
 
function prov(a1,b1,a2,b2,a3,b3:integer):Boolean;
begin
prov:=(b1=a2) and (b2=a3) or (b1=b2) and (a2=a3) or (b1=a2) and (b2=b3) or (b1=b2) and (a2=b3) or (a1=a2) and (b2=a3) or (a1=b2) and (a2=a3) or (a1=a2) and (b2=b3) or (a1=b2) and (a2=b3)
end;
Тогда, если входные данные были помещены в целые переменные k1,n1,k2,n2,k3,n3, решение запишется в виде:
 
if prov(k1,n1,k2,n2,k3,n3) or prov(k2,n2,k1,n1,k3,n3) or prov(k1,n1,k3,n3,k2,n2) then
                        writeln(‘можно построить цепочку’)
            else     writeln(‘невозможно’);
 
Тестовые примеры
 

 

Входные данные
Выходные данные
4 3, 5 2, 4 5
4 3, 3 2, 4 5
4 3, 5 3, 4 5
0 5, 3 5, 4 0
1 3, 5 2, 4 5
4 3, 3 2, 1 5
1 5, 3 3, 4 0
1 2, 3 4, 5 6
«можно построить цепочку»
«можно построить цепочку»
«можно построить цепочку»
«можно построить цепочку»
«невозможно»
«невозможно»
«невозможно»
«невозможно»
 
 
Задача 2. (100 баллов)
 
«Игра в числа»
 
Два программиста решили поиграть в числа. Каждый из них загадывает четырехзначное десятичное число, затем бросают кубик, на гранях которого написаны цифры 2, 3, 4, 5, 6, 7. Выпавшее число выбирают в качестве основания системы исчисления, в которую переводят задуманные числа. Выигрывает тот из участников, который задумал число, сумма цифр которого в выбранной системе исчисления оказывается наибольшей. Напишите программу, которая будет помогать находить победителя. Входные данные: два целых десятичных четырехразрядных числа задуманных программистами и одно число от 2 до 7 – основание системы счисления. Программа выдает сообщение: «выиграл первый», если сумма цифр первого числа в заданной системе исчисления больше чем второго, «выиграл второй», если меньше и «ничья», если суммы цифр оказались равны. Выводить цифры записи чисел в новой системе исчисления на экран не обязательно, однако можно это сделать для самоконтроля.
 
Например:
 
Задуманы числа 1234 и 4323, основание системы исчисления 4. Получим 1234=1031024, 4323=10032034, ответ «выиграл второй».
Задуманы числа 6060 и 6600, основание системы исчисления 7. Получим 6060=234457, 6600=251467, ответ «ничья».
 
Решение. Пусть a и b – задуманные числа, d – выбранное основание системы исчисления. При нахождении остатка от деления c:=a mod d – найдем младшую цифру записи числа a в новой системе исчисления и прибавим ее к сумме цифр a1:=a1+c. Выполнив присваивание a:=a div d отбросим эту цифру. Будем повторять операции, пока переменная a после очередного деления на d не обернется в 0. Таким образом, получим значение суммы цифр числа a в новой записи. Аналогично найдем b1 – сумму цифр числа b. Сравнивая числа a1 и b1, выберем и напечатаем нужный ответ. Ниже приведено решение на языке Паскаль.
  
program igra;
var
   a,b,c,d,a1,b1:integer;
begin
     readln(a);
     readln(b);
     readln(d);
     a1:=0;
     while a>0 do
     begin
     c:=a mod d;
     a:=a div d;
     write(c); {печать для проверки *}
     a1:=a1+c
     end;
 writeln;
     b1:=0;
     while b>0 do
     begin
     c:=b mod d;
     b:=b div d;
     write(c); {печать для проверки *}
     b1:=b1+c
     end;
     writeln;
     if a1>b1 then writeln('выиграл первый');
     if a1<b1 then writeln('выиграл второй');
     if a1=b1 then writeln('ничья')
end.
    
* Цифры печатаются в обратном порядке
 
Тестовые примеры
 
Входные данные
Выходные данные
1111, 2222, 3
3366, 6633, 5
3366, 6633, 4
6030, 3060, 5
1024, 2048, 2
4096, 1024, 4
«выиграл первый»
«выиграл первый»
«выиграл второй»
«выиграл второй»
«ничья»
«ничья»
 
Задача 3. (100 баллов)
 
«Рассылка рекламы»
 
Фирма «ХабаровскКрайСпам» занимается рассылкой рекламных газет и буклетов по Хабаровскому краю. По договоренности с почтой, каждая рекламная посылка должна содержать строго определенное количество (N) экземпляров рекламных изданий. Но есть еще дополнительные условия:
 
1) Два рекламных буклета не должны соприкасаться в посылке, так как из-за особенностей полиграфического покрытия они склеиваются и портятся. То есть газеты играют роль «прокладки» между буклетами.
2) Каждая посылка должна быть уникальной, то есть отличаться от других порядком укладки или количеством различных типов изданий (буклетов и газет). Это дополнительный рекламный ход компании, который состоит в том, что каждый клиент должен получать индивидуальную укладку или содержание посылки.
 
Необходимо разработать программу для фирмы «ХабаровскКрайСпам», которая позволит заранее определить максимальное количество вариантов правильной комплектации посылок в зависимости от N. Входные данные: N — количество экземпляров рекламных изданий в одной посылке. 0<N<100. Выходные данные: M — максимальное количество вариантов комплектации посылок для заданного N. Например, для N=1 имеется 2 варианта (0 — газета, 1 — буклет), N=2 — три варианта (00, 01, 10).
 
Решение. Задачу можно решить с помощью перебора, но это худший вариант. Проще всего заметить закономерность: для N=1 имеется 2 варианта (0 — газета, 1 — буклет), N=2 — три варианта (00, 01, 10), N=3 — пять вариантов (000, 010, 100, 001, 101). Для каждого последующего N количество вариантов будет равняться сумме количеств для N-1 и N-2: F(N) = F(N-1)+F(N-2). Действительно, мы всегда можем к уже существующей последовательности добавить газету. Таких вариантов будет F(N-1) (для заданного N). А для того, чтобы добавить буклет, нужно к предыдущей последовательности добавить одну газету и один буклет. Таких вариантов будет F(N-2). Итак, решением будет нахождение числа с порядковым номером N-1 из последовательности чисел Фибоначчи: 1, 2, 3, 5,…, Фii-1i-2,….
 
Тестовые примеры
 
Входные данные
Выходные данные
4
8
13
610
 
Задача 4. (100 баллов)
 
«Посетим Хабаровский краевой краеведческий музей»
 
В Хабаровском краевом краеведческом музее имени Н.И. Гродекова недавно установили новые камеры слежения, которые позволяют регистрировать время прихода и ухода каждого посетителя. Так за день получается N пар значений, где первое значение в паре показывает время прихода посетителя, а второе — время его ухода. Дирекция музея хочет узнать, какое максимальное число посетителей одновременно находилось в музее и промежуток времени, когда это происходило. Помогите дирекции решить поставленную задачу.
Входные данные: N — количество посетителей за день;
A1, B
A2, B  - времена прихода и ухода посетителей.
AN, BN
0<N<100, 0<Ai, Bi<86400 (в секундах)
Выходные данные: K0 — максимальное число посетителей, которые одновременно находились в музее; X, Y — начало и конец промежутка времени, когда это происходило.
 
Решение. Допишем значения массива времени ухода в конец массива времени прихода, взяв их со знаком минус. Отсортируем полученный массив по возрастанию абсолютной величины его значений. В результате моменты прихода и ухода расположатся в массиве в хронологическом порядке, при этом значения для времени прихода будут положительными, а для времени ухода отрицательными. Для решения задачи заведем счетчик посетителей. Двигаясь по полученному массиву, будем определять, когда посетитель входит в музей (элемент положительный) и увеличивать значение счетчика на 1, а когда выходит (элемент отрицательный) – уменьшать на 1. Максимальное значение счетчика будет равно максимальному числу посетителей. Для того чтобы найти значение границ интервала времени нужно запоминать время, когда входит новый посетитель. Когда же посетитель выходит и значение счетчика в этот момент является наибольшим, следует выбирать в качестве начала интервала запомненное время входа, а в качестве конца интервала текущее время выхода. 
 program muzeum;
var
   a,b:array [1..200] of real;
   i,j,k,k0,n:integer;
   x,y,c:real;
begin
     readln (n);
     for i:=1 to n do
         readln(a[i],b[i]);
     for i:=1 to n do
         a[n+i]:=-b[i];
     for i:=1 to n+n-1 do
         for j:=i+1 to n+n do
         if abs(a[i])>abs(a[j]) then
         begin
         c:=a[i]; a[i]:=a[j]; a[j]:=c
         end;
    
k:=0;
     k0:=0;
     for i:=1 to n+n do
     if a[i]>0 then
               begin
               k:=k+1;
               c:=a[i]
               end  else
               begin
               if k>=k0 then begin
                            k0:=k; x:=c; y:=-a[i]
                            end;
               k:=k-1;
               end;
     writeln (x:4:0,y:4:0);
     writeln (k0)
end.
Тестовые примеры

 

Входные данные
Выходные данные
2
1 10
5 20
5 10
2
5
1 10
3 9
5 20
7 17
19 25
7 9
4
6
1 11
4 10
6 8
9 10
2 7
5 20
6 7
5
3
1 10
2 9
3 8
3 8
3
3
1 2
3 4
5 6
1 2 или 3 4 или 5 6
1
4
1 3
2 4
5 7
6 8
2 3 или 6 7
2
Copyright © 2005–2017 ХабЦНИТ ТОГУ Отправить письмо
Создание сайтов в Хабаровске