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

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

알리바바

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

요약
세 종류의 토큰 보유량과 교환 규칙이 주어질 때, 각 종류별 필요량을 모두 충족하는 최소 교환 횟수를 구하고 불가능하면 NIE를 출력한다.
난이도

어려움10점 중 8점

유형
BFS, 그래프, 최단 경로, 구현
정답자
아직 제출이 없습니다

문제

참깨 동굴을 열려면 알리바바는 금화 토큰 zz개, 은화 토큰 ss개, 동화 토큰 mm개 이상을 가지고 있어야 한다. 처음에 알리바바는 각 종류의 토큰을 일정 개수씩 가지고 있으며, 정해진 규칙에 따라 동굴의 수호자와 토큰을 교환할 수 있다. 각 규칙은 다음과 같은 형태이다.

z1,s1,m1→z2,s2,m2(zi,si,mi∈{0,1,2,3,4})z_1, s_1, m_1 \to z_2, s_2, m_2 \qquad (z_i, s_i, m_i \in \{0, 1, 2, 3, 4\})

이는 알리바바가 금화 z1z_1개, 은화 s1s_1개, 동화 m1m_1개를 내주고 그 대가로 금화 z2z_2개, 은화 s2s_2개, 동화 m2m_2개를 받을 수 있다는 뜻이다. 한 번의 교환에서 얻은 토큰은 다음 교환에서 다시 사용할 수 있다.

각 테스트 케이스마다, 유한한 횟수의 교환을 거쳐 알리바바가 각 종류별로 필요한 개수 이상의 토큰을 모두 가질 수 있는지 판단하여라. 가능하다면 그러한 교환 순서의 최소 횟수를 출력하고, 불가능하다면 NIE(폴란드어로 "아니오")를 출력한다.

입력

첫째 줄에는 테스트 케이스의 수를 나타내는 양의 정수 dd (d≤10d \le 10)가 주어진다. 이어서 테스트 케이스들이 주어지며, 각 테스트 케이스는 여러 줄로 이루어진다.

각 테스트 케이스는 다음과 같다.

  • 첫째 줄: 알리바바가 처음에 가진 금화, 은화, 동화 토큰의 개수를 나타내는 세 음이 아닌 정수 zp,sp,mp∈{0,1,2,3,4}z_p, s_p, m_p \in \{0, 1, 2, 3, 4\}
  • 둘째 줄: 동굴을 여는 데 필요한 금화, 은화, 동화 토큰의 개수를 나타내는 세 정수 z,s,m∈{0,1,2,3,4}z, s, m \in \{0, 1, 2, 3, 4\}
  • 셋째 줄: 규칙의 개수 rr (1≤r≤101 \le r \le 10)
  • 다음 rr개의 줄: 각 줄마다 규칙 z1,s1,m1→z2,s2,m2z_1, s_1, m_1 \to z_2, s_2, m_2를 나타내는 여섯 정수 z1,s1,m1,z2,s2,m2∈{0,1,2,3,4}z_1, s_1, m_1, z_2, s_2, m_2 \in \{0, 1, 2, 3, 4\}

한 줄 안의 수들은 공백 하나로 구분된다.

출력

각 테스트 케이스마다 한 줄을 출력한다. 알리바바가 필요한 만큼의 토큰을 갖추기 위해 최소로 수행해야 하는 교환 횟수(음이 아닌 정수)를 출력하거나, 그러한 교환 순서가 존재하지 않으면 NIE를 출력한다.

예제3

  1. 예제 1

    입력
    2
2 2 2
3 3 3
3
0 1 1 2 0 0
1 0 1 0 2 0
1 1 0 0 0 2
1 1 1
2 2 2
4
1 0 0 0 1 0
0 1 0 0 0 1
0 0 1 1 0 0
2 0 0 0 2 2
    예상 출력
    NIE
9

  2. 예제 2

    입력
    1
1 0 0
0 1 0
1
1 0 0 0 1 0
    예상 출력
    1

  3. 예제 3

    입력
    1
0 0 0
4 0 0
1
0 0 0 4 0 0
    예상 출력
    1