C. Voting

Codeforces

IDCF749C

Time1000ms

Memory256MB

Difficulty—

greedyimplementationtwo pointers

English · Original

Chinese · Translation

Formal · Original

There are _n_ employees in Alternative Cake Manufacturing (ACM). They are now voting on some very important question and the leading world media are trying to predict the outcome of the vote. Each of the employees belongs to one of two fractions: depublicans or remocrats, and these two fractions have opposite opinions on what should be the outcome of the vote. The voting procedure is rather complicated: 1. Each of _n_ employees makes a statement. They make statements one by one starting from employees 1 and finishing with employee _n_. If at the moment when it's time for the _i_\-th employee to make a statement he no longer has the right to vote, he just skips his turn (and no longer takes part in this voting). 2. When employee makes a statement, he can do nothing or declare that one of the other employees no longer has a right to vote. It's allowed to deny from voting people who already made the statement or people who are only waiting to do so. If someone is denied from voting he no longer participates in the voting till the very end. 3. When all employees are done with their statements, the procedure repeats: again, each employees starting from 1 and finishing with _n_ who are still eligible to vote make their statements. 4. The process repeats until there is only one employee eligible to vote remaining and he determines the outcome of the whole voting. Of course, he votes for the decision suitable for his fraction. You know the order employees are going to vote and that they behave optimal (and they also know the order and who belongs to which fraction). Predict the outcome of the vote. ## Input The first line of the input contains a single integer _n_ (1 ≤ _n_ ≤ 200 000) — the number of employees. The next line contains _n_ characters. The _i_\-th character is '_D_' if the _i_\-th employee is from depublicans fraction or '_R_' if he is from remocrats. ## Output Print '_D_' if the outcome of the vote will be suitable for depublicans and '_R_' if remocrats will win. [samples] ## Note Consider one of the voting scenarios for the first sample: 1. Employee 1 denies employee 5 to vote. 2. Employee 2 denies employee 3 to vote. 3. Employee 3 has no right to vote and skips his turn (he was denied by employee 2). 4. Employee 4 denies employee 2 to vote. 5. Employee 5 has no right to vote and skips his turn (he was denied by employee 1). 6. Employee 1 denies employee 4. 7. Only employee 1 now has the right to vote so the voting ends with the victory of depublicans.

Alternative Cake Manufacturing（ACM）公司有 #cf_span[n] 名员工。他们正在对一个非常重要的问题进行投票，全球主流媒体正试图预测投票结果。每位员工属于两个派系之一：depublicans 或 remocrats，这两个派系对投票结果持有对立观点。投票程序相当复杂：你已知员工投票的顺序，并且他们都会采取最优策略（他们也知晓投票顺序以及每个人所属的派系）。请预测投票结果。输入的第一行包含一个整数 #cf_span[n]（#cf_span[1 ≤ n ≤ 200 000]）—— 员工人数。第二行包含 #cf_span[n] 个字符。第 #cf_span[i] 个字符为 '_D_' 表示第 #cf_span[i] 名员工属于 depublicans 派系，或为 '_R_' 表示属于 remocrats 派系。如果投票结果有利于 depublicans，则输出 '_D_'；如果 remocrats 获胜，则输出 '_R_'。考虑第一个样例的一种投票场景： ## Input 输入的第一行包含一个整数 #cf_span[n]（#cf_span[1 ≤ n ≤ 200 000]）—— 员工人数。第二行包含 #cf_span[n] 个字符。第 #cf_span[i] 个字符为 '_D_' 表示第 #cf_span[i] 名员工属于 depublicans 派系，或为 '_R_' 表示属于 remocrats 派系。 ## Output 如果投票结果有利于 depublicans，则输出 '_D_'；如果 remocrats 获胜，则输出 '_R_'。 [samples] ## Note 考虑第一个样例的一种投票场景：员工 #cf_span[1] 禁止员工 #cf_span[5] 投票。员工 #cf_span[2] 禁止员工 #cf_span[3] 投票。员工 #cf_span[3] 无投票权，跳过本轮（被员工 #cf_span[2] 禁止）。员工 #cf_span[4] 禁止员工 #cf_span[2] 投票。员工 #cf_span[5] 无投票权，跳过本轮（被员工 #cf_span[1] 禁止）。员工 #cf_span[1] 禁止员工 #cf_span[4]。此时仅有员工 #cf_span[1] 拥有投票权，投票结束，depublicans 获胜。

**Definitions** Let $ n \in \mathbb{Z} $, $ 1 \leq n \leq 200{,}000 $, be the number of employees. Let $ S = (s_1, s_2, \dots, s_n) $ be a sequence over $ \{D, R\} $, where $ s_i $ denotes the fraction of the $ i $-th employee in voting order. **Constraints** Each $ s_i \in \{D, R\} $. **Objective** Simulate a sequential voting game where, in each round, the current voter eliminates the next opposing voter (in circular order), and voting continues until one fraction remains. All players act optimally, knowing the full sequence and each other's affiliations. Output the surviving fraction: $ D $ if depublicans win, $ R $ if remocrats win.

Samples

Input #1

5
DDRRR

Output #1

Input #2

6
DDRRRR

Output #2

API Response (JSON)

{
  "problem": {
    "name": "C. Voting",
    "description": {
      "content": "There are _n_ employees in Alternative Cake Manufacturing (ACM). They are now voting on some very important question and the leading world media are trying to predict the outcome of the vote. Each of",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF749C"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "There are _n_ employees in Alternative Cake Manufacturing (ACM). They are now voting on some very important question and the leading world media are trying to predict the outcome of the vote.\n\nEach of...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "Alternative Cake Manufacturing（ACM）公司有 #cf_span[n] 名员工。他们正在对一个非常重要的问题进行投票，全球主流媒体正试图预测投票结果。\n\n每位员工属于两个派系之一：depublicans 或 remocrats，这两个派系对投票结果持有对立观点。投票程序相当复杂：\n\n你已知员工投票的顺序，并且他们都会采取最优策略（他们也知晓投票顺序以及每个人所属的派系...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n \\in \\mathbb{Z} $, $ 1 \\leq n \\leq 200{,}000 $, be the number of employees.  \nLet $ S = (s_1, s_2, \\dots, s_n) $ be a sequence over $ \\{D, R\\} $, where $ s_i $ denotes the fra...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments