Задача 4: Любовь и двери

@AEHale · Регистрация: 06.10.2021

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

Коварный Джафар разделил Аладдина и Жасмин, заманив их в разные концы
длинного коридора и заперев между ними n дверей. Теперь, чтобы вновь
увидеться, влюблённым необходимо открыть все эти двери по очереди.
Каждая из дверей является золотой или серебряной и открывается одним из двух
ключей из соответствующего материала, причём может быть открыта этим ключом
с любой стороны. Используя магию джинна, Аладдин может сделать так, чтобы у
него и Жасмин появилось по одному ключу разного типа. Это значит, что если у
Аладдина появится золотой ключ, то у Жасмин — серебряный, а если у Аладдина
будет серебряный ключ, то у Жасмин — золотой.
Помимо этого, Аладдин может попросить джинна изменить материал любой из
дверей (с золотого на серебряный или наоборот). Но каждую такую операцию
джинн будет выполнять ровно одну минуту.
После того, как джинн закончит изменять двери, Аладдин и Жасмин начнут
открывать их, двигаясь навстречу друг другу. Будем считать, что открытие дверей
и перемещение между ними происходит мгновенно. Через какое наименьшее время
они смогут наконец встретиться?Входные данные
Первая строка входных данных содержит целое число n (1 ≤ n ≤ 105) — количество
дверей. Следующие n строк содержат по одной цифре 1 или 2 в строке. Эти цифры
определяют порядок следования дверей в коридоре. Единица значит, что
соответствующая дверь золотая, а двойка — что серебряная.
Выходные данные
Выведите одно число — наименьшее количество минут, через которое будут
открыты все двери.
Система оценки
Решения, правильно работающие для случаев, в которых количество золотых
дверей не превосходит трёх, получат не менее 12 баллов.
Решения, правильно работающие для случаев, в которых общее количество
дверей не превосходит 100, получат не менее 32 баллов.
Решения, правильно работающие для случаев, в которых общее количество
дверей не превосходит 1000, получат не менее 56 баллов.
Примеры
Ввод Вывод Пояснение
8
1
2
2
1
2
1
1
1
2
Нужно выдать тому, кто находится у первой двери серебряный
ключ, а тому, кто у последней — золотой. Далее нужно
изменить тип первой и пятой двери, тогда последовательность
дверей станет такой: 2, 2, 2, 1, 1, 1, 1, 1. После этого ключами
можно будет открыть все двери. Можно показать, что быстрее,
чем за две операции, справится не выйдет.
4
2
1
1
1
0
9
1
1
1
1
2
1
1
1
1

@AEHale · 29.10.2021, 11:39 **[ТС]**

помогите пжлст:3

@eaa · 29.10.2021, 11:58

AEHale, чем помочь?

@AEHale · 29.10.2021, 12:01 **[ТС]**

именно вот эту я не представляю как решить

@JuLoSpace · 11.01.2022, 18:42

Решение задачи на c++ с помощью префиксных сумм. Считаем сколько раз встречается 1 и 2. Далее проходимся по n, считая "стоимость" до середины.

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
32
ll n;
cin >> n;
 
vector<ll> one(n+1);
vector<ll> two(n+1);
 
for (ll i = 0; i < n; i++) {
    ll a;
    cin >> a;
 
    if (a == 1) {
        one[i + 1] = one[i] + 1;
        two[i + 1] = two[i];
    }
    else if (a == 2) {
        one[i + 1] = one[i];
        two[i + 1] = two[i] + 1;
    }
}
 
ll cnt = 1e9;
    
for (ll i = 0; i < n; i++) {
    ll tob1 = one[i + 1];
    ll toa1 = two[n] - two[i+1];
    cnt = min(cnt, toa1 + tob1);
    tob1 = two[i + 1];
    toa1 = one[n] - one[i+1];
    cnt = min(cnt, toa1 + tob1);
}
 
cout << cnt;

Новые блоги и статьи Все статьи Все блоги /
Автоматическое создание документа при проведении другого документа Maks 29.03.2026 Реализация из решения ниже выполнена на нетиповых документах, разработанных в конфигурации КА2. Есть нетиповой документ "ЗаявкаНаРемонтСпецтехники" и нетиповой документ "ПланированиеСпецтехники". В. . .	Настройка движения справочника по регистру сведений Maks 29.03.2026 Решение ниже реализовано на примере нетипового справочника "ТарифыМобильнойСвязи" разработанного в конфигурации КА2, с целью учета корпоративной мобильной связи в коммерческом предприятии. . . .	Автозаполнение реквизита при выборе элемента справочника 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. Перед реализацией необходимо выполнить настройку системной учетной записи электронной. . .

@AEHale -6 / 2 / 1 Регистрация: 06.10.2021 Сообщений: 24

	Задача 4: Любовь и двери 29.10.2021, 04:41. Показов 15494. Ответов 4 Метки c++, python (Все метки) Коварный Джафар разделил Аладдина и Жасмин, заманив их в разные концы длинного коридора и заперев между ними n дверей. Теперь, чтобы вновь увидеться, влюблённым необходимо открыть все эти двери по очереди. Каждая из дверей является золотой или серебряной и открывается одним из двух ключей из соответствующего материала, причём может быть открыта этим ключом с любой стороны. Используя магию джинна, Аладдин может сделать так, чтобы у него и Жасмин появилось по одному ключу разного типа. Это значит, что если у Аладдина появится золотой ключ, то у Жасмин — серебряный, а если у Аладдина будет серебряный ключ, то у Жасмин — золотой. Помимо этого, Аладдин может попросить джинна изменить материал любой из дверей (с золотого на серебряный или наоборот). Но каждую такую операцию джинн будет выполнять ровно одну минуту. После того, как джинн закончит изменять двери, Аладдин и Жасмин начнут открывать их, двигаясь навстречу друг другу. Будем считать, что открытие дверей и перемещение между ними происходит мгновенно. Через какое наименьшее время они смогут наконец встретиться?Входные данные Первая строка входных данных содержит целое число n (1 ≤ n ≤ 105) — количество дверей. Следующие n строк содержат по одной цифре 1 или 2 в строке. Эти цифры определяют порядок следования дверей в коридоре. Единица значит, что соответствующая дверь золотая, а двойка — что серебряная. Выходные данные Выведите одно число — наименьшее количество минут, через которое будут открыты все двери. Система оценки Решения, правильно работающие для случаев, в которых количество золотых дверей не превосходит трёх, получат не менее 12 баллов. Решения, правильно работающие для случаев, в которых общее количество дверей не превосходит 100, получат не менее 32 баллов. Решения, правильно работающие для случаев, в которых общее количество дверей не превосходит 1000, получат не менее 56 баллов. Примеры Ввод Вывод Пояснение 8 1 2 2 1 2 1 1 1 2 Нужно выдать тому, кто находится у первой двери серебряный ключ, а тому, кто у последней — золотой. Далее нужно изменить тип первой и пятой двери, тогда последовательность дверей станет такой: 2, 2, 2, 1, 1, 1, 1, 1. После этого ключами можно будет открыть все двери. Можно показать, что быстрее, чем за две операции, справится не выйдет. 4 2 1 1 1 0 9 1 1 1 1 2 1 1 1 1 0

@AEHale -6 / 2 / 1 Регистрация: 06.10.2021 Сообщений: 24
	29.10.2021, 11:39 [ТС]
	помогите пжлст:3 0

@eaa Status 418 4584 / 2350 / 601 Регистрация: 26.11.2017 Сообщений: 5,262 Записей в блоге: 3
	29.10.2021, 11:58
	AEHale, чем помочь? 0

@AEHale -6 / 2 / 1 Регистрация: 06.10.2021 Сообщений: 24
	29.10.2021, 12:01 [ТС]
	именно вот эту я не представляю как решить 0