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


You probably remember one of the favorite games of your childhood, the colored building blocks. Recently, Bob has found all of his old blocks in the attic, so he thought it was time to build some cool stuff. He would like to build as many sets as possible that he didn't buy earlier but still can build using his own blocks. He started to make notes on how many blocks of different types and colors he found. Unfortunately, he found the blocks scattered in various parts of the attic, so sometimes he made multiple items in his notes about blocks of the same type and color. Write a program that helps him summarize the number of his blocks of different types and colors and decides whether a chosen set can be built or not.

Input Specification

The input consists of two parts. The first part contains the blocks needed to build the chosen set. The second part lists the blocks Bob found in the attic and lasts till end-of-file. The first part is separated from the second part by a blank line. All lines of the input (except the blank line) are of the form type color count, where type is a unique identifier of a block type (positive integer), color is a spaceless string containing the color of the block, and count is either the number of blocks needed to build the chosen set or the number of blocks that were found by Bob in the attic. You may assume that no lines of the input contains more than 30 characters.

Output Specification

The first line of the output should contain either the string “Can be built” or the string “Cannot be built” depending on whether the chosen set can be built using Bob's blocks. The following lines should contain the required number of blocks of different types and colors, as well as the number of blocks at Bob's disposal. Use the exact format of the sample output. These lines should be sorted by the types of blocks in ascending order. Blocks of the same type should be sorted by the lexicographic order of their colors.

Sample Input 1

  1. 3001 red 10
  2. 3003 green 4
  3. 3002 yellow 20
  4. 3003 red 30
  5. 3001 blue 10
  6. 3001 red 2
  7. 3003 green 1
  8. 3002 yellow 23
  9. 3003 red 30
  10. 3001 red 2
  11. 3001 red 7
  12. 3003 green 3
download as text file

Output for Sample Input 1

  1. Can be built
  2. 3001 red: 11/10
  3. 3002 yellow: 23/20
  4. 3003 green: 4/4
  5. 3003 red: 30/30
download as text file

Sample Input 2

  1. 3001 red 2
  2. 3001 green 3
  3. 3001 red 5
download as text file

Output for Sample Input 2

  1. Cannot be built
  2. 3001 green: 0/3
  3. 3001 red: 5/2
download as text file
University of Debrecen; Faculty of Informatics; v. 03/01/2019