미신 파괴자

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

요약
각 도시의 네 자리 차량 ID 목록에 대해, 모든 ID가 숫자를 순열하고 +, -, *, /와 괄호를 넣어 10을 만들 수 있는지 판정한다.
난이도

보통10점 중 7점

유형
완전 탐색, 재귀, 수학, 구현
정답자
아직 제출이 없습니다

문제

시드니의 CityRail이 운행하는 모든 전동차 차량에는 네 자리 숫자로 이루어진 고유한 ID 번호가 있다. 이 지역 학생들 사이에는 흔히 퍼져 있는 미신이 하나 있는데, 어떤 ID 번호든 그 네 자리 숫자의 순서를 자유롭게 바꾸고(순열), 괄호를 사용하며, 연산 집합 {+, -, *, /} 의 사칙연산을 적절히 조합하면 항상 1010 을 만들 수 있다는 것이다.

여러분의 임무는 시드니 CityRail의 차량과, 다른 도시에서 수집한 차량 ID 번호들에 대해 이 미신이 실제로 성립하는지 검증하는 것이다.

참고: 여기서 / 는 정수 나눗셈을 의미한다. 대부분 이미 알고 있겠지만 두 가지 예를 들면, 5 / 2 의 결과는 2 이고 2 / 5 의 결과는 0 이다.

입력

입력은 여러 개의 테스트 케이스로 구성된다. 각 테스트 케이스는 다음과 같다.

  • 한 줄에 정수 NN (1<N<10001 < N < 1000) 이 주어진다. 이는 한 도시에서 수집한 ID의 개수를 나타낸다.
  • 이어지는 NN 개의 줄에는 각각 네 자리 숫자가 하나씩 주어진다.

한 줄에 0 만 주어지면 입력의 끝을 의미하며, 이 값은 처리하지 않는다.

출력

각 테스트 케이스마다 조사 결과를 한 줄에 TRUE 또는 BUSTED 로 출력한다. 해당 도시의 모든 차량 ID 번호에 대해 미신이 성립하면(즉 모두 1010 을 만들 수 있으면) TRUE 를, 그렇지 않으면 BUSTED 를 출력한다.

예제4

  1. 예제 1

    입력
    2
    6666
    5555
    1
    1234
    0
    
    예상 출력
    BUSTED
    TRUE
    
  2. 예제 2

    입력
    1
    1234
    0
    
    예상 출력
    TRUE
    
  3. 예제 3

    입력
    1
    6666
    0
    
    예상 출력
    BUSTED
    
  4. 예제 4

    입력
    3
    1234
    5555
    9999
    0
    
    예상 출력
    TRUE