Задача 76225

Тема:    [ Многомерные массивы ]

Сложность: 2+ Классы:

Условие

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

Решение

Нас интересуют точки решётки (с целыми координатами) в первом квадранте, попадающие внутрь круга радиуса . Интересующее нас множество (назовём его X) состоит из объединения вертикальных столбцов убывающей высоты. 

*
*	*	*
*	*	*
*	*	*	*

Идея решения состоит в том, чтобы " двигаться вдоль его границы", спускаясь по верхнему его краю, как по лестнице. Координаты движущейся точки обозначим <k,l>. Введём ещё одну переменную s и будем поддерживать истинность такого условия:

<k,l> находится сразу над k-ым столбцом;
s — число точек в предыдущих столбцах.

Формально:

• l — минимальное среди тех l≥0, для которых <k,l> не принадлежит X;
• s — число пар натуральных x,y, для которых x < k и  <x,y> принадлежит X.

Обозначим эти условия через (И).

        k := 0; l := 0;
        while <0,l> принадлежит X do begin
        | l := l + 1;
        end;
        {k = 0, l - минимальное среди тех l >= 0,
         для которых <k,l> не принадлежит X}
        s := 0;
        {инвариант: И}
        while not (l = 0) do begin
        | s := s + l;
        | {s - число точек в столбцах до k-го включительно}
        | k := k + 1;
        | {точка <k,l> лежит вне X, но, возможно, её надо сдвинуть
        |    вниз, чтобы восстановить И}
        | while (l <> 0) and (<k, l-1> не принадлежит X) do begin
        | | l := l - 1;
        | end;
        end;
        {И, l = 0, поэтому k-ый столбец и все следующие пусты, а
           s равно искомому числу}

Оценка числа действий очевидна: сначала мы движемся вверх не более чем на шагов, а затем вниз и вправо — в каждую сторону не более чем на шагов.

Источники и прецеденты использования

книга
Автор	А.Шень
Название	Программирование: теоремы и задачи
Издательство	МЦНМО
Издание	второе
Год издания	2004
глава
Номер	1
Название	Переменные, выражения, присваивания
параграф
Номер	1
Название	Задачи без массивов
задача
Номер	1.1.29