피터는 분자(molecule)를 판별하는 기계를 만드는 회사에서 일한다.

각 분자의 무게는 양의 정수이다.

이 기계에는 판별 범위 [l, u]라는 것이 있다(단, l과 u는 양의 정수).

기계가 분자들의 집합을 판별할 수 있는 경우는, 이 집합이 다음과 같은 부분집합을 갖는 경우와 같다: 부분집합에 속하는 분자들의 총 무게가 이 기계의 판별 범위에 속한다.

다시 말해서, n개의 분자가 주어지고 이 분자들의 무게는 w₀, ..., w_n-1이라고 가정하자.

이때 l ≤ w_i1 + ... + w_im ≤ u 를 만족하는 서로 다른 인덱스들의 집합 I = {i₁, ..., i_m} 가 존재한다면 판별은 성공이다.

기계의 명세에 따르면, l과 u의 차이는 가장 무거운 분자와 가장 가벼운 분자의 무게 차이보다 크거나 같다는 것이 보장된다.

즉, w_max = max(w₀, ..., w_n-1) 와 w_min = min(w₀, ..., w_n-1) 에 대해 u - l ≥ w_max - w_min 이다.

여러분은 판별 범위에 속하는 총 무게를 갖는 임의의 부분집합을 찾거나 또는 그런 부분집합이 없음을 판단하는 프로그램을 작성하면 된다.

Detecting Molecules timer 1초 memory 64MB

Detecting Molecules 1초 64MB