TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  考试列表  判题结果  信息发布  解题排行
  • 首页
  • 题库
  • P6037
  • 题目
  • P6037【赏月的欢乐赛】白露暧空,素月流天
    限制 : 时间限制 : - MS   空间限制 : 262144 KB
    评测说明 : 1s,256MB
    问题描述

    腾腾的雾露,使天空朦朦胧胧的,而明月的光芒却仍然漫天照射。这句诗出自南北朝谢庄的《月赋》,抒发羁旅孤独、“怨遥”、“伤远”之感,思人怀归之情。

    nodgd在月光下通过玩翻硬币游戏来消磨羁旅孤独的情感。nodgd将$n$枚硬币排成一行,每一枚硬币可能是正面朝上或者反面朝上。nodgd设计了两种操作规则:假设当前有$k$枚硬币正面朝上,

    1. 如果$k>0$,就将从左到右的第$k$枚翻转一次,否则结束游戏;

    2. 如果$k<n$,就将从左到右的第$k+1$枚翻转一次,否则结束游戏。

    nodgd仔细研究发现,无论初始局面如何,一直使用其中某一种操作,都会在有限次翻转后结束游戏。nodgd觉得这个结论很有趣,还想进一步研究初始局面与翻转次数的关系,即任给一个初始局面,只用第$1$种操作或者只用第$2$种操作,分别需要翻转多少次才能结束游戏。但是nodgd赏月去了,顺手就把这道题放在了“赏月的欢乐赛”里面。

    输入格式

    输入一行,一个只包含$0$和$1$的字符串,表示从左到右的每一枚硬币的初始状态,$0$表示反面朝上,$1$表示正面朝上。

    输出格式

    输出一行,两个整数,分别是只用第$1$种操作和只用第$2$种操作,需要翻转多少次才能结束游戏。

    提示

    输入输出样例1

    样例输入
    000
    
    样例输出
    0 3
    
    样例说明

    如果只用第$1$种操作,直接结束游戏,翻转了$0$次;

    如果只用第$2$种操作,则000→100→110→111,然后结束游戏,翻转了$3$次。

    输入输出样例2

    样例输入
    0101
    
    样例输出
    8 8
    
    样例说明

    如果只用第$1$种操作,则0101→0001→1001→1101→1111→1110→1100→1000→0000,然后结束游戏,翻转了$8$次;

    如果只用第$2$种操作,则0101→0111→0110→0100→0000→1000→1100→1110→1111,然后结束游戏,翻转了$8$次。

    数据规模与约定

    设总共有$n$枚硬币;

    对于20%的数据,\(n\leq 20\)

    对于40%的数据,\(n\leq 2000\)

    对于70%的数据,\(n\leq 2\times10^5\)

    对于100%的数据,$1\leq n\leq 2\times10^6$。


    来源  感谢nodgd