CF749C Voting

    • 7通过
    • 20提交
  • 题目来源 CodeForces 749C
  • 评测方式 RemoteJudge
  • 标签
  • 难度 提高+/省选-
  • 时空限制 1000ms / 256MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 体验新版界面

    最新讨论 显示

    推荐的相关题目 显示

    题意翻译

    给定一个字符串,字符串中字符为D或R,代表两个团队

    从1开始,每个人都有发言的权利,发言时,可以禁言一个人,使那个人以后都不能发言

    如果一圈发言完还有1个以上的人能发言,就从1重新开始,直到只有1个人能发言,那个人所在的团队获胜

    题目描述

    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.

    输入输出格式

    输入格式:

    The first line of the input contains a single integer $ n $ ( $ 1<=n<=200000 $ ) — 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.

    输出格式:

    Print 'D' if the outcome of the vote will be suitable for depublicans and 'R' if remocrats will win.

    输入输出样例

    输入样例#1: 复制
    5
    DDRRR
    
    输出样例#1: 复制
    D
    
    输入样例#2: 复制
    6
    DDRRRR
    
    输出样例#2: 复制
    R
    

    说明

    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.
    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。