Задания для проведения муниципального этапа Всероссийской олимпиады школьников по информатике в 2008/2009 учебном году в Хабаровском крае Задача (100 баллов)
Задания для проведения муниципального этапа Всероссийской олимпиады школьников по информатике в 2008/2009 учебном году в Хабаровском крае Задача (100 баллов) icon

Задания для проведения муниципального этапа Всероссийской олимпиады школьников по информатике в 2008/2009 учебном году в Хабаровском крае Задача (100 баллов)



НазваниеЗадания для проведения муниципального этапа Всероссийской олимпиады школьников по информатике в 2008/2009 учебном году в Хабаровском крае Задача (100 баллов)
Дата конвертации21.09.2012
Размер89.92 Kb.
ТипЗадача
источник

Задания для проведения муниципального этапа Всероссийской олимпиады школьников по информатике в 2008/2009 учебном году в Хабаровском крае


Задача 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
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Выходные данные: 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, B1

A2, B2 - времена прихода и ухода посетителей.

...

AN, BN

0i, 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







Похожие:

Задания для проведения муниципального этапа Всероссийской олимпиады школьников по информатике в 2008/2009 учебном году в Хабаровском крае Задача (100 баллов) iconМетодические рекомендации для проведения муниципального этапа Олимпиады по химии в 2011-2012 учебном году
Настоящие требования к проведению муниципального этапа всероссийской олимпиады школьников по химии (далее – Олимпиада) составлены...
Задания для проведения муниципального этапа Всероссийской олимпиады школьников по информатике в 2008/2009 учебном году в Хабаровском крае Задача (100 баллов) iconИнформация об итогах муниципального этапа всероссийской олимпиады школьников по информатике в 2009-2010 учебном году

Задания для проведения муниципального этапа Всероссийской олимпиады школьников по информатике в 2008/2009 учебном году в Хабаровском крае Задача (100 баллов) iconВсероссийская олимпиада школьников по информатике требования к проведению муниципального этапа всероссийской олимпиады школьников по информатике в 2011/2012 учебном году Липецк 2011 оглавление
Российской Федерации, осуществляющего управление в сфере образования (далее организатор регионального этапа Олимпиады), и региональной...
Задания для проведения муниципального этапа Всероссийской олимпиады школьников по информатике в 2008/2009 учебном году в Хабаровском крае Задача (100 баллов) iconРезультаты муниципального этапа всероссийской олимпиады школьников по литературе в 2012/2013 учебном году 9 класс Максимальный балл: 9 класс – 100 баллов
Результаты муниципального этапа всероссийской олимпиады школьников по литературе в 2012/2013 учебном году 9 класс
Задания для проведения муниципального этапа Всероссийской олимпиады школьников по информатике в 2008/2009 учебном году в Хабаровском крае Задача (100 баллов) iconПриказ №632 Об итогах муниципального этапа всероссийской олимпиады школьников в 2012-2013 учебном году По итогам муниципального этапа всероссийской олимпиады школьников
Утвердить список победителей и призёров муниципального этапа всероссийской олимпиады школьников (Приложение 2)
Задания для проведения муниципального этапа Всероссийской олимпиады школьников по информатике в 2008/2009 учебном году в Хабаровском крае Задача (100 баллов) iconПриказ №616 о проведении муниципального этапа всероссийской предметной олимпиады школьников
Сэд-26-01-21-1186 «О проведении муниципального этапа, дистанционного тура регионального этапа всероссийской олимпиады школьников...
Задания для проведения муниципального этапа Всероссийской олимпиады школьников по информатике в 2008/2009 учебном году в Хабаровском крае Задача (100 баллов) iconО проведении II этапа Всероссийской олимпиады школьников 2010 2011 учебном году
«Об утверждении Положения о всероссийской олимпиаде школьников» в период с 15 ноября по 15 декабря 2010 года будет проводиться муниципальный...
Задания для проведения муниципального этапа Всероссийской олимпиады школьников по информатике в 2008/2009 учебном году в Хабаровском крае Задача (100 баллов) iconМетодические рекомендации по проведению и задания муниципального этапа всероссийской олимпиады школьников по биологии в 2009-2010 учебном году
...
Задания для проведения муниципального этапа Всероссийской олимпиады школьников по информатике в 2008/2009 учебном году в Хабаровском крае Задача (100 баллов) iconРезультаты муниципального этапа всероссийской олимпиады школьников по русскому языку в 2012/2013 учебном году 7 класс Максимальный балл: 7 класс – 100 баллов
Результаты муниципального этапа всероссийской олимпиады школьников по русскому языку в 2012/2013 учебном году 7 класс
Задания для проведения муниципального этапа Всероссийской олимпиады школьников по информатике в 2008/2009 учебном году в Хабаровском крае Задача (100 баллов) iconПротокол заседания жюри II (муниципального) этапа Всероссийской олимпиады школьников по информатике 8 класс Дата проведения: Максимальное количество баллов
Протокол заседания жюри II (муниципального) этапа Всероссийской олимпиады школьников по информатике – 8 класс
Разместите кнопку на своём сайте:
Документы


База данных защищена авторским правом ©lib2.podelise.ru 2000-2013
При копировании материала обязательно указание активной ссылки открытой для индексации.
обратиться к администрации
Документы