#P2674. 宝藏岛
宝藏岛
题目背景
一群海盗找到了一个宝藏岛,岛上堆满了金币。海盗们决定按照一定的规则分配金币:每个人轮流拿金币,每次只能拿一堆中的一部分,但拿的数量不能超过当前堆的一半。海盗们都很聪明,都希望自己拿到的金币最多。作为船长,你需要帮助海盗们制定最佳的拿取策略。
题目描述
有n堆金币,每堆有a[i]个金币。两个人轮流拿,每次可以从任意一堆中拿取至少1个,最多不超过该堆当前数量的一半(向下取整)。无法拿取的人输。假设双方都采取最优策略,判断先手是否必胜。
输入格式
第一行一个整数n,表示堆数。 第二行n个整数a[i],表示每堆金币的数量。
输出格式
如果先手必胜,输出"First",否则输出"Second"。
样例
3
3 4 5
First
样例解释
先手可以从5的那堆拿2个,剩下3个,然后后手面对3,4,3的局面,最终先手胜。