P4301 [CQOI2013]新Nim游戏

    • 271通过
    • 495提交
  • 题目提供者 kkksc03 吉祥物
  • 评测方式 云端评测
  • 标签 构造 线性基 贪心 各省省选 2013 重庆
  • 难度 省选/NOI-
  • 时空限制 1000ms / 128MB

题解

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

    推荐的相关题目 显示

    题目描述

    传统的Nim游戏是这样的:有一些火柴堆,每堆都有若干根火柴(不同堆的火柴数量可以不同)。两个游戏者轮流操作,每次可以选一个火柴堆拿走若干根火柴。可以只拿一根,也可以拿走整堆火柴,但不能同时从超过一堆火柴中拿。拿走最后一根火柴的游戏者胜利。

    本题的游戏稍微有些不同:在第一个回合中,第一个游戏者可以直接拿走若干个整堆的火柴。可以一堆都不拿,但不可以全部拿走。第二回合也一样,第二个游戏者也有这样一次机会。从第三个回合(又轮到第一个游戏者)开始,规则和Nim游戏一样。

    如果你先拿,怎样才能保证获胜?如果可以获胜的话,还要让第一回合拿的火柴总数尽量小。

    输入输出格式

    输入格式:

    第一行为整数k。即火柴堆数。

    第二行包含k个不超过10^9的正整数,即各堆的火柴个数。

    输出格式:

    输出第一回合拿的火柴数目的最小值。如果不能保证取胜,输出-1。

    输入输出样例

    输入样例#1: 复制
    6
    5 5 6 6 5 5
    输出样例#1: 复制
    21

    说明

    k<=100

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