На вход программы поступает последовательность из целых положительных чисел. Необходимо выбрать такую подпоследовательность подряд идущих чисел, чтобы их сумма была максимальной и делилась на 89, а также её длину. Если таких подпоследовательностей несколько, выбрать такую, у которой длина меньше.
Даны два входных файла (файл A и файл B), каждый из которых содержит в первой строке количество чисел N (2 ≤ N ≤ 68000). В каждой из последующих N строк записано одно целое положительное число, не превышающее 10000. Программа должна вывести длину найденной последовательности.
Пример входного файла:
8
2
3
4
93
42
34
5
95
Для делителя 50 при указанных входных данных значением искомой суммы должно быть число 100 (3 + 4 + 93 или 5 + 95). Следовательно, ответ на задачу — 2. В ответе укажите два числа: сначала значение искомой длины для файла A, затем для файла B.
Ответ:
Решение. Перебираем все возможные суммы, которые начинаются на 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.
Примечание.
Путь к файлу необходимо указать согласно расположению файла на Вашем компьютере.
PDF-версии: 