P1247 取火柴游戏

    • 131通过
    • 309提交
  • 题目提供者
  • 评测方式 云端评测
  • 标签 博弈论
  • 难度 普及/提高-
  • 时空限制 1000ms / 128MB

题解

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

    推荐的相关题目 显示

    题目描述

    输入k及k个整数n1,n2,…,nk,表示有k堆火柴棒,第i堆火柴棒的根数为ni;接着便是你和计算机取火柴棒的对弈游戏。取的规则如下:每次可以从一堆中取走若干根火柴,也可以一堆全部取走,但不允许跨堆取,也不允许不取。

    谁取走最后一根火柴为胜利者。

    例如:k=2,n1=n2=2,A代表你,P代表计算机,若决定A先取:

    A:(2,2)→(1,2) {从一堆中取一根}

    P:(1,2)→(1,1) {从另一堆中取一根}

    A:(1,1)→(1,0)

    P:(1,0)→ (0,0) {P胜利}

    如果决定A后取:

    P:(2,2)→(2,0)

    A:(2,0)→ 0,0) {A胜利}

    又如k=3,n1=1,n2=2,n3=3,A决定后取:

    P:(1,2,3)→(0,2,3)

    A:(0,2,3)→(0,2,2)

    A已将游戏归结为(2,2)的情况,不管P如何取A都必胜。

    编一个程序,在给出初始状态之后,判断是先取必胜还是先取必败,如果是先取必胜,请输出第一次该如何取。如果是先取必败,则输出“lose”。

    输入输出格式

    输入格式:

    第一行,一个正整数k

    第二行,k个整数n1,n2,…,nk

    输出格式:

    如果是先取必胜,请在第一行输出两个整数a,b,表示第一次从第b堆取出a个。第二行为第一次取火柴后的状态。如果有多种答案,则输出<b,a>字典序最小的答案(即b最小的前提下a最小)。

    如果是先取必败,则输出“lose”。

    输入输出样例

    输入样例#1: 复制
    3
    3 6 9
    
    输出样例#1: 复制
    4 3
    3 6 5
    
    输入样例#2: 复制
    4
    15 22 19 10
    输出样例#2: 复制
    lose

    说明

    k<=500000

    ni<=1e9

    时限2s

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