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

@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, зачем в разделе по питону код на плюсах, да еще в теме двухлетней давности?

Новые блоги и статьи Все статьи Все блоги /
Автозаполнение реквизита при выборе элемента справочника Maks 27.03.2026 Программный код из решения ниже на примере нетипового документа "ЗаявкаНаРемонтСпецтехники" разработанного в конфигурации КА2. При выборе "Спецтехники" (Тип Справочник. Спецтехника), заполняется. . .	Сумматор с применением элементов трёх состояний. Hrethgir 26.03.2026 Тут. https:/ / fips. ru/ EGD/ ab3c85c8-836d-4866-871b-c2f0c5d77fbc Первый документ красиво выглядит, но без схемы. Это конечно не даёт никаких плюсов автору, но тем не менее. . . всё может быть. . .	Автозаполнение реквизитов при создании документа Maks 26.03.2026 Программный код из решения ниже размещается в модуле объекта документа, в процедуре "ПриСозданииНаСервере". Алгоритм проверки заполнения реализован для исключения перезаписи значения реквизита,. . .	Команды формы и диалоговое окно Maks 26.03.2026 1. Команда формы "ЗаполнитьЗапчасти". Программный код из решения ниже на примере нетипового документа "ЗаявкаНаРемонтСпецтехники" разработанного в конфигурации КА2. В качестве источника данных. . .
Кому нужен AOT? DevAlt 26.03.2026 Решил сделать простой ланчер Написал заготовку: dotnet new console --aot -o UrlHandler var items = args. Split(":"); var tag = items; var id = items; var executable = args;. . .	Отправка уведомления на почту при создании или изменении элементов справочника Maks 24.03.2026 Программная отправка письма электронной почты на примере типового справочника "Склады" в конфигурации БП3. Перед реализацией необходимо выполнить настройку системной учетной записи электронной. . .	модель ЗдравоСохранения 5. Меньше увольнений- больше дохода! anaschu 24.03.2026 Теперь система здравосохранения уменьшает количество увольнений. 9TO2GP2bpX4 a42b81fb172ffc12ca589c7898261ccb/ https:/ / rutube. ru/ video/ a42b81fb172ffc12ca589c7898261ccb/ Слева синяя линия -. . .	Midnight Chicago Blues kumehtar 24.03.2026 Такой Midnight Chicago Blues, знаешь?. . Когда вечерние улицы становятся ночными, а ты не можешь уснуть. Ты идёшь в любимый старый бар, и бармен наливает тебе виски. Ты смотришь на пролетающие. . .

@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