무인 편의점과 위조 상품권

시간 제한0.5초메모리 제한512 MB

요약
각 고객이 지불한 금액을 만족하면서 전체가 싼 상품권 C1장과 비싼 상품권 C2장을 정확히 사용하고, x번째 비싼 상품권을 낼 수 있는 고객의 수를 센다.
난이도

어려움10점 중 8점

유형
동적 계획법, 수학, 그리디
정답자
아직 제출이 없습니다

문제

Albert는 무인 편의점을 운영하고 있다. 고객들은 편의점에서 물건을 산 후 지폐 형태의 상품권을 이용하여 무인 기계를 통해 결제를 하는데, 상품권의 단위는 "비싼"것과 "싼" 것의 두 종류만 있다: V_1V\_1 달러짜리 "싼" 상품권과 V_2V\_2 달러짜리 "비싼" 상품권 (0<V_1<V_20 \lt V\_1 \lt V\_2 는 정수). 편의상 기계는 거스름돈을 돌려주지 않는다.

매일 자정 Albert는 기계를 열어 상품권을 검사하는데, 간혹 위조된 상품권을 발견하기도 한다. 정확히 어떤 손님이 위조 상품권을 사용했는지 알아내고 싶지만, CCTV에 녹화된 내용을 세세히 체크해야하고, 이는 시간이 너무 오래 걸린다. "용의자"를 줄이기 위해 Albert가 활용할 수 있는 정보를 요약해보니 아래와 같았다:

  1. 현재 기계에는 싼 상품권 C_1C\_1장 그리고 비싼 상품권 C_2C\_2장이 들어있다.
  2. 총 NN 명의 손님이 결제를 했고, 결제 로그에 따르면 ii 번째 손님이 지불한 금액은 정확히 A_iA\_i 달러 이다.
  3. 기계는 거스름돈을 주지 않으므로 V_1×C_1+V_2×C_2=∑_iA_iV\_1 \times C\_1 + V\_2 \times C\_2 = \sum\_{i} A\_i 임을 확인할 수 있다.
  4. 기계는 손님들이 지불한 상품권을 투입된 순서대로 보관한다 - 단, 싼 상품권과 비싼 상품권을 구분하여 각각 순서대로 보관한다.
  5. 기계에 xx 번째로 투입된 V_2V\_2 달러 (비싼) 상품권이 위조 상품권이다 (1≤x≤C_21 \le x \le C\_2).

Albert는 자신이 가진 정보를 최대한 활용하여 용의자의 수를 줄이고 싶다. ii 번째 고객이 용의자가 되려면 ii 번째 고객이 xx번째 비싼 상품권을 지불함과 동시에 나머지 손님들도 정확히 자신의 결제금액 만큼만 지불할 수 있는 방법이 존재해야 한다. 구체적으로, jj번째 손님이 사용한 싼 상품권이 b_jb\_j 장이고 비싼 상품권이 c_jc\_j 장 이라고 했을 때, 아래 조건을 모두 만족하는 b_j,c_j\\{b\_j, c\_j\\} 가 존재하면 ii 번째 고객은 용의자가 된다:

  • 조건1: 모든 고객 jj에 대하여 0≤b_j≤C_10 \le b\_j \le C\_1 그리고 0≤c_j≤C_20 \le c\_j \le C\_2 그리고 V_1b_j+V_2c_j=A_jV\_1 b\_j + V\_2 c\_j = A\_j
  • 조건2: ∑_j=1Nb_j=C_1\sum\_{j=1}^{N} b\_j = C\_1 그리고 ∑_j=1Nc_j=C_2\sum\_{j=1}^{N} c\_j = C\_2 (즉, 모든 고객의 b_j,c_jb\_j, c\_j 값을 더하면 C_1,C_2C\_1, C\_2과 일치)
  • 조건3: ∑_j=1i−1c_j<x≤∑_j=1ic_j\sum\_{j=1}^{i-1} c\_j \lt x \le \sum\_{j=1}^{i} c\_j (즉, xx 번째로 기계에 투입된 V_2V\_2 달러 상품권은 ii 번째 고객이 투입함)

예를 들어 V=\[1,5]V = \[1, 5], C=\[10,3]C = \[10, 3], N=4N = 4, A=\[5,10,5,5]A = \[5, 10, 5, 5] 그리고 x=1x = 1 이라 하자. 즉, 현재 기계에는 싼 상품권 C_1=10C\_1=10장, 비싼 상품권 C_2=3C\_2=3장이 있고 (따라서 총 금액은 2525 달러가 된다), 총 4명의 고객이 순서대로 55, 1010, 55, 55 달러 만큼 결제하였음을 알 수 있다. x=1x = 1 이므로 비싼 상품권 중 가장 처음에 투입된 상품권이 위조 상품권임을 알 수 있다.

  • 가령 b=\[0,10,0,0],c=\[1,0,1,1]b = \[0, 10, 0, 0], c = \[1, 0, 1, 1] 라 하자.

    • 1번 고객은 (위조된) 비싼 상품권 1장을 사용해 5달러를 결제했다.
    • 2번 고객은 싼 상품권 10장을 사용해 10달러를 결제했다.
    • 3번 고객과 4번고객은 각각 비싼 상품권 1장을 사용해 5달러를 결제했다.
    • 상기한 3가지 조건을 i=1i=1일 때 만족하므로 1번 고객은 용의자이다.

  • 가령 b=\[5,5,0,0],c=\[0,1,1,1]b = \[5, 5, 0, 0], c = \[0, 1, 1, 1] 라 하자.

    • 1번 고객은 싼 상품권 5장을 사용해 5달러를 결제했다.
    • 2번 고객은 싼 상품권 5장과 (위조된) 비싼 상품권 1장을 사용해 10달러를 결제했다.
    • 3번 고객과 4번 고객은 각각 비싼 상품권 1장을 사용해 5달러를 결제했다.
    • 상기한 3가지 조건을 i=2i=2일 때 만족하므로 2번 고객은 용의자이다.

  • 다른 다양한 b,cb, c 값들이 세 조건을 모두 만족하지만 i=3i = 3 혹은 i=4i = 4일 때 세 조건을 만족하는 경우는 없으므로 고객 3, 4는 용의자가 아니다.

입력으로 V,C,N,A,xV, C, N, A, x가 주어졌을 때, 용의자의 수를 추려 Albert를 도와주자. 위 예제의 경우 1, 2번 두 고객이 용의자이므로 정답은 2가 된다. 만약 세 조건을 만족하는 용의자가 0명이라면 -1을 출력한다 - 예제에서 보여지듯 Albert가 활용할 수 있는 정보에 오류가 있을 수도 있으므로, 용의자가 0명인 경우가 발생할 수 있다.

입력

입력 첫 줄에 테스트 케이스의 수 TT가 주어진다.

각 테스트 케이스의 첫줄에는 V_1,C_1,V_2,C_2V\_1, C\_1, V\_2, C\_2가 공백으로 구분되어 주어진다.

둘째 줄에는 NN과 xx가 공백으로 구분되어 주어진다.

셋째 줄에는 NN개의 정수가 공백으로 구분되어 주어지는데, A_iA\_i 값을 나타낸다.

출력

각 테스트 케이스의 정답인 용의자 수를 각 줄에 출력한다. 단, 용의자가 0명인 경우, -1을 출력한다.

제한

  • 주어지는 모든 수는 정수이다.
  • 1≤T≤201 \le T \le 20
  • 1≤V_1<V_2≤151 \le V\_1 \lt V\_2 \le 15
  • 1≤C_1,C_2≤10,0001 \le C\_1, C\_2 \le 10\\,000
  • 1≤x≤C_21 \le x \le C\_2
  • 1≤N≤1001 \le N \le 100
  • 1≤i≤N1 \le i \le N 인 각 ii 에 대하여: 1≤A_i≤1001 \le A\_i \le 100
  • 모든 테스트 케이스에 대하여 V_1×C_1+V_2×C_2=∑_i=1NA_iV\_1 \times C\_1 + V\_2 \times C\_2 = \sum\_{i=1}^{N} A\_i 임이 보장된다

예제1

  1. 예제 1

    입력
    8
1 10 5 3
4 1
5 10 5 5
1 10 5 3
4 2
5 10 5 5
1 10 5 3
4 3
5 10 5 5
1 5 5 1
2 1
5 5
2 3 3 3
3 2
4 4 7
2 3 3 3
3 2
3 3 9
2 3 3 3
3 2
4 5 6
3 2 4 2
2 2
5 9
    예상 출력
    2
2
3
2
-1
1
1
-1