14.1. Прогресія (впорядкування методом обліку)
Впорядкувати масив різних цілих чисел методом обліку масивом множин.
Перебрати всі можливі пари: різниця + перший елемент.
Оптимізувати перебір відкиданням тих пар, які задають члени вже знайдених прогресій максимальної довжини.
Авторське розв'язання має такий вигляд.
const n_=500000; n256=n_ div 256;
var s: array [0..n256] of set of byte; {Данi про множину}
d, {Рiзниця арифметичної прогресiї}
j, {Найбiльша знайдена довжина арифметичної прогресiї}
k, {Зчитане число або 1-ий член прогресiї}
l, {Кiлькiсть елементiв множини або членiв прогресiї}
max, {Найбiльший елемент множини}
n: longint; {Кiлькiсть елементiв множини}
incl: boolean;{Чи можна знайти ще один елемент прогресії}
o: text; BEGIN
assign(o,'SEQUENCE.IN'); reset(o);
read(o,n); for l:= 1 to n do begin
read(o,k); if max < k then max:=k;
include(s[k div 256],k mod 256) end; close(o);
assign (o,'SEQUENCE.OUT'); rewrite(o); j:=0; k:=1;
repeat d:=1; if (k mod 256) in s[k div 256] then
repeat l:=1; if (k < d) or
not (((k-d) mod 256) in s[(k-d) div 256]) then begin
if k+l*d<=n_ then
repeat incl:=k+l*d<=n_;
if incl then begin
if ((k+l*d) mod 256) in
s[(k+l*d) div 256] then inc(l)
else incl:=false end;
until not incl end;
if l> j then begin rewrite(o); j:=l end;
if l>=j then writeln (o,l,' ',k,' ',d);
inc(d);
until max < k+(j-1)*d;
inc(k);
until k+j-1>max; close(o) END.14.2. Поверхня куба (аналітична геометрія)
Подати поверхню куба розгорткою, тобто для кожної грані визначити формули переходу від координат 3-вимірного простору до координат 2-вимірної розгортки.
Замінити перехід з однієї грані на іншу через точку ребра, що має два образи на розгортці, ламаною без самоперетинів, всі ланки якої належать периметру многокутника-розгортки.
Обчислити остачу вiд дiлення на подвоєну площу всієї поверхні куба площу частини поверхні куба, обмеженої ламаною, як остачу суми доданків xj yj + 1 – yj xj + 1.
Тут (xj; yj ) — координати j-ої вершини образу ламаної на розгортці (перша вершина збігається з останньою).