Programming contests

DEIK Regionális Programozó Csapatverseny, középiskolai kategória, 2019. december 8.

December 8, 2019 10:15 AM – December 8, 2019 3:15 PM

Apple Trees

The autumn harvest has begun in grandfather's garden, which is full of apple trees. He's expecting a record yield this year; therefore, he's having a hard time finding the most efficient way to harvest all the apples. Grandfather has N boxes, and each of them can hold K kilograms of apple. Luckily enough, grandfather can determine at a glance how many kilograms of apple is produced by each of the M apple trees in his garden. Help grandfather compute the minimum number of boxes needed to harvest all the apples. Unfortunately, there may not be enough boxes to harvest the apples from all of the trees.

Input Specification

The first line of the input contains an integer T representing the number of test cases that follow. The first line of each test case contains three integers: the capacity of the boxes (K, 1 ≤ K ≤ 200), the number of boxes (N, 1 ≤ N ≤ 200), and the number of apple trees (M, 1 ≤ M ≤ 500). The next line consists of exactly M integers between 1 and 100, representing the yield of each apple tree.

Output Specification

The program should output exactly one line for each test case. If all the apples can be harvested with the boxes at our disposal, then print the number of boxes required. Otherwise, print the word “impossible”.

Sample Input

  1. 3
  2. 10 5 5
  3. 10 10 10 10 10
  4. 15 2 4
  5. 1 2 3 4
  6. 10 3 3
  7. 10 20 30
download as text file

Output for Sample Input

  1. 5
  2. 1
  3. impossible
download as text file
University of Debrecen; Faculty of Informatics; v. 03/01/2019