[CDJ] 2017 Round 1A - B. Ratatouille

문제 링크

CodeJam 2017 Round 1B B번 문제 Steed 2: Ratatouille

[CodoeJam]

출처 : https://code.google.com/codejam/contest/5304486/dashboard#s=p1

[BOJ]

참고(Small) : https://www.acmicpc.net/problem/14799

참고(Large) : https://www.acmicpc.net/problem/14800

문제 요약

- Ratatouille 음식 키트를 만드는 데 필요한 재료 N개가 있다.

- 하나의 재료 양은 필요 양의 90~110% 범위 내에 있어야 한다.

- 각 필요 재료의 패키지 P개가 있을 때, 각 재료의 패키지를 선택하여 음식 키트를 만들 수 있다.

- 최대 인분으로 음식 키트를 만들 수 있는 패키지를 수를 구하여라

- [음식 키트를 만들 수 있는 예] 

  키트를 만드는 데 필요한 재료로 토마토 500g 과 양파 300g 인 경우,

  토마토 재료 패키지 900g, 양파 재료 패키지 660g 있을 때, 

  토마토 900g은 2인분 필요 토마토 양인 1000g의 90%이고 양파 660g은 2인분 필요 양파 양인 600g의 110%이므로 

  해당 패키지로 음식 키트를 만들 수 있다. 

- [음식 키트를 만들 수 없는 예]

   위 방법으로 계속 하였을 경우, 

   토마토 재료 패키지 1500g, 양파 재료 패키지 809g 있을 때,

   3인분의 음식 키트를 만들고자 하면 토마토 1500g, 양파 900g이 필요하지만 

   해당 패키지를 이용하면 90~110% 범위 내가 아니므로 음식 키트를 만들수 없다.

입출력

입력

T (테스트케이스 수)

N (재료 수) P(패키지 수)

Q(i , j) ( i 번째에 재료의 j 번째 패키지 양) 

출력

각 테스트 케이스는 "Case #x:" 로 표시하며 그 다음 줄에 결과를 출력한다.

최대 인분의 키트를 만들 수 있는 패키지 수를 출력한다.

Limits

1 ≤ T ≤ 100.
1 ≤ R_i ≤ 10⁶, for all i.
1 ≤ Q_ij ≤ 10⁶, for all i and j.

Small dataset

1 ≤ N ≤ 2.
1 ≤ P ≤ 8.

Large dataset

1 ≤ N ≤ 50.
1 ≤ P ≤ 50.

N × P ≤ 1000.

Sample

Input	Output
6 2 1 500 300 900 660 2 1 500 300 1500 809 2 2 50 100 450 449 1100 1101 2 1 500 300 300 500 1 8 10 11 13 17 11 16 14 12 18 3 3 70 80 90 1260 1500 700 800 1440 1600 1700 1620 900	Case #1: 1 Case #2: 0 Case #3: 1 Case #4: 0 Case #5: 3 Case #6: 3

문제 해설

// TODO

소스 코드