ALGORITHM HOMEWORK 9 Solved

No     Change
Chad     has       been     looking  for        a          rare       anime    garage   kit         for        years.

He        just       learned  about    the        seller     that       has       exactly   what      he         wants.   The       seller     is          a          character           known   for strange  rules     of         trade: she           never    gives     any       change.

The       price     of         the        garage   kit         is          M.         Chad     has       brought  N          coins     with       him       such      that       the        i-th        coin            has       value     ai.         He        is          determined         to get    the        garage   kit         and       is          willing    to         pay       more     than      M,            if          necessary,         but        he         wants    to         overpay as         little       as         possible. Moreover,          he wants            to         minimize the            number  of         coins     he         uses.

Please   help      him       figure    out        which    coins     he         should   use       for        the        purchase.

Input
The       first       line       contains one       positive  integer   M,         the        price     of         the        garage   kit.        The       price     will        not        exceed 10,000.

The       following line       contains one       positive  integer   N,         the        number  of         coins     Chad     has,      N          <=        100.

The       next      N          lines      contain  poisitve  integers indicating           the        value     of         each     coin      that       Chad     has.      The       values archer   any       positive integers  no         greater  than      10,000.

Chad     has       brought  enough  money   to         buy       the        kit,        so         the        total      value     of         his        coins     will        always   be         equal to         or         greater  than      the price of         the        kit.

Output

Output   a          single    line       containing          two       integers: the        total      amount  paid      and       the        total      number  of         coins     used.

Example            1
 

Example            2
 

Page          1/1

Array Partition
 

Given    an         array     A          of         N          natural   numbers and       a          number  M         (1         <=        M         <=        N).        Split      the        given array     into       M         consecutive        subarrays such    that       the        maximum           sum      of         the        values   in          the        subarrays           is minimal.

For        example:            A          =          [4,3,2,1], M         =          3.         The       optimal  split       is          {4},       {3},       {2,1}.     The       maximum           sum of         all         subarrays           is          4,         which    is minimum         possible for        3          splits.    (Any      other     split       would    result     in          at least      one       subarray whose   sum      of         values   is          greater  than      4.) Input

The       first       line       contains 2          integer   N,         M         as         described           above.   1          <=        M         <=        N          <=        10^5.

In          the        next      line,      there     are        N          natural   numbers indicating           the        elements            of         the        array.    0          <= A[i]        <=        10^9      for        1          <=        i           <=        N Output

Output   one       integer   followed by         a          newline, indicating           the        minimal  maximum           sum      of         any       subarray in          the optimal  split.

Example            1
 

Example            2
 

Example            3
 

Page          1/1

Badminton         Class
Kou       school   is          preparing           for        badminton          championship.     In         this       championship     players  are        mixed    doubles. The       coach is creating          the        pairs/teams        for        the        championship     according           to         students’            skill       levels    based    on         their previous year      performance. He  wants    to         place     the        male     student  with       the        highest  skill       levels    with       the        top        female student. Then     the        second  ranking  male student       with       the        second  ranking  female   students.            And       so         on         and       so         forth until      the        largest   number  of         mixed    doubles is          built.

Your      task      is          to         determine           how      many     male     students are        left        unmatched         and       smallest skill       level      of         such unmatched         student.

Input
The       first       line       of         the        input     contains two       integers M         (1         <=        M         <=        10000)   and       F          (1         <=        F <=        10000),  representing       the        number  of male  and       female   students,            respectively.       Each     of         the        following M         lines describe the        skill       levels    of         the        male     students.            Then each          of         the        following F          lines      describe the        skill       level of         the        female   students.            All         skill       levels    are        between 2          and       60.

Output
You       should   print      a          line       that       contains the        number  of         male     students that       could     not        be         matched.            If          this number  is          not        zero,     you should         also      print      an         additional           number  indicating           the        skill       level      of         the        least skilled    unmatched         male     student.

Example            1
 

Example            2
 

Example            3
 Input:

4         2

5

5

10

15

20

18

 


Xiangliu
Polycephalic       or         multi-headed       animals  are        rare       in          biology  but        common in          mythology          and       heraldry: multi-headed snakes,  like the  8-headed           Yamata  no         Orochi   in          Japanese           mythology,         the        9-headed           Lernaean           Hydra    in Greek    mythology          and       3-headed Cerberus          in          Greek    mythology.

 Xiangliu, known   in          the        Classic  of         Mountains          and       Seas, is a          N-headed           snake    monster that       brings    flooding and destruction         in          Chinese mythology.

Now      it          appears at         the        plain      of         Xia        Kingdom.           The       king      Yu is     alarmed, and       calls      on         his        archers  to slay       the        serpent and        save      the        kingdom.



 
 
 

To         slay       Xiangliu and       stop      flooding, the        archers  must shoot         down     all         its         heads.   There    are        M         archers  in          the kingdom.            Each     archer   can       shoot     down     one       of         the snake’s         heads.   The       heads    of         the        snake    are        of different sizes.     In         order     to         shoot     down     a          head,    an         archer   have     to be     able      to         draw     a          longbow which    had a          draw     weight proportional           to         the        size       of         that       head.    The       archers demand  that       for        shooting down     a          head, an         archer   must be paid      a          wage     equal     to         one       gold      coin      per        each     pound of the        archer’s maximum           draw weight.

After      having   lost       a          lot         of         money   due       to         flooding, Yu        wants    to         minimize the        expense of         slaying   Xiangliu. Your job        is          to         help      the king, decide   how      many     and       which    archers  to         hire.

Input
The       first       line       contains 2          integers, indicating           the        number  N          of         heads    that       Xiangliu has,      and       the        number  m of         archers  in          the kingdom.       1          ≤          N,M      ≤          10^5.

The       next      N          lines      contain  positive  integers no         greater  than      10^9      that       give      the        sizes     of         the        snake’s  heads.   The i-th        integer   ai means that       the        archer   needs    to         be         able      to         draw     a          longbow with       a          draw     weight   no         less than      ai          pounds  to         shoot     down     the        i-th head of         Xiangliu.

The       following M         lines      each     contain  a          positive  integer   no         greater  than      10^9,     and       specify   the        maximum           draw weights  of         the archers         in          the        kingdom,            also      in          pounds.

Output
Output   a          number  followed by         a          newline, indicating           the        minimum            number  of         gold      coins     that       the        kings needs    to         pay       to         slay       the serpent.        If          it          is          not        possible for        archers  of         Xia        to         slay       the dragon,  output    the        line       "Xia       is          doomed!".

 

Example            3
 


Sprinklers
Farmer   John     has       a          large     field,      and       he         is          thinking  of         planting sweet    corn      in          some     part       of         it.          After surveying           his        field,      FJ         found that           it          forms    a          horizontal           strip      l           meters   long      and       w          meters   wide.

There    are        n          sprinklers           installed at         the        horizontal           center    line       of         the        strip.     For       each     sprinkler you       are given     its         radius    of operation        and       its         position  as         the        distance from      the        left        end       of         the        center    line. Farmer  John     wants    to         plant     sweet    corn      in          the whole           field,      but        he         wishes   to         turn       on         as         few sprinklers           as         possible to         save      the        water.



 
 
 

   Find      the        minimum            number  of         sprinklers           that       need     to         be         turned   on         in          order     to water     the        entire    field. Input

1000)     of         a          sprinkler.

The       picture   above    illustrates           the        first       case      from      the sample         input. Output

Output   one       integer   followed by         a          newline: the        minimum            number  of         sprinklers           needed  to         water     the        entire    strip.

If           it          is          impossible          to         water     the        entire    strip,     output    -1.

Example            1          (shown  in          the        image    above)