На плоскости дано 2N (1 ≤ N ≤ 5000) различных точек. Требуется провести прямую, по обе стороны от которой оказалось бы поровну точек, а сама она не проходила бы ни через одну из них.
Считайте, что компьютер выполняет вычисления над вещественными числами с неограниченной точностью. Прямую можно выводить в любой форме, например, как заданную параметрическим способом или общим уравнением прямой.
На замкнутой бумажной полоске написаны нолики и единички. Можно сделать один разрез, получив число из нулей и единиц. Нужно выбрать место разреза так, чтобы жто число было минимальным. Например, для полоски
010010110001100
оптимальное место разреза будет за последней единицей. В этом случае образуется число
000100101100011
Количество цифр на полоске не превосходит 30000. Если есть несколько возможностей провести оптимальный разрез, выведите любую из них.
Один из способов экономного хранения текста состоит в том, что текст записывается как последовательность номеров из словаря, содержащего все встречающиеся в тексте слова. Для экономного хранения словаря слова располагают по алфавиту, разбивают на небольшие группы (в каждой не больше m слов), а каждую группу сжимают, используя так называемое сжатие слева: в каждом слове указывается, сколько букв нужно взять из предыдущего слова, а дальше записывается остаток, завершающийся специальным символом. Например, группа
чернила, чернильница, чернильный, чернильными, черт, чертеж, чертежница, чиж
представляется как
0чернила*6ьница*8ый*9ми*3т*4еж*6ница*1иж*
Здесь * – признак конца слова (отдельный байт), а числа – количества букв от предыдущего слова (числа помещаются в один байт). Требуется составить программу, которая, получив число m, количество слов n и упорядоченный список слов, вычислила бы такое разбиение слов на группы (без нарушения алфавитного порядка), при котором сжатая запись словаря имела бы наимньшую длину.
Проводить само сжатие не требуется. Число m не превосходит 32, тем самым ограничивая количество шагов, требуемых для извлечения слова из словаря, а n меньше 30000.
Выберите одну из приведенных ниже функций, на понятном Вам языке программирования и определите ее назначение. Постарайтесь строго доказать Ваше утверждение.
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; }
Примечание: обе функции (на Паскале и Си++) исполняют один и тот же алгоритм. Функция вызывается от одного аргумента – натурального числа.