蓝桥杯——盾神与格子游戏(动态规划+递推)

资源限制

内存限制:256.0MB   C/C++时间限制:1.0s   Java时间限制:3.0s   Python时间限制:5.0s

问题描述

  在盾神很小很小还不会怎样编程的时候,他迷上了一款风靡一时的双人游戏!游戏双方在地上画n个格子,然后在最后一格放上一颗石头。每人每轮可以把石头向前移动1到3格,最后谁把石头移出第一格就赢了。盾神那时候很傻很天真,每次都是随便乱玩,结果每次都会输。。。
  盾神今天回想起来,那时候的自己真是弱暴了!!!今天的盾神不仅一眼把这个游戏的必胜方法秒解,还提出了一个进化版:每人每轮不是把石头向前移动1到3格那么简单,而是有m种选择:第i种可以向前移动ai格。其他规则还是和以前一样。那么聪明的你,能告诉盾神,如果双方都采取最优策略,先手第一步该怎样做才可以保证必胜?

输入格式

  第一行为两个数n,m。
  第二行m个数,表示ai。

输出格式

  如果先手必败,输出“poor dun”,否则输出先手第一步应该向前移动多少格,如果有多种方案,选择移动距离最少的那个。

样例输入

6 3
1 10 100

样例输出

10

样例输入

6 3
1 2 3

样例输出

2

样例输入

6 3
1 1 1

样例输出

poor dun

数据规模和约定

  对于20%的数据,ai为从1到

版权声明:本文为博主作者:又阔乐辣原创文章,版权归属原作者,如果侵权,请联系我们删除!

原文链接:https://blog.csdn.net/m0_73581472/article/details/136891698

共计人评分,平均

到目前为止还没有投票!成为第一位评论此文章。

(0)
青葱年少的头像青葱年少普通用户
上一篇 2024年4月1日
下一篇 2024年4月1日

相关推荐