Главная
Библиотека
Управление персоналом
Вася и Маша организовали производство бирдекелей. Они договорились работать день через день, при этом Вася любит простую и...

Вася и Маша организовали производство бирдекелей. Они договорились работать день через день, при этом Вася любит простую и понятную работу, а Маша — сложную и творческую. В первый день работает Вася, во второй — Маша, потом снова Вася и т.д. К ним

«Вася и Маша организовали производство бирдекелей. Они договорились работать день через день, при этом Вася любит простую и понятную работу, а Маша — сложную и творческую. В первый день работает Вася, во второй — Маша, потом снова Вася и т.д. К ним»

8 октября 2025
Управление персоналом

Условие:

Распределение задач*
Ограничение времени 1 секунда
Ограничение памяти 256 Мб
Ввод стандартный ввод
Вывод стандартный вывод
Вася и Маша организовали производство бирдекелей. Они договорились работать день через день, при этом Вася любит простую и понятную работу, а Маша — сложную и творческую. В первый день работает Вася, во второй — Маша, потом снова Вася и т.д.

К ним поступило
N
N заказов, для каждого заказа известна его продолжительность в днях и для каждого из дней известно, будет ли в этот день работа сложной или простой. Заказы можно выполнять в любом порядке, перерывов между заказами нет.

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

Формат ввода
В первой строке задается число
N
N (
1
≤
N
≤
100
000
1≤N≤100000) — количество заказов.

В следующих
N
N строках описываются заказы. Каждое описание представляет собой строку, состоящую из символов
S
S и
D
D, обозначающих, соответственно, простую и сложную работу в этот день. Длина строки не превосходит 100 символов. Суммарная длина всех строк не превосходит
1
000
000
1000000 символов.

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

Пример
Ввод Вывод
4
DSD
SS
DD
SDD
3
Примечания
Наибольшее количество дней с простой работой достается Васе при выполнении работ в порядке SDD, SS, DD, DSD

Решение:

Для решения задачи мы будем использовать жадный алгоритм. Основная идея заключается в том, чтобы максимизировать количество простых задач, выполняемых Васей, при этом учитывая, что он работает в нечетные дни, а Маша — в четные. ### Шаг 1: Понимание задачи Вася работает в нечетные дни (1-й, 3-й, 5-й и т.д.), а Маша — в четные (2-й, 4-й, 6-й и т.д.). Мы должны определить порядок выполнения заказов, чтобы Вася получил максимальное количество простых задач. ### Шаг 2: Анализ заказов Каждый заказ имеет определенную продолжительность в днях и может быть простым (S) или сложным (D). Мы должны учиты...