cho.sh

StarCowraft

아직 제출이 없습니다시간 제한1초메모리 제한128 MB

문제

StarCowraft II 베타 버전이 준비되었다! 농부 John과 Bessie가 서로의 군대를 일대일 전투에 붙여 여러 전략을 시험하고 있다. StarCowraft II의 목표는 전투에서 상대의 군대를 물리치는 것이다.

각 플레이어의 군대가 전투를 벌인다. 군대는 최대 세 종류의 '유닛'으로 구성되며, 각 유닛의 강함(strength)은 플레이어가 알 수 없는 양의 실수 상수로 주어진다: 강함이 $S_1$인 cattlebruiser, 강함이 $S_2$인 cow templar, 강함이 $S_3$인 ultracow이다. 주어진 유일한 제한 정보는 어떤 유닛도 다른 어떤 유닛보다 100배를 초과해 강하지 않다는 것, 즉 모든 $i, j$에 대해 $S_i \le 100 \cdot S_j$라는 것이다.

한 군대의 총 강함은 그 군대에 속한 모든 유닛의 강함을 더한 값이다. 예를 들어 (다른 유닛과 함께) cattlebruiser를 23개 보유한 군대는 그 cattlebruiser들만으로 $23 \cdot S_1$의 강함을 얻는다.

서로 맞선 두 군대가 전투하면 총 강함이 더 큰 군대가 이긴다. 두 군대의 총 강함이 정확히 같으면 두 플레이어 중 한 명이 무작위로 이긴다.

John과 Bessie는 $N$ ($0 \le N \le 300$)번의 "시험 전투"를 치렀다. $i$번째 시험 전투에서 John의 군대는 cattlebruiser $J_{1,i}$개, cow templar $J_{2,i}$개, ultracow $J_{3,i}$개로 구성되었고 ($0 \le J_{1,i} + J_{2,i} + J_{3,i} \le 1000$), Bessie의 군대는 cattlebruiser $B_{1,i}$개, cow templar $B_{2,i}$개, ultracow $B_{3,i}$개로 구성되었다 ($0 \le B_{1,i} + B_{2,i} + B_{3,i} \le 1000$). 두 군대가 맞붙은 뒤 승자를 하나의 '승리 문자' $V_i$로 기록했다: John이 이겼으면 "J", Bessie가 이겼으면 "B".

이 승패 기록이 두 사람이 가진 유일한 정보이지만, 두 대전 군대의 유닛 구성이 주어졌을 때 추가 전투의 결과 중 일부를 예측하고 싶어 한다. 다만 어떤 전투는 주어진 정보만으로는 승자를 확실히 결정하지 못할 수도 있다.

John과 Bessie가 이미 치른 $N$번의 시험 전투 결과가 주어질 때, $M$ ($1 \le M \le 2000$)번의 새로운 전투 각각에 대해 (가능하다면) 승자를 결정하는 프로그램을 작성하라.

시험 전투로 보고된 결과는 정확하며, 이 결과들과 모순되지 않는 강함 값 $S_1, S_2, S_3$의 조합이 적어도 하나 존재한다.

군대 강함이 어떻게 계산되는지 보이기 위해, (John도 Bessie도 모르지만) 우리는 $S_1 = 9.0$, $S_2 = 7.0$, $S_3 = 4.0$임을 아는 게임에서 벌어진 다음 시험 전투들을 살펴보자:

   ---- Farmer John ----    ------- Bessie ------    Battle
   J1  J2  J3 J_Strength    B1  B2  B3 B_Strength   Outcome
    6   5   4    105         5   4   7    101          J
    5   4   2     81         3   5   5     82          B
    9   0  10    121         8   2   7    114          J

이 결과들로부터 아래에 적힌 이유에 따라 다음 결과들을 추론할 수 있다:

   ---- Farmer John ----    ------- Bessie ------    Battle
   J1  J2  J3 J_Strength    B1  B2  B3 B_Strength   Outcome
    6   6   4    112         5   4   7    101          J
              John의 군대가 시험 전투 1보다도 더 강하다
    9   0  10    121         8   2   6    110          J
              Bessie의 군대가 시험 전투 3보다도 더 약하다

입력

  • 첫째 줄: 공백으로 구분된 두 정수 $N$과 $M$.
  • 둘째 줄부터 $N+1$째 줄까지: $i+1$째 줄은 하나의 시험 전투를 공백으로 구분된 일곱 개 항목으로 나타낸다 — 승리 문자와 여섯 개의 유닛 개수 정수: $V_i$, $J_{1,i}$, $J_{2,i}$, $J_{3,i}$, $B_{1,i}$, $B_{2,i}$, $B_{3,i}$.
  • $N+2$째 줄부터 $N+M+1$째 줄까지: $i+N+1$째 줄은 하나의 "새로운 전투"를 여섯 개의 정수로 나타낸다: $J_{1,i}$, $J_{2,i}$, $J_{3,i}$, $B_{1,i}$, $B_{2,i}$, $B_{3,i}$.

출력

  • 첫째 줄부터 $M$째 줄까지: $i$째 줄에 $i$번째 새로운 전투의 결과를 출력한다: John이 반드시 이기면 "J", Bessie가 반드시 이기면 "B", 주어진 정보로는 승자를 결정할 수 없으면 "U"(undecidable, 결정 불가).

힌트

아래 테스트 케이스의 처음 두 새로운 전투는 문제 설명에서 추론한 두 전투에 해당한다. 세 번째 새로운 전투의 결과는 John과 Bessie가 현재 가진 정보만으로는 결정할 수 없다. 구체적으로, $S_1 = 9.0, S_2 = 7.0, S_3 = 4.0$과 $S_1 = 12.0, S_2 = 20.0, S_3 = 10.0$은 모두 시험 전투 결과와 모순되지 않지만, 세 번째 새로운 전투에 대입하면 서로 다른 결과를 준다.