TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  考试列表  判题结果  问题讨论与解答  统计信息与排名
  • 首页
  • 题库
  • P1578
  • 题目
  • P1578【Usaco Dec07 Brone】作弊的发牌者
    限制 : 时间限制 : 10000 MS   空间限制 : 65536 KB
    问题描述

    贝茜正在与她的N-1(2 <= N <= 100)个朋友打牌。她们玩的牌一副为K(N <= K <= 100,000,K为N的倍数)张。所有牌中,一共有M(M = K / N)张“好牌”,其余的K - M张为“差牌”。贝茜是游戏的发牌者,很自然地,她想把所有好牌都留给自己。她热衷于获胜,即使为此必须采取一些不正当的手段。

    在若干局游戏后,贝茜的朋友们开始怀疑贝茜在游戏中作弊,于是她们想了
    个对策:使用新的发牌规则。规则具体如下:

    1. 贝茜把牌堆的最上面一张发给她右边的奶牛

    2. 每当贝茜发完一张牌,她都得将牌堆顶部接下来的P(1 <= P <= 10)张牌
    放到底部去(一般把这个操作称为切牌)

    3. 然后,贝茜对逆时针方向的下一头奶牛重复上述的操作

    贝茜绝望地认为,她再也不可能获胜了,于是她找到了你,希望你告诉她,将好牌放在初始牌堆的哪些位置,能够确保它们在发完牌后全集中到她手里。顺带说明一下,我们把牌堆顶的牌定义为1号牌,从上往下第二张定义为2号牌,依此类推。

    输入格式

    * 第1行: 3个用空格隔开的整数:N、K,以及P

    输出格式

    * 第1..M行: 每行输出一个正整数,表示贝茜应该在初始牌堆的这个位置放一张好牌。所有的位置按升序输出。

    样例输入

    3 9 2

    样例输出

    3
    7
    8

    提示

    输入说明:

    贝茜和她的某两个朋友在打一副总共是9张的牌。她每发出一张牌后,都得
    在牌堆顶部取出两张放到堆底。


    输出说明:

    贝茜选择在牌堆中初始位置3、7、8各放一张好牌,这样她能在发完牌后如
    愿以偿地拿到所有的好牌。以下是对这场游戏的模拟,牌堆中的数字代表这张牌
    在初始牌堆中的位置:
    牌堆 奶牛1 奶牛2 贝茜
    初始状态 1 2 3 4 5 6 7 8 9 - - - - - - - - -
    将牌堆顶的牌[1号牌]发给奶牛1 2 3 4 5 6 7 8 9 1 - - - - - - - -
    切牌(#1 of 2) 3 4 5 6 7 8 9 2 1 - - - - - - - -
    切牌(#2 of 2) 4 5 6 7 8 9 2 3 1 - - - - - - - -
    将牌堆顶的牌[4号牌]发给奶牛2 5 6 7 8 9 2 3 1 - - 4 - - - - -
    切牌(#1 of 2) 6 7 8 9 2 3 5 1 - - 4 - - - - -
    切牌(#2 of 2) 7 8 9 2 3 5 6 1 - - 4 - - - - -
    将牌堆顶的牌[7号牌]发给贝茜 8 9 2 3 5 6 1 - - 4 - - 7 - -
    切牌(#1 of 2) 9 2 3 5 6 8 1 - - 4 - - 7 - -
    切牌(#2 of 2) 2 3 5 6 8 9 1 - - 4 - - 7 - -
    将牌堆顶的牌[2号牌]发给奶牛1 3 5 6 8 9 1 2 - 4 - - 7 - -
    切牌(#1 of 2) 5 6 8 9 3 1 2 - 4 - - 7 - -
    切牌(#2 of 2) 6 8 9 3 5 1 2 - 4 - - 7 - -
    将牌堆顶的牌[6号牌]发给奶牛2 8 9 3 5 1 2 - 4 6 - 7 - -
    切牌(#1 of 2) 9 3 5 8 1 2 - 4 6 - 7 - -
    切牌(#2 of 2) 3 5 8 9 1 2 - 4 6 - 7 - -
    将牌堆顶的牌[3号牌]发给贝茜 5 8 9 1 2 - 4 6 - 7 3 -
    切牌(#1 of 2) 8 9 5 1 2 - 4 6 - 7 3 -
    切牌(#2 of 2) 9 5 8 1 2 - 4 6 - 7 3 -
    将牌堆顶的牌[9号牌]发给奶牛1 5 8 1 2 9 4 6 - 7 3 -
    切牌(#1 of 2) 8 5 1 2 9 4 6 - 7 3 -
    切牌(#2 of 2) 5 8 1 2 9 4 6 - 7 3 -
    将牌堆顶的牌[5号牌]发给奶牛2 8 1 2 9 4 6 5 7 3 -
    切牌(#1 of 2) 8 1 2 9 4 6 5 7 3 -
    切牌(#2 of 2) 8 1 2 9 4 6 5 7 3 -
    将牌堆顶的牌[8号牌]发给贝茜 - 1 2 9 4 6 5 7 3 8

    发牌结束后,贝茜拿到了牌堆中初始位置分别为3、7、8的牌。


    来源  Usaco Dec07 Brone