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

@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 раз!

Новые блоги и статьи Все статьи Все блоги /
PhpStorm 2025.3: WSL Terminal всегда стартует в ~ and_y87 14.12.2025 PhpStorm 2025. 3: WSL Terminal всегда стартует в ~ (home), игнорируя директорию проекта Симптом: После обновления до PhpStorm 2025. 3 встроенный терминал WSL открывается в домашней директории. . .	Access VikBal 11.12.2025 Помогите пожалуйста !! Как объединить 2 одинаковые БД Access с разными данными.	Новый ноутбук volvo 07.12.2025 Всем привет. По скидке в "черную пятницу" взял себе новый ноутбук Lenovo ThinkBook 16 G7 на Амазоне: Ryzen 5 7533HS 64 Gb DDR5 1Tb NVMe 16" Full HD Display Win11 Pro	Музыка, написанная Искусственным Интеллектом volvo 04.12.2025 Всем привет. Некоторое время назад меня заинтересовало, что уже умеет ИИ в плане написания музыки для песен, и, собственно, исполнения этих самых песен. Стихов у нас много, уже вышли 4 книги, еще 3. . .	От async/await к виртуальным потокам в Python IndentationError 23.11.2025 Армин Ронахер поставил под сомнение async/ await. Создатель Flask заявляет: цветные функции - провал, виртуальные потоки - решение. Не threading-динозавры, а новое поколение лёгких потоков. Откат?. . .
Поиск "дружественных имён" СОМ портов Argus19 22.11.2025 Поиск "дружественных имён" СОМ портов На странице: https:/ / norseev. ru/ 2018/ 01/ 04/ comportlist_windows/ нашёл схожую тему. Там приведён код на С++, который показывает только имена СОМ портов, типа,. . .	Сколько Государство потратило денег на меня, обеспечивая инсулином. Programma_Boinc 20.11.2025 Сколько Государство потратило денег на меня, обеспечивая инсулином. Вот решила сделать интересный приблизительный подсчет, сколько государство потратило на меня денег на покупку инсулинов. . . .	Ломающие изменения в C#.NStar Alpha Etyuhibosecyu 20.11.2025 Уже можно не только тестировать, но и пользоваться C#. NStar - писать оконные приложения, содержащие надписи, кнопки, текстовые поля и даже изображения, например, моя игра "Три в ряд" написана на этом. . .	Мысли в слух kumehtar 18.11.2025 Кстати, совсем недавно имел разговор на тему медитаций с людьми. И обнаружил, что они вообще не понимают что такое медитация и зачем она нужна. Самые базовые вещи. Для них это - когда просто люди. . .	Создание Single Page Application на фреймах krapotkin 16.11.2025 Статья исключительно для начинающих. Подходы оригинальностью не блещут. В век Веб все очень привыкли к дизайну Single-Page-Application . Быстренько разберем подход "на фреймах". Мы делаем одну. . .

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

	Перемещение карточек 24.08.2020, 10:02. Показов 5710. Ответов 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 Гвоздь Задиров 1718 / 1117 / 337 Регистрация: 25.01.2019 Сообщений: 2,940
	24.08.2020, 11:10
	del 0

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

@Folian Гвоздь Задиров 1718 / 1117 / 337 Регистрация: 25.01.2019 Сообщений: 2,940
	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