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

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

지폐 자르기

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

요약
센트 단위 목표 금액과 여러 지폐 액수가 주어질 때, 지폐 일부를 반씩 계속 잘라 만든 조각들의 합이 목표 금액과 정확히 같아질 수 있는지 판정한다.
난이도

보통10점 중 5점

유형
수학, 정수론, 그리디, 비트 연산
정답자
아직 제출이 없습니다

문제

Philip은 큰 문제를 자주 겪는다. 저녁을 먹거나 맥주를 몇 잔 마신 뒤에 친구에게 돈을 빚지거나 친구가 자신에게 돈을 빚지는 경우가 많다. 금액은 대개 작지만 Philip은 동전을 싫어해서 지갑에 지폐만 넣고 다닌다. 그래서 보통 정확한 금액을 낼 수 없다. 동전을 싫어하므로 친구가 동전으로 거스름돈을 주는 것도 허용하지 않는다. 지폐로 거스름돈을 받는 것은 허용한다.

이 문제를 해결하려고 Philip과 친구들은 지폐를 잘라서 내기로 했다. 자르기 쉽도록 지폐를 똑같은 크기의 두 조각으로 자르고, 그 조각을 다시 두 조각으로 자르는 식으로 계속한다. 이렇게 하면 낼 수 있는 금액의 범위가 훨씬 넓어진다. Philip은 어떤 금액을 정확히 낼 수 있는지 궁금해한다.

입력

첫째 줄에 정수 tt (1 ≤ tt ≤ 100)가 주어진다. 이는 테스트 케이스의 수이다. 각 테스트 케이스는 다음과 같다.

  • Philip이 내야 하는 금액 xx (0.01 ≤ xx ≤ 10 000.00)가 한 줄에 주어진다. 소수점 둘째 자리까지 표기하며 소수점 기호로 마침표를 쓴다.
  • 서로 다른 지폐의 수 nn (1 ≤ nn ≤ 1 000)이 한 줄에 주어진다.
  • nn개의 줄에 각 지폐의 값 bib_i (1 ≤ bib_i ≤ 10 000)가 주어진다.

출력

각 테스트 케이스마다:

  • 금액을 정확히 낼 수 있으면 yes, 그렇지 않으면 no를 한 줄에 출력한다.

예제1

  1. 예제 1

    입력
    4
    10.75
    3
    2
    10
    20
    0.33
    1
    1
    10000.00
    1
    2500
    1.00
    2
    3
    5
    
    예상 출력
    yes
    no
    yes
    yes