Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
Statistical Charts
Submit Problem
Online Status
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Knapsack I
Time Limit: 1000MSMemory Limit: 131072K
Total Submissions: 1094Accepted: 325


Lambert wants to carry several kinds of items with a knapsack. Items of each kind have integral size and infinite supply. The knapsack also has an integral capacity. Due to some esoteric reasons, an item of any kind can be divided evenly into a fixed number of identical parts. The resulting parts can again be divided, and the process of even division can go on endlessly. Given n kinds of items, can the capacity of the knapsack be fulfilled?


The input contains multiple test cases. Each test case begins with a line containing three positive integers n, x and k (n ≤ 1000, k ≥ 2), where x is the capacity of the knapsack, and k means each division divides an item or a divided part into k identical smaller parts. Then comes a line containing n positive integers, the sizes of different kinds of items.


For each test case, output one line containing “Yes” if the knapsack can be fulfilled or “No” otherwise.

Sample Input

2 3 5
4 11
3 16 2
3 6 9

Sample Output



[Submit]   [Go Back]   [Status]   [Discuss]

Home Page   Go Back  To top

All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator