XIV городская олимпиада школьников
Санкт-Петербурга по информатике

Теоретический тур, 7 февраля 1999 года

Задачи

Задача A. Поровну

На плоскости дано 2N (1 ≤ N ≤ 5000) различных точек. Требуется провести прямую, по обе стороны от которой оказалось бы поровну точек, а сама она не проходила бы ни через одну из них.

Считайте, что компьютер выполняет вычисления над вещественными числами с неограниченной точностью. Прямую можно выводить в любой форме, например, как заданную параметрическим способом или общим уравнением прямой.

Задача B. Двоичная полоска

На замкнутой бумажной полоске написаны нолики и единички. Можно сделать один разрез, получив число из нулей и единиц. Нужно выбрать место разреза так, чтобы жто число было минимальным. Например, для полоски

010010110001100

оптимальное место разреза будет за последней единицей. В этом случае образуется число

000100101100011

Количество цифр на полоске не превосходит 30000. Если есть несколько возможностей провести оптимальный разрез, выведите любую из них.

Задача C. Словарь

Один из способов экономного хранения текста состоит в том, что текст записывается как последовательность номеров из словаря, содержащего все встречающиеся в тексте слова. Для экономного хранения словаря слова располагают по алфавиту, разбивают на небольшие группы (в каждой не больше m слов), а каждую группу сжимают, используя так называемое сжатие слева: в каждом слове указывается, сколько букв нужно взять из предыдущего слова, а дальше записывается остаток, завершающийся специальным символом. Например, группа

чернила, чернильница, чернильный, чернильными, черт, чертеж, чертежница, чиж

представляется как

0чернила*6ьница*8ый*9ми*3т*4еж*6ница*1иж*

Здесь * – признак конца слова (отдельный байт), а числа – количества букв от предыдущего слова (числа помещаются в один байт). Требуется составить программу, которая, получив число m, количество слов n и упорядоченный список слов, вычислила бы такое разбиение слов на группы (без нарушения алфавитного порядка), при котором сжатая запись словаря имела бы наимньшую длину.

Проводить само сжатие не требуется. Число m не превосходит 32, тем самым ограничивая количество шагов, требуемых для извлечения слова из словаря, а n меньше 30000.

Задача D. Таинственная функция

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

    
function func(x: longint): longint;
var
    y, z: longint;
begin
    func := -1;
    x := x - 1;
    if x mod 8 <> 0 then
        exit;
    y := 1;
    z := 2;
    x := x div 8;
    repeat
        if odd(x) then begin
            x := x - y - z;
            y := y + z + z;
        end;
        x := x div 2;
        z := z * 2;
    until x <= 0;
    if odd(x) then begin
        x := x + y - z;
        y := z + z - y;
    end;
    if x = 0 then
        func := y;
end;

long func(long x) {
    if (--x % 8) return -1;
    x /= 8;
    long y = 1, z = 2;
    do {
        if (x % 2) {
            x -= y + z;
            y += 2 * z;
        }
        x /= 2;
        z *= 2;
    } while (x > 0);
    if (x % 2) {
        x += y - z;
        y = 2 * z - y;
    }
    if (x) 
        return -1;
    else
        return y;    
}

Примечание: обе функции (на Паскале и Си++) исполняют один и тот же алгоритм. Функция вызывается от одного аргумента – натурального числа.