Форум программистов, компьютерный форум, киберфорум
JavaScript для начинающих
Войти
Регистрация
Восстановить пароль
Блоги Сообщество Поиск Заказать работу  
 
 
Рейтинг 5.00/15: Рейтинг темы: голосов - 15, средняя оценка - 5.00
34 / 25 / 8
Регистрация: 16.11.2019
Сообщений: 179

Клиппи и Мерлин

25.03.2020, 13:03. Показов 3306. Ответов 31
Метки нет (Все метки)

Студворк — интернет-сервис помощи студентам
Клиппи и Мерлин решили грабить банк, который представляет собой N расположенных в ряд банковских ячеек, пронумерованных последовательно числами от 1 до N.

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

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

Входные данные

В первой строке вводятся два числа — N ( 2 ≤N≤ 105) и K (0 ≤K<N− 1) соответственно. В второй строке вводятся N чисел ai(0 ≤ai≤ 109) — стоимости хранимых ценностей в ячейках от 1 до N соответственно.

Выходные данные

Выведите два числа в возрастающем порядке — номера ячеек, которые нужно ограбить, чтобы суммарно украсть как можно более дорогие ценности, не вызвав при этом лишних подозрений. Если вариантов несколько выберите тот, в котором меньший номер вскрываемой ячейки был как можно ближе к единице, чтобы в экстренном случае покинуть банк как можно скорее. Если и таких вариантов несколько, выберите тот, в котором и больший номер вскрываемой ячейки был как можно меньше.
0
Programming
Эксперт
39485 / 9562 / 3019
Регистрация: 12.04.2006
Сообщений: 41,671
Блог
25.03.2020, 13:03
Ответы с готовыми решениями:

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

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

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

31
Эксперт JS
6496 / 3907 / 2006
Регистрация: 14.06.2018
Сообщений: 6,781
25.03.2020, 16:10
Здравствуйте.

Как раз тот случай, когда ответ нужен в качестве юнит-тестов ))))))
Не люблю задачки на интеллект. От них голова болит...
JavaScript
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
// Функция создания случайного целого числа из диапазона
const rand = (min, max) => Math.floor(Math.random() * (max - min + 1) + min);
let n = rand(2, 105);
let k = rand(0, n - 2);
let ai = [];
for (let i = 0; i < n; i++)
    ai[i] = rand(0, 109);
let all;
let max = -1;
for (let i = 0; i < ai.length - 1; i++)
    for (let j = i + 1; j < ai.length; j++) {
        if (j - i > k) {
            let sum = ai[i] + ai[j];
            if (sum > max) {
                all = { i, j, sum };
                max = sum;
            }
        }
    }
console.log(`N=${n}`);
console.log(`K=${k}`);
console.log(ai.join(", "));
console.log(`${ai[all.i]} ${ai[all.j]}`);
Добавлено через 1 час 12 минут
----
Теперь приступим к реализации примитивного пользовательского ввода, который требуется по условию задачи из Питона.
В браузере самым примитивным инструментом ввода/вывода являются prompt()/alert().
PHP/HTML
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
<!DOCTYPE html>
<html>
<head>
    <meta charset="utf-8">
</head>
<body>
    <script>
        let n = +prompt("Введите N:");
        let k = +prompt("Введите K:");
        let ai = [];
        for (let i = 1; i <= n; i++)
            ai[i - 1] = +prompt(`Введите ${i}-е число:`);
 
        let all;
        let max = -1;
        for (let i = 0; i < ai.length - 1; i++)
            for (let j = i + 1; j < ai.length; j++) {
                if (j - i > k) {
                    let sum = ai[i] + ai[j];
                    if (sum > max) {
                        all = { i, j, sum };
                        max = sum;
                    }
                }
            }
        alert(`${ai[all.i]} ${ai[all.j]}`);
    </script>
</body>
</html>
0
Эксперт Python
5438 / 3859 / 1215
Регистрация: 28.10.2013
Сообщений: 9,552
Записей в блоге: 1
28.03.2020, 00:57
Квадратичная сложность - плохая асимптотика. Такое решение тестирующие системы не принимают.
2
Эксперт JSЭксперт HTML/CSS
2151 / 1496 / 651
Регистрация: 16.04.2016
Сообщений: 3,696
28.03.2020, 23:43
Как вариант при O(n) - https://codepen.io/qwerty_wasd/pen/bGdOOgJ
(модалки не использовал - трясет меня от них)

JavaScript
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
let opCell = {
  // N = length, v = cost
  cells: Array.from(
    { length: 100 },
    v => Math.floor(Math.random() * 10) + 1
  ),
  // K
  step: Math.floor(Math.random() * 10) + 1,
 
  // get result
  getCellsThief: (c, s) => {
    let tmp = [0 ,0];
    opCell.cells.forEach((v, i, a) => {
      if (a[i + opCell.step] && tmp[1] < v + a[i + opCell.step]) tmp = [i, v + a[i + opCell.step]];
    });
    return `Cells: #${tmp[0] + 1} and #${tmp[0] + opCell.step + 1}`;
  },
};
 
console.log(opCell.getCellsThief(opCell.cells, opCell.step));
0
Эксперт Python
5438 / 3859 / 1215
Регистрация: 28.10.2013
Сообщений: 9,552
Записей в блоге: 1
29.03.2020, 22:00
Не то... неверно работает. Значит нет олимпиадников среди javascript программистов.

Вот переписал код с нечитабельного javascript на понятный Python:
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def rob(a:list, step:int) -> (int,int):
    len_a = len(a)
    tmp = [0, 0]
    for i,v in enumerate(a):
        # проверка выхода индекса за границы списка
        if i + step < len_a - 1:
            val = v + a[i + step]
            if tmp[1] < val: 
                tmp = [i, val]
   
    return tmp[0] + 1, tmp[0] + step + 1
 
#arr = [random.randint(1,1000) for _ in range(20)] 
# получившийcя список
arr = [128, 662, 237, 27, 101, 957, 871, 812, 647, 597, 4, 295, 797, 325, 556, 150, 70, 805, 272, 803]
print(rob(arr, 2))
Правильный ответ: 5 и 17 индексы: то есть ячейки с ценой 957 (самая дорогая) и 805 (вторая по ценности)
Код выдает: (6, 8) Даже с учетом ошибок с индексами на единицу - вторая вещь даже близка не та.
Также не соблюдается условие: между ними должно быть не меньше K банковских ячеек.
1
Эксперт JSЭксперт HTML/CSS
2151 / 1496 / 651
Регистрация: 16.04.2016
Сообщений: 3,696
30.03.2020, 12:17
Цитата Сообщение от Garry Galler Посмотреть сообщение
Значит нет олимпиадников среди javascript программистов
посты темы и заявление не коррелируют. И программист это инженер - специалист, способный мыслить системно и подбирать для построения абстракции релеватный набор инструментов.

Цитата Сообщение от Garry Galler Посмотреть сообщение
с нечитабельного javascript на понятный Python:
субъективно... и Вы в ветке JS(инструмента для front-задач). Нравится Вам это или нет.

Далее -
Цитата Сообщение от Garry Galler Посмотреть сообщение
Также не соблюдается условие:
не также, а именно поэтому и неверный результат. Вы правы - я поторопился и сглупил, за что приношу извинения перед гостями темы, которых мог ввести в заблуждение.

Вот исправленный вариант(в песочнице поправил)
JavaScript
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
let opCell = {
  // N = length = 100, v = cost
  cells: Array.from(
    { length: 15 },
    v => Math.floor(Math.random() * 1000) + 1
  ),
  // K
  step: Math.floor(Math.random() * 10) + 1,
 
  // get result
  getCellsThief: (c, s) => {
    // set result array
    let res = [0, 0];
    // get index max value
    res[0] = c.indexOf(Math.max(...c));
    // divide array in two parts(left \ right, delta in step), concatenate, get max value in resulting array and look its index in a source
    // from index + step if allowed or from 0 index
    res[1] = c.indexOf(Math.max(...[...(c[res[0] - s] ? c.slice(0, res[0] - s) : []), ...(c[res[0] + s + 1] ? c.slice(res[0] + s + 1) : [])]), (c[res[0] - s - 1] ? 0 : res[0] + s + 1));
    return res.sort((a, b) => a - b).join` and `;
  },
};
1
Эксперт Python
5438 / 3859 / 1215
Регистрация: 28.10.2013
Сообщений: 9,552
Записей в блоге: 1
30.03.2020, 13:19
Цитата Сообщение от Qwerty_Wasd Посмотреть сообщение
посты темы и заявление не коррелируют
Если вы не в курсе, это олимпиадная задача.
Цитата Сообщение от Qwerty_Wasd Посмотреть сообщение
Вот исправленный вариант
ОМГ. Ну почему опять нечитабельно?
Цитата Сообщение от Qwerty_Wasd Посмотреть сообщение
Вы в ветке JS(инструмента для front-задач)
То есть инструмент для фронтенд-задач обязан быть нечитабельным?
И здесь никогда не слышали про правило 80 символов?
-----------------------------------------
А где тесты кода? Просто, судя по алгоритму, решение даже близко не похоже на то, которое проходит все тесты (я его знаю).
0
Эксперт JS
6496 / 3907 / 2006
Регистрация: 14.06.2018
Сообщений: 6,781
30.03.2020, 13:48
Цитата Сообщение от Garry Galler Посмотреть сообщение
То есть инструмент для фронтенд-задач обязан быть нечитабельным?
У нас тут на ветке форума два противоборствующих лагеря тупоконечников и остроконечников.

Есть мнение, что чем нечитаемее код, тем лучше.
И второе мнение, что чем примитивнее написана длинная простынка кода, тем лучше.

Добавлено через 1 минуту
Цитата Сообщение от Garry Galler Посмотреть сообщение
А где тесты кода?
С первого дня вопю ))
0
30.03.2020, 14:30

Не по теме:

Garry Galler,

Цитата Сообщение от Garry Galler Посмотреть сообщение
Если вы не в курсе, это олимпиадная задача.
так и есть, я не в курсе. Я не олимпиадник... не кретин надеюсь, но и ничего особенного.
Цитата Сообщение от Garry Galler Посмотреть сообщение
ОМГ. Ну почему опять нечитабельно?
субъективно. Мне читабельно. Я спокойно могу детерминировать тротлы в такком коде. Но я не возмущаюсь, когда кто-то не может\хочет это делать. Ибо не жду того от других. А код именно на JS пишу не
Цитата Сообщение от amr-now Посмотреть сообщение
чем нечитаемее код, тем лучше
а как можно короче, ибо язык сценариев, что я использовал, интерпретируем. Чем короче текст скрипта, тем быстрее он спарсится. Именно исходя из этого я так пишу на нем.

Цитата Сообщение от Garry Galler Посмотреть сообщение
То есть инструмент для фронтенд-задач обязан быть нечитабельным?
ну опять же ))
В общем не держите зла. Но и на поводу у Вас я не пойду.

Цитата Сообщение от Garry Galler Посмотреть сообщение
И здесь никогда не слышали про правило 80 символов?
нет не слышал. Я ведь не программист. Сфера моей основной деятельности несколько иная.

Цитата Сообщение от Garry Galler Посмотреть сообщение
Просто, судя по алгоритму, решение даже близко не похоже на то, которое проходит все тесты (я его знаю).
Вы же понимаете что решение задачи может быть не одним?



0
Эксперт Python
5438 / 3859 / 1215
Регистрация: 28.10.2013
Сообщений: 9,552
Записей в блоге: 1
30.03.2020, 15:27
Цитата Сообщение от Qwerty_Wasd Посмотреть сообщение
Чем короче текст скрипта, тем быстрее он спарсится.
Дело не в краткости - дело в вашем непонимании правильно оформленного кода для чтения его другим человеком.
Вы могли бы сделать переносы строк кода по правилу 80 символов на строку.
Это базовый guide style для любых языков программирования.

Короткий код, может быть, и спарсится на пару наносекунд быстрее, но если его алгоритм никуда не годится, то какое его премущество перед более длинным кодом?

Цитата Сообщение от Qwerty_Wasd Посмотреть сообщение
Вы же понимаете что решение задачи может быть не одним?
Правильных решений может быть много. Но пока я видел только одно (не с O(N^2) асимптотикой). Ваше работает неверно при больших k (близких к максимальному: array.length -2, array.length -3 и т.д.)
0
Эксперт JS
6496 / 3907 / 2006
Регистрация: 14.06.2018
Сообщений: 6,781
30.03.2020, 15:30
Нашел.
Это задача по информатике для 6-8 классов средней школы.

Добавлено через 3 минуты
----
Garry Galler, Qwerty_Wasd, а если серьезно, то для JavaScript существуют утилиты-минификаторы кода.
Не обязательно целенаправленно писать нечитаемый код.
0
Эксперт Python
5438 / 3859 / 1215
Регистрация: 28.10.2013
Сообщений: 9,552
Записей в блоге: 1
30.03.2020, 15:33
Цитата Сообщение от amr-now Посмотреть сообщение
задача по информатике для 6-8 классов средней школы
Для школьников там решение за квадрат. А вот за O(N) это уже олимпиада.
0
Эксперт JSЭксперт HTML/CSS
2151 / 1496 / 651
Регистрация: 16.04.2016
Сообщений: 3,696
30.03.2020, 15:42
amr-now,
Цитата Сообщение от amr-now Посмотреть сообщение
утилиты-минификаторы кода
стараюсь не пользоваться ими для JS, ибо алгоритм большинства из них - тупо создать словарь из сокращений и полифиллов, что в разы увеличивает объем кода. К примеру тот же гугловский кложур.
0
Эксперт PHP
 Аватар для Fedor Vlasenko
936 / 693 / 236
Регистрация: 01.02.2015
Сообщений: 1,848
30.03.2020, 15:46
написал как сам понял задачу
JavaScript
1
2
3
4
5
6
7
8
const n = 50;
const rand = (max, min) => Math.floor(Math.random() * (max - min + 1)) + min;
// ячейки с деньгами
let cells = Array.from(new Array(n), (_, i) => [rand(1, 109), i]);
// отсортировали
cells = cells.sort((a, b) => b[0] === a[0] ? a[1] - b[1] : b[0] - a[0]);
//решение первые элементы массива согласно условиям k 0,1 или 0,2
console.log(cells)
0
Эксперт JSЭксперт HTML/CSS
2151 / 1496 / 651
Регистрация: 16.04.2016
Сообщений: 3,696
30.03.2020, 15:48
Цитата Сообщение от Garry Galler Посмотреть сообщение
дело в вашем непонимании правильно оформленного кода для чтения его другим человеком.
не фантазируйте. Понимание есть, как и понимание где он нужен - при работе в команде например. И amr-now, я не пишу его целенаправленно - просто по привычке настрочил как для себя. И тут на форуме - я не лезу из кожи вон во всех деталях.

Garry Galler, я претензию Вашу понял. Будет время и желание - заморочнусь и перепишу почище и понятнее. Не будет оных - се ля ви.
0
Эксперт Python
5438 / 3859 / 1215
Регистрация: 28.10.2013
Сообщений: 9,552
Записей в блоге: 1
30.03.2020, 15:51
Цитата Сообщение от Qwerty_Wasd Посмотреть сообщение
не фантазируйте.
Я не фантазирую. Я оцениваю. По объективным критериям. Вам еще многому нужно научиться в программировании не для себя.
0
Эксперт JSЭксперт HTML/CSS
2151 / 1496 / 651
Регистрация: 16.04.2016
Сообщений: 3,696
30.03.2020, 15:54
Garry Galler,
Цитата Сообщение от Garry Galler Посмотреть сообщение
Вам еще многому нужно научиться в программировании не для себя
если не трудно - примеры.
0
566 / 465 / 183
Регистрация: 14.10.2017
Сообщений: 1,259
30.03.2020, 16:07
JavaScript
1
2
3
4
5
6
7
8
9
10
11
12
13
let twoRobbers = (arr, dist) => {
    let res = [0, 0, 0];
    for(let i = 0, len = arr.length - dist; i < len; i++ ) {
        let max = i + dist + 1;
        for(let j = max; j < arr.length; j++)
            if(arr[j] > arr[max]) 
                max = j;
        if(arr[i] + arr[max] > res[0])
            res =  [arr[i] + arr[max], i, max];  
    }
    return [res[1] + 1, res[2] + 1];
};  
console.log(twoRobbers(arr, 2));
0
Эксперт JSЭксперт HTML/CSS
2151 / 1496 / 651
Регистрация: 16.04.2016
Сообщений: 3,696
30.03.2020, 16:24
Цитата Сообщение от Garry Galler Посмотреть сообщение
Ваше работает неверно при больших k
мое работает именно так как я его задумал.
Разберемся -
условия

1. ячейки - 2 ≤N≤ 105
2. шаг - не меньше K, 0 ≤K<N− 1

искомое
две ячейки с разницей не менее K ячеек с максимальным, из имеющихся, профитом.


то есть при
Code
1
[128, 662, 237, 27, 70, 957, 871, 812, 647, 999999999, 4, 295, 797, 325, 556, 150, 170, 805, 11272, 803]
с шагом не менее 17 ячеек

второй ячейки просто нет. Что и выдает мой скрипт в виде -1

Я также держу рядом мысль, что я не догнал просто условия задачи. Кому не трудно помогите докрутить педали - интересно.
0
566 / 465 / 183
Регистрация: 14.10.2017
Сообщений: 1,259
30.03.2020, 16:39
Цитата Сообщение от Qwerty_Wasd Посмотреть сообщение
с шагом не менее 17 ячеек
второй ячейки просто нет. Что и выдает мой скрипт в виде -1
может я чего не понял, но у вас массив 20, шаг 17, должно быть 6 вариантов из которых выбирается наибольший, не?
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
inter-admin
Эксперт
29715 / 6470 / 2152
Регистрация: 06.03.2009
Сообщений: 28,500
Блог
30.03.2020, 16:39
Помогаю со студенческими работами здесь

Клиппи и Мерлин грабят банк
Клиппи и Мерлин грабят банк Клиппи и Мерлин решили грабить банк, который представляет собой N расположенных в ряд банковских ячеек,...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
20
Ответ Создать тему
Новые блоги и статьи
Оттенки серого
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),. . .
[Owen Logic] Поддержание уровня воды в резервуаре количеством включённых насосов: моделирование и выбор регулятора
ФедосеевПавел 14.03.2026
Поддержание уровня воды в резервуаре количеством включённых насосов: моделирование и выбор регулятора ВВЕДЕНИЕ Выполняя задание на управление насосной группой заполнения резервуара,. . .
делаю науч статью по влиянию грибов на сукцессию
anaschu 13.03.2026
прикрепляю статью
SDL3 для Desktop (MinGW): Создаём пустое окно с нуля для 2D-графики на SDL3, Си и C++
8Observer8 10.03.2026
Содержание блога Финальные проекты на Си и на C++: hello-sdl3-c. zip hello-sdl3-cpp. zip Результат:
Установка CMake и MinGW 13.1 для сборки С и C++ приложений из консоли и из Qt Creator в EXE
8Observer8 10.03.2026
Содержание блога MinGW - это коллекция инструментов для сборки приложений в EXE. CMake - это система сборки приложений. Здесь описаны базовые шаги для старта программирования с помощью CMake и. . .
Как дизайн сайта влияет на конверсию: 7 решений, которые реально повышают заявки
Neotwalker 08.03.2026
Многие до сих пор воспринимают дизайн сайта как “красивую оболочку”. На практике всё иначе: дизайн напрямую влияет на то, оставит человек заявку или уйдёт через несколько секунд. Даже если у вас. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2026, CyberForum.ru