암호문
시간 제한2초메모리 제한128 MB
최대 40개의 양의 정수와 목표값 K가 주어질 때, 합이 K가 되는 부분집합을 비트 문자열로 찾아야 합니다.
문제
길이가 n인 이진 암호문을 찾아야 한다. 암호문은 순서대로 t1, t2, ..., tn으로 이루어져 있으며, 각 ti는 0 또는 1이다.
양의 정수 a1, a2, ..., an과 암호화된 값 K가 주어진다. 이 값들은 다음 식을 만족한다.
K = a1t1 + a2t2 + ... + antn
조건을 만족하는 n비트 이진 문자열을 구하라.
입력
첫째 줄에 비트 수 n (5 <= n <= 40)이 주어진다.
둘째 줄부터 n개의 줄에 a1, a2, ..., an이 순서대로 한 줄에 하나씩 주어진다.
마지막 줄에는 K가 주어진다. 모든 ai는 자연수이며, n개의 수 전체의 합은 2,000,000,000을 넘지 않는다.
출력
조건을 만족하는 n비트 이진 문자열을 출력한다. 답이 여러 개라면 그중 하나만 출력한다.