Перемещение карточек

@Jorka · Регистрация: 25.07.2020

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

Перед вами выложены n карточек слева направо. i-я слева карточка имеет цвет ci: ‘R’, если карточка красная, и ‘W’, если карточка белая.

Вы можете делать операции двух типов (любое количество раз, в любом порядке):

Выбрать любую карточку и поменять ее цвет (белый на красный, красный на белый)

Выбрать две (необязательно соседних) карточки и поменять их местами

Назовем ряд карточек некрасивым, если в нём есть красная карточка, идущая сразу после (правее) белой. Сколько минимум операций нужно совершить, чтобы ряд стал красивым?

Формат входных данных
На первой строке задано число n (1≤n≤2⋅10**5) — количество карточек. На второй строке задана строка из n символов ci (цвет i-й карточки), при этом ci может быть либо символом ‘R’, либо символом ‘W’.

Формат результата
Выведите одно число — минимальное количество операций, чтобы сделать ряд красивым.

Примеры
Входные данные
2
WR
Результат работы
1
Входные данные
2
WW
Результат работы
0
Входные данные
4
RWRW
Результат работы
1
Примечания
В первом примере можно поменять местами первую и вторую карточку, получим красивый ряд.

Во втором примере ничего менять не нужно, ряд и так красивый.

В третьем примере можно перекрасить вторую карточку.

Добавлено через 38 минут
Ну или идею если может кто?

@Folian · 24.08.2020, 11:10

del

@Jorka · 24.08.2020, 11:12 **[ТС]**

Folian, что del

@XLAT · 24.08.2020, 11:41

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

Ну или идею если может кто?

1. Пересчитать количество красных и белых карт.
2. Взять минимальное число из этих двух сумм.
3. Разделить на два.
4. Если есть остаток, то добавить к результату.

для приведённых пример такой алгоритм работает.

@Folian · 24.08.2020, 11:58

XLAT,

RRRWWW 0
RWRRWWR 1
RRRWWRRR 2

задачка нетривиальная маленько оказывается)

@Jorka · 24.08.2020, 12:00 **[ТС]**

XLAT, Это только для приведённых примеров, к сожалению.

@XLAT · 24.08.2020, 12:23

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

Это только для приведённых примеров, к сожалению.

вы привели тестовый стенд, моё решение ему удовлетворяет - требую приз.

@Folian · 24.08.2020, 12:48

А если так?

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
33
34
35
36
#include <iostream>
#include <vector>
#include <algorithm>
 
int main()
{
    //std::vector<bool> arr = { 0,1,0,0,1,1,0 };
    std::vector<bool> arr;
 
    bool x;
    while (std::cin >> x) arr.push_back(x);
 
    std::vector<bool> brr(arr);
 
    for (auto i : arr) std::cout << i << " ";
    std::cout << "\n";
 
    std::sort(brr.begin(), brr.end());
 
    for (auto i : brr) std::cout << i << " ";
    std::cout << "\n";
 
    int count = 0;
 
    for (size_t i = 0; i < arr.size(); ++i)
    {
        if (arr[i] != brr[i]) count++;
    }
 
    int result = count / 2 + count % 2;
 
    std::cout << result;
 
    system("pause");
    return 0;
}

вкратце это (XOR с отсортированной строкой)/2 + остаток

@XLAT · 24.08.2020, 12:58

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

А если так?

я автору сделал намёк, чтобы дал ссыль на тестовый стенд,
но он не хочет

@Jorka · 24.08.2020, 13:03 **[ТС]**

XLAT, ahaha, ты что девочка намёками общаться? я бы мог дать, но там надо регаться и быть школьником.

@Folian · 24.08.2020, 13:20

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

я автору сделал намёк, чтобы дал ссыль на тестовый стенд,
но он не хочет

да мне сама задача интересна стала

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

ты что девочка намёками общаться?

не хами

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

надо регаться и быть школьником.

информ~.мццме чтоль? Там паспорт не требуют, давай ссыль.

@zayats80888 · 24.08.2020, 13:25

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

вкратце это (XOR с отсортированной строкой)/2 + остаток

Мне кажется в лоб проще будет(O(n)).
Хотя возможно я что то не учёл.

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

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <iostream>
#include <vector>
 
int main()
{
    size_t n;
    std::cin >> n;
    std::vector<char> cards(n);
    (std::cin >> std::ws).read(cards.data(), n);
    const char* first = cards.data();
    const char* last = first + n - 1;
    size_t result = 0;
    for (; first < last; ++first, --last)
    {
        for (; *first == 'R' && first < last; ++first);
        for (; *last == 'W' && first < last; --last);
        if (first < last)
            ++result;
    }
    std::cout << result;
}

@XLAT · 24.08.2020, 13:28

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

ты что девочка намёками общаться?

ага, всё ясно, у тебя всё запущено:
как раз с девочками и не надо изъясняться намёками, иначе долго ждать придётся:
(вот тут тебе как раз я намекнул, потому что несильно то и хотелось)
всегда говорю им четко и прямо, что мне надо от них, пусть и не всегда получаю то что надо,
но зато экономлю время для этого форума.

потом,
задач у меня полно всяких разных других, нет стенда? а вот же примеры афтор не забыл,
но тогда вот и лови решение

@Jorka · 24.08.2020, 14:35 **[ТС]**

Folian, zayats80888, XLAT, задача расчитана на людей, кто только начал учить язык программирования, тут нет никаких подвохов, мне бы просто идею надо было, чтобы я написал, по какому принципу менять, а по какому принципу переставлять. И да, я говорил про то, что ты получается как девочка намёками общаешься, и это не чтобы задеть, а просто шутка.

Добавлено через 4 минуты
zayats80888, вот всё вроде верно, но я не пойму что написанно над циклом)

Добавлено через 3 минуты
да и в цикле что-то странное xDD

Добавлено через 9 минут
zayats80888, У тебя всё правильно написанно, можешь, пожалуйста объяснить что там ты сделал, потому что я ничего не понимаю, так странные звёздочки, data, read, циклы странные.

@zayats80888 · 24.08.2020, 14:48

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

потому что я ничего не понимаю

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

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

вот всё вроде верно

На самом деле там у меня UB, т.к. возможен декремент last, когда он указывает на первый элемент массива. Что бы исправить, нужно перенести iteration expression в тело цикла(в тело условия if (first < last))

C++
1
2
3
4
5
6
7
8
9
10
for (; first < last;)
{
    //...
    if (first < last)
    {
        ++result;
        ++first;
        --last;
    }
}

@Avazart · 24.08.2020, 14:58

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

C++
1
2
3
4
5
6
7
8
9
const char* first = cards.data();
 const char* last = first + n - 1;
 size_t result = 0;
 for (; first < last; ++first, --last)
 {
 for (; *first == 'R' && first < last; ++first);
 for (; *last == 'W' && first < last; --last);
 if (first < last)
 ++result;

}

У вектора есть итераторы.

@XLAT · 24.08.2020, 15:22

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

У тебя всё правильно написанно

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

На самом деле там у меня UB

поэтому я и не люблю посты с задачами с таск-трекеров без ссылок на эти задачи.

@XLAT · 24.08.2020, 15:43

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

RRRWWW 0
RWRRWWR 1
RRRWWRRR 2

не в лоб:

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <iostream>
#include <string>
 
void go(std::string s)
{   std::cout << s;
    int cnt = -1;
    for(int i = 0, j = s.size() -1; i < j; cnt++)
    {   i = s.find ("W", i);
        j = s.rfind("R", j);
        std::swap(s[i], s[j]);
    }
    std::cout << "  \t- "<< cnt << "\n";
}
 
int main()
{
    go("RRRWWW");
    go("RWRRWWR");
    go("RRRWWRRR");
}

Название: !1.jpg
Просмотров: 77

Размер: 5.4 Кб

@zayats80888 · 24.08.2020, 15:50

Не по теме:

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

У вектора есть итераторы.

Итераторы говнокод не преукрасят, а вектор там вместо new/delete, не более того :)

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

поэтому я и не люблю посты с задачами

Это ж мой косяк от лени и невнимательности. Я не стану так оправдывать философию "бах-бах и в продакшен!" :)

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

не в лоб

проверь для "WWW" или "RRR".

@XLAT · 24.08.2020, 16:00

знаю,
что должен быть подвох, так как при сборке механизма обнаружились ненужные детали:

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

Выбрать любую карточку и поменять ее цвет (белый на красный, красный на белый)

Добавлено через 5 минут

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

проверь для "WWW" или "RRR".

во, вы вовремя, теперь я знаю куда воткнуть ту "ненужную" деталь!

"RRR" проваливает, а значит нужна всего лишь одна операция по замене последнего R

ладно афтор пусть доделает))

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

Мне кажется в лоб проще будет(O(n)).

если за один проход, то это не в лоб или я не прав?

не важно какая там у нас аналитика, строку по любому нужно обойти минимум 1 раз!

Новые блоги и статьи Все статьи Все блоги /
Знаешь почему 90% людей редко бывают счастливыми? kumehtar 14.04.2026 Потому что они ждут. Ждут выходных, ждут отпуска, ждут удачного момента. . . а удачный момент так и не приходит.	Фиксация колонок в отчете СКД Maks 14.04.2026 Фиксация колонок в СКД отчета типа Таблица. Задача: зафиксировать три левых колонки в отчете. Процедура ПриКомпоновкеРезультата(ДокументРезультат, ДанныеРасшифровки, СтандартнаяОбработка) / / . . .	Настройки VS Code Loafer 13.04.2026 { "cmake. configureOnOpen": false, "diffEditor. ignoreTrimWhitespace": true, "editor. guides. bracketPairs": "active", "extensions. ignoreRecommendations": true, . . .	Оптимизация кода на разграничение прав доступа к элементам формы Maks 13.04.2026 Алгоритм из решения ниже реализован на нетиповом документе, разработанного в конфигурации КА2. Задачи, как таковой, поставлено не было, проделанное ниже исключительно моя инициатива. Было так:. . .
Контроль заполнения и очистка дат в зависимости от значения перечислений Maks 12.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "ПланированиеПерсонала", разработанного в конфигурации КА2. Задача: реализовать контроль корректности заполнения дат назначения. . .	Архитектура слоя интернета для сервера-слоя. Hrethgir 11.04.2026 В продолжение https:/ / www. cyberforum. ru/ blogs/ 223907/ 10860. html Знаешь что я подумал? Раз мы все источники пишем в голове ветки, то ничего не мешает добавить в голову такой источник, который сам. . .	Подстановка значения реквизита справочника в табличную часть документа Maks 10.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "ПланированиеПерсонала", разработанного в конфигурации КА2. Задача №1: при указании работ (справочник РаботыПоРемонтуСпецтехники),. . .	Очистка реквизитов документа при копировании Maks 09.04.2026 Алгоритм из решения ниже применим как для типовых, так и для нетиповых документов на самых различных конфигурациях. Задача: при копировании документа очищать определенные реквизиты и табличную. . .

@Jorka 11 / 10 / 5 Регистрация: 25.07.2020 Сообщений: 302

	Перемещение карточек 24.08.2020, 10:02. Показов 5817. Ответов 24 Метки нет (Все метки) Перед вами выложены n карточек слева направо. i-я слева карточка имеет цвет ci: ‘R’, если карточка красная, и ‘W’, если карточка белая. Вы можете делать операции двух типов (любое количество раз, в любом порядке): Выбрать любую карточку и поменять ее цвет (белый на красный, красный на белый) Выбрать две (необязательно соседних) карточки и поменять их местами Назовем ряд карточек некрасивым, если в нём есть красная карточка, идущая сразу после (правее) белой. Сколько минимум операций нужно совершить, чтобы ряд стал красивым? Формат входных данных На первой строке задано число n (1≤n≤2⋅10*5) — количество карточек. На второй строке задана строка из n символов ci (цвет i-й карточки), при этом ci может быть либо символом ‘R’, либо символом ‘W’. Формат результата Выведите одно число — минимальное количество операций, чтобы сделать ряд красивым. Примеры Входные данные 2 WR Результат работы 1 Входные данные 2 WW Результат работы 0 Входные данные 4 RWRW Результат работы 1 Примечания В первом примере можно поменять местами первую и вторую карточку, получим красивый ряд. Во втором примере ничего менять не нужно, ряд и так красивый. В третьем примере можно перекрасить вторую карточку. Добавлено через 38 минут* Ну или идею если может кто? 0

@Folian Гвоздь Задиров 1719 / 1118 / 337 Регистрация: 25.01.2019 Сообщений: 2,946
	24.08.2020, 11:10
	del 0

@Jorka 11 / 10 / 5 Регистрация: 25.07.2020 Сообщений: 302
	24.08.2020, 11:12 [ТС]
	Folian, что del 0

@Folian Гвоздь Задиров 1719 / 1118 / 337 Регистрация: 25.01.2019 Сообщений: 2,946
	24.08.2020, 11:58
	XLAT, RRRWWW 0 RWRRWWR 1 RRRWWRRR 2 задачка нетривиальная маленько оказывается) 0

@Jorka 11 / 10 / 5 Регистрация: 25.07.2020 Сообщений: 302
	24.08.2020, 12:00 [ТС]
	XLAT, Это только для приведённых примеров, к сожалению. 0

@Jorka 11 / 10 / 5 Регистрация: 25.07.2020 Сообщений: 302
	24.08.2020, 13:03 [ТС]
	XLAT, ahaha, ты что девочка намёками общаться? я бы мог дать, но там надо регаться и быть школьником. 0

@Jorka 11 / 10 / 5 Регистрация: 25.07.2020 Сообщений: 302
	24.08.2020, 14:35 [ТС]
	Folian, zayats80888, XLAT, задача расчитана на людей, кто только начал учить язык программирования, тут нет никаких подвохов, мне бы просто идею надо было, чтобы я написал, по какому принципу менять, а по какому принципу переставлять. И да, я говорил про то, что ты получается как девочка намёками общаешься, и это не чтобы задеть, а просто шутка. Добавлено через 4 минуты zayats80888, вот всё вроде верно, но я не пойму что написанно над циклом) Добавлено через 3 минуты да и в цикле что-то странное xDD Добавлено через 9 минут zayats80888, У тебя всё правильно написанно, можешь, пожалуйста объяснить что там ты сделал, потому что я ничего не понимаю, так странные звёздочки, data, read, циклы странные. 0