P2565 [SCOI2009]骰子的学问

    • 11通过
    • 51提交
  • 题目提供者
  • 评测方式 云端评测
  • 标签 搜索 置换 贪心 各省省选 2009 四川 Special Judge
  • 难度 尚无评定
  • 时空限制 1000ms / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 最新讨论 显示

    推荐的相关题目 显示

    题目描述

    小鱼儿是个数学天才。一天晚上他研究一个和字符串有关的penney-ante游戏。游戏的规则如下:

    1.有两个玩家,开始时每人选择一个长度相同的字符串;

    2.一个字符生成器不断的随机生成字母添加到字符串S的末尾,S初始为空串;

    3.如果S包含了某个玩家选择的字符串则游戏结束,该玩家获胜。

    假设玩家1和玩家2分别选择了两个字符串A和B,如果玩家1可以以较大概率战胜玩家2,我们记作A>B。 咋一看来,小鱼儿觉得如果A>B且B>C则A>C。可事实恰好相反,存在字符串A, B, C使得A>B, B>C, C>A。

    小鱼儿被这种戏的一个反常现象所吸引,通过查阅资料,他了解到这种现象被称为“非传递性悖论”,在许多非完全信息游戏(比如军棋)中,经常会有这样的例子。可是它到底是如何产生的呢?小鱼儿决定设计一种游戏,从中可以容易的找到非传递的例子,以便更清楚的认识“非传递性”。当然,这样的游戏越简单道理越深刻,于是小鱼儿想起了最简单的掷骰子游戏……

    这个游戏是这样的,假设有n个骰子D1~Dn,每个骰子有m个面。每个面上标有一个1~n×m的正整数,并且所有骰子的所有n×m个面上的数字各不相同。满足这条编号要求,并且每个面被随到的概率相等的,这样的n个骰子称为一组“好骰子”。游戏开始时,两个玩家分别选两个骰子Di和Dj,各掷一次来比较掷出来那一面的数值,数大的获胜。

    小鱼儿请你帮忙设计一组“好骰子”,使得对任意一个骰子Di,它总能战胜Dai。此处战胜是指选择前者的玩家获胜的概率超过1/2;a1~an为输入的1~n的正整数。

    输入输出格式

    输入格式:

    第一行为两个整数n, m。第二行有n个整数,为a1,a2, …, an。

    输出格式:

    包含n行,每行m个1~n×m的正整数,各不相同,以空格分开。

    如果有多解,输出任意一组解;如果无解,输出一个整数0。

    输入输出样例

    输入样例#1: 复制
    3 4
    2 1 2
    
    输出样例#1: 复制
    0

    说明

    30%的数据满足n, m≤10

    100%的数据满足3≤n, m≤200

    感谢 @cn:苏卿念 提供spj

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