Вася составляет 5 буквенные слова в которых есть только буквы волк

* Учтите, что в данных заданиях более не требуется учитывать эффективность алгоритма (с 2021 года)!

✎ Программа эффективна по времени и по памяти (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.

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) ИЛИ (один сомножитель делится на 2, а другой — на 29)

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

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.

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

27_6: Разбор 27 задания демоверсии 2018 года (ФИПИ):
* Учтите, что в данных заданиях более не требуется учитывать эффективность алгоритма (с 2021 года)!

На вход программы поступает последовательность из N целых положительных чисел, все числа в последовательности различны. Рассматриваются все пары различных элементов последовательности (элементы пары не обязаны стоять в последовательности рядом, порядок элементов в паре не важен). Необходимо определить количество пар, для которых произведение элементов делится на 26.

Описание входных и выходных данных В первой строке входных данных задаётся количество чисел N (1 ≤ N ≤ 1000). В каждой из последующих N строк записано одно целое положительное число, не превышающее 10 000.
В качестве результата программа должна напечатать одно число: количество пар, в которых произведение элементов кратно 26.

Пример входных данных:

4 2 6 13 39

Пример выходных данных для приведённого выше примера входных данных:

Из четырёх заданных чисел можно составить 6 попарных произведений:

2·6 = 12 2·13 = 26 2·39 = 78 6·13 = 78 6·39 = 234 13·39 = 507

Из них на 26 делятся 4 произведения:

2·13=26; 2·39=78; 6·13=78; 6·39=234

Требуется написать эффективную по времени и по памяти программу для
решения описанной задачи.

Показать решение:
* Учтите, что в данных заданиях более не требуется учитывать эффективность алгоритма (с 2021 года)!

Произведение двух чисел делится на 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

27_7: задание досрочного экзамена 2020 г, ФИПИ (2 вариант):
* Учтите, что в данных заданиях более не требуется учитывать эффективность алгоритма (с 2021 года)!

Дана последовательность N целых положительных чисел. Рассматриваются все пары элементов последовательности, разность которых чётна, и в этих парах, по крайней мере, одно из чисел пары делится на 19. Порядок элементов в паре неважен. Среди всех таких пар нужно найти и вывести пару с максимальной суммой элементов. Если одинаковую максимальную сумму имеет несколько пар, можно вывести любую из них. Если подходящих пар в последовательности нет, нужно вывести два нуля.

Описание входных и выходных данных
В первой строке входных данных задаётся количество чисел N (2 ≤ N ≤ 10 000). В каждой из последующих N строк записано одно натуральное число, не превышающее 10 000.
Пример входных данных:

5 38 12 57 16 57

Пример выходных данных для приведённого выше примера входных данных:

57 57

Пояснение. Из данных пяти чисел можно составить три различные пары, удовлетворяющие условию: (38, 12), (38, 16), (57, 57). Наибольшая сумма получается в паре (57, 57). Эта пара допустима, так как число 57 встречается в исходной последовательности дважды.

Напишите эффективную по времени и памяти программу для решения этой задачи.

Программа считается эффективной по времени, если при увеличении количества исходных чисел N в k раз время работы программы увеличивается не более чем в k раз.
Программа считается эффективной по памяти, если память, необходимая для хранения всех переменных программы, не превышает 1 Кбайт и не увеличивается с ростом N.

Максимальная оценка за правильную (не содержащую синтаксических ошибок и дающую правильный ответ при любых допустимых входных данных) программу, эффективную по времени и памяти, – 4 балла.
Максимальная оценка за правильную программу, эффективную только по времени или только по памяти, – 3 балла.
Максимальная оценка за правильную программу, не удовлетворяющую требованиям эффективности, – 2 балла.

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

Показать решение:
* Учтите, что в данных заданиях более не требуется учитывать эффективность алгоритма (с 2021 года)!

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

const p = 19; var N: integer; a: integer; m0, m1: integer; mp0, mp1: integer; 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; 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, 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 балла.

#include 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  else { if (imp1 == -1  } } int im0 = -1, im1 = -1; // индексы общих максимумов for (int i = 0; i  N; ++i)  else  } } 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   <' '   ; return 0; }

#include 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

Запишем все исходные числа в массив, переберём все возможные пары и выберем подходящую. Такое решение не является эффективным ни по памяти (требуемая память зависит от размера исходных данных), ни по времени (количество возможных пар, а значит, количество действий и время счёта с ростом количества исходных элементов растут квадратично). Подобная программа оценивается не выше 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.

Выбрать из каждой пары одно число

27_1:
* Учтите, что в данных заданиях более не требуется учитывать эффективность алгоритма (с 2021 года)!

Задание А (более легкое, чем Б)
Имеется набор данных, состоящий из 5 пар положительных целых чисел. Необходимо выбрать из каждой пары ровно одно число так, чтобы сумма квадратов всех выбранных чисел была нечетной и при этом максимально возможной. Если получить требуемую сумму невозможно, в качестве ответа нужно выдать 0.

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

Максимальная оценка за правильную программу — 2 балла.

Задание Б (более сложное, чем А)
Имеется набор данных, состоящих из пар положительных целых чисел. Необходимо выбрать из каждой пары ровно одно число так, чтобы сумма квадратов всех выбранных чисел была нечетной и при этом максимально возможной. Если получить требуемую сумму невозможно, в качестве ответа нужно выдать 0.

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

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

Максимальная оценка за правильную программу, эффективную по времени и по памяти, — 4 балла.

Как в варианте А, так и в варианте Б программа должна напечатать одно число — максимально возможную сумму, соответствующую условиям задачи (или 0, если такую сумму получить нельзя).

Например: 2 6 4 1 7 3 2 9 7 4 sum=231

✍ Показать решение:
* Учтите, что в данных заданиях более не требуется учитывать эффективность алгоритма (с 2021 года)!

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

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

n:longint; ;

x,y: integer; max: integer; min: integer; sum:longint; min_kvadr:longint; i:integer;

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);

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)

min_kvadr:=1073676289;

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; i:integer; begin sum:=0; readln(n); min_kvadr:=1073676289; 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);  sum[k+1]:=sum[k-2]+sqr(y);  sum[k+2]:=sum[k-1]+sqr(x);  sum[k+3]:=sum[k-1]+sqr(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); sum[k+1]:=sum[k-2]+sqr(y); sum[k+2]:=sum[k-1]+sqr(x); sum[k+3]:=sum[k-1]+sqr(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.

Набор данных, состоящих из троек чисел

27_2:
* Учтите, что в данных заданиях более не требуется учитывать эффективность алгоритма (с 2021 года)!

Вам предлагается два задания с похожими условиями: задание А и задание Б. Вы можете решать оба задания или одно из них по своему выбору. Задание Б более сложное, его решение оценивается выше. Итоговая оценка выставляется как максимальная из оценок за задания А и Б.

А. Имеется набор данных, состоящий из 5 троек положительных целых чисел. Необходимо выбрать из каждой тройки ровно одно число так, чтобы сумма всех выбранных чисел не делилась на 5 и при этом была минимально возможной. Если получить требуемую сумму невозможно, в качестве ответа нужно выдать 0.

Напишите программу для решения этой задачи. В этом варианте задания оценивается только правильность программы, время работы и размер использованной памяти не имеют значения.
Максимальная оценка за правильную программу — 2 балла.

Б. Имеется набор данных, состоящий из троек положительных целых чисел. Необходимо выбрать из каждой тройки ровно одно число так, чтобы сумма всех выбранных чисел не делилась на 5 и при этом была минимально возможной. Если получить требуемую сумму невозможно, в качестве ответа нужно выдать 0.

Постарайтесь сделать программу эффективной по времени и по используемой памяти.

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

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

Максимальная оценка за правильную программу, эффективную по времени и по памяти, — 4 балла.

Как в варианте А, так и в варианте Б программа должна напечатать одно число — минимально возможную сумму, соответствующую условиям задачи (или 0, если такую сумму получить нельзя).

Напоминаем! не забудьте указать, к какому заданию относится каждая из представленных Вами программ.

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

Входные данные
Для варианта А на вход программе подается 5 строк, каждая из которых содержит три натуральных числа, не превышающих 10000.

Пример входных данных для варианта А:

1 3 2 2 1 2 2 5 1 1 3 4 6 1 1

Для варианта Б на вход программе в первой строке подается количество троек чисел N (1 Показать решение:

* Учтите, что в данных заданиях более не требуется учитывать эффективность алгоритма (с 2021 года)!

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

Чтобы получить минимально возможную сумму, будем брать из каждой тройки наименьшее число. Если полученная при этом сумма будет кратна 5, ее придется увеличить. Для этого достаточно в одной из троек, где хотя бы два числа имеют разные остатки при делении на 5, заменить ранее выбранное число на число с другим остатком от деления на 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 26 27 28 29 30 31 32

const aMax = 10000; var N: longint; a, b, c, tmp: longint; s: longint; D_min: longint; 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; 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.

const aMax = 10000; var N: longint; a, b, c, tmp: longint; s: longint; D_min: longint; 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; 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.

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.

Анализ пар, находящихся на расстоянии

27_3: Разбор 27 задания демоверсии 2019 года (ФИПИ):
* Учтите, что в данных заданиях более не требуется учитывать эффективность алгоритма (с 2021 года)!

На вход программы поступает последовательность из N целых положительных чисел, все числа в последовательности различны. Рассматриваются все пары различных элементов последовательности, находящихся на расстоянии не меньше чем 4 (разница в индексах элементов пары должна быть 4 или более, порядок элементов в паре неважен).
Необходимо определить количество таких пар, для которых произведение элементов делится на 29.

Описание входных и выходных данных:
В первой строке входных данных задаётся количество чисел N (4 ≤ N ≤ 1000). В каждой из последующих N строк записано одно целое положительное число, не превышающее 10 000.
В качестве результата программа должна вывести одно число: количество пар элементов, находящихся в последовательности на расстоянии не меньше чем 4, в которых произведение элементов кратно 29.

Пример входных данных:

7 58 2 3 5 4 1 29

Пример выходных данных для приведённого выше примера входных данных:

Из 7 заданных элементов с учётом допустимых расстояний между ними можно составить 6 произведений:

58·4 = 232 :29=8 58·1 = 58 :29=2 58·29 = 1682 :29=58 2·1 = 2 2·29 = 58 :29=2 3·29 = 87 :29=3

Из них на 29 делятся 5 произведений.

Требуется написать эффективную по времени и памяти программу для решения описанной задачи.

Показать решение:
* Учтите, что в данных заданиях более не требуется учитывать эффективность алгоритма (с 2021 года)!

✎ Программа на языке Паскаль (версия 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.

Видео на RuTube здесь

27_5:
* Учтите, что в данных заданиях более не требуется учитывать эффективность алгоритма (с 2021 года)!

Датчик передаёт каждую секунду по каналу связи неотрицательное целое число, не превосходящее 1000, — текущий результат измерений. Временем, в течение которого происходит передача, можно пренебречь.
Необходимо найти в заданной серии показаний датчика минимальное чётное произведение двух показаний, между моментами передачи которых прошло не менее 8 секунд. Если получить такое произведение не удаётся, ответ считается равным -1. Общее количество показаний датчика в серии не превышает 10 000.

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

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

ОБЯЗАТЕЛЬНО укажите, что программа является решением ЗАДАНИЯ А. Максимальная оценка за выполнение задания А — 2 балла.

Б. Напишите программу для решения поставленной задачи, которая будет эффективна как по времени, так и по памяти (или хотя бы по одной из этих характеристик). Программа считается эффективной по времени, если время работы программы пропорционально количеству полученных показаний прибора N, т. е. при увеличении N в k раз время работы программы должно увеличиваться не более чем в k раз. Программа считается эффективной по памяти, если размер памяти, использованной в программе для хранения данных, не зависит от числа А и не превышает 1 килобайта.
Перед программой укажите версию языка программирования и кратко опишите использованный алгоритм.

ОБЯЗАТЕЛЬНО укажите, что программа является решением ЗАДАНИЯ Б. Максимальная оценка за правильную программу, эффективную по времени и по памяти, — 4 балла.
Максимальная оценка за правильную программу, эффективную по времени, но неэффективную по памяти, — 3 балла.

Пример входных данных:

10 5 4 3 2 1 6 7 8 9 4

Программа должна вывести одно число — описанное в условии произведение, либо -1, если получить такое произведение не удаётся.
Пример выходных данных для приведённого выше примера входных данных:

Показать решение:
* Учтите, что в данных заданиях более не требуется учитывать эффективность алгоритма (с 2021 года)!

✎ Задание А (решение на языке Паскаль, версия 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):

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

Для каждого показания с номером k, начиная с k = 9, рассмотрим все допустимые по условиям задачи пары, в которых данное показание получено вторым. Минимальное произведение из всех этих пар будет получено, если первым в паре будет взято минимальное подходящее показание среди всех, полученных от начала приёма и до показания с номером k — 8. Если очередное показание чётное, минимальное среди предыдущих может быть любым, если нечётное — только чётным.

Для получения эффективного по времени решения нужно по мере ввода данных помнить абсолютное минимальное и минимальное чётное показание на каждый момент времени, каждое вновь полученное показание умножать на соответствующий ему минимум, имевшийся на 8 элементов ранее, и выбрать минимальное из всех таких произведений. Ниже приводится пример такой программы на Паскале, эффективной по памяти и по времени.

const s = 8; amax = 1001; var N: integer; a: array[1..s] of integer; a_: integer; ma: integer; me: integer; mp: integer; p: integer; i, j: integer; begin readln(N); 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.

Опубликовано admin / July 25, 2017 / 0 Комментарии / Рубрики: егэ практика

Информатика ЕГЭ 19, 20 и 21 задания разбор

19-е задание: «Анализ алгоритма логической игры»
Уровень сложности — повышенный,
Требуется использование специализированного программного обеспечения — нет,
Максимальный балл — 1,
Примерное время выполнения — 6 минут.

Проверяемые элементы содержания: Умение анализировать алгоритм логической игры

20-е задание: «Поиск выигрышной стратегии»
Уровень сложности — повышенный,
Требуется использование специализированного программного обеспечения — нет,
Максимальный балл — 1,
Примерное время выполнения — 6 минут.

Проверяемые элементы содержания: Умение найти выигрышную стратегию игры

21-е задание: «Дерево игры для выигрышной стратегии»
Уровень сложности — повышенный,
Требуется использование специализированного программного обеспечения — нет,
Максимальный балл — 1,
Примерное время выполнения — 10 минут.

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

До ЕГЭ 2021 года — эти задания были объединены в задание № 26 ЕГЭ

Плейлист видеоразборов задания на YouTube:

Игра с двумя кучами камней или табличка

19_8:

Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежат две кучи камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в одну из куч (по своему выбору) один камень или увеличить количество камней в куче в два раза. Игра завершается в тот момент, когда суммарное количество камней в кучах становится не менее 59. Победителем считается игрок, сделавший последний ход, т.е. первым получивший такую позицию, при которой в кучах будет 59 или больше камней.
В начальный момент в первой куче было 5 камней, во второй куче – S камней; 1 ≤ S ≤ 53 .

Задание 19 ЕГЭ.
Известно, что Ваня выиграл своим первым ходом после неудачного первого хода Пети. Укажите минимальное значение S , когда такая ситуация возможна.

Задание 20 ЕГЭ.
Найдите минимальное значение S , при котором у Пети есть выигрышная стратегия, причём одновременно выполняются два условия:
− Петя не может выиграть за один ход;
− Петя может выиграть своим вторым ходом независимо от того, как будет ходить Ваня.

Задание 21 ЕГЭ.
Найдите два значения S , при которых одновременно выполняются два условия:
– у Вани есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Пети;
– у Вани нет стратегии, которая позволит ему гарантированно выиграть первым ходом.
Найденные значения запишите в ответе в порядке возрастания.

Показать решение:
✎ Задание 19:

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

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

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

Ответ: 14

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

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

Проигрышные позиции: (6,26) (8,25) (10,24) (12,23) (14,22)

Ответ: 24

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

Ответ: 23 25

19_9:

Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежат две кучи камней. Игроки ходят по очереди, первый ход делает Петя.
За один ход игрок может убрать из одной из куч один камень или уменьшить количество камней в куче в два раза (если количество камней в куче нечётно, остаётся на 1 камень больше, чем убирается).

Например, пусть в одной куче 6, а в другой 9 камней; такую позицию мы будем обозначать (6, 9). За один ход из позиции (6, 9) можно получить любую из четырёх позиций: (5, 9), (3, 9), (6, 8), (6, 5).

Игра завершается в тот момент, когда суммарное количество камней в кучах становится не более 20. Победителем считается игрок, сделавший последний ход, то есть первым получивший позицию, в которой в кучах будет 20 или меньше камней. В начальный момент в первой куче было 10 камней, во второй куче – S камней, S > 10.

Задание 19 ЕГЭ.
Найдите значение S , при котором Ваня выигрывает своим первым ходом при любой игре Пети?

Задание 20 ЕГЭ.
Найдите минимальное и максимальное значение S , при котором у Пети есть выигрышная стратегия, причём одновременно выполняются два условия:
− Петя не может выиграть за один ход;
− Петя может выиграть своим вторым ходом независимо от того, как будет ходить Ваня.
Найденные значения запишите в ответе в порядке возрастания.

Задание 21 ЕГЭ.
Найдите значение S , при котором одновременно выполняются два условия:
– у Вани есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Пети;
– у Вани нет стратегии, которая позволит ему гарантированно выиграть первым ходом.

Ответы:
21
22 44
24

Показать решение (Excel):
✎ Задание 19:

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

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

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

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

Ответ: 22 44

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

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

Ответ: 24

19_7:

Два игрока, Петя и Ваня, играют в следующую игру. На табличке написаны два значения. Оба игрока в свой ход могут заменить одно из значений на сумму обеих (по своему выбору). Первый ход делает Петя. Игра считается законченной когда сумма обеих значений равняется не меньше 56. То есть выигрывает игрок, получивший 56 или более в сумме. Начальное значение (10, S).

Задание 19 ЕГЭ.
Найдите максимальное S при котором Петя не может выиграть первым ходом.

Задание 20 ЕГЭ.
У кого из игроков есть выигрышная стратегия при начальном значении (9, 15).

Задание 21 ЕГЭ.
У кого из игроков есть выигрышная стратегия при начальном значении (3,7)? Опишите эту стратегию и изобразите дерево всех возможных партий при этой стратегии.

Показать решение:

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

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

Для того, чтобы сделать сумму большей, Петя заменит первое значение на сумму, так как оно меньше второго значения (10

19_6:

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

В начальный момент в первой куче было 5 камней, во второй куче – S камней; 1 ≤ S ≤ 38.
Задание 19.
При каких S: 1а) Петя выигрывает первым ходом; 1б) Ваня выигрывает первым ходом?

Задание 20.
Назовите одно любое значение S, при котором Петя может выиграть своим вторым ходом.

Задание 21.
Назовите значение S, при котором Ваня выигрывает своим первым или вторым ходом.

Показать решение:

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

5 + 20*2 = 45 (>44) * 5 - кол-во камней в первой куче, оно не меняется по условию

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

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

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

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

Видеорешение на RuTube здесь

Задания для тренировки 19, 20, 21 заданий ЕГЭ (взяты из КИМ и сборников прошлых лет)

Игра с одной кучей камней

19_3. Демоверсия ЕГЭ 2018 информатика:

Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в кучу один камень или увеличить количество камней в куче в два раза. Например, имея кучу из 15 камней, за один ход можно получить кучу из 16 или 30 камней. У каждого игрока, чтобы делать ходы, есть неограниченное количество камней.

Игра завершается в тот момент, когда количество камней в куче становится не менее 29. Победителем считается игрок, сделавший последний ход, то есть первым получивший кучу, в которой будет 29 или больше камней. В начальный момент в куче было S камней, 1 ≤ S ≤ 28.

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

Задание 19 ЕГЭ
а) Укажите такие значения числа S, при которых Петя может выиграть в один ход.
б) Укажите такое значение S, при котором Петя не может выиграть за один ход, но при любом ходе Пети Ваня может выиграть своим первым ходом. Опишите выигрышную стратегию Вани.

Задание 20 ЕГЭ
Укажите два таких значения S, при которых у Пети есть выигрышная стратегия, причем:
- Петя не может выиграть за один ход;
- Петя может выиграть своим вторым ходом независимо от того, как будет ходить Ваня.
Для указанных значений S опишите выигрышную стратегию Пети.

Задание 21 ЕГЭ
Укажите значение S, при котором:
- у Вани есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Пети;
- у Вани нет стратегии, которая позволит ему гарантированно выиграть первым ходом.

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

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

✍ Показать решение:

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

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

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

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

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

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

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

19_4: Досрочный егэ по информатике 2018, вариант 1:

Два игрока, Паша и Вася, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Паша. За один ход игрок может добавить в кучу один или четыре камня или увеличить количество камней в куче в пять раз. Игра завершается в тот момент, когда количество камней в куче становится не менее 69.
Победителем считается игрок, сделавший последний ход, то есть первым получивший кучу, в которой будет 69 или больше камней. В начальный момент в куче было S камней, 1 ≤ S ≤ 68.

Задание 19 ЕГЭ.
а) Укажите все такие значения числа S, при которых Паша может выиграть в один ход. Обоснуйте, что найдены все нужные значения S, и укажите выигрывающий ход для каждого указанного значения S.

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

Задание 20 ЕГЭ. Укажите 2 таких значения S, при которых у Паши есть выигрышная стратегия, причём Паша не может выиграть за один ход и может выиграть своим вторым ходом независимо от того, как будет ходить Вася. Для каждого указанного значения S опишите выигрышную стратегию Паши.

Задание 21 ЕГЭ. Укажите хотя бы одно значение S, при котором у Васи есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Паши, и у Васи нет стратегии, которая позволит ему гарантированно выиграть первым ходом. Для указанного значения S опишите выигрышную стратегию Васи. Постройте дерево всех партий, возможных при этой выигрышной стратегии Васи (в виде рисунка или таблицы).

✍ Показать решение:

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

Видеорешение на RuTube здесь

19_1:

Два игрока, Паша и Валя, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Паша. За один ход игрок может добавить в кучу один камень или увеличить количество камней в куче в два раза. Например, имея кучу из 7 камней, за один ход можно получить кучу из 14 или 8 камней. У каждого игрока, чтобы сделать ход, есть неограниченное количество камней.

Игра завершается в тот момент, когда количество камней в куче становится не менее 28. Если при этом в куче осталось не более 44 камней, то победителем считается игрок, сделавший последний ход. В противном случае победителем становится его противник. Например, если в куче было 23 камня, и Паша удвоит количество камней в куче, то игра закончится и победителем будет Валя. В начальный момент в куче было S камней, 1≤ S ≤ 27.

Задание 1
а) При каких значениях числа S Паша может выиграть в один ход? Укажите все такие значения и соответствующие ходы Паши.
б) У кого из игроков есть выигрышная стратегия при S = 26, 25, 24? Опишите выигрышные стратегии для этих случаев.

Задание 2
У кого из игроков есть выигрышная стратегия при S = 13, 12? Опишите соответствующие выигрышные стратегии.

Задание 3
У кого из игроков есть выигрышная стратегия при S = 11? Постройте дерево всех партий, возможных при этой выигрышной стратегии (в виде рисунка или таблицы). На ребрах дерева указывайте, кто делает ход; в узлах - количество камней в позиции.

✍ Показать решение:

а) Паша имеет выигрышную стратегию и может выиграть за один ход, если 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 б), а следующий ход за Валей.

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

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

�� Видео (аналитическое решение)
Видеорешение на RuTube здесь

Задания с двумя кучами камней или табличка

19_5:

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

Задание 1.
Для каждой из начальных позиций (6, 33), (8, 32) укажите, кто из игроков имеет выигрышную стратегию. В каждом случае опишите выигрышную стратегию; объясните, почему эта стратегия ведёт к выигрышу, и укажите, какое наибольшее количество ходов может потребоваться победителю для выигрыша при этой стратегии.

Задание 2.
Для каждой из начальных позиций (6, 32), (7, 32), (8, 31) укажите, кто из игроков имеет выигрышную стратегию.

Задание 3.
Для начальной позиции (7, 31) укажите, кто из игроков имеет выигрышную стратегию. Постройте дерево всех партий, возможных при указанной вами выигрышной стратегии. Представьте дерево в виде рисунка или таблицы.

✍ Показать решение:

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

Видеорешение на RuTube здесь

Игра с набором слов

19_2:

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

Например, есть набор слов ; для заданного набора слов Петя своим первым ходом может назвать букву В, И или С. Если Петя выберет букву В, то победит Ваня (следующие ходы: Петя - В, Ваня - О, Петя - Л, Ваня - К).