Задания к олимпиаде по информатике 11 класс



Задания для 11 класса к олимпиаде по информатике

  •            Вар-т 1            Вар-т 2            Вар-т 3            Вар-т 4

    Задание 1.

    Найти максимальную по длине последовательность z,
    полученную вычеркиванием элементов как из x, так и из y.

    Пусть x = x1,x2, ... ,xm, y = y1,y2, ... ,yn.

    Заведем матрицу A[0..m,0..n].
    Элемент A[i,j] будет длиной максимальной общей подпоследовательности y x1, ... ,xi и y y1, ..., yj.
    Сначала A[i,0] = A[0,j]=0, i=0, ... ,m, j=0, ... ,n.
    Пусть xi = yj, тогда требуется увеличить длину максимальной общей подпоследовательности x1, ...

    Задание 2.

    Элементами массива a[1..n] являются неубывающие массивы [1..m] целых чисел (a: array [1..n] of array [1..m] of integer; a[1][1] <= ... <= a[1][m], ..., a[n][1] <= ... <= a[n][m]).
    Известно, что существует число, входящее во все массивы a[i] (существует такое х, что для всякого i из [1..n] найдётся j из [1..m], для которого a[i][j]=x).
    Найти одно из таких чисел х.

    Задание 3.

    Задан набор неповторяющихся пар (Ai,Aj), Ai, Aj принадлежат множеству А = {A1, A2, ..., An}.
    Необходимо составить цепочку максимальной длины по правилу (Ai,Aj) + (Aj,Ak) = (Ai,Aj,Ak).

    При образовании этой цепочки любая пара может быть использована не более одного раза.

    Задание 4.

    Элементами массива a[1..n] являются неубывающие массивы [1..m] целых чисел (a: array [1..n] of array [1..m] of integer; a[1][1] <= ... <= a[1][m], ..., a[n][1] <= ... <= a[n][m]).
    Известно, что существует число, входящее во все массивы a[i] (существует такое х, что для всякого i из [1..n] найдётся j из [1..m], для которого a[i][j]=x).
    Найти одно из таких чисел х.

    Задание 5.

    Перечислить все разбиения N на целые положительные слагаемые

    Пример: N = 4, разбиения: 1 + 1 + 1 + 1, 2 + 1 + 1, 2 + 2, 3 + 1, 4.

    First = (1, 1, ..., 1) - N единиц Last = (N)

    Чтобы разбиения не повторялись, договоримся перечислять слагаемые в невозрастающем порядке.
    Сказать, сколько их будет всего, не так-то просто. Для составления алгоритма Next зададимся тем же вопросом: в каком случае i-ый член разбиения можно увеличить, не меняя предыдущих?

    Задания к олимпиаде по информатике 11 класс


               Вар-т 1            Вар-т 2            Вар-т 3            Вар-т 4