Задание №27 ЕГЭ Информатика с ответом и решением

Перебираем все возможные суммы, которые начинаются на i-⁠том элементе и заканчиваются на j-⁠том элементе. Нашли бОльшую сумму — обновили ms (макс. сумму) и m (мин. длину). Нашли такую же сумму, как уже найденная максимальная, — обновили m при необходимости.

Приведём переборное решение задачи на языке Python.

f = open('27_B.txt')

n = int(f.readline())

nums = list(map(int, f.readlines()[:n]))

m, ms = float('inf'), 0

for i in range(len(nums)):

for j in range(i, len(nums)):

s = sum(nums[i:j + 1])

if s % 89 == 0 and s > ms:

ms, m = s, j - i + 1

if s % 89 == 0 and s == ms:

m = min(m, j - i + 1)

print(m)

Приведём динамическое решение задачи на языке Python.

f = open('27_B.txt')

k, s = 89, 0

mins = {0: (0, 0)}

res = []

for i in range(1, int(f.readline())+1):

s += int(f.readline())

if s % k in mins:

res += [(s - mins[s % k][0], mins[s % k][1] – i)]

else:

mins[s % k] = (s, i)

print(-max(res)[1])

Приведём решение задачи через метод частичных сумм на языке Python.

f = open('27_B.txt')

n = int(f.readline())

k = 89

r = {0: (0, 0)}

ms = 0

m = float('inf')

for _ in range(n):

x = int(f.readline())

t = {}

for key in r:

t[(key+x) % k] = (r[key][0] + x, r[key][1] + 1)

if x % k not in t:

t[x % k] = (x, 1)

r = t.copy()

if 0 in r:

if ms < r[0][0]:

ms = r[0][0]

m = r[0][1]

elif ms == r[0][0]:

m = min(t[0][1], m)

print(m)

Приведём решение Юрия Красильникова на языке Python.

a = [int(s) for s in open('27_B.txt')][1:]

p = 0

b = [0]

nk = [[0]] + [[] for _ in range(88)]

for i in range(len(a)):

p += a[i]

b.append(p)

r = p%89

if len(nk[r]) < 2: nk[r].append(i+1)

else: nk[r][1] = i+1

r = sorted([(b[x[1]]-b[x[0]],x[0]-x[1]) for x in nk if len(x) == 2],reverse=True)

print(-r[0][1])

Приведём решение задачи на языке Pascal.

var

i, d: longint;

n: longint;

mins: array [0..88] of longint;

minl: array [0..88] of longint;

sum, maxsum, minlen, num, ms, l: longint;

f: text;

begin

assign(f,'C:\27_B.txt');

reset(f);

readln(f, n);

for i := 0 to 88 do mins[i] := 1000000001;

for i := 0 to 88 do minl[i] := 0;

sum := 0;

maxsum := 0;

minlen := 0;

ms := 0;

l := 0;

for i := 1 to n do begin

readln(f, num);

sum := sum + num;

d := sum mod 89;

if d = 0 then begin

maxsum := sum;

minlen := i;

end

else begin

ms := sum - mins[d];

l := i - minl[d];

if ms > maxsum then begin

maxsum := ms;

minlen := l;

end;

if (ms = maxsum) and (l < minlen) then begin

maxsum := ms;

minlen := l;

end;

end;

if sum < mins[d] then begin

mins[d] := sum;

minl[d] := i;

end;

end;

writeln(minlen);

end.

В результате работы данного алгоритма при вводе данных из файла A ответ — 159, из файла B — 67059.

Примечание.

Путь к файлу необходимо указать согласно расположению файла на Вашем компьютере.