Introduction
You and a friend are playing a game. Being a computer scientist, and hating to lose, you write a
program that will determine ahead of time whether you will win or not.
If you will not win, you will be a sore loser and refuse to play. If you will win, you will graciously agree to play
and beat your friend.
This is likely the last game you will be playing with your friend, but in the mean time, the game rules are as follows:
There are two players: A and B.
There are N coins initially.
Players take turns picking up coins from the pile. The number of coins that any player can pick in one turn can be one of the numbers in a specific set S = {S[1], S[2], ..., S[I], ..., S[K]}. In order for a player to select S[I] coins, atleast that many coins must be remaining.
Player A starts the game.
The winner is the player who is able topick up exactly all the remaining coins.
Write a program that given N and S will determine player A's strategy that will allow him to always win, regardless of what the other player does.
If there is a strategy that will guarentee A's victory, print the minumum number of coins A must select. Input Specifications
Your program will take from STDIN
A number N ≤ 100 representing the number of coins
A number K ≤ 5 representing the size of set S
This will be followed by K lines where line I contains the value S[I] (1 ≤ I ≤ K).
Output Specifications
Based on the input,
If A has a winning strategy, print out the minimum number A can choose with their first turn and still be assured victory.
If no guaranteed winning strategy is available for A, print out -1
Sample Input/Output Input
1 1 1
Output
1
Ex planation
Player A wins by going first and taking the only coin.
Input
2 1 1
Output
-1
Ex planation
Player A can only take 1 coin and player B will then take the second coin. It is not possible for player A to win.
Input
10 3 1 3 4
Output
1
Ex planation
A picks 1 (leaving 9 coins) If B picks 1 (leaving 8 coins)
Then A picks 1 (leaving 7 coins)
If B picks 1 (leaving 6 coins) - CASE A
Then A picks 4 (leaving 2 coins)
B has to pick 1 coin, leaving 1 - A wins
If B picks 3 (leaving 4 coins) - CASE B Then A picks all 4 coins - A wins
If B picks 4 (leaving 3 coins) Then A picks all 3 - A wins
If B picks 3 (leaving 6 coins)
This reduces to CASE A and A wins
If B picks 4 (leaving 5 coins)
Then A picks 3 (leaving 2 coins)
Then B must pick 1, leaving 1 - A wins
只需考虑先手必胜和先手必败的情况。
import java.util.*; public class CoinGame { public static int minCoinNum(int n, int[] A) { boolean[] f = new boolean[n+1]; int k = A.length; for(int i=0; i<k; i++) { if(A[i] > n) break; f[A[i]] = true; } for(int i=1; i<=n; i++) { for(int j=0; j<k; j++) { if(A[j] > i) break; f[i] = !f[i-A[j]]; if(f[i]) break; } } for(int j=0; j<k; j++) { if(A[j] > n) break; if(!f[n-A[j]]) return A[j]; } return -1; } public static void main(String[] args) { Scanner s = new Scanner(System.in); int n = s.nextInt(); int k = s.nextInt(); int[] A = new int[k]; for(int i=0; i<k; i++) { A[i] = s.nextInt(); } s.close(); Arrays.sort(A); System.out.println(minCoinNum(n, A)); } }
相关推荐
Bloomberg Businessweek - August 31, 2015 Bloomberg Businessweek - August 31, 2015 Bloomberg Businessweek - August 31, 2015
Bloomberg Businessweek - 202
Bloomberg Businessweek - 18.04.2022
Bloomberg Businessweek-2019-11-18.rar
Bloomberg Businessweek - 16.05.2022
Bloomberg Businessweek - 12.04.2021
Bloomberg Businessweek - 08.11.2021
Bloomberg Businessweek - 18.10.2021
Bloomberg Businessweek - 11.10.2021
Bloomberg Businessweek - 04.10.2021
Bloomberg Businessweek - 09.08.2021
名称:Bloomberg ---------------------------------------- 版本:1.4.0 作者:https://www.bloomberg.com/lens 分类:商业购物 ---------------------------------------- 概述:将彭博的力量带到任何地方的任何...
公开整理-Bloomberg-ESG-Disclosure数据集.xlsx
Bloomberg Businessweek-2019-11-18.pdf
Bloomberg Businessweek - 09.05.2022
无限的文章访问bloomberg.com 彭博解锁•在Bloomberg.com上无限数字访问•消除隐私烦恼。---------------------------------------------------------------- ------安装(Chrome扩展名)-个人电脑访问Chrome Web ...
Bloomberg Businessweek Europe - 05.07.2021
Bloomberg Businessweek Europe - 21.06.2021
Reproducible-Research-Johns-Hopkins-Bloomberg-School-of-Public-Health-Coursera 可重复研究 Coursera 课程的笔记和测验答案
支持的工具:-CHelper-JHelper-Hightail-Mind Sport-Caide-acmX问题解析器可用于以下网站:-A2OJ-ACMP-AtCoder-Baekjoon在线法官-Bloomberg CodeCon-CodeChef-Codeforces-COJ-CSAcademy-CSU-ACM在线法官-DevSkill-...