9-11классы. Ответы и система оценивания

Школьный этап Всероссийской олимпиады школьников

по информатике

2016-2017 учебный год

9-11классы

ОТВЕТЫ и СИСТЕМА ОЦЕНИВАНИЯ

* Максимальное количество баллов – 400

«Пересечение множеств» - 100 баллов

(Время: 1 сек. Память: 16 Мб)

Решение

Эта задача сложна своими ограничениями. Самое ресурсоемкое, но простое решение, которое может прийти в голову - это считать данные в массивы, исключить из них повторяющиеся элементы, далее пробегая по одному из них смотреть: есть ли он во втором и если есть, то выводить в выходной файл. Здесь только исключение повторящихся элементов может при неэффективном решении иметь сложность O(n2), что для миллиона элементов может вызвать TLE (Time limit exceeded).

Рассмотрим теперь верное решение этой задачи. Здесь вовсе не нужны два массива, длина которых может быть до миллиона. В силу конечности диапазона возможных значений мы можем описать некоторый массив a[i] для i=0..105, в i-м значении будем хранить 0, если число i не содержится ни в одном из двух наборов чисел. Если число i имеется в первом наборе, то запишем туда 1, а если и в обоих наборах, то запишем туда 2. После чего пробегая по массиву нужно будет вывести все i, у которых a[i]=2. Заполнение массива a[i] происходит следующим образом: сначала все элементы обнуляются, далее при чтении элемента x первого набора можно выполнять присваивание a[x]=1. При просмотре элементов второго набора для каждого элемента y можно a[y]=2 только в том случае, когда a[y]=1.

НЕ нашли? Не то? Что вы ищете?

Приведенный выше алгоритм можно формализовать к следующему виду:

int a[0..105]={0...0};

read(n, m);

for i=1..n{

read(x);

a[x]=1;

}

for i=1..m{

read(y);

if(a[y]==1) a[y]=2;

}

for i=0..105{

if(a[i]==2) write(i,' ');

}

Задача B. «Перестановка» - 100 баллов.

(Время: 1 сек. Память: 16 Мб)

Для решения этой задачи надо было проверить на истинность три равенства – равно ли число сумме двух других.

Решение на языке Паскаль

var a, b, c : Longint;

begin assign(input, 'input. txt');

reset(input);

assign(output, 'output. txt');

rewrite(output);

Read(a, b, c);

if (a=b+c) or (b=a+c) or (c=a+b) then Write('YES') else Write('NO');

end.

1

352

YES

2

225

NO

3

224

YES

«Делимость на 7» - 100 баллов.

(Время: 1 сек. Память: 16 Мб)

На первый взгляд, задача может показаться достаточно сложной в реализации и многие, возможно, прибегнут к тяжелому решению: переводу длинного двоичного числа в десятичное и многократному делению длинного десятичного на 7; либо к делению длинного двоичного на двоичное 7. В любом из этих случаев не избежать достаточно сложных механизмов реализации длинной арифметики. Причем в данных ограничениях неэффективная реализация может привести к превышению времени выполнения программы.

Используем следующее свойство: число в системе счисления с основанием K делится на K-1 тогда и только тогда, когда сумма цифр данного числа так же делится на K-1. Всем известно, что в десятичной системе число делится на 9 тогда и только тогда, когда сумма его цифр делится на 9. А вышеописанное свойство - это некоторое обобщение известного всем факта. В нашем случае мы можем это использовать. Для этого следует перевести заданное число в 8-ную систему счисления, сложить полученные цифры и проверить делимость на 7 уже обычного числа. Напомним, что каждая тройка цифр двоичного числа представляет отдельную цифру того же числа в 8-ой системе счисления.

Алгоритм проверки делимости двоичного числа S на 7 можно описать следующим образом:

read(S);

while(len(S) mod 3 > 0) S = '0'+S;

while(s>''){

x = x+s[1]*4+s[2]*2+s[3];

delete(s,1,3);

}

if(x mod 7 = 0) write('Yes') else write('No');

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

Задача D. «Спичрайтер» – 100 баллов.

(Время: 1 сек. Память: 16 Мб)

Решение

1 var

2 s : AnsiString;

3 ms : array [0..20000] of AnsiString;

4 i, lm, j : Longint;

5 f : Boolean;

6 begin

7 assign(input, 'input. txt');

8 reset(input);

9 assign(output, 'output. txt'); rewrite(output);

10 ReadLn(s);

11 lm := 0;

12 f := false;

13 ms[0] := '';

14 fori:=1 to length(s) do

15 if s[i] = '.' then begin

16 if f thenWrite(' ')

17 else f := true;

18 Write(ms[lm]);

19 forj:=lm-1 downto 0 do Write(' ',ms[j]);

20 Write('.');

21 lm := -1;

22 end else begin

23 if s[i] <> ' ' thenms[lm] :=ms[lm] +s[i]

24 else begin

25 inc(lm);

26 ms[lm] := '';

27 end;

28 end;

29 end.

Система оценки

Решения для предложений, состоящих из одного слова, оцениваются в 10 баллов. Решения для одного предложения оцениваются в 40 баллов.