Клиппи и Мерлин грабят банк

@nikolayfedoroff · Регистрация: 29.05.2019

Студворк — интернет-сервис помощи студентам

Решаю задачу по программированию.
Условие:
Клиппи и Мерлин решили грабить банк «Документы», который представляет из себя N расположенных в ряд банковских ячеек, пронумерованных последовательно числами от 1 до N .

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

Чтобы не вызывать лишних подозрений, Клиппи и Мерлин решили ограбить всего две ячейки "— по одной на каждого. Также, чтобы охрана банка не почуяла неладного, они решили работать далеко друг от друга "— между ними должно быть не меньше K банковских ячеек.

Входные данные
В первой строке вводятся два числа "— N ( 2 ≤ N ≤ 10⁵ ) и K ( 0 ≤ K < N - 1 ) соответственно. В второй строке вводятся N чисел a i ( 0 ≤ a i ≤ 10 ⁹ ) "— стоимости хранимых ценностей в ячейках от 1 до N соответственно.

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

Примеры
входные данные
6 2
2 4 3 1 4 4
выходные данные
2 5

У меня есть несколько решений.

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
n, k = map(int, input().split())
arr = list(map(int, input().split()))
 
max1 = -1
max2 = -1
 
x, y = 0, 0
 
for i in range(n-k-1):
    if arr[i+k+1] > max1:
        max1 = arr[i+k+1]
    if arr[i] + arr[i+k+1] > max2:
        max2 = arr[i] + arr[i+k+1]
        x, y = i, i+k+1
 
print(x+1, y+1)

и еще одно...

Python
1
2
3
4
5
6
7
8
9
10
11
N,K = map(int,input().split())
mass = list(map(int,input().split()))
 
 
min1, max1 = 0, K+1
for i in range(len(mass)-K-1):
    for j in range(K+1+i,N):
        if mass[i]+mass[j]>mass[min1]+mass[max1]:
            min1,max1 = i,j
 
print(min1+1,max1+1)

Первое - попытка линейного перебора, с ошибками в тестах. Второе - обычный перебор с превышение TL. В чем ошибка в первом решении и есть ли смысл, его развивать дальше? Если решали эту задачу, прошу объяснить алгоритм. Заранее спасибо

@hacthies · 12.08.2019, 09:59

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <iostream>
using namespace std;
const int N=1E5;
int a[N], p[N], s[N];
 
int main() {
int n, k, i, j;
cin >> n >> k;
for (i=0, j=0; i<n; i++) {
cin >> a[i];
if (a[i] > a[j]) {p[i] = i; j = i;} else p[i] = p[j];
}
for (i=n-1, j=n-1; i>=0; i--) {
if (a[i] >= a[j]) {s[i] = i; j = i;} else s[i] = s[j];
}
int f = 0, l = 0, r = k+1;
for (i=l, j=r; j<n; i++, j++) {
int t = a[p[i]] + a[s[j]];
if (t > f) {l = p[i]; r = s[j]; f = t;}
}
cout << (l+1) << " " << (r+1);
}

Вот, правда, я думаю, что уже поздно

На будущее, извиняюсь, что C++, но тут легко переписать

@Rorik · 02.07.2020, 14:58

Есть такое решение на питоне, но оно не проходит все тесты

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
n, k = map(int, input().split())
a = list(map(int, input().split()))
ibest = 0
jbest = 1
imin = 0
for j in range(2, n - k):
    if a[j - 1] > a[imin]:
        imin =  j - 1
    if a[j + k] + a[imin] > a[jbest] + a[ibest]:
        jbest = j + k
        ibest = imin
          
print(ibest + 1, jbest + 1)

@Garry Galler · 02.07.2020, 18:53

Сообщение от Rorik

но оно не проходит все тесты

Специально для тебя запостили решение на С++ - его алгоритм тесты проходит.
Просто тупо перепиши.

@Rorik · 03.07.2020, 09:18

Я не знаю С++ и не понимаю что за p[N], s[N] в 4 строке - это отдельные массивы?

@gurulTailan · 03.07.2020, 10:11

Правильное решение (проверено на платформе сириуса):

Python
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
N = int(1E5)
n, k = map(int, input().split())
j = 0
a = list(map(int, input().split())) + [0] * (N - n)
p = [0] * N
s = [0] * N
for i in range(n):
    if a[i] > a[j]:
        p[i] = i
        j = i
    else:
        p[i] = p[j]
j = n - 1
for i in range(n - 1, -1, -1):
    if a[i] >= a[j]:
        s[i] = i
        j = i
    else:
        s[i] = s[j]
m, l, r = 0, 0, k + 1
i = l
for j in range(r, n):
    t = a[p[i]] + a[s[j]]
    if t > m:
        l = p[i]
        r = s[j]
        m = t
    i += 1
print(l + 1, r + 1)

Рыжий Лис · 03.07.2020, 10:44

Сообщение от Rorik

4 строке - это отдельные массивы?

Да, это три разных переменных.

@1timchik1 · 03.07.2020, 19:14

Товарищи, кто правильно решил задачу, можете кто-нибудь кинуть тесты кроме стандартных

@pchela_sociofob · 12.07.2021, 09:01

1timchik1, на StackOverFlow есть такие, если еще не поздно

Input:

Кликните здесь для просмотра всего текста

# Содержимое файлов с тестами
$ tail -n +1 -- input_*

==> input_1.txt <==
6 0
2 9 9 1 4 4

==> input_2.txt <==
6 1
5 7 6 8 0 0

==> input_3.txt <==
6 1
5 9 9 1 4 6

==> input_4.txt <==
10 1
1 1 4 1 1 1 3 1 3 1

Output:

Кликните здесь для просмотра всего текста

input_1.txt
2 3

input_2.txt
2 4

input_3.txt
2 6

input_4.txt
3 7

@Tanzhor_RIK · 03.10.2022, 07:50

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
n, k = map(int, input().split())
a = list(map(int, input().split()))
maxi2 = -1
imax = 0
ibest = 0
jbest = k + 1
for i in range(k + 1, n):
    if a[i - k  - 1] > a[imax]:
        imax = i - k - 1
    if a[i] + a[imax] > maxi2:
        maxi2 = a[i] + a[imax]
        ibest = imax
        jbest = i
print(ibest + 1, jbest + 1)

@TheBestTiger · 02.01.2023, 15:52

Код для с++

C++
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
#include <iostream>
#include <vector>
using namespace std;
int main()
{
    int n,k;
    cin >> n >> k ;
    vector <int> a(n);
    for (int i=0; i<n; i++)
        cin >> a[i] ;
    int maxiii;
    maxiii=-1;
    int imx;
    imx=0;
    int jbest;
    jbest=k+1;
    int ibest;
    ibest=0;
    for (int i=k+1; i<n; i++) {
        if (a[i-k-1]>a[imx])
            imx=i-k-1;
        if (a[i]+a[imx]>maxiii) {
            maxiii=a[i]+a[imx];
            ibest=imx;
            jbest=i;
        }
    }
    cout << ibest+1 << " " << jbest+1 ;
    return 0;
}

@Kivik · 04.07.2024, 10:46

C++
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
#include <iostream>
#include <vector>
 
using namespace std;
 
int main()
{
    //Заполняем массив:
    int n, k;
    cin >> n >> k;
    vector <int> rpt(n);
    for (int i = 0; i < n; ++i) {
        cin >> rpt[i];
    }
    int imax = 0;
    int jbest = k + 1;
    int ibest = 0;
    for (int i = k + 1; i < n; ++i) {
        if (rpt[i - k - 1] > rpt[imax]) {
            imax = i - k - 1;
        }
        if (rpt[imax] + rpt[i] > rpt[ibest] + rpt[jbest]) {
            ibest = imax;
            jbest = i;
        }
    }
 
 
    cout << ibest + 1 << " " << jbest + 1;
    return 0;
}

Итак, немного комментариев к основной логике программы (циклу):
Допустим, нам дан массив: 3 6 2 1 8 2, К = 2 (минимум 2 ячейки должно быть между 2 ячейками)

Изначально ставим "метку" на k + 1 = 3. 3 (( 6 2 )) 1 8 2 То бе ж на элемент "1" (Четвертый элемент с начала массива).
В цикле мы будем искать максимальный "левый" элемент относительно 2 "ячеек - перегородок". Т.е. в данном случае т.к. по умолчанию imax = 0 - ничего не изменится. А вот в следующей итерации уже мы поставим левую "метку" на 6 и скажем, что т.к. 6 > 3, то делаем imax = 1. Правую сторону обработать несколько легче: мы просто будем проверять максимальна ли сумма максимального левого элемента и произвольного правого, таким образом находя максимальный правый элемент.

@iSmokeJC · 04.07.2024, 11:09

Kivik, зачем в разделе по питону код на плюсах, да еще в теме двухлетней давности?

Новые блоги и статьи Все статьи Все блоги /
1С: Программный отбор элементов справочника по группе Maks 22.03.2026 Установка программного отбора элементов справочника "Номенклатура" из модуля формы документа. В качестве фильтра для отбора справочника служит группа номенклатуры. Отбор по наименованию группы. . .	Как я обхитрил таблицу Word Alexander-7 21.03.2026 Когда мигает курсор у внешнего края таблицы, и нам надо перейти на новую строку, а при нажатии Enter создается новый ряд таблицы с ячейками, то мы вместо нервных нажатий Энтеров мы пишем любые буквы. . .	Krabik - рыболовный бот для WoW 3.3.5a AmbA 21.03.2026 без регистрации и смс. Это не торговля, приложение не содержит рекламы. Выполняет свою непосредственную задачу - автоматизацию рыбалки в WoW - и ничего более. Однако если админы будут против -. . .	1С: Программный отбор элементов справочника по значению перечисления Maks 21.03.2026 Установка программного отбора элементов справочника "Сотрудники" из модуля формы документа. В качестве фильтра для отбора служит значение перечислений. / / Событие "НачалоВыбора" реквизита на форме. . .
Переходник USB-CAN-GPIO Eddy_Em 20.03.2026 Достаточно давно на работе возникла необходимость в переходнике CAN-USB с гальваноразвязкой, оный и был разработан. Однако, все меня терзала совесть, что аж 48-ногий МК используется так тупо: просто. . .	Оттенки серого Argus19 18.03.2026 Оттенки серого Нашёл в интернете 3 прекрасных модуля: Модуль класса открытия диалога открытия/ сохранения файла на Win32 API; Модуль класса быстрого перекодирования цветного изображения в оттенки. . .	SDL3 для Desktop (MinGW): Рисуем цветные прямоугольники с помощью рисовальщика SDL3 на Си и C++ 8Observer8 17.03.2026 Содержание блога Финальные проекты на Си и на C++: finish-rectangles-sdl3-c. zip finish-rectangles-sdl3-cpp. zip	Символические и жёсткие ссылки в Linux. algri14 15.03.2026 Существует два типа ссылок — символические и жёсткие. Ссылка в Linux — это запись в каталоге, которая может указывать либо на inode «файла-ИСТОЧНИКА», тогда это будет «жёсткая ссылка» (hard link),. . .

@Rorik 25 / 14 / 2 Регистрация: 28.06.2020 Сообщений: 50
	03.07.2020, 09:18
	Я не знаю С++ и не понимаю что за p[N], s[N] в 4 строке - это отдельные массивы? 0

@1timchik1 30 / 29 / 2 Регистрация: 27.06.2020 Сообщений: 14
	03.07.2020, 19:14
	Товарищи, кто правильно решил задачу, можете кто-нибудь кинуть тесты кроме стандартных 0

@pchela_sociofob 31 / 18 / 5 Регистрация: 30.08.2020 Сообщений: 55
	12.07.2021, 09:01
	1timchik1, на StackOverFlow есть такие, если еще не поздно Input: Кликните здесь для просмотра всего текста # Содержимое файлов с тестами $ tail -n +1 -- input_* ==> input_1.txt <== 6 0 2 9 9 1 4 4 ==> input_2.txt <== 6 1 5 7 6 8 0 0 ==> input_3.txt <== 6 1 5 9 9 1 4 6 ==> input_4.txt <== 10 1 1 1 4 1 1 1 3 1 3 1 Output: Кликните здесь для просмотра всего текста input_1.txt 2 3 input_2.txt 2 4 input_3.txt 2 6 input_4.txt 3 7 0

@iSmokeJC 19530 / 11067 / 2931 Регистрация: 21.10.2017 Сообщений: 23,294
	04.07.2024, 11:09
	Kivik, зачем в разделе по питону код на плюсах, да еще в теме двухлетней давности? 1