Задача №1 Значение арифметического выражения 4912 – 710 + 78 – 49 записали в системе счисления с основанием 7. Сколько цифр «6» содержится в этой записи?


Чтобы посмотреть этот PDF файл с форматированием и разметкой, скачайте его и откройте на своем компьютере.
КамГУ им
.

Витуса Беринга

Олимпиада по информатике


Задача №1

Знач
ение арифметического выражения
49
12


7
10
+ 7
8


49

записали в системе
счисления с основанием 7. Сколько цифр ©6 содержится в этой записи?

Подробно распишите решение.


Критерии оценивания

Кр
итерий

Балл

Решение подробно расписано, получен верный результат

10 баллов

В решении
допущены отдельные неточности (1
-
2
), приводящие к
неправильному результату, алгоритм решения правильный

5 баллов

По решению видно, что ученик правильно представляет ход

решения задачи, однако допущено большое количество
неточностей (3 и более), получен неверный результат

2

балла

Ученик не правильно подошел к решению задачи

0 баллов


Решение

Распишем арифметическое выражение с помощью степеней
7

7
2
4

+
7
8
-
7
10
-
7
2

Рассмотр
им запись
A
=
7
24
+7
8

в 7
й системе счисления
:

100..0100..0
7

разряд

24

23



8

7



0

А

1

0



1

0



0

Рассмотрим запись
B
=
7
10

в 7
й системе счисления
:

100..0
7

разряд

10

9

8



1

0

B

1

0

0



0

0

Рассмотрим запись
C
=
A
-
B

в 7
й системе счисления
:

66..6010..0
7

разря
д


24

23

22



10

9

8

7



0

A

-

1

0

0



0

0

1

0



0

B





1

0

0

0



0

C

=


6

6



6

0

1

0



0

В
10
м разряде невозможно 0
-
1, поэтому занимаем 1 у
24
го разряда, равного
1

(остается
0
), 10
-
1 в
7
й системе счисления равно
6
.

Рассмотрим запись
C
-
7
2

в
7
й систе
ме счисления:

7
2
=
1
00
7

разряд


23



10

9

8

7



2

1

0

C

-

6



6

0

1

0



0

0

0

7
2








1

0

0

ИТОГО

=

6



6

0

0

6



6

0

0


Ответ:
20

©6

.




Задача №2

Сколько различных решений имеет система логических уравнений

(x
1



y
1
)


(

x
2




y
2
)

(x
2



y
2
)


(

x
3




y
3
)

...

(x
7



y
7
)


(

x
8




y
8
)

где
x
1
, ,
x
8
,
y
1
, ,
y
8
,


логические переменные? В ответе не нужно перечислять
все различные наборы значений переменных, при которых выполнено данное
равенство.
Подробно распишите решение.


Критерии оценивания

Критери
й

Балл

Решение подробно расписано, получен верный результат

15 баллов

В решении допущены отдельные неточности (
1
-
2
), приводящие к
неправильному результату, алгоритм решения правильный

7 баллов

По решению видно, что ученик правильно представляет ход
реше
ния задачи, однако допущено большое количество
неточностей (3 и более), получен неверный результат

3

балла

Ученик не правильно подошел к решению задачи

0 баллов


Решение

I.

Перепишем систему в виде


Пусть
Z
1

�= 0 =
Z
2

=� 1 =
Z
3

= 0� =
 >
Z
7

�= 0 =
Z
8

= 1

(1,0,1,0,1,0,1,0)

Пусть
Z
1

= 1

�=
Z
2

= 0

�=
Z
3

= 1

>  >
Z
7

= 1

�=
Z
8

= 0 (0,1,0,1,

0,1,0,1)


II.

У системы, зависящей от
Z
i
, 2 решения.

Т.к.
,
то для
Z
i
=0


3
решения, зависящих от
x
i
,
y
i
, для
Z
i
=1


1
решение,
зав
исящее от
x
i
,
y
i
.


III.

Для (1,0,1,0,1,0,1,0)


81 решение, для (0,1,0,1,0,1,0,1)


81 решение


Ответ
:
81+81=162
.



Задача №3

Исполнитель Редактор получает на вход строку цифр и преобразовывает её.
Редактор может выполнять две команды, в обеих командах
v

и
w

обо
значают
цепочки цифр.

заменить (v, w)

нашлось (v)

Дана программа для исполнителя Редактор:

НАЧАЛО

ПОКА нашлось (2222) ИЛИ нашлось (666)


ЕСЛИ нашлось (2222)


ТО заменить (2222, 6)


ИНАЧЕ заменить (666, 2)


КОНЕЦ ЕСЛИ

КОНЕЦ ПОКА

КОНЕЦ

Какая строка п
олучится в результате применения приведённой ниже программы к
строке, состоящей из 79 идущих подряд цифр 6? В ответе запишите полученную
строку.


Критерии оценивания

Критерий

Балл

Получен верный результат

10 баллов

Получен неверный результат

0 баллов


Р
ешение

Начальная строка

666..6

(
79 ©6
)

ПОКА нашлось (2222) ИЛИ
нашлось (666)

ДА

ЕСЛИ нашлось (2222)


ТО заменить (2222, 6)


ИНАЧЕ заменить (666, 2)


КОНЕЦ ЕСЛИ

266..6

(
76

©
6, 1 ©2
)

Блок ПОКА ИНАЧЕ повторяется еще 3
раза

222266..6 (67 ©6, 4
©2)

ПОКА
нашлось (2222)

ИЛИ нашлось (666)


ДА

ЕСЛИ нашлось (2222)


ТО заменить (2222, 6)


ИНАЧЕ заменить (666, 2)



КОНЕЦ ЕСЛИ

66..6 (68 ©6)

ПОКА нашлось (2222) ИЛИ
нашлось (666)

ДА

ЕСЛИ нашлось (2222)


ТО заменить (2222, 6)


ИНАЧЕ заме
нить (666, 2)


КОНЕЦ ЕСЛИ

266..6 (65 ©6, 1 ©2)

Блок ПОКА ИНАЧЕ повторяется еще 3
раза

222266..6 (56 ©6, 4 ©2)


..

66..6 (13 ©6)

ПОКА нашлось (2222) ИЛИ
нашлось (666)

ДА

ЕСЛИ нашлось (2222)


ТО заменить (2222, 6)


ИНАЧЕ заменить (666, 2)


КОНЕЦ ЕСЛИ

266..6 (
10

©6, 1 ©2)

Блок ПОКА ИНАЧЕ повторяется еще 3
раза

22226

ПОКА
нашлось (2222)

ИЛИ нашлось (666)

ДА

ЕСЛИ нашлось (2222)


ТО заменить (2222, 6)


ИНАЧЕ заменить (666, 2)



КОНЕЦ ЕСЛИ

66

ПОКА нашлось (2222) ИЛИ нашлось (66
6)

НЕТ


Ответ
:
66
.




Задача №4

Дан фрагмент электронной таблицы:


А

В

C

1

20

???

35

2

=C1
-
2*B1*B1

=(B1*B1*B1
-
4)/A1

=C1
-
8*B1

Какое целое число должно быть записано в ячейке
B
1, чтобы
построенная после выполнения вычислений диаграмма по
значениям диа
пазона ячеек A2:С2 соответствовала рисунку?
Известно, что все значения диапазона, по которым построена
диаграмма, имеют один и тот же знак.


Критерии оценивания

Критерий

Балл

Решение подробно расписано, получен верный результат

5 баллов

В решении допущен
ы отдельные неточности, приводящие к
неправильному результату, алгоритм решения правильный

2 баллов

Ученик не правильно подошел к решению задачи

0 баллов


Решение


А

В

C

1

20

x

35

2

=C1
-
2*B1*B1

=(B1*B1*B1
-
4)/A1

=C1
-
8*B1


Заменим значение ячейки
B
1
на

x
,

тогда

A
2=
35
-
2
x
2

B
2=
(
x
3
-
4)/2
0

C
2=35
-
8
x
.

По диаграмме видно, что круг разбит на
3
равных

части
. Следовательно

A2=B2=C2


Проверим


Ответ
: 4
.



Задача №
5

Введём выражение
M & K
, обозначающее поразрядную конъюнкци
ю
M

и
K

(логическое ©И между соответствующими битами двоичной записи).
Определите
набольшее натуральное число
A
, такое что выражение

( (
x

&

46

=

0)


(
x

&
18
=

0))


((
x

& 115

0)


(
x

&
A

=
0))

тождественно истинно (то есть принимает значение 1 при любом

натуральном
значении переменной
x
)?

Распишите решение.


Критерии оценивания

Критерий

Балл

Решение подробно расписано, получен верный результат

1
5

баллов

В решении допущены отдельные неточности (до 2), приводящие к
неправильному результату, алгоритм реше
ния правильный

7

баллов

По решению видно, что ученик правильно представляет ход
решения задачи, однако допущено большое количество
неточностей (3 и более), получен неверный результат

3

балла

Ученик не правильно подошел к решению задачи

0 баллов


Решение

Введем обозначения

X
46

=

(
x
&
46
= 0
)
;
X
18
=(
x
&
1
8
=

0 )
;
X
115

= (
x
&
115

= 0 )
;

X
A

= (
x
&
A

= 0)
, получим



A

имеет значение, когда

.

Переведем все числа в двоичную систему счисления


46



0
101110
2
,


18


0
01
0010
2
,

115


111
001
1
2

,
когда

*0*000*

,
когда

**0**0*

, когда


-

это числа,

,

т.е.
в
A

©0 должны стоять в 6,4,0 разрядах (т.
к. там могут появиться ©1), а в
остальных разрядах любые числа


-

это числа,

,

т.е.
d

A

©0 должны стоять в 6,5,0 разрядах (т.к. там могут появиться ©1) и во 3,2
(т.к. там может быть что угодно), а в остальны
х разрядах любые числа
.

Объединив два условия для А получим


6

5

4

3

2

1

0

0

0

0

0

0

*

0

Наи
боль
шим числом будет
10, т.е. 2


Ответ
: 2
.



Задача №
6

Элементами множества А являются натуральные числа. Известно, что выражение

(
x

{2, 4, 6, 8, 10, 12}) → (((
x

{3, 6, 9, 12, 15})


¬(
x

A)) → ¬(
x

{2, 4, 6, 8, 10, 12}))

истинно (т. е. принимает значение 1) при любом значении переменной
х
.

Определите наименьшее возможное значение суммы элементов множества A.

Распишите решение.


Критерии оценивания

Критерий

Балл

Решение подробно расписано, получен верный результат

10 баллов

В решении допущены отдельные неточности (до 2), приводящие к
неправильному результату, алгоритм решения правильный

5 баллов

По решению видно, что ученик правильно представляет ход
решения за
дачи, однако допущено большое количество
неточностей (3 и более), получен неверный результат

2 балла

Ученик не правильно подошел к решению задачи

0 баллов


Решение

Введем обозначения
,
получим


Следовательно, о
бъединение множеств

должно покрывать
все натуральные
числа.

Определим

множество
, это пересечение
P

и
Q
,
т.е. {6,12}, следовательно
все числа кроме 6 и 12, значит минимальное
A



это {6,12}.

Сумма равна 18.


Ответ
: 18
.



Задача №
7

Показать, что любую сумму, большую 7 копеек, можно выплатить, используя
только 3
-
х и 5
-
ти копеечные монеты
, при этом использовать максимально
возможное количество 3
-
х копеечных монет
.

1)

До

20 баллов.

Написать програм
му, решающую данную задачу.

2)

До

7

баллов.

Описать алгоритм решения задачи.

Формат входных данных

На вход программа получает
N

(7

N

100000
)
.

Формат выходных данных

Программа должна вывести

2
числа
:
количество монет
по
3 коп. и количество
монет
по
5 коп.

При
мер

Вход

Выход

12

4 0

22

4 2


Критерий оценивания

Критерий

Балл

Написан код программы, правильно работающий в обоих случаях.

Допускается наличие 1
-
3 синтаксических ошибок, не искажающих
смысл решения (неправильное название функции, отсутствие ©
;


и
т.д
.
)

20 баллов

Д
опущено 4 и более синтаксических ошибок в решении на 20
баллов

10 баллов

Представлен верный алгоритм решения задачи.

Программа не написана или написана неверно

7

баллов

Ученик не правильно подошел к решению задачи

0 баллов


Решение

Для р
ешения этой задачи можно разделить число нацело N на 3 и рассмотреть
остаток от деления. Существует три варианта: если остаток 0, то сумма
выплачивается трехкопеечными монетами; если остаток 1 (наименьшее такое
число 10), то необходимо убрать 3 монеты по 3

копейки и добавить 2 монеты по 5
копеек; если остаток от деления 2, то необходимо убрать 1 трёхкопеечную монету
и добавить 1 монету достоинством 5 копеек.


Пр
и
мер программы на языке
C
++

int main(int argc, char** argv) {


int N;


cin� � N;


int x = N/3;


int y = 0;



switch(N%3){



case 1: x
-
=3;




y+=2;




break;



case 2: x
--
;




y++;



}


cout x " " y;



}




Задача

№8

Число вводится своим двоичным представлением. Необходимо определить
делится ли число на 15.

1)

До
25

баллов.

Напишите пр
ограмму,
решающую заданную задачу
.

2)

До
10

баллов.

Описать алгоритм решения задачи.

Формат входных данных

Входные данные содержат двоичное представление числа,
длина числа не
превыш
ает 10000 двоичных разрядов

Формат выходных данных

Программа должна вывести
о
твет на поставленный вопрос
:
YES

или
NO


Пример

Вход

Выход

1111

YES

10000011111

NO


Критерий оценивания

Критерий

Балл

Написан правильно работающий код программы.

Допускается
наличие 1
-
3 синтаксических ошибок, не искажающих смысл
решения (неправильное н
азвание функции, отсутствие ©
;
 и т.д.)

25 баллов

Допущено 4 и более синтаксических ошибок в решении на 20
баллов

15 баллов

Представлен верный алгоритм решения задачи
либо написана
программа по неоптимальному алгоритму

10 баллов

Представлен верный алгор
итм решения задачи с некоторыми
неточностями

5

балл
ов

Верно представлен неоптимальный алгоритм

3 балла

Ученик не правильно подошел к решению задачи

0 баллов


Решение

Неоптимальное

Возможно ученик переведет число из двоичной системы счисления в десятичну
ю
и проверит делимость на 15. Однако данный алгоритм будет работать не для всех
входных данных (слишком большое значение может применять переведенное
число)


Оптимальное

Распишем число в виде многочлена

S

=
a
[
n
]*
16
n

+
a
[
n
-
1]*1
6
(
n
-
1)

+ ...
+ a[1]*
16

+ a[0].

S mod
15
= (a[n]*(
16
n
-
1)+a[n] + a[n
-
1]*(
16
(n
-
1)
-
1)+a[n
-
1] + ...
+ a[1]*(
16
-
1)+a[1]
+ a[0]) mod
15

А так как 1
6
k

-

1 делится на
15

нацело, то и

S mod
15

= (a[n] + ... +a[1] +a[0]) mod
15
,

Р
азбиваем двоичное число справа налево на тетрады, которые однозначно

можно
преобразовать в шестнадцатеричные цифры, находим их сумму и делим ее на 15.
Если остаток 0, то введенное число делится на 15, иначе
-

нет.


Пример программы на языке
C
++

int main(int argc, char** argv) {


string HEX="0000*0001*0010*0011*0100*

0101*0
110*0111*1000*1001*1010*

1011*1100*1101*1110*1111*";


string number;


cin� � number;


int sum = 0;


while (number.length�()=4){



-
4,4);



sum+=HEX.find(tetr+"*")/5;



number.erase(number.length()
-
4,4);


}


if ( num
ber.length() ){



string add = "";



add.append("0000",4
-

number.length());



number = add + number;



sum+=HEX.find(number+"*")/5;


}


if (! (sum%15))



cout "YES";


else



cout "NO";



}




Таблица баллов

Задача

Максимальный балл

1

10

2

15

3

10

4

5

5

15

6

10

7

20

8

25

ИТОГО

110



Приложенные файлы

  • pdf 4368809
    Размер файла: 624 kB Загрузок: 0

Добавить комментарий