✎ Программа эффективна по времени и по памяти (4 балла):

• Язык Паскаль (версия PascalABC):

var N: integer; {количество чисел} a: integer; {очередное число} n58, n29, n2: integer; k58: integer; {количество требуемых пар} i: integer;   begin readln(N); n58 := 0; n29 := 0; n2 := 0; for i := 1 to N do begin readln(a); if a mod 58 = 0 then n58 := n58 + 1 else if a mod 29 = 0 then n29 := n29 + 1 else if a mod 2 = 0 then n2 := n2 + 1; end; k58 := n58 * (n58 - 1) div 2 + n58 * (N - n58) + n2 * n29; writeln(k58) end.

var N: integer; {количество чисел} a: integer; {очередное число} n58, n29, n2: integer; k58: integer; {количество требуемых пар} i: integer; begin readln(N); n58 := 0; n29 := 0; n2 := 0; for i := 1 to N do begin readln(a); if a mod 58 = 0 then n58 := n58 + 1 else if a mod 29 = 0 then n29 := n29 + 1 else if a mod 2 = 0 then n2 := n2 + 1; end; k58 := n58 * (n58 - 1) div 2 + n58 * (N - n58) + n2 * n29; writeln(k58) end.

• Язык Python (версия Python 3):

n=int(input()) n58,n29,n2=0,0,0 for i in range(n): a=int(input()) if a % 28 == 0: n58+=1 elif a % 29 == 0: n29+=1 elif a % 2 == 0: n2+=1 k58=n58 * (n58-1) // 2 + n58 * (n-n58) + n2 * n29 print(k58)

n=int(input()) n58,n29,n2=0,0,0 for i in range(n): a=int(input()) if a % 28 == 0: n58+=1 elif a % 29 == 0: n29+=1 elif a % 2 == 0: n2+=1 k58=n58 * (n58-1) // 2 + n58 * (n-n58) + n2 * n29 print(k58)

Произведение двух чисел делится на 58, если выполнено одно из следующих условий (условия не могут выполняться одновременно).

A. Оба сомножителя делятся на 58.

Б. Один из сомножителей делится на 58, а другой не делится.

B. Ни один из сомножителей не делится на 58, но один сомножитель делится на 2, а другой — на 29.

Почему именно 2 и 29?

Берем два делителя числа 58, произведение которых дает число 58: 2*29 = 58. При этом одно из них — наименьший делитель (в нашем случае 2), а другой, не должен делиться на первый найденный делитель (29/2 <> 0).

Условие делимости произведения на 58 можно сформулировать проще, например так:

(один из сомножителей делится на 58) 
                    ИЛИ 
(один сомножитель делится на 2, а другой — на 29)

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

При вводе чисел можно определять, делится ли каждое из них на 58, 2 и 29, и подсчитывать следующие значения:

1. n58 — количество чисел, кратных 58;
2. n29 —количество чисел, кратных 29, но не кратных 2 и 58;
3. n2 — количество чисел, кратных 2, но не кратных 29 и 58.

Сами числа при этом можно не хранить. Каждое число учитывается не более чем в одном из счётчиков.

Количество пар, удовлетворяющих условию А, можно вычислить по формуле n58*(n58 - 1)/2.

Количество пар, удовлетворяющих условию Б, можно вычислить по формуле n58*(N - n58).

Количество пар, удовлетворяющих условию В, можно вычислить по формуле n2 * n29.

Поэтому искомое количество пар вычисляется по формуле:

n58 * (n58 - 1)/2 + n58 * (N - n58) + n2 * n29

✎ Программа неэффективная (2 балла):

• Язык Паскаль (версия PascalABC):

var i, j, k, n: integer; a: array[1..1000]of integer;//очередное значение   begin readln(n); for i := 1 to n do begin readln(a[i]); end; k := 0; for i := 1 to n - 1 do for j := i + 1 to n do if a[i] * a[j] mod 58 = 0 then k := k + 1; writeln(k); end.

var i, j, k, n: integer; a: array[1..1000]of integer;//очередное значение begin readln(n); for i := 1 to n do begin readln(a[i]); end; k := 0; for i := 1 to n - 1 do for j := i + 1 to n do if a[i] * a[j] mod 58 = 0 then k := k + 1; writeln(k); end.

Полный перебор: все числа сохраняются в массиве, рассматриваются все возможные пары и подсчитывается количество подходящих произведений.

Произведение двух чисел делится на 26, если выполнено одно из следующих условий (условия не могут выполняться одновременно).
А. Оба сомножителя делятся на 26.
Б. Один из сомножителей делится на 26, а другой не делится.
В. Ни один из сомножителей не делится на 26, но один сомножитель делится на 2, а другой – на 13.
Примечание для проверяющего. Условие делимости произведения на 26 можно сформулировать проще, например, так:
(один из сомножителей делится на 26) ИЛИ
(один сомножитель делится на 2, а другой – на 13).
Но в этом случае пара сомножителей может удовлетворять обоим условиям, что затруднит подсчёт количества пар.

При вводе чисел можно определять, делится ли каждое из них на 26, 2 и 13, и подсчитывать следующие значения:
1) n26 – количество чисел, кратных 26;
2) n13 – количество чисел, кратных 13, но не кратных 26;
3) n2 – количество чисел, кратных 2, но не кратных 26.

Примечание для проверяющего. Сами числа при этом можно не хранить.
Каждое число учитывается не более чем в одном из счётчиков.
Количество пар, удовлетворяющих условию А, можно вычислить по формуле n26·(n26 – 1)/2.
Количество пар, удовлетворяющих условию Б, можно вычислить по формуле n26·(N – n26).
Количество пар, удовлетворяющих условию В, можно вычислить по формуле n2·n13.
Поэтому искомое количество пар вычисляется по формуле

n26·(n26 – 1)/2 + n26·(N – n26) + n2·n13

✎ Программа эффективна и по времени, и по памяти (4 балла):
Программа на языке Паскаль (версия PascalABC):

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22

var N: integer; {количество чисел} a: integer; {очередное число} n26, n13, n2: integer; k26: integer; {количество требуемых пар} i: integer; begin readln(N); n26 := 0;n13 := 0;n2 := 0; for i := 1 to N do begin readln(a); if a mod 26 = 0 then n26 := n26 + 1 else if a mod 13 = 0 then n13 := n13 + 1 else if a mod 2 = 0 then n2 := n2 + 1; end; k26 := n26 * (n26 - 1) div 2 + n26 * (N - n26) + n2 * n13; writeln(k26) end.

var N: integer; {количество чисел} a: integer; {очередное число} n26, n13, n2: integer; k26: integer; {количество требуемых пар} i: integer; begin readln(N); n26 := 0;n13 := 0;n2 := 0; for i := 1 to N do begin readln(a); if a mod 26 = 0 then n26 := n26 + 1 else if a mod 13 = 0 then n13 := n13 + 1 else if a mod 2 = 0 then n2 := n2 + 1; end; k26 := n26 * (n26 - 1) div 2 + n26 * (N - n26) + n2 * n13; writeln(k26) end.

Программа на языке Python (версия Python 3):

1 2 3 4 5 6 7 8 9 10 11 12

n=int(input()) n26,n13,n2=0,0,0 for i in range(n): a=int(input()) if a % 26 == 0: n56+=1 elif a % 13 == 0: n13+=1 elif a % 2 == 0: n2+=1 k26=n26 * (n26-1) // 2 + n26 * (n-n26) + n2 * n13 print(k26)

n=int(input()) n26,n13,n2=0,0,0 for i in range(n): a=int(input()) if a % 26 == 0: n56+=1 elif a % 13 == 0: n13+=1 elif a % 2 == 0: n2+=1 k26=n26 * (n26-1) // 2 + n26 * (n-n26) + n2 * n13 print(k26)

Программа на языке Бейсик:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22

N26 = 0 N2 = 0 N13 = 0 NX = 0 INPUT N FOR I = 1 TO N INPUT A IF A MOD 26 = 0 THEN N26 = N26 + 1 ELSE IF A MOD 13 = 0 THEN N13 = N13 + 1 ELSE IF A MOD 2 = 0 THEN N2 = N2 + 1 ELSE NX = NX + 1 END IF END IF END IF NEXT I K26 = N26*(N26 - 1)\2 + N26*(N2 + N13 + NX) + N2*N13 PRINT K26

N26 = 0 N2 = 0 N13 = 0 NX = 0 INPUT N FOR I = 1 TO N INPUT A IF A MOD 26 = 0 THEN N26 = N26 + 1 ELSE IF A MOD 13 = 0 THEN N13 = N13 + 1 ELSE IF A MOD 2 = 0 THEN N2 = N2 + 1 ELSE NX = NX + 1 END IF END IF END IF NEXT I K26 = N26*(N26 - 1)\2 + N26*(N2 + N13 + NX) + N2*N13 PRINT K26

• ✎ Программа эффективна по времени и памяти

Язык Pascal (PascalABC):
Вариант 1:

const p = 19;   var N: integer; {количество чисел} a: integer; {очередное число} m0, m1: integer; {чётный и нечётный максимумы} mp0, mp1: integer; {чётный и нечётный максимумы, кратные p} x, y: integer; {ответ – пара чисел} i: integer;   begin m0 := 0; m1 := 0; mp0 := 0; mp1 := 0; x := 0; y := 0; readln(N); for i := 1 to N do begin readln(a); // для четных if a mod 2 = 0 then begin // если кратное if (a mod p = 0) and (a >= mp0) then begin if mp0 > m0 then m0:= mp0; mp0:=a end else if a > m0 then m0 := a; end else begin // для нечетных if (a mod p = 0)and(a>=mp1) then begin if mp1>m1 then m1:=mp1; mp1 := a; end else if a>m1 then m1:=a; end; end; // writeln('mp0=', mp0, 'm0=', m0); if (mp0 > 0) and (m0 > 0) then begin x := mp0; y := m0; end; // writeln('mp1=', mp1, 'm1=', m1); if (mp1 > 0) and (m1 > 0) and (mp1 + m1 > x + y) then begin x := mp1; y := m1; end; writeln('=', x, ' ', y) end.

const p = 19; var N: integer; {количество чисел} a: integer; {очередное число} m0, m1: integer; {чётный и нечётный максимумы} mp0, mp1: integer; {чётный и нечётный максимумы, кратные p} x, y: integer; {ответ – пара чисел} i: integer; begin m0 := 0; m1 := 0; mp0 := 0; mp1 := 0; x := 0; y := 0; readln(N); for i := 1 to N do begin readln(a); // для четных if a mod 2 = 0 then begin // если кратное if (a mod p = 0) and (a >= mp0) then begin if mp0 > m0 then m0:= mp0; mp0:=a end else if a > m0 then m0 := a; end else begin // для нечетных if (a mod p = 0)and(a>=mp1) then begin if mp1>m1 then m1:=mp1; mp1 := a; end else if a>m1 then m1:=a; end; end; // writeln('mp0=', mp0, 'm0=', m0); if (mp0 > 0) and (m0 > 0) then begin x := mp0; y := m0; end; // writeln('mp1=', mp1, 'm1=', m1); if (mp1 > 0) and (m1 > 0) and (mp1 + m1 > x + y) then begin x := mp1; y := m1; end; writeln('=', x, ' ', y) end.

Язык Pascal (PascalABC):
Вариант 2:

const p = 19;   var n, i, x, k19n, k19chet, n19chet, n19n, m1, m2: integer;   begin readln(n); {количество чисел} readln(x); {первое число} // обнуление всех переменных   k19chet := 0; // четный кратный n19chet := 0; // четный некратный k19n := 0; // нечетный кратный n19n := 0; // нечетный некратный m1 := 0; m2 := 0; // максимальные // цикл до n - 1, т.к. первое число уже считали for i := 1 to n - 1 do begin // проверка, если четный и кратный if (x mod p = 0) and (x mod 2 = 0) and (x > k19chet) then begin k19chet := x; end; // проверка, если четный и некратный if (x mod p <> 0) and (x mod 2 = 0) and (x > n19chet) then begin n19chet := x; end; // проверка, если нечетный и кратный if (x mod p = 0) and (x mod 2 = 1) and (x > k19n) then begin k19n := x; end; // проверка, если нечетный и некратный if (x mod p <> 0) and (x mod 2 = 1) and (x > n19n) then begin n19n := x; end;   readln(x); // считываем очередное число // если x кратно и есть такое некратное n19chet, сумма с которым была бы больше чем m1 + m2 if (x mod p = 0) and ((x + n19chet) mod 2 = 0) and (x + n19chet > m1 + m2) and (n19chet > 0) then begin m1 := x; m2 := n19chet; end; // если x кратно и есть такое некратное n19n, сумма с которым была бы больше чем m1 + m2 if (x mod p = 0) and ((x + n19n) mod 2 = 0) and (x + n19n > m1 + m2) and (n19n > 0) then begin m1 := x; m2 := n19n; end; // если есть такое кратное k19n, сумма с которым была бы четной и больше чем m1 + m2 if ((x + k19n) mod 2 = 0) and (x + k19n > m1 + m2) and (k19n > 0) then begin m1 := x; m2 := k19n; end; // если есть такое кратное k19chet, сумма с которым была бы четной и больше чем m1 + m2 if ((x + k19chet) mod 2 = 0) and (x + k19chet > m1 + m2) and (k19chet > 0) then begin m1 := x; m2 := k19chet; end; end; writeln(m1, ' ', m2) end.

const p = 19; var n, i, x, k19n, k19chet, n19chet, n19n, m1, m2: integer; begin readln(n); {количество чисел} readln(x); {первое число} // обнуление всех переменных k19chet := 0; // четный кратный n19chet := 0; // четный некратный k19n := 0; // нечетный кратный n19n := 0; // нечетный некратный m1 := 0; m2 := 0; // максимальные // цикл до n - 1, т.к. первое число уже считали for i := 1 to n - 1 do begin // проверка, если четный и кратный if (x mod p = 0) and (x mod 2 = 0) and (x > k19chet) then begin k19chet := x; end; // проверка, если четный и некратный if (x mod p <> 0) and (x mod 2 = 0) and (x > n19chet) then begin n19chet := x; end; // проверка, если нечетный и кратный if (x mod p = 0) and (x mod 2 = 1) and (x > k19n) then begin k19n := x; end; // проверка, если нечетный и некратный if (x mod p <> 0) and (x mod 2 = 1) and (x > n19n) then begin n19n := x; end; readln(x); // считываем очередное число // если x кратно и есть такое некратное n19chet, сумма с которым была бы больше чем m1 + m2 if (x mod p = 0) and ((x + n19chet) mod 2 = 0) and (x + n19chet > m1 + m2) and (n19chet > 0) then begin m1 := x; m2 := n19chet; end; // если x кратно и есть такое некратное n19n, сумма с которым была бы больше чем m1 + m2 if (x mod p = 0) and ((x + n19n) mod 2 = 0) and (x + n19n > m1 + m2) and (n19n > 0) then begin m1 := x; m2 := n19n; end; // если есть такое кратное k19n, сумма с которым была бы четной и больше чем m1 + m2 if ((x + k19n) mod 2 = 0) and (x + k19n > m1 + m2) and (k19n > 0) then begin m1 := x; m2 := k19n; end; // если есть такое кратное k19chet, сумма с которым была бы четной и больше чем m1 + m2 if ((x + k19chet) mod 2 = 0) and (x + k19chet > m1 + m2) and (k19chet > 0) then begin m1 := x; m2 := k19chet; end; end; writeln(m1, ' ', m2) end.

Язык Python (Python 3):

p = 19 m0 = m1 = mp0 = mp1 = 0 N = int(input()) for i in range(N): a = int(input()) if a % 2 == 0: if a % p == 0 and a >= mp0: if mp0 > m0: m0 = mp0 mp0 = a elif a > m0: m0 = a else: if a % p == 0 and a >= mp1: if mp1 > m1: m1 = mp1 mp1 = a elif a > m1: m1 = a x = y = 0 if mp0 > 0 and m0 > 0: x = mp0; y = m0 if mp1 > 0 and m1 > 0 and mp1 + m1 > x + y: x = mp1; y = m1 print(x,y)

p = 19 m0 = m1 = mp0 = mp1 = 0 N = int(input()) for i in range(N): a = int(input()) if a % 2 == 0: if a % p == 0 and a >= mp0: if mp0 > m0: m0 = mp0 mp0 = a elif a > m0: m0 = a else: if a % p == 0 and a >= mp1: if mp1 > m1: m1 = mp1 mp1 = a elif a > m1: m1 = a x = y = 0 if mp0 > 0 and m0 > 0: x = mp0; y = m0 if mp1 > 0 and m1 > 0 and mp1 + m1 > x + y: x = mp1; y = m1 print(x,y)

Ещё один путь решения – записать всю последовательность в массив и анализировать её в несколько проходов. Ниже приводится реализующая такой алгоритм программа на языке C++. В этой программе массив с исходными данными обрабатывается два раза: на первом проходе находятся индексы максимального чётного и нечётного элементов, кратных p, на втором проходе – общие чётный и нечётный максимумы. При этом элементы, выделенные как кратные при первом проходе, во время второго прохода из сравнения исключаются. Такая программа эффективна по времени (несмотря на повторную обработку массива, общее время работы пропорционально N), но неэффективна по памяти. Максимальная оценка за такую программу при отсутствии в ней синтаксических и содержательных ошибок – 3 балла.

✎ Правильная программа на языке C++, эффективная только по времени

С++:

#include <iostream> using namespace std; int main() { const int p = 19; // делитель int N; cin >> N; // количество элементов int a[N]; // элементы последовательности for (int i = 0; i < N; ++i) cin >> a[i]; int imp0 = -1, imp1 = -1; //индексы максимумов, кратных p for (int i = 0; i < N; ++i) { if (a[i] % p == 0) { if (a[i] % 2 == 0) { if (imp0 == -1 || a[i] > a[imp0]) imp0 = i; } else { if (imp1 == -1 || a[i] > a[imp1]) imp1 = i; } } } int im0 = -1, im1 = -1; // индексы общих максимумов for (int i = 0; i < N; ++i) { if (i != imp0 && i != imp1) { if (a[i] % 2 == 0) { if (im0 == -1 || a[i] > a[im0]) im0 = i; } else { if (im1 == -1 || a[i] > a[im1]) im1 = i; } } } int x = 0, y = 0; // пара чисел для ответа if (imp0 != -1 && im0 != -1) { x = a[imp0]; y = a[im0]; } if (imp1 != -1 && im1 != -1 && a[imp1] + a[im1] > x + y) { x = a[imp1]; y = a[im1]; } cout << x << ' ' << y << endl; return 0; }

#include <iostream> using namespace std; int main() { const int p = 19; // делитель int N; cin >> N; // количество элементов int a[N]; // элементы последовательности for (int i = 0; i < N; ++i) cin >> a[i]; int imp0 = -1, imp1 = -1; //индексы максимумов, кратных p for (int i = 0; i < N; ++i) { if (a[i] % p == 0) { if (a[i] % 2 == 0) { if (imp0 == -1 || a[i] > a[imp0]) imp0 = i; } else { if (imp1 == -1 || a[i] > a[imp1]) imp1 = i; } } } int im0 = -1, im1 = -1; // индексы общих максимумов for (int i = 0; i < N; ++i) { if (i != imp0 && i != imp1) { if (a[i] % 2 == 0) { if (im0 == -1 || a[i] > a[im0]) im0 = i; } else { if (im1 == -1 || a[i] > a[im1]) im1 = i; } } } int x = 0, y = 0; // пара чисел для ответа if (imp0 != -1 && im0 != -1) { x = a[imp0]; y = a[im0]; } if (imp1 != -1 && im1 != -1 && a[imp1] + a[im1] > x + y) { x = a[imp1]; y = a[im1]; } cout << x << ' ' << y << endl; return 0; }

• ✎ Правильная, но неэффективная программа на языке Паскаль
Запишем все исходные числа в массив, переберём все возможные пары и выберем подходящую. Такое решение не является эффективным ни по памяти (требуемая память зависит от размера исходных данных), ни по времени (количество возможных пар, а значит, количество действий и время счёта с ростом количества исходных элементов растут квадратично). Подобная программа оценивается не выше 2 баллов.

Язык Pascal (версия PascalABC):

const p = 19; var N: integer; {количество чисел} a: array [1..10000] of integer; {исходные данные} x, y: integer; {ответ – пара чисел} i, j: integer; begin readln(N); for i := 1 to N do readln(a[i]); x := 0; y := 0; for i := 1 to N - 1 do begin for j := i + 1 to N do begin if ((a[i] - a[j]) mod 2 = 0) and ((a[i] mod p = 0) or (a[j] mod p = 0)) and (a[i] + a[j] > x + y) then begin x := a[i]; y := a[j] end end end; writeln(x, ' ', y) end.

const p = 19; var N: integer; {количество чисел} a: array [1..10000] of integer; {исходные данные} x, y: integer; {ответ – пара чисел} i, j: integer; begin readln(N); for i := 1 to N do readln(a[i]); x := 0; y := 0; for i := 1 to N - 1 do begin for j := i + 1 to N do begin if ((a[i] - a[j]) mod 2 = 0) and ((a[i] mod p = 0) or (a[j] mod p = 0)) and (a[i] + a[j] > x + y) then begin x := a[i]; y := a[j] end end end; writeln(x, ' ', y) end.

✎ Задание Б (алгоритм), более сложное, 4 балла:

• поскольку в задании указано, что «имеется набор данных, состоящих из пар…», то введем в программу переменную n для количества пар, значение которой будет считываться со стандартного входного потока:

n:longint; {количество пар чисел};

n:longint; {количество пар чисел};

• объявим сами числа типа integer, переменную цикла — i — типа integer и дополнительные переменные, смысл которых будет объяснен ниже. Объявление сделаем в отдельных строках (так делать не обязательно), чтобы можно было ввести удобно комментарии:

x,y: integer; {пара чисел} max: integer; {максимальное из пары} min: integer; {минимальное из пары} sum:longint; {сумма квадратов отобранных чисел} min_kvadr:longint; {мин. нечетная разница квадратов max и min} i:integer;

x,y: integer; {пара чисел} max: integer; {максимальное из пары} min: integer; {минимальное из пары} sum:longint; {сумма квадратов отобранных чисел} min_kvadr:longint; {мин. нечетная разница квадратов max и min} i:integer;

• так как в задании не оговаривается, что пары чисел считывается из файла, значит их необходимо считать со стандартного входного потока оператором readln(); т.е. организуем цикл:

for i:=1 to n do begin readln(x,y); ...

for i:=1 to n do begin readln(x,y); ...

Допустим имеем пары:

2 6
4 1
7 3
2 9
7 4

• Чтобы получить в итоге максимальную сумму, то необходимо суммировать те числа из пар чисел, которые максимальны в паре, т.е. в нашем случае будем суммировать квадраты выделенных чисел из пар:

2 6
4 1
7 3
2 9
7 4

• но сначала определим максимальное и минимальное число из каждой пары:

if x>y then begin max:=x; min:=y end else begin max:=y;min:=x end;

if x>y then begin max:=x; min:=y end else begin max:=y;min:=x end;

• далее суммируем квадраты максимальных чисел:

sum:=sum+sqr(max);

sum:=sum+sqr(max);

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

2 6 - разница 32 (36 - 4)
4 1 - разница 15 (16 - 1)
7 3 - разница 40 (49 - 9)
2 9 - разница 77 (81 - 4)
7 4 - разница 33 (49 - 16)

• поиск минимальной и нечетной разницы между квадратами чисел в паре:

if((max-min) mod 2 > 0) and ((sqr(max)-sqr(min)) < min_kvadr) then min_kvadr:=sqr(max) - sqr(min)

if((max-min) mod 2 > 0) and ((sqr(max)-sqr(min)) < min_kvadr) then min_kvadr:=sqr(max) - sqr(min)

• для переменной, обозначающей разницу, до цикла необходимо назначить максимально возможное значение:

min_kvadr:=1073676289; {32 767 * 32 767 (самое большое в типе integer) }

min_kvadr:=1073676289; {32 767 * 32 767 (самое большое в типе integer) }

• таким образом, в цикле у нас происходит:
• 1. поиск максимального и минимального числа из пары;
• 2. вычисляется сумма максимальных чисел из каждой пары;
• 3. находится минимальная разница квадратов максимального и минимального числа в парах.
• после цикла необходимо проверить сумму на нечетность. Если сумма четная (чего НЕ должно быть по условию), то отнимем от суммы вычисленную минимальную разницу. Но при этом учтем, что если не нашлось нечетной минимальной разницы, то выводим 0 (по условию):

if sum mod 2 = 0 then begin if min_kvadr = 1073676289 then sum := 0 else sum:=sum - min_kvadr end;

if sum mod 2 = 0 then begin if min_kvadr = 1073676289 then sum := 0 else sum:=sum - min_kvadr end;

Эффективная программа на языке Паскаль (версия Pascal ABC):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

var
 n:longint; {количество пар чисел}
 x,y: integer; {пара чисел}
 max: integer; {максимальное из пары}
 min: integer; {минимальное из пары}
 sum:longint; {сумма квадратов отобранных чисел}
 min_kvadr:longint; {мин. нечетная разница квадратов max и min}
 i:integer;
begin
sum:=0;
readln(n);
min_kvadr:=1073676289;  {32 767 * 32 767, самое большое integer}
for i:=1 to n do begin
  readln(x,y);
  if x>y then begin max:=x; min:=y end
  else begin max:=y;min:=x end;
  sum:=sum+sqr(max);
  if((max-min) mod 2 > 0) and (sqr(max)-sqr(min) < min_kvadr) then
    min_kvadr:=sqr(max) - sqr(min)
end;
if sum mod 2 = 0 then begin
  if min_kvadr = 1073676289 then sum := 0
  else sum:=sum - min_kvadr
end;
writeln('sum=',sum)
end.

Пример работы программы:

3
1 4
2 4
3 4
sum=41

✎ Задание А (более легкое, 2 балла максимум):

• так как в задании указано, что пар чисел ровно 5, то введем в программу константу n=5

Решение на языке Паскаль (версия PascalABC):

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25

const n = 5; {количество пар чисел} var x,y: longint; {пара чисел} max_sum: longint; {максимальная из сумм} sum:array [1..15]of longint; {суммы квадратов всех комбинаций чисел} i,k:longint; begin readln(x,y); sum[1]:=sqr(x); sum[2]:=sqr(y); k:=3; {счетчик для сумм} for i:=2 to n do begin readln(x,y); sum[k]:=sum[k-2]+sqr(x); {1 шаг: s3=s1+x*x}{2 шаг: s7=s4+x*x} sum[k+1]:=sum[k-2]+sqr(y); {1 шаг: s4=s1+y*y}{2 шаг: s8=s4+y*y} sum[k+2]:=sum[k-1]+sqr(x); {1 шаг: s5=s2+x*x}{2 шаг: s9=s6+x*x} sum[k+3]:=sum[k-1]+sqr(y); {1 шаг: s6=s2+y*y}{2 шаг: s10=s6+y*y} k:=k+4; end; max_sum:=sum[1]; for i:=1 to n*n do if (sum[i]>max_sum) and (sum[i] mod 2 <>0) then max_sum:=sum[i]; if (max_sum=sum[1]) and (max_sum mod 2 = 0) then max_sum:=0; writeln(max_sum) end.

const n = 5; {количество пар чисел} var x,y: longint; {пара чисел} max_sum: longint; {максимальная из сумм} sum:array [1..15]of longint; {суммы квадратов всех комбинаций чисел} i,k:longint; begin readln(x,y); sum[1]:=sqr(x); sum[2]:=sqr(y); k:=3; {счетчик для сумм} for i:=2 to n do begin readln(x,y); sum[k]:=sum[k-2]+sqr(x); {1 шаг: s3=s1+x*x}{2 шаг: s7=s4+x*x} sum[k+1]:=sum[k-2]+sqr(y); {1 шаг: s4=s1+y*y}{2 шаг: s8=s4+y*y} sum[k+2]:=sum[k-1]+sqr(x); {1 шаг: s5=s2+x*x}{2 шаг: s9=s6+x*x} sum[k+3]:=sum[k-1]+sqr(y); {1 шаг: s6=s2+y*y}{2 шаг: s10=s6+y*y} k:=k+4; end; max_sum:=sum[1]; for i:=1 to n*n do if (sum[i]>max_sum) and (sum[i] mod 2 <>0) then max_sum:=sum[i]; if (max_sum=sum[1]) and (max_sum mod 2 = 0) then max_sum:=0; writeln(max_sum) end.

✎ Задание Б (4 балла)

Пример правильной и эффективной программы для задания Б на языке Паскаль (версия PascalABC):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

const
  aMax = 10000;{наибольшее возможное исходное число}
 
var
  N: longint; {количество троек}
  a, b, c, tmp: longint;{тройка чисел}
  s: longint;{сумма выбранных чисел}
  D_min: longint;{мин. разница в тройке не кратная 5}
  i: longint;{}
 
begin
  s := 0;
  D_min := aMax + 1;
  readln(N);
  for i := 1 to N do 
  begin
    readln(a, b, c);
    if (a > b) then begin tmp := a;a := b;b := tmp end;
    if(b > c) then begin
      tmp := b;b := c;c := tmp;
      if (a > b) then begin tmp := a;a := b;b := tmp end
    end; {a,b,c отсортированы по возрастанию}
    s := s + a;
    if((b - a) mod 5 > 0 ) and ((b - a) < D_min) then D_min := b - a;
    if((c - a) mod 5 > 0 ) and ((c - a) < D_min) then D_min := c - a
  end;
  if s mod 5 = 0 then begin
    if D_min > aMax then s := 0
    else s := s + D_min
  end;
  writeln(s)
end.

✎ Задание А (2 балла)

На языке Паскаль (версия PascalABC):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

var
  a: array[1..5, 1..3] of longint; 
  i1, i2, i3, i4, i5: longint; 
  s, sMin: longint;
 
begin
  for i1 := 1 to 5 do 
    readln(a[i1, 1], a[i1, 2], a[i1, 3]); 
  sMin := 100000; 
  for i1 := 1 to 3 do 
    for i2 := 1 to 3 do 
      for i3 := 1 to 3 do
        for i4 := 1 to 3 do
          for i5 := 1 to 3 do 
          begin
            s := a[1, i1] + a[2, i2] + a[3, i3] + a[4, i4] + a[5, i5];
            if (s mod 5 = 0) and (s < sMin) then 
              sMin := s
          end;
  if (sMin = 100000) then 
    sMin := 0; 
  writeln(sMin)
end.

✎ Программа на языке Паскаль (версия PascalABC). Программа неэффективна ни по времени, ни по памяти (2 балла):

• Перебор всех вариантов произведений:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18

const s = 4;//требуемое расстояние   var n, i, j, cnt: integer; a: array[1..1000] of integer;   begin readln(n); cnt := 0; for i := 1 to n do readln(a[i]); for i := 1 to n - s do for j := i + s to n do if a[i] * a[j] mod 29 = 0 then cnt := cnt + 1; writeln(cnt) end.

const s = 4;//требуемое расстояние var n, i, j, cnt: integer; a: array[1..1000] of integer; begin readln(n); cnt := 0; for i := 1 to n do readln(a[i]); for i := 1 to n - s do for j := i + s to n do if a[i] * a[j] mod 29 = 0 then cnt := cnt + 1; writeln(cnt) end.

✎ Программа на языке Паскаль (версия PascalABC). Программа эффективна и по времени, и по памяти (4 балла):

• Если один из сомножителей делится без остатка на 29, то произведение с любым другим сомножителем тоже будет делится на 29.
• Последние рассматриваемые 4 элемента можно хранить как 4 счётчика: количество делящихся на 29 среди всех считанных чисел, всех считанных чисел без последнего, всех считанных чисел без 2 последних, всех считанных чисел без 3 последних, – и также сдвигать их после очередного шага.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31

const s = 4;//требуемое расстояние   var n,i: integer; n1, n2, n3, n4: integer; //хранение последних s счетчиков a_: integer; //очередное значение cnt: integer;//количество искомых пар   begin readln(n); n1 := 0;n2 := 0;n3 := 0;n4 := 0; cnt := 0; for i := 1 to n do begin readln(a_); // очередное значение if i > s then if a_ mod 29 = 0 then cnt := cnt + (i - s) else cnt := cnt + n4; // сдвигаем элементы счетчика n4 := n3; n3 := n2; n2 := n1; // обновляем счетчик кратных 29 if a_ mod 29 = 0 then n1 := n1 + 1; end; writeln(cnt) end.

const s = 4;//требуемое расстояние var n,i: integer; n1, n2, n3, n4: integer; //хранение последних s счетчиков a_: integer; //очередное значение cnt: integer;//количество искомых пар begin readln(n); n1 := 0;n2 := 0;n3 := 0;n4 := 0; cnt := 0; for i := 1 to n do begin readln(a_); // очередное значение if i > s then if a_ mod 29 = 0 then cnt := cnt + (i - s) else cnt := cnt + n4; // сдвигаем элементы счетчика n4 := n3; n3 := n2; n2 := n1; // обновляем счетчик кратных 29 if a_ mod 29 = 0 then n1 := n1 + 1; end; writeln(cnt) end.

✎ Задание А (решение на языке Паскаль, версия pascalABC):
Ниже приводится пример переборного решения на Паскале, неэффективного ни по памяти, ни по времени, но являющегося правильным ответом на задание А.

const s = 8;{требуемое расстояние между показаниями}   var N: integer; a: array[1..10000] of integer; {все показания датчика} mp: integer; {минимальное значение произведения} i, j: integer;   begin readln(N); {Ввод значений датчика} for i := 1 to N do readln(a[i]); mp := 1000 * 1000 + 1; for i := 1 to N - s do begin for j := i + s to N do begin if (a[i] * a[j] mod 2 = 0) and (a[i] * a[j] < mp) then mp := a[i] * a[j] end; end; if mp = 1000 * 1000 + 1 then mp := -1; writeln(mp) end.

const s = 8;{требуемое расстояние между показаниями} var N: integer; a: array[1..10000] of integer; {все показания датчика} mp: integer; {минимальное значение произведения} i, j: integer; begin readln(N); {Ввод значений датчика} for i := 1 to N do readln(a[i]); mp := 1000 * 1000 + 1; for i := 1 to N - s do begin for j := i + s to N do begin if (a[i] * a[j] mod 2 = 0) and (a[i] * a[j] < mp) then mp := a[i] * a[j] end; end; if mp = 1000 * 1000 + 1 then mp := -1; writeln(mp) end.

✎Задание Б (решение на языке Паскаль, версия pascalABC):

const
  s = 8; {требуемое расстояние между показаниями}
  amax = 1001;{больше максимально возможного показания}
 
var
  N: integer;
  a: array[1..s] of integer; {хранение s показаний датчика} 
  a_: integer; {ввод очередного показания} 
  ma: integer; {минимальное число без s последних} 
  me: integer; {минимальное чётное число без s последних} 
  mp: integer; {минимальное значение произведения} 
  p: integer;
  i, j: integer;
 
begin
  readln(N);
  {Ввод первых s чисел}
  for i := 1 to s do readln(a[i]);
  {Ввод остальных значений, поиск минимального произведения} 
  ma := amax;me := amax;mp := amax * amax;
  for i := s + 1 to N do 
  begin
    readln(a_);
    if a[1] < ma then ma := a[1];
    if (a[1] mod 2 = 0) and (a[1] < me) then me
    := a[1];
    if a_ mod 2 = 0 then p := a_ * ma
    else if me < amax then p := a_ * me
    else p := amax * amax;
    if (p < mp) then mp := p;
    {сдвигаем элементы вспомогательного массива влево}
    for j := 1 to s - 1 do
      a[j] := a[j + 1];
    a[s] := a_
  end;
  if mp = amax * amax then mp := -1;
  writeln(mp)
end.

• Нарисуем таблицу, в первом столбце которой будем откладывать количество камней в первой куче, а в первой строке — количество камней во второй куче. Получим матрицу. Поскольку в первой куче количество начинается с 5, то это и будет первым значением в таблице. Во второй куче начнем с наибольшего возможного числа — 53. Таблица пригодится для решения заданий 20 и 21:



• Для начала найдем все выигрышные позиции для первой строки таблицы, т.е. для первого хода. Обозначим их плюсами (+):



Выигрышные позиции для первой строки ищем по принципу увеличения количества камней S в 2 два раза: 5 + S*2 >=59. Получим S>=27
• Для того, чтобы получить наименьшее значение S, в качестве первого хода Пети необходимо увеличивать в два раза вторую кучу. Т.е. для решения задания необходимо найти такое наименьшее S, при котором Петя походил неверно, и попал своим ходом в выигрышную позицию для своего соперника, т.е. в ячейку с плюсом:



S = 14
1 ход Петя: 14*2 = (5,28)
2 ход Ваня: 28*2 = (5,56), Сумма = 61, Выигрыш! 

Ответ: 14
  
✎ Задание 20:

• Проанализируем таблицу, и для каждой строки найдем выигрышные позиции с одного хода. Т.е. которые позволят игроку, оказавшемуся «на них», выиграть за один ход (получить суммарно 59 и более камней):



При заполнении таблицы выигрышными позициями можно проследить закономерность «узора», а заполнять позиции по аналогии.
• Найдем проигрышные позиции: те, которые ведут только в выигрышные позиции для соперника (ведут только в плюсы)



Проигрышные позиции: (6,26) (8,25) (10,24) (12,23) (14,22)
• В задании требуется найти минимальное S, котором выиграет Петя, но выиграет он НЕ первым своим ходом, а вторым. То есть в нашем случае необходимо найти S, которое может перевести соперника в проигрышную позицию. То есть в минус. Для первой строки (так как первым будет ходить Петя) таких значений два:



• Наименьшее S = 24

Ответ: 24
 
✎ Задание 21:

• Для решения этого задания найдем выигрышные позиции со второго хода, т.е. которые могут перевести соперника в проигрышную позицию (с минусом):



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

Ответ: 23 25

• В столбце А отложим значения — количество камней в первой куче. Начнем с ячейки А2, в которую внесем начальное количество камней, т.е. 10. Автозаполнением продлим значения вниз до 0:



• В строке 1 таблицы (начиная с ячейки B1) отложим значения для второй кучи. Поскольку в задании говорится, что победа будет достигнута при S<=20, и достигнуть этого значения более сильной командой можно уменьшив кол-во камней во второй куче в два раза, начиная с числа 40: 40/20. То есть возьмем значение больше 40, примерно 45. Используем автозаполнение до значения 11:



• Из двух команд, которые могут выполнять игроки, выберем наиболее сильную, т.е. благодаря которой можно быстрее достичь выигрышного диапазона и попасть в значения S<=20. Это команда уменьшения количества камней в два раза, т.е. /2.
• Для каждой из ячеек полученной таблицы рассчитаем значение, полученное в результате уменьшения в два раза той кучи камней, в которой большее количество камней (так как это даст меньший результат). Например, для ячейки С5, в которой игрок имеет в первой куче 7 камней, а во второй куче 44 камня, мы бы выполнили действие 44/2+7. Т.е. уменьшили вдвое вторую кучу, т.к. в ней больше камней. Еще необходимо обращать внимание на четность и нечетность значений (в Excel это функция ЕНЕЧЁТ — возвращает ИСТИНУ, если значение нечетно).
• Чтобы автоматизировать процесс необходимо использовать формулу, в которой найдем максимальное значение из двух вариантов:

Минимальное из
(ЕСЛИ(ЕНЕЧЁТ(1-я куча) то (1-я куча+1)/2+2-я куча, 
иначе 1-я куча/2+2-я куча);
ЕСЛИ(ЕНЕЧЁТ(2-я куча) то (2-я куча+1)/2+1-я куча, 
иначе 2-я куча/2+1-я куча)).

• Выразив это в формуле Excel, получим результат, который внесем в ячейку B2:

 = МИН(ЕСЛИ(ЕНЕЧЁТ($A2);($A2+1)/2+B$1;$A2/2+B$1);ЕСЛИ(ЕНЕЧЁТ(B$1);(B$1+1)/2+$A2;B$1/2+$A2))

• Здесь знак $ будем использовать для фиксации столбца А и строки 1 при копировании формулы.
• Скопируем формулу на всю таблицу.
• Выделим всю таблицу и используем Условное форматирование для выделения тех значений, которые попадают в выигрыш (<21):



• Выделенные значения — это значения, которые можно получить в сумме двух куч, выполнив ход из данной ячейки. И по сути, это и есть выигрышные позиции с 1 хода.
• Далее следуем логике рассуждения: Ваня сможет выиграть своим первым ходом в том случае, если Петя оказывается РЯДОМ с выигрышной позицией, и любой его ход попадает ТОЛЬКО в выигрышные позиции для Вани (в выделенную область). Это позиция при S = 21:

Ответ: 21
✎ Задание 20:

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



• Петя может выиграть свои вторым ходом, если он не может выиграть первым ходом, но может выполнить ход в позицию, проигрышную для соперника (в ячейку, выделенную красным). Такие позиции назовем выигрышные позиции со второго хода. Найдем минимальное и максимальное значение S при таком первом ходе Пети:



При S=44 Пете необходимо уменьшить 2-ю кучу вдвое (44/2 = 22), чтобы оказаться в проигрышной позиции для соперника.

Ответ: 22 44
  
✎ Задание 21:

• Выделим все такие выигрышные позиции со второго хода:



• Далее придерживаемся следующей логики: Ваня сможет выиграть свои первым или вторым ходом, но при этом не гарантированно первым ходом, если у Пети будет возможность выполнить ходы только в позиции выигрышные со второго хода. Найдем такое S:



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

Ответ: 24

• Задание 19.
  Максимальное S при котором Петя НЕ может выиграть своим первым ходом S = 22. Петя проиграет, если в сумме получится 55 и меньше. Первое значение = 10, необходимо найти второе значение, при этом максимальное. Схематично отобразим варианты ходов:

(10,22) - ход Пети - (10+22, 22) - итог суммы обеих значений таблички: 32 + 22 = 54 (<56)

Для того, чтобы сделать сумму большей, Петя заменит первое значение на сумму, так как оно меньше второго значения (10<22)
• Задание 20.
  В начальной позиции (9, 15) выигрышная стратегия есть у Вани. Для себя отобразим схематично выигрышную партию Вани:



Зеленым цветом выделены выигрышные ходы.
• Задание 21.
  В начальной позиции (3, 7) выигрышная стратегия есть у Вани. Изобразим дерево всех возможных партий при этой стратегии (раз говорится "при этой стратегии" имеем в виду, выигрышную стратегию Вани):




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

• Нарисуем таблицу, в первом столбце которой будем откладывать количество камней в первой куче, а в первой строке - количество камней во второй куче. Получим матрицу. Поскольку в первой куче количество начинается с 5, то это и будет первым значением в таблице. Во второй куче начнем с наибольшего возможного числа - 38:


 
Задание 19 а):

• Далее будем рассуждать так: Петя может выиграть первым ходом, выполнив команду *2 (увеличить количество камней в куче в два раза), если вместо S (кол-во камней во второй куче), мы будем изменять значение, начиная от 20, до последнего возможного по условию значения 38:

5 + 20*2 = 45 (>44)

* 5 - кол-во камней в первой куче, оно не меняется по условию

• Соответственно, все значения большие 20 дадут в результате число большее 44. Укажем это в таблице. + означает выигрышную позицию с первого хода:


Ответ 1 а): S = [20;38] (На ЕГЭ пояснить ходы, например: (5; 20) -> (Ход Пети)-> (5;40); 40 + 5 = 45)
  
Задание 19 б):

• Поскольку Ваня будет ходить вторым, то необходимо поменять количество камней и в первой куче. Значит рассмотрим ситуации, что Петя мог бы ходить первым ходом в (7;S) и в (10;S). Укажем, будут ли эти позиции выигрышные с одного хода: например (7;19) выигрышная позиция, т.к. игрок выполнит ход в (7;38) и выиграет (7 + 38 = 45). Соответственно, выигрышными являются и все позиции (7;больше 19). Проанализируем таблицу, увеличивая количество камней в первой куче и выполняя поиск выигрышных позиций с одного хода:



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



• Находим единственное такое значение - (5; 19). Т.е. S = 19.

Ответ 1 б): S = 19 (На ЕГЭ пояснить ходы, например: (5; 19) -> (Ходы Пети): (5;21),(5;28);(7;19);(7;28). Везде следующим ходом выиграет Ваня, см. предыдущ. пункт)
  
Задание 20:

• Обратим внимание, что в таблице, все образовавшиеся "уголки" являются проигрышными позициями (с 1-го хода): то есть если игрок, оказывается в такой позиции, то он может выполнить ход только в выигрышные позиции (то есть следующим ходом выиграет соперник):



• Логика рассуждений: Петя сможет выиграть своим вторым ходом, когда своим первым ходом он попадет в проигрышную позицию, т.е. переведет соперника в проигрышную ситуацию. Такие значения: S = 16, 17 или 18. Назовем эти позиции выигрышными со второго хода (2+):

Ответ 2: S = 16, 17 или 18 (На ЕГЭ пояснить ходы, ссылаясь на объяснения в предыдущих пунктах)
 
Задание 21:

Ответ 3: S = 14 (На ЕГЭ пояснить ходы, ссылаясь на объяснения в предыдущих пунктах)

Задание 19.
• а) Петя может выиграть, если S = 15, ... 28

15, ..., 28 - выигрышные позиции с первого хода

• б) Ваня может выиграть первым ходом (как бы ни играл Петя), если в куче будет S = 14 камней. Тогда после первого хода Пети в куче будет 15 или 28 камней. В обоих случаях Ваня удваивает кучу и выигрывает в один ход.

S = 14
Петя: 14 + 1 = 15  выигрышная позиция (см. п. а). Выигрывает Ваня
Петя: 14 * 2 = 28   выигрышная позиция (см. п. а). Выигрывает Ваня

14 - проигрышная позиция

Задание 20.

• Возможные значения S: 7, 13. В этих случаях Петя, очевидно, не может выиграть первым ходом. Однако он может получить кучу из 14 камней: в первом случае удвоением, во втором - добавлением одного камня. Эта позиция разобрана в п. 1б. В ней игрок, который будет ходить (теперь это Ваня), выиграть не может, а его противник (то есть Петя) следующим ходом выиграет.

S = 7
Петя: 7 * 2 = 14  проигрышная позиция (см. п. 1 б). Выигрывает Петя
S = 13
Петя: 13 + 1 = 14 проигрышная позиция (см. п. 1 б). Выигрывает Петя

7, 13 - выигрышные позиции со второго хода

Задание 21.

• Возможные значения S: 12. После первого хода Пети в куче будет 13 или 24 камня. Если в куче их станет 24, Ваня удвоит количество камней и выиграет первым ходом. Ситуация, когда в куче 13 камней, разобрана в п. 2. В этой ситуации игрок, который будет ходить (теперь это Ваня), выигрывает своим вторым ходом.

S = 12
Петя: 12 + 1 = 13  
Ваня: 13 + 1 = 14 проигрышная позиция (см. п. 1 б). Выигрывает Ваня вторым ходом!

В таблице изображено дерево возможных партий (и только их) при описанной стратегии Вани. Заключительные позиции (в них выигрывает Ваня) подчеркнуты. На рисунке это же дерево изображено в графическом виде.

Дерево всех партий, возможных при стратегии Вани:

* красный круг означает выигрыш

19.
а) S ≥ 14. При количестве камней в куче от 14 и выше Паше необходимо увеличить их количество в пять раз, тем самым получив 70 или более камней.

S ≥ 14 выигрышные позиции

 
б) S = 13. Паша своим первым ходом может сделать 14, 17 или 65 камней, после этого Вася увеличивает количество в пять раз, получая 70, 85 или 325 камней в куче.

S = 13 
Паша 1 ход: 13 + 1 = 14
Паша 1 ход: 13 + 4 = 17
Паша 1 ход: 13 * 5 = 65

Ваня 1 ход: [14, 17, 65] * 5 = S ≥ 14  Ваня выигрывает

13 - проигрышная позиция

20. S = 9, 12. Для данных случаев Паше необходимо прибавить 4 камня к куче из 9 камней, либо 1 камень к куче из 12, и получить кучу из 13 камней.
После чего игра сводится к стратегии, описанной в пункте 1б.

S = 13 
Паша 1 ход: 9 + 4 = 13  Паша выигрывает
Паша 1 ход: 12 + 1 = 13 Паша выигрывает

9, 12 - выигрышные позиции со второго хода

21. S = 8. Своим первым ходом Паша может сделать количество камней в куче 9, 12 или 40. Если Паша увеличивает кол-во в пять раз, тогда Вася выигрывает своим первым ходом, увеличивая количество камней в пять раз.
Для случая 9 и 12 камней Вася использует стратегию, указанную в п.2.

S = 8 
Паша 1 ход: 8 + 1 = 9   Ваня Выигрывает (см. п.2)
Паша 1 ход: 8 + 4 = 12  Ваня Выигрывает (см. п.2)
Паша 1 ход: 8 * 5 = 40  

а) Паша имеет выигрышную стратегию и может выиграть за один ход, если S = 27: тогда ему достаточно добавить один камень, чтобы игра закончилась при 28 камнях в куче; или если S = 14, 15, 16, 17, 18, 19, 20, 21, 22 (44/2 = 22 и 28/2 = 14, т.е. от 14 до 22): тогда необходимо удвоить кучу.

S=27
Паша: 27 + 1 = 28 - Выигрыш!

27 - выигрышная позиция

б) При S = 26 выигрышная стратегия есть у Вали. Паша делает ход первым, у него есть возможность либо удвоить количество камней в куче, и тогда количество превысит 44, - выигрывает Валя; либо увеличить количество на один камень, станет 27 камней: следующая Валя, - она может положить один камень и выиграть.

S=26
Паша: 26 * 2 = 52   Валя выигрывает! или:
Паша: 26 + 1 = 27
Валя: 27 + 1 = 28 - Выигрыш! 

26 - проигрышная позиция

При S = 25 выигрышная стратегия есть у Паши. Удваивать количество камней нет смысла, т.к. количество превысит 44, значит, Паша добавит один камень, их станет 26, следующая Валя, — она может либо добавить камень (станет 27 камней, следующим ходом выиграет Паша) либо удвоить — и сразу проиграть, т.к. станет более 44 камней.

S=25
Паша: 25 + 1 = 26
Валя: 26 ...  проигрышная позиция (см. выше) Паша выигрывает!

25 - выигрышная позиция

При S = 24 выигрышная стратегия есть у Вали. Паша делает ход первым: удваивать кучу нет смысла, т.к. в ней станет более 44, значит, Паша добавит один камень, их станет 25; следующая — Валя: она может только добавить один камень (станет 26 камней, следующим ходом Паша оказывается в проигрышной позиции, см. пункт при S = 26).

S=24
Паша: 24 + 1 = 25 
Валя: 25 ...  выигрышная позиция (см. выше) Валя выигрывает!
 
24 - проигрышная позиция

При S = 13 или S = 12 выигрышная стратегия есть у Паши. Паша удваивает количество и в куче остается 26 или 24 камня. Это проигрышная позиция для того, кто ходит (см. п. 1 б), а следующий ход за Валей.
При S = 11 выигрышная стратегия есть у Вали. Паша делает первый ход: в куче остается либо 22, либо 12 камней. Обе эти позиции выигрышные для того, кто ходит. При S = 12 последовательность игры описана в пункте 2, а при S = 22 - в пункте 1а.

  
Дерево возможных партий:


* Для Вали отображены только ходы по стратегии
** красный круг означает выигрыш
*** фиолетовый круг - конец игры (проигрыш)

• Задание 1. В начальных позициях (6, 33), (8, 32) выигрышная стратегия есть у Вани.
• Задание 2. В начальных позициях (6, 32), (7, 32) и (8, 31) выигрышная стратегия есть у Пети.
• Задание 3. В начальной позиции (7, 31) выигрышная стратегия есть у Вани.

А) Для выигрыша Пете достаточно выбрать первую букву слова с нечетным количеством букв, тогда последний ход делает Петя. При исходном наборе слов выигрышная стратегия есть у Пети. Она заключается в том, что своим первым ходом он должен выбрать букву И (слово ИКЛМНИКЛМНХ из 11 букв). Ване придется выбрать букву К. Таким образом, они последовательно будут называть буквы первого слова, пока Петя не выберет последнюю букву Х. На этом игра закончится выигрышем Пети. При данной стратегии возможна только одна партия. Заключением партии будет написано слово ИКЛМНИКЛМНХ.

Б) При исходном наборе слов выигрышная стратегия есть у Пети. Она заключается в том, чтобы выбрать слово с нечетным количеством букв, т.к. при такой стратегии последнюю букву в любом случае записывает Петя. Т.о., Петя должен выбрать букву Т, т.к. в первом слове 99 букв.

2. Если поменять местами во втором слове (НМЛКИНМЛКИ) буквы Н и И, то получится следующий набор слов:

   {ИКЛМНИКЛМНХ, ИМЛКННМЛКИ}
   

   Для данного набора выигрышная стратегия есть у Вани. Петя в любом случае должен будет выбрать букву И, а Ваня следующим ходом может перевести игру в проигрышную позицию для Пети, т.е. перейти на второе слово, назвав букву М. Такая стратегия приведет Ваню к выигрышу, так как последнюю букву слова - И - запишет именно он.

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

Дерево возможных партий:

* Для Вани отображены только ходы по стратегии
** Красный круг означает выигрыш

• в цикле со счетчиком i запрашиваются значения элементов массива, т.е. формируется массив;
• из постановки задания видим, что необходимо найти количество чего-то, это значит, что нужно использовать переменную счетчик;
• объявлены три целочисленных переменных: i, j, k; переменная i использована в первом цикле, значит для счетчика можно взять переменную k;
• счетчик всегда нужно обнулять, поэтому следующим оператором будет:

k:=0;

k:=0;

• определим, количество чего нам необходимо считать: количество элементов массива не кратных 3. Кратность можно определить через остаток от деления: если значение элемента массива при делении на 3 в остатке не возвращает 0, значит элемент не кратен трем;
• остаток при делении в паскале — оператор mod. Поскольку необходимо просмотреть каждый элемент массива, то это нужно делать в цикле for;
• переменная i уже использована в первом цикле for, значит, для очередного цикла возьмем неиспользованную переменную j:

for j:=1 to N do if a[j] mod 3 <> 0 then

for j:=1 to N do if a[j] mod 3 <> 0 then

• если условие истинно (т.е. нашелся элемент массива, не кратный трем), то увеличиваем счетчик:

inc(k);

inc(k);

• после цикла остается вывести значение счетчика, т.е. вывести количество элементов массива не кратных 3:

writeln(k);

writeln(k);

Результат:

k:=0;
for j:=1 to N do
  if a[j] mod 3 <> 0 then
    inc(k);
writeln(k);

• Решение на языке Паскаль:

1 2 3 4 5 6 7 8 9

k := 0; for i := 1 to N do if (a[i] > 100) and (a[i] mod 5 = 0) then k:=k+1; for i := 1 to N do begin if (a[i] > 100) and (a[i] mod 5 = 0) then a[i] := k; writeln(a[i]) end

k := 0; for i := 1 to N do if (a[i] > 100) and (a[i] mod 5 = 0) then k:=k+1; for i := 1 to N do begin if (a[i] > 100) and (a[i] mod 5 = 0) then a[i] := k; writeln(a[i]) end

Решение на языке Python:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23

a = [] n = 2000 // менять значение n нельзя for i in range(0, n): a.append(int(input())) j = 0 k = 0 m = 0 for i in range(0, n): if a[i]%2 == 0: j+=1 else: k+=1 if k>j: j = 0 for i in range(0, n): if a[i]>j and a[i] % 2 != 0: j = a[i] print(j) else: for i in range(0, n): if a[i]>m and a[i] % 2 == 0: m = a[i] print(m)

a = [] n = 2000 // менять значение n нельзя for i in range(0, n): a.append(int(input())) j = 0 k = 0 m = 0 for i in range(0, n): if a[i]%2 == 0: j+=1 else: k+=1 if k>j: j = 0 for i in range(0, n): if a[i]>j and a[i] % 2 != 0: j = a[i] print(j) else: for i in range(0, n): if a[i]>m and a[i] % 2 == 0: m = a[i] print(m)

1 2 3 4 5

k := 0; for i := 1 to N - 1 do if ((a[i] < 100) and (a[i] > 9)) or ((a[i + l] < 100) and (a[i + 1] > 9)) then inc(k); writeln(k);

k := 0; for i := 1 to N - 1 do if ((a[i] < 100) and (a[i] > 9)) or ((a[i + l] < 100) and (a[i + 1] > 9)) then inc(k); writeln(k);

Проанализируем данный фрагмент кода на языке Python:
• В первой строчке кода объявляется список а. Дальше, идет объявление переменной n = 20, она отвечает за размер массива.
При решении такого рода задач, необходимо помнить, что массив в Python — это список и это динамический тип данных. Кроме того, нумерация элементов массива начинается с 0.
• Ниже мы видим инициализацию списка а. Мы должны дописать код дальнейшей программы, который последует после заполнения списка пользователем.
• Итак, по условию мы должны находить пары элементов, сумма которых делится на 2, но не делится на 4, причем парами считаются соседние элементы, например: a[0] и a[1], a[1] и a[2].
• Мы можем узнать, делится ли данный элемент на число, если остаток от деления на него равен 0, и не делится — в противном случае. Тогда сумма соседних элементов при делении на 2 должна давать остаток 0, а при делении на 4 наоборот — отличный от 0.
• Введем цикл, который будет перебирать все элементы массива, считать сумму соседей и проверять истинность условия.

for i in range(0, n-1): j = a[i] + a[i+1] if j%2 == 0 and j%4 != 0:

for i in range(0, n-1): j = a[i] + a[i+1] if j%2 == 0 and j%4 != 0:

Так как мы рассматриваем элемент a[i + 1], значит, цикл должен работать до n — 1, чтобы не выйти за границы диапазона массива.
• Когда мы определились с условием, за счетчик возьмем переменную k, которую допустимо брать исходя из комментариев к программе.

... if j%2 == 0 and j%4 != 0: k+=1

... if j%2 == 0 and j%4 != 0: k+=1

• Мы добавили допустимую переменную j, чтобы условный оператор выглядел компактнее.
• Однако задача еще не решена. Во-первых, мы должны до цикла инициализировать счетчик k = 0. Так как иначе Python выдаст ошибку.
Дело в том, что мы пытаемся присвоить переменной k его же значение, но на 1 больше, но интерпретатор «не встречал» раньше переменной k, из-за чего возникает ошибка.
• Кроме того, добавим вывод результата после цикла.
• Таким образом, правильный вариант с учетом доработок:

a = [] n = 20 for i in range(0, n): a.append(int(input())) k = 0 for i in range(0, n - 1): j = a[i] + a[i + 1] if j%2 == 0 and j%4 != 0: k += 1 print(k)

a = [] n = 20 for i in range(0, n): a.append(int(input())) k = 0 for i in range(0, n - 1): j = a[i] + a[i + 1] if j%2 == 0 and j%4 != 0: k += 1 print(k)

• из постановки задания видим, что необходимо искать количество чего-то, это значит, что нужно использовать переменную счетчик; возьмем для нее объявленную переменную k;
• счетчик всегда нужно сначала обнулять, поэтому следующим оператором будет:

k:=0;

k:=0;

• определим, количество чего нам необходимо считать: количество троек элементов массива, состоящих из равных между собой чисел. Т.е. необходимо сравнивать между собой каждые три подряд идущих элемента массива, например так:

if (a[i]=a[i+1]) and (a[i]=a[i+2]) then inc(k);

if (a[i]=a[i+1]) and (a[i]=a[i+2]) then inc(k);

• inc(k) — оператор, увеличивающий счетчик k на единицу;
• условие необходимо выполнять в цикле, так как нужно проверить все элементы массива; цикл со счетчиком необходимо организовать от 1 до N-2, в противном случае индексы элементов a[i+2] выйдут за границы диапазона массива (например, при i = 40, получим … a[40+2], а 42-го элемента массива не существует, поэтому цикл надо делать до i = 38, т.е. N-2).

Результат:

for i:=1 to N-2 do
    if (a[i]=a[i+1]) and (a[i]=a[i+2]) then
      inc(k);
writeln(k);

• Возьмем такое наименьшее число, находящееся в интервале от 3 до 44, для которого применима только одна команда:

12 
к нему применима только команда - прибавь 1 
12 * 4 = 48 - это больше, чем 44 

• Отобразим число 12 на графе, указав и саму команду и результат. То есть для 12 можно использовать только одну команду (12 + 1 = 13):


Пояснение: Красным цветом будем выделять количество команд для получения конкретного числа, а в круг обводить итоговое суммарное количество команд.

• Дальше будем использовать метод решения с конца, т.е. двигаясь от наибольших подходящих чисел (в конкретном случае с 12) — к наименьшим.


Пояснение: поскольку это задача динамического программирования, то полученные промежуточные результаты, используются для дальнейших вычислений:

• для 11 взят результат, полученный для 12 (1);
• для 10 взят результат, полученный для числа 11 (2);
• для 9 взят результат, полученный для 10 (3);
• и т.д.
• Для последнего числа 3 получено 10 команд.

• Изобразим траекторию в виде луча, на котором отложим отрезки:



• Поскольку 8 и 10 обязательно должны содержаться в расчете, то для поиска общего количества программ необходимо найти произведение количества программ отдельных отрезков:

1 * 2 * 3
или
(2 -> 8) * (8 -> 10) * (10 -> 12)

• Найдем отдельно количество программ каждого из отрезков:
• 2 -> 8 = 15
• На интервале от 2 до 8 возьмем наименьшее число, для которого исполнима только одна из команд:

7
7 + 1 = 8
7 + 2 = 9 - нельзя, вне интервала

• Рассмотрим все числа интервала, двигаясь от большего к меньшему:



• 8 -> 10 = 2
• очевидно, что это две программы:



• 10 -> 12 = 2



• Выполним произведение полученных результатов:

15 * 2 * 2 = 60

var
  x, L, M, D: longint;
 
begin
  x := 1000;
  while true do
  begin
    D := x;
    L := 23;
    M := 141;
    while L <= M do
    begin
      L := L + D;
      M := M - 3 * D;
    end;
    if (l = 53) and (x mod 2 <> 0) then 
    begin
      print(x); break;
    end;
    x -= 1;
  end;
end.

✎ Аналитическое решение:
Разберем решение по одному из возможных вариантов выполнения данного задания.
Рассмотрим алгоритм:

• Результатом программы является вывод L.
• Цикл перестанет работать, когда L станет больше M (т.к. while L<=M).
• D в программе - это и есть искомый x (D:=x;).
• В цикле оператор L:=L+D работает, как сумматор: L накапливает в себе сумму всех D, тогда как D в нашей задаче не меняется и равна введенному x.
• Сумматор (L) до цикла обычно обнуляется, сделаем это: т.е. в строке 5 вместо L:=23 представим, что L:=0. Тогда и условие задачи поменяется: т.е. вместо указанного в условии числа 53 программа выводит L равное 53-23 = 30. А в условии цикла M также изменит свое значение на 141-23=118:

1 2 3 4 5 6 7 8 9 10

... L:=23; M:=141; while L<=M do // L<=118 для первой итерации begin L:=L+D; M:=M-3*D; end; writeln(L); // выводится L = 30 end.

... L:=23; M:=141; while L<=M do // L<=118 для первой итерации begin L:=L+D; M:=M-3*D; end; writeln(L); // выводится L = 30 end.

• Так как по заданию необходимо найти наибольший x, то представим, что он равен как раз 30:

L = L + D => L = 0 + 30 => L = 30 

• Но число 30 - четное, а по условие необходимо нечетное x.
• Значит, одного прохождения цикла недостаточно.
• Предположим, что цикл имеет две итерации. За два прохождения цикла L увеличится на 2*D, то есть нужно взять такое D, чтобы 2*D было равно 30:

30 / 2 = 15 
То есть D = x = 15

• Проверим:

D=15         1 проход       2 проход      
L:=L+D:       0+15=15        15+15=30       
M:=M-3*D:   118-3*15=73    73-3*15 = 28   
L<=M:        да: 15<=73    нет: 30 > 28

• Т.е. D=15 полностью подходит, и это наибольшее возможное число при данных условиях.

Для начала рассмотрим алгоритм программы:
1. В начале программы вводится x, две переменные - B и D присваивают значение введенного x. Переменной A присваивается значение 9, а переменная S обнуляется.
2. Далее следует цикл, который зависит от переменной D (равной x): пока x div 2 > 0 выполняется тело цикла. Т.е. пока x, деленный целочисленно на 2, больше нуля.
3. В теле цикла происходит увеличение переменной S либо на 9 (А:=9), либо на 1 в зависимости от четности значения D. Т.е. переменная S увеличивается на 9 в случае, если очередное значение D - четное и увеличивается на 1, если очередное значение D - нечетное.
4. В конце цикла D целочисленно делится на 2 (D := D div 2).
5. По условию программы S должно быть равно 30. Посчитаем максимальное количество итераций цикла: 2ⁿ <= 200, т.е. n = 7 (максимальное значение D - 200 - делим целочисленно на 2, пока это возможно). При этом минимальное количество итераций - 6 (2ⁿ >=100, т.е. n = 6)
6. За 7 или 6 итераций цикла необходимо получить S = 30, каждую итерацию цикла, увеличивая S либо на 1, либо на 9. Рассмотрим варианты:

30 = 9 + 9 + 9 + 1 + 1 + 1  ->  (получаем 6 итераций, что соответствует действительности)
30 =  9 + 9 + 12 * 1 (если взять две девятки, то цикл должен работать 14 раз 
(9 + 9 + [12 единиц]), а это невозможно)

7. Из 6 итераций имеем: 3 итерации с D - нечетным (когда s = s + 1) и 3 итерации с D - четным (когда s = s + 9)
8. Четность чисел в двоичной системе счисления зависит от младшего бита: если младший бит = 0, то число четное, если 1, то число нечетное. Поскольку нам необходимо найти наибольшее x, то необходимо в трех старших битах данного числа, выраженного в двоичной системе счисления, поместить 1, а в остальных трех битах разместить 0. При этом необходимо не забыть про еще один старший бит равный 1 (в итерациях его нет, т.к. это последняя единица, которая уже не удовлетворяет условию цикла: условие цикла ложно while (1 div 2) > 0 - ложь):

11110002 = 12010
первая единица будет стоять всегда, она не участвует в итерациях цикла

Проверка:
120| 0  - соответствует s + 9
 60| 0  - соответствует s + 9
 30| 0  - соответствует s + 9
 15| 1  - соответствует s + 1
  7| 1  - соответствует s + 1
  3| 1  - соответствует s + 1
  1|
 

✎ 2 способ:

Рассмотрим алгоритм:
• Значение искомого x присваивается сразу двум переменным B и D, но B более нигде не используется, поэтому забудем про нее. D - это x.

В цикле:

• D mod 2 - это крайняя справа цифра числа в двоичной системе счисления (младший разряд); т.е.:

например, если D = 510 = 1012, то D mod 2 = 1 (101)

• в цикле есть сумматор S, результат которого выводится в программе (результат 30), и который накапливает в себя значения по следующему принципу:
• если указанная крайняя цифра = 1, то в S добавляется 1, если крайняя цифра = 0, то в S добавляется 9 (А = 9);
• последнее действие цикла D:= D div 2 - это отсечение крайнего младшего разряда числа D в двоичной системе счисления, т.е.:

если было D = 510 = 1012, то стало D = 102

• условие цикла: пока D при целочисленном делении на 2 больше 0 (while (D div 2)>0);
• анализ алгоритма показывает, что вводимый x можно рассматривать в двоичной системе счисления. Поскольку сумматор S выводит в результате число 30, то можно понять, как накапливается это число в S:

30 = 9 + 9 + 9 + 1 + 1 + 1  ->  (получаем 6 итераций цикла)

• поскольку цифра 9 прибавлялась 3 раза и единица прибавлялась 3 раза, значит, в двоичной записи исходного числа D было 3 цифры 0 и три цифры 1. Чтобы получить наибольшее x, как указано в задании, расположим в старших битах единицы, а в младших 0:

111000

• важно не забыть крайнюю слева цифру 1, которая останется не учтенной в цикле, так как условие при последней единице не выполняется:

при оставшемся D = 1 условие while (1 div 2) > 0 не работает, 
поэтому добавляем еще старший разряд "1"
таким образом, получаем число в двоичной системе: 1111000 

• переведем в десятичное представление:

64 32 16  8  4  2  1
1  1   1  1  0  0  0   = 64 + 32 + 16 + 8 = 12010

• В конце программы алгоритм выводит значение L, равное 2 (по условию). В цикле L - это счетчик, увеличивающийся каждую итерацию цикла (каждое прохождение цикла) на 1.
• Таким образом, цикл работает два раза.
• В цикле x постоянно уменьшается на 1 разряд, т.е. от него отсекается цифра справа (x:=x div 10):

например, x = 243
после выполнения x:=x div 10 получаем
х = 24

• Так как цикл работает два раза, значит x - двухзначное число, т.е. после двух проходов (итераций) цикла условие цикла перестало работать (x стало <= 0).

Рассмотрим работу с M в цикле:

• В первую итерацию цикла М всегда заменится на значение x mod 10, так как изначально М = 0.
• Из предыдущего пункта имеем, что M - это наименьшая цифра числа:

например, x = 243
после выполнения M := x mod 10; получаем
1 шаг: М = 3
2 шаг: М = 3
3 шаг: М = 2 

• В результате работы программы на экран выводится М = 8.

Рассмотрим две цифры числа x путем подстановки:

• Поскольку по условию нам нужно наибольшее x, то попробуем в единицы записать число 8:

? 9

• В таком случае во второй итерации цикла условие в цикле M < (x mod 10) не будет работать, и программа распечатает 9 (вместо 8). Т.е. 9 не походит:

if M  < (x mod 10) then
      M:=x mod 10;
1 шаг: 
if 0  < (9) then
      M:=9;
2 шаг:
if 9 < (любая цифра) then ... 
Условие не работает, программа распечатает М = 9. Не подходит!

• Поставим вместо разряда единиц число 8:

? 8

• После первой итерации цикла M = 8 (по условию нам подходит):

if M  < (x mod 10) then
      M:=x mod 10;
1 шаг: 
if 0  < (8) then
      M:=8;

• Теперь рассмотрим первую цифру числа x:

9 8
если она равна 9 (то есть число 98), 
то М станет = 9 (а нам необходимо, чтобы осталось 8):

1 шаг: 
if 0  < (8) then
      M:=8;
2 шаг:
if 8 < 9 then ... 
Условие работает, программа распечатает М = 9. Не подходит!

• Возьмем цифру 8 (88):

8 8
1 шаг: 
if 0  < (8) then
      M:=8;
2 шаг:
if 8 < 8 then ... 
Условие не работает, программа распечатает М = 8. Подходит!

• Наибольшее х = 88.

Рассмотрим алгоритм:

В цикле:

• Наличие операторов x mod 2 и x div 2 говорит о том, что эту задачу можно решать, представляя x в двоичной системе счисления.
• В цикле есть счетчик M, который увеличивается на единицу и в конце программы будет соответствовать количеству итераций цикла. Таким образом, имеем 7 проходов цикла.
• Условие if x mod 2 <> 0 проверяет на нечетность младший разряд числа в двоичной системе:

например, если было x = 510 = 1012, 
то if x mod 2 <> 0 проверяет if 1 <> 0

• Если в младшем разряде стоит единица (в двоичной системе число состоит только из 1 и 0), то срабатывает счетчик L, который увеличивается на единицу.
• В строке x := x div 2; отсекается младший разряд двоичного представления значения x, т.е.:

если было, например, x = 510 = 1012, то стало x = 102

• Таким образом, счетчик L подсчитывает количество единиц в двоичной записи числа. Так как в результате выводится L = 5, то в двоичной записи числа 5 единиц.
• Так как цикл работает 7 раз, и в каждой итерации от числа в двоичной записи отсекается один разряд, то имеем 7 разрядов (цифр) в числе.
• Итого, в двоичной записи 5 единиц и 2 нуля. Для получения наименьшего x (по заданию) расположим цифры следующим образом:

10011112 = 64 + 8 + 4 + 2 + 1 = 7910

  
✎ Способ 2 (длительный, аналитический):
 

Для начала рассмотрим алгоритм программы:

• В начале программы вводится x, и обнуляются две переменные - L и M.
• Далее следует цикл, который зависит от переменной x: пока x > 0 выполняется тело цикла.
• В теле цикла каждый его шаг происходит увеличение переменной M на единицу. Т.е. переменная M - это счетчик, соответственно, его значение по завершению работы цикла будет соответствовать количеству шагов (итераций) цикла.
• В конце программы печатается сначала L, потом M. Т.е. L должно быть равно 5, а M = 7. Раз M будет равно 7, то из предыдущего пункта видим, что цикл имеет 7 шагов, т.е. 7 итераций.
• L - это тоже счетчик, но из условия if x mod 2 <> 0 видим, что счетчик L подсчитывает количество нечетных промежуточных x. Т.е. x в цикле постоянно меняется, а L проверяет x и в случае нечетного значения увеличивается на единицу. В программе L должно стать 5.
• В цикле x делится целочисленно на 2: x := x div 2
• Поскольку цикл завершит работу, когда x = 0, то последним шагом будет x = 1 div 2 = 0. Т.е. в предпоследнем шаге x = 1.
• Решим данную задачу с конца, проследив все итерации цикла. Получается, что из предыдущего шага в следующий шаг x изменяется по двум правилам, назовем их командами:

1. x*2 -> если предыдущий x - четный, 
например 4 div 2 - обратное действие 2*2 = 4

2. x*2+1 -> если предыдущий x - нечетный, 
например 5 div 2 - обратное действие 2*2+1 = 5

• Так как L в результате равно 5, значит, в программе 5 команд № 2 и 2 команды №1 (7-5 = 2)
• Нарисуем дерево команд и получающиеся значения, начиная с последней итерации цикла до начальной итерации. Т.е. начнем с завершения цикла, когда x стал = 0:



• Вниз уходят команды, дающие четные значения x, а вверх - нечетные. Поскольку нам необходимо найти наименьший x, то "выгоднее" проследить нижние ветви дерева, т.к. они в результате дают меньшие значения.
• Из дерева видим, что первая команда - это команда 2. В итоге осталось 4 команды № 2 и 2 команды № 1.
• Нам выгодно с самого начала "двигаться" по дереву, используя команды №1 (чтобы x был наименьшим). Поэтому вторая и третья ветвь будут соответствовать команде №1. Поскольку первых команд должно быть только две, остальные команды будут №2.
• Итого получаем следующий путь по дереву, в результате которого x становится равным 79.

Рассмотрим алгоритм:
• В конце программы на экран выdодится сначала значение переменной L, затем M. Т.е. согласно заданию, получается что:

в конце программы: 
L = 42   M = 4

• В цикле while две операции указывают на то, что данное задание проще рассматривать при работе с числом в 8-й системе счисления:

1. x mod 8 - младший разряд числа в 8-й системе счисления 
т.е., например: 568
тогда  x mod 8 - это цифра 6

2. x := x div 8 - "отсекание" младшего разряда числа в 8-й системе счисления
т.е., например: x = 4610 = 568
тогда  x := x div 8 -> x = 510 = 58
 

• Таким образом, в цикле рассматриваются цифры числа в 8-й системе счисления. В конце цикла, каждый раз от числа "отсекается" крайний разряд, тем самым число теряет цифру. Цикл выполняется до тех пор, пока есть цифры в числе (while x > 0).
• М - это счетчик итераций, т.е. шагов цикла, т.к. М увеличивается каждый раз на единицу. Поскольку количество цифр числа уменьшается с каждой итерацией, то М в результате возвращает количество цифр числа - по заданию М = 4. Значит, число x - четырехзначное.
• В условии if x mod 8 > 3 then проверяется каждая цифра числа: если она больше трех, то выполняется действие L := L * (x mod 8);. Дословно, это говорит о том, что L - это произведение цифр числа (в его 8-м представлении), которые больше трех.
• Таким образом соберем все выводы:

М = 4 - количество цифр числа т.е.
x в 8-й системе счисления имеет 4 разряда: ? ? ? ?
L = 42 произведение цифр, которые больше трех.

• По заданию нам необходимо найти наименьшее x. Теперь, зная, что х - четырехзначное, а 42 - произведение его цифр, больших трех, найдем, как получается 42:

42 = 6 * 7 

• Соответственно, для старшего разряда поставим единицу, а один разряд оставим равным 0:

x = 10678

• Осталось перевести получившееся число в 10-ю систему счисления, чтобы найти исходный x:

10678 = 56710

Результат: 567

✎Один из вариантов решения:
• В цикле while две операции указывают на то, что данное задание можно рассматривать при работе с числом в 8-й системе счисления:

1. n mod 8 - младший разряд числа в 8-й системе счисления 
т.е., например: 568
тогда  n mod 8 - это цифра 6

2. n := n div 8 - "отсекание" младшего разряда числа в 8-й системе счисления
т.е., например: n = 4610 = 568
тогда  n := n div 8 -> n = 510 = 58
 

• Таким образом, в цикле рассматриваются цифры числа в 8-й системе счисления. В конце цикла, каждый раз от числа "отсекается" крайний разряд, тем самым число теряет цифру. Цикл выполняется до тех пор, пока есть цифры в числе (while n > 0).
• i - это сумматор, который аккумулирует (суммирует) цифры восьмеричного числа: поскольку n mod 8 - младшая цифра числа, и каждую итерацию цикла от числа отсекается цифра младшего разряда, то на каждом шаге в i добавляется очередная справа цифра числа:

Например:  n = 2568
1) i := i + n mod 8; => i = 0 + 6 = 6  (256)
2) i := i + n mod 8; => i = 6 + 5 = 11  (256)
3) i := i + n mod 8; => i = 11 + 2  = 13 (256)

• В конце программы распечатывается значение i mod 7, т.е. остаток от деления получившейся суммы на число 7.
• Таким образом соберем все выводы:

i - сумматор цифр введенного числа n в его восьмеричном представлении
n - двузначные десятичные числа (по условию)
результат программы = i mod 7 = 0, т.е. остаток от деления итоговой суммы на 7 (= 0)

• Поскольку в условии говорится о десятичных числах, т.е. вводятся двузначные десятичные числа. Рассмотрим максимальное и минимальное двухзначное десятичное число, преобразованное в 8-ю систему счисления:

nmin = 1010 = 128
nmax = 9910 = 1438
 

• Выберем суммы цифр чисел в диапазоне от 12 до 143 (исключая цифры большие 7, т.к. 8-я с.с):

16 = 1+6 = 7 (7 mod 7 = 0), 
25 = 2+5 = 7 (7 mod 7 = 0), 
34 = 3+4 = 7 (7 mod 7 = 0), 
43 = 4+3 = 7 (7 mod 7 = 0), 
52 = 5+2 = 7 (7 mod 7 = 0), 
61 = 6+1 = 7 (7 mod 7 = 0), 
70 = 7+0 = 7 (7 mod 7 = 0), 
77 = 7+7 = 14 (14 mod 7 = 0), 
106 = 1+6 = 7 (7 mod 7 = 0), 
115 = 1+1+5 = 7 (7 mod 7 = 0), 
124 = 1+2+4 = 7 (7 mod 7 = 0), 
133 = 1+3+3 = 7 (7 mod 7 = 0), 
142 = 1+4+2 = 7 (7 mod 7 = 0),

• Посчитаем количество таких чисел - их 13.

Рассмотрим алгоритм.
• Программа получает на вход число x.
• В цикле, пока число x больше 0, в зависимости от того, четное ли число x выполняются действия:
• если четное, то в переменную a добавляется остаток от деления числа x на 9;

if x mod 2 = 0 then a := a + x mod 9

if x mod 2 = 0 then a := a + x mod 9

• если нечетное, то переменная b умножается на остаток от деления числа x на 9;

else b := b * (x mod 9);

else b := b * (x mod 9);

• x целочисленно делится на 9.

x := x div 9;

x := x div 9;

• Эти три действия в цикле - ни что иное, как работа с цифрами числа в 9-й системе счисления. Тогда, проверим значение x на четность в 9-й с.с.:
• если четное, то в переменную a добавляется крайняя справа цифра числа (остаток от деления числа x на 9);
• если нечетное, то переменная b умножается на крайнюю справа цифру числа x;
• x целочисленно делится на 9: значит, отсекаем от x в 9-й с.с. крайнюю справа цифру.
• Теперь попробуем подобрать наименьшее число x, рассматривая его пока в 9-й с.с.
Вспомним, что для систем счисления с нечётным основанием (наш случай, 9 - нечетное) справедливо утверждение, что число чётно тогда и только тогда, когда сумма всех его цифр чётна.

произведение цифр (b) должно быть равно 9 (если число x нечетное)
сумма цифр (a) должна быть равна 1 (если число x четное)

однозначное число:
минимальное 9, но цифры 9 в 9-й с.с. нет.
других вариантов получить 9 нет

двухзначное число:
минимальное 33
3 + 3 = 6 (четное) => a = 0 + 3 = 3, не подходит (т.к. а=1)
других вариантов получить 9 нет

трехзначное число:
1 случай:
минимальное 133
1 + 3 + 3 = 7 (нечетное) => b = 1 * 3 = 3
отсекаем: x = 13
1 + 3 = 4 (четное) => a = 0 + 3 = 3, не подходит (т.к. а=1)

2 случай:
следующее минимальное 313
3 + 1 + 3 = 7 (нечетное) => b = 1 * 3 = 3
отсекаем: x = 31
3 + 1 = 4 (четное) => a = 0 + 1 = 1
отсекаем: x = 3
3 (нечетное) => b = 3 * 3 = 9
отсекаем: x = 0, конец цикла

• Результаты нас устраивают (a = 1, b = 9). Переведем число 313 из 9-й с.с. в 10-ю:

3139 = 3 * 92 + 1 * 9 + 3 = 25510

• В начале программы запрашивается x. Переменной L присваивается значение x, а переменной M - значение 5.
• Затем в условии проверяется четность переменной L: если переменная четная, то M присваивается значение 24.
• Далее следует цикл, зависящий от переменных L и M: цикл завершится, когда L сравняется с M, т.е. согласно условию, когда L = M = 5 (так как по завершению программы на экран выводится число 5):

По завершению программы:
L = M = 5

• Кроме того, по условию известно, что x > 40.
• В цикле из переменной большего значения вычитается переменная меньшего значения (алгоритм Евклида поиска наибольшего общего делимого):

НОД (a, b) = если a > b, то НОД (a-b, b) = если b > a, то НОД (a, b-a)

• Поскольку в результате работы программы распечатывается значение M, равное 5, то можно утверждать, что если условие if L mod 2 = 0 не будет истинным, то в цикле постоянно будет происходить действие L:=L-M). Т.е. постоянно вычитается 5.
• Исходя из предыдущего пункта, исходное число x должно быть кратно 5, так как в результате печатается 5 (M). А при M=24 алгоритм не выдаст в результате значение 5.
• Первое наименьшее число, кратное 5 и большее 40 (по условию) - это 45.
• Проверим по алгоритму:

L  M

45 5
40 5
35 5
30 5
25 5
20 5
15 5
10 5
5  5 

• Если следовать алгоритму Евклида, то число 5 (результат) - это наибольший общий делитель числа 5 (исходное значение M) и числа x (введенного числа). Поскольку x больше 40, то наименьшим значением для которого общим делителем с числом 5 будет само число 5 - это число 45.