oj mrJudge
Toggle navigation
  • Login
    • Forget Password
      Login
User Image

Hello, Stranger

Guest
  • Analysis Mode
  • Problems
    • All Problems
    • Latest Problems
  • Join Us Now
  • Registration
  • Contact Us
  • Infomation
  • About
    • Terms of Use
    • Technical Specifications
    • Credits

easy Batch , stdin/stdout

Registered Users Only

Please login to utilize this feature.

Do note that this website only supports submissions in C++.

problem.html

There are N types of boxes, each with a given size that is a positive integer; the greatest size is H, and the sizes are distinct. The function A(n) is defined to be the least number of those boxes to hold n units of stuff without any leftover space; that is, their sizes have to add up to n. (Each type can be used any number of times. A(n) is undefined if this is impossible.)

If n is an element of a set S, n is called "relatively easy to make among S" if and only if A(n) is defined and there do not exist a and b in S such that a < n < b, A(a) and A(b) are defined, and A(n) ≥ ((b-n)A(a)+(n-a)A(b))/(b-a).

For a given positive integer ≤ T, find the greatest number that is relatively easy to make among the set of nonnegative numbers of the form kH+T, possibly up to a certain limit, where k is an integer. If present, the limit is greater than T.

Here's a hint: A related problem was discussed earlier in this training. The corresponding slides are attached. This may be useful.

Input

The first line contains the two integers N and T in that order, followed by the aforementioned limit if there is one, or 0 if there is no limit. The second line contains the N box sizes in descending order.

Output

The output should contain a single integer, the answer as described in the third paragraph; if no such number exists, the output should be empty.

Subtasks

#1 (10 points): N ≤ 8; H < 32; T < 64; the limit is present and less than 128.
#2 (15 points): N ≤ 128; H < 2048; 4294967296 ≤ T < 256; the limit is not present.
#3 (15 points): N ≤ 512; H < 32768; 4294967296 ≤ T < 256; the limit is not present.
#4 (60 points): N ≤ 16; H < 8192; T < 256; the limit is not present.

Sample Test Case

Input

3 9 20
6 2 1

Output

3

Explanation

The set under consideration contains 3, 9, and 15. A(3) = 2 (1 and 2), A(9) = 3 (1, 2, and 6), and A(15) = 4 (1, 2, 6, and 6). 9 is not relatively easy to make among this set because A(9) ≥ ((15-9)A(3)+(9-3)A(15))/(15-3), but 3 is.

Tags

Subtasks and Limits

Subtask Score #TC Time Memory Scoring
11081s64MBMinimum
21581s64MBMinimum
31581s64MBMinimum
460121s64MBMinimum
5011s64MBMinimum

Judge Compile Command

g++-8 ans.cpp -o easy -Wall -Wshadow -static -O2 -lm -m64 -s -w -std=gnu++17 -fmax-errors=512

Accepted Submissions

subIDUserTimeMax Time

Past Submissions

subIDUserTimeScore
mrJudge 09.05.20
Copyright © 2020 mrJudge. All rights reserved.