Задача 6867. Источник: Поляков. Задание КИМ 27
(Д. Козлов) Мистер Шерлок Холмс взялся за одно очень крупное и интересное дело. На Риджент-стрит расположено N домов по кругу (это значит, что первый и последний дома – соседи). В каждом из этих домов содержится определённое количество улик (целое число от 0 до 10 включительно). Гениальный сыщик хочет собрать как можно больше улик, не посещая при этом двух соседних домов ни разу. Также Шерлок Холмс хочет завершить этот обыск как можно скорее и успеть на чашку чая с доктором Ватсоном. Помогите ему при помощи современных технологий XXI века как можно быстрее определить, какое максимальное количество улик удастся собрать при заданных условиях.
Входные данные. Даны два входных файла (файл A и файл B), каждый из которых в первой строке содержит натуральное число N (1 < N ≤ 10 000 000) – количество домов. Каждая из следующих N строк содержит одно целое число, не превышающее 10, – количество улик.
Пример входного файла:
4
1
2
3
1
При таких исходных данных Шерлоку Холмсу удастся собрать максимум 4 улики. Такое возможно при посещении домов под номерами 1 и 3. Ответ: 4.
В ответе укажите два числа: сначала искомое значение для файла А, затем для файла B.
Решение
Чтобы первый и последний дом не обрабатывались вместе, сделаем два прохода по данным: от первого дома до предпоследнего и от второго дома до последнего. На каждом проходе будем сохранять три последних максимальных суммы. Новый максимум определяется как сумма максимальной суммы из первых двух и нового числа улик. После обработки всех домов, выбираем максимальное значение из полученных.
Python
f = open("27-177b.txt")
n = int(f.readline())
a = [int(x) for x in f]
mx = 0
for z in range(2):
mx0, mx1, mx2 = 0, a[z], a[z + 1]
for i in range(2 + z, n + z - 1):
if mx0 > mx1:
mx0, mx1, mx2 = mx1, mx2, mx0 + a[i]
else:
mx0, mx1, mx2 = mx1, mx2, mx1 + a[i]
mx = max(mx, mx1, mx2)
print(mx)
PascalABC
var
n, max, max0, max1, max2, t, i, j, z: Integer;
a: array [1..331235] of Integer;
f: TEXT;
begin
Assign(f, '27-177b.txt');
Reset(f);
Readln(f, n);
for i := 1 to n do
Readln(f, a[i]);
max := 0;
for z := 0 to 1 do
begin
max0 := 0;
max1 := a[1 + z];
max2 := a[2 + z];
for i := 3 + z to n + z - 1 do
if max0 > max1 then
begin
t := max0 + a[i];
max0 := max1;
max1 := max2;
max2 := t;
end
else
begin
t := max1 + a[i];
max0 := max1;
max1 := max2;
max2 := t;
end;
if max1 > max then
max := max1;
if max2 > max then
max := max2;
end;
Writeln(max);
end.
C++
#include <iostream>
#include <fstream>
using namespace std;
int main()
{
ifstream f;
f.open("27-177b.txt");
int n;
f >> n;
int *a = new int[331235];
for (int i = 0; i < n; i++)
f >> a[i];
int max = 0;
for (int z = 0; z < 2; z++)
{
int max0 = 0, max1 = a[z], max2 = a[z + 1];
for (int i = 2 + z; i < n + z - 1; i++)
if (max0 > max1)
{
int t = max0 + a[i];
max0 = max1;
max1 = max2;
max2 = t;
}
else
{
int t = max1 + a[i];
max0 = max1;
max1 = max2;
max2 = t;
}
if (max1 > max)
max = max1;
if (max2 > max)
max = max2;
}
cout << max << endl;
delete[] a;
}
Ответ
72 991844