Add number

時(shí)間限制(普通/Java):1000MS/3000MS 運(yùn)行內(nèi)存限制:65536KByte
總提交: 60 測(cè)試通過(guò): 21

描述

?

Employees of Baidu like to play a game called Making Numbers. It goes like this: there are two players in the game, one is called little A, the other little B. There are some cards with a number on each one of them, little A chooses a number X from 1 to N randomly, while little B has to choose some cards, the sum of which equals X. Now there are already M cards with numbers, and K blank cards. At the beginning of the game, little B is allowed to write numbers on the blank cards. Now little B wants to know, if it is possible to write some numbers that will assure him of the victory, that is to say, if it is possible for him to make up any number from 1 to N with the cards.

?

輸入

?

The input consists of several test cases. The first line is an integer T,

The first line of each case shows 3 numbers, N M K, the next line follows M numbers that are already written on M cards. 1<=N<=99999999,0<=M<=19,1<=K<=19 and the numbers on M cards are above 0, smaller than or equals N, in non-descending order.

?

輸出

?

If little B can make it, output "YES", else output "NO".

?

樣例輸入

?

3 15 0 412 3 2 3 3 3 13 3 2 3 3 3

?

樣例輸出

?

YES YES NO

?

題目來(lái)源

第四屆北京郵電大學(xué)程序設(shè)計(jì)競(jìng)賽 2010

?

1 #include <stdio.h> 2 int main() 3 { 4 int T; 5 scanf("%d", &T); 6 while(T--){ 7 int n, m, k; 8 scanf("%d %d %d", &n, &m, &k); 9 int a[100]; 10 for(int i = 0; i < m; i++){ 11 scanf("%d", a+i); 12 } 13 int sum = 0; 14 int tmp = 1; 15 while(sum < n && k >= 0){ 16 bool flag = false; 17 for(int i = 0; i < m; i++){ 18 if(a[i] && a[i] <= tmp){ 19 sum += a[i]; 20 a[i] = 0; 21 flag = true; 22 } 23 } 24 if(!flag){ 25 sum += tmp; 26 k--; 27 } 28 tmp = sum + 1; 29 } 30 if(k >= 0 && sum >= n){ 31 puts("YES"); 32 } 33 else{ 34 puts("NO"); 35 } 36 } 37 return 0; 38 }

?

轉(zhuǎn)載于:https://www.cnblogs.com/luotinghao/p/3411224.html

總結(jié)

以上是生活随笔為你收集整理的toj 3616 Add number (没想到啊~~)的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。