Leaves and bees P27309


Statement
 

pdf   zip

thehtml

It is spring! The vegetable garden of our friend Pau Gargallo is full of flowers. However, and for reasons difficult to explain (and that they don’t mind) we are more interested in the leaves. Pau only let us to cut plants with flower, and he charges us F cents of euro for each flowered plant that we cut; moreover, we know that we can obtain L cents of euro for each leaf that we sell in the black market of collectors of leaves. ¿Would you know to tell us which is the maximal profit that we can obtain, and how many plants we should cut to reach it? In case that there were many different ways to reach the same profit, our lazy nature drives us to accept only as correct answer the one which requires to cut the minimal number of plants.

A small detail: some flowers have bees! Under any circumstances we dare to cut plants which flower has at least a bee.

Input An input contains only a garden. The first line of the garden contains the numbers 0≤ F≤ 1000, 0≤ L≤ 1000 and 3≤ m≤ 1000, that are, respectively, the cost of cutting a plant, the profit that we obtain per leaf, and the length of the garden. The description of a garden of length m takes up m lines. (look the instances of the input to undestand better the explanation).

  • Each row of the garden can contain a plant.
  • The character - indicates the stem of the plant.
  • The character b indicates a leaf that belongs to the stem placed immediately below.
  • The character P indicates a leaf that belongs to the stem placed immediately above.
  • A square 3 by 3 formed by characters x or B, and placed at the end of a stem (the stem ends in the middle of the wall on the left of the square), indicates that the plant is flowered. The characters B represent pieces of flower taken up by bees.

    Any plant has a stem of length greater than 80.

The plants placed in the first and the last position of the garden never will have flowers. The characters of two different plants will never superimpose.

Output

Your program must print two lines, each one of them ended in a return of line. In the first line it must print the maximal profit that can be obtained from the garden in euro cents, and in the second line the minimal number of necessary cuts to reach it.

Scoring

  • TestA:  ‍35 Points ‍

    Test cases where between each pair of stems there is, at least, a space without plant, as in the instance 1 or the instance 2.

  • TestA:  ‍65 Points ‍

    Test cases without the previous limitation.

Public test cases
  • Input

    0 1 11
             b b  xxx
    --------------xxx
      P P P bP P  xxx
    ------------
      PPbb         bb xxx
    ------------------xxx  
     b xxx         PP xxx
    ---xxx
       xxBb xxx
    --------xxx
        PPP xxx

    Output

    17
    3
    
  • Input

    4 2 12
            bxxx
    ---------xxx
            Pxxx
            bxxx
    ---------xBx
            Pxxx
       b b   xxx
    ---------xxx
       P P   xxx
       b b   xxx
    ---------xBx
       P P   xxx
    

    Output

    4
    1
    
  • Input

    13 3 26
    ----------------
    -bPbxxx   PPPP
    ----xxx
    -bP xxx
    ---
    -PP  bbb xxx
    ---------xxx
    -----PPPPxxx b xxx
    ---------------xxx
    -----  PPP P P xxxbbbbb
    -----------------------
    ---------xxx  P P P  PP
    ---------xxx
    - PbPbPbPxxxbb
    -------------- bxxx
    ----------------xxx
    ---PbPxxxP P PPPxxx
    ------xxx
    - bPb xxx bbxxx
    ------------xxx
    - bbb  PPP  xxx
    -----
    --b P
    ----------
    --    bbPPbbbbbb
    --------------------
    

    Output

    32
    4
    
  • Information
    Author
    Omer Giménez
    Language
    English
    Translator
    Carlos Molina
    Original language
    Spanish
    Other languages
    Spanish
    Official solutions
    C++
    User solutions
    C++