Решение одной олимпиадной задачи

Слайд 1

Слайд 2

K- периодичный массив В данной задаче речь пойдет только о массивах, все элементы которых равны 1 и/или 2. Массив a называется k -периодичным, если его длина делится нацело на k , и существует такой массив b длины k , что a представляет собой записанный ровно n /k раз подряд массив b . Иными словами, массив a является k -периодичным, если он имеет период длины k . Например, любой массив является n -периодичным, где n — длина массива. Массив [2,1,2,1,2,1] является одновременно 2-периодичным и 6-периодичным, а массив [1,2,1,1,2,1,1,2,1] является одновременно 3-периодичным и 9-периодичным. Для заданного массива a , состоящего только из единиц и двоек, найдите наименьшее количество элементов, которые необходимо изменить, чтобы он стал k -периодичным. Если массив уже является k -периодичным, то искомое значение равно 0.

Слайд 3

K- периодичный массив Входные данные В первой строке входных данных содержится пара целых положительных чисел n , k (1 ≤ k ≤ n ≤ 100), где n — длина массива, а значение k делит нацело n . Вторая строка содержит последовательность элементов заданного массива a 1 , a 2 ,..., a n (1 ≤ a i ≤ 2), a i — i -й элемент массива. Выходные данные Выведите наименьшее количество элементов массива, которые надо изменить, чтобы он стал k -периодическим. Если массив уже является k -периодичным, то выведите 0.

Слайд 4

Примеры Входные данные Результат 6 2 2 1 2 2 2 1 1 8 4 1 1 2 1 1 1 2 1 0 9 3 2 1 1 1 2 1 1 1 2 3 Комментарий В первом примере достаточно заменить четвертый элемент с 2 на 1, тогда массив примет вид [2,1,2,1,2,1]. Во втором примере заданный массив уже 4-периодичный. В третьем примере достаточно каждое вхождение двойки заменить на единицу. В этом случае массив примет вид [1,1,1,1,1,1,1,1,1] — этот массив одновременно 1-, 3- и 9-периодичный.

Слайд 5

Алгоритм решения (рассмотрим для k=2) Определим q – количество вхождений массива b в массив a Посчитаем количество «2» и «1» на каждом 1 и 2 месте Для этого создаем a) Массив e , который считает количество е диниц b) Массив d , который считает количество д воек 1е места 2е места

Слайд 6

Сравниваем значения массивов e и d Например e d a И создаем «идеальный» массив b 0 <3 -> b[1]=2 2>1 -> b[2]=1 0 2 3 1 } для случая 2 1 2 2 2 1 } => b 2 1

Слайд 7

Просматриваем весь массив a , сравниваем с массивом b каждую пару чисел и считаем несовпадения.

Слайд 8

Program k09; var k,n,i,q,s,j:longint; a,b,e,d:array [1..100] of longint; begin readln(n,k); for i:=1 to n do read(a[i]); q:=n div k; { определяем количество вхождений } for i:=0 to q-1 do for j:=1 to k do if a[k*i+j] = 1 then e[j]:=e[j]+1 else d[j]:=d[j]+1; { создаем массивы d и e} for j:=1 to k do if e[j]>d[j] then b[j]:=1 else b[j]:=2; { создаем «идеальный» массив b} for i:=0 to q-1 do for j:=1 to k do if a[k*i+j]<>b[j] then s:=s+1; { считаем замены } writeln(s); end.

Слайд 9

For i:= 0 to 3-1 do for j:= 1 to 2 do 1. i = 0 1) j = 1 a[2*0 +1]ǂ1 d[1]=0+1=1 d 2) j = 2 a[ 2*0+2]=1 e[2]=0+1=1 e 1 1

Слайд 10

2. i = 1 1) j = 1 a[2*1 +1]ǂ1 d[1]=1+1=2 d 2) j = 2 a[ 2*1+2]ǂ1 d[2]=0+1=1 d 2 2 1

Слайд 11

1. i = 2 1) j = 1 a[2*2 +1]ǂ1 d[1]=2+1=3 d 2) j = 2 a[ 2*2+2]=1 e[2]=1+1=2 e 3 1 0 2

Слайд 12

«1» - e «2» - d 1) 0<3 -> b[1]=2 2) 2>1 -> b[2]=1 m 0 2 3 1 2 1

Слайд 13

Автор Бирбасова Татьяна, ученица 11 а класса МБОУ «СОШ № 32» города Энгельса