아직 만들고 있는 페이지입니다.

이 페이지는 아직 만드는 중입니다. 보이는 내용은 바뀔 수 있습니다.

Detecting Molecules

시간 제한1초메모리 제한512 MB

요약
분자 무게들과 무게 폭보다 넓은 탐지 범위가 주어질 때, 합이 범위에 들어가는 부분집합을 찾거나 없다고 판정한다.
난이도

보통10점 중 6점

유형
그리디, 정렬
정답자
아직 제출이 없습니다

문제

Petr is working for a company that has built a machine for detecting molecules. Each molecule has a positive integer weight. The machine has a detection range [l, u], where l and u are positive integers. The machine can detect a set of molecules if and only if this set contains a subset of the molecules with total weight belonging to the machine's detection range.

Formally, consider n molecules with weights w0 ..., w**n-1. The detection is successful if there is a set of distinct indices I = {i1, ..., im} such that l ≤ wi1 + ... +wim ≤ u.

Due to specifics of the machine, the gap between l and u is guaranteed to be greater than or equal to the weight gap between the heaviest and the lightest molecule. Formally, u - l ≥ wmax - wmin, where wmax = max(w0, ..., w**n-1) and wmin = min(w0, ..., w**n-1).

Your task is to write a program which either finds any one subset of molecules with total weight within the detection range, or determines that there is no such subset.

예제

이 문제는 공개된 예제가 없습니다.