ALGORITHM HOMEWORK 11 Solved

Ways to      Add
A          very      simple   problem: given     a          integer   N,         how      many     ways     can       K          integers less       than      N          add       up         to            N?

For       example,            for        N          =          6          and       K          =          2,         there     is          7          ways:

 

For       N          =          3          and       K          =          3,         there     is          10         ways.

 

Input     One      line       containing          two       integers N,         K,         1          <=        N,K       <=        100.

Output  A          single    line       containing          the        answer  modulo  10^9+7.

Example            1
 

Example            2
 

Page          1/1

Batch         Processing
Since    Light     Kingdom did        not        pay       you       salary    for        a          whole    year,     you       decided to         leave     and       work      for            Conflict  Empire.  Now,     you are  again     an         operator of         a          super    computing          center    and       in          control   of         M            nodes.

One      day,      a          research institute  from      Conflict  Empire  submitted           N          computational     tasks     numbered          from      1          to         N.            Given    the running         time      needed  for        each     task,      you       are        to         distribute            the        tasks     among   the        available            nodes    such      that       the        node     with heaviest       workload            completes          as         early     as         possible. Restriction:         every     node            must     process at         least      one       task      and       must     process a           contiguous         subsection          of         tasks.    That      is,         you            need     to         find       a          sequence           0          =          L0         <          L1         <          …         <          LM-1       <          LM         =          N            where    the        i-th        node processes   tasks     Li-1+1,    Li-1+2,    …,        Li.

Input
The       first       line       of         the        input     contains two       integers N          and       M         (1         <=        M         <=        N          <=        500),            representing       the        number  of         tasks     and       the number         of         nodes    you       control,  respectively.       The       second  line            contains N          integers Ti          (1         <=        Ti          <          10,000,000),       representing       the time needed  to         complete            each     task.

Output
Print      one       line       containing          the        input     T1,        T2,        …,        TN         divided  into       M         parts     such      that       the        maximum            sum      of         a          single    part       is minimized.       You       should   use       character           '/'          to         separate the        parts     and       there            must     be         a          space    character           between every     numbers or         '/'s.

If          there     is          more     than      one       solution, print      the        one       that       minimizes           the        sum      of         the        first       part,      then            the        second  part       and       so         on.

Example            1
 

Example            2
 

Page          1/1

Date  Overflow
 The       Year      2000     problem, also      known   as         the        Y2K problem,      the        Millennium          bug,      Y2K      bug,      the        Y2K      glitch, or Y2K,            refers    to         events   related   to         the        formatting           and storage        of         calendar data      for        dates     beginning           in          the            year 2000.          Problems           were     anticipated,         and       arose,    because many    programs           represented        four-digit years     with       only the        final      two       digits     –          making  the        year      2000 indistinguishable      from      1900.    The       assumption         of         a twentieth-century            date      in          such      programs           could     cause various     errors,   such      as         the        incorrect display   of         dates and           the            inaccurate          ordering of         automated          dated    records or          real-time events.

In   fact,      there     are        also      many     other,    similar   problems. Suppose          you       have     two       computers          C1        and       C2        with            different bugs:

One      with       the        ordinary Y2K      bug       (i.e.       displaying           a1:=1900           instead  of         b1:=2000),          and       one       displaying            a2:=1904           instead  of b2:=2040        (i.e.,      after      the        year      2040,    the        computer           starts     showing wrong    year,     starting  with            1904).

Now      imagine you       see       C1        displays the        year      y1:=1941            and       C2        the        year      y2:=2005.

 You    know     the        actual    year      cannot   be         1941     since     in          that       case      C2        will        display   the        same     year,     and       it         can       not        be         2005, either.       If          the        year      is          2005,    y1         would    be         1905,    hence    it’s        impossible.

Looking           at         y1,        we        know     the        actual    year      could     be         1941,    2041,    2141,    etc.

Then   we        calculate what      C2        would    display   for        1941,    2041,    2141.    It          turns     it          will        be         1941,    1905,    2005.

So      it’s        possible the        actual    year      is          2141.

To        calculate the        actual    year      from      those     buggy    computers          requires a          lot         of         work.     You       are        hired     to         write            a          program to         solve this           problem: Find      the        first       possible real       year,     knowing what      some     other     computers          say            (yi)        and       knowing their      bugs (displaying  ai          instead  of         bi).

Note      that       the        year      ai          is          definitely not        after      the        year      the        computer           was       built.      Since    the        actual    year            can’t      be         before   the        year      the computers     were     built,      the        year      your      program is          looking  for        can’t      be            before   any       ai          .

Input
The       first       line       contains 1          integer   n,         the        number  of         computers,         1          <=        n          <=        20.

In         the        following n          lines,     each     line       contains 3          integer   yi,         ai,         bi          for        each     computer,           0<         =          ai            <=        yi          <          bi          <          10000.

yi          is          the        year      the        i-th        computer           displays, bi          is          the        year      the        bug       will        happen, and       ai          is            the        year      displayed           instead  of         bi.

Output
Output   an         integer   z          where    z          is          the        smallest possible year      followed by         a          newline.

If          there     is          no         such      year      less       than      10000,   output    -1.

Example            1
 

Example            2
Page          1/2

 

Example            3
 

Example            4
 

Page          2/2

Ayu’s         Candies
 

Ayu       has       three     flavors   of         candies: banana  flavored, grape    flavored and       cherry    flavored. She       also      has       three     boxes    numbered 1,            2          and       3,         each     of         which    contains some     of         those     candies. Now      Ayu       wants    to         move     candies  such      that            after      the        movement, each  box       contains the        candies  of         only      one       flavor     and       no         two       boxes    contain  same            flavored candies. Your      task      is          to         help      Ayu find the        minimum            number  of         candy    movements.

Input
The       input     consists of         only      one       line,      containing          9          integers. The       first       three     integers represent           the        number  of            banana  flavored, grape    flavored and       cherry    flavored candies  in          the        first       box,      the        second  three     integers represent           the            number  of         banana flavored,  grape    flavored and       cherry    flavored candies  in          the        second  box,      and       the        last       three            integers represent           the        number  of banana           flavored, grape    flavored and       cherry    flavored candies  in          the        third      box.      It            is          guaranteed         that       the        total      number  of candies          never    exceeds 231.

For       example,            the        input     10              15              20              30              12              8                15              8                31         indicates that       there     are        10            banana  flavored candies  in          box       1,         12 grape flavored candies  in          box       2          and       31         cherry    flavored candies  in          box            3.

Output
Print      one       line       S                x           indicating           which    flavor     of         candies  go         in          which    box       to         minimize the        number  of            candy    movements.        S           is          a string  of         three     letters    G ,         B          and       C          (representing      the        flavor     of            grape,   banana  and       cherry,   respectively)       indicating           the        flavor associated with       each     box.      x           is          the        minimum            number  of         candy    movements.

If                                                                                                  there is          more     than      one       solution, print      the        alphabetically      smallest string                                                                                                      as   S .

Example            1
 

Example            2
 

Page          1/1

Grocery     Delivery
 

Nia       hates     shopping            and       she       really     despises grocery  shopping.           She       orders   her        groceries            from      a          local      store.            In         preparation for    drone    deliveries,          the        store     has       new      rules     about    packing  items     for        delivery:

 they    will        deliver   exactly   two       boxes    to         the        customer            (even    if          the        order     is          small     and       one       of         the        boxes    is          empty) the          capacity of         each     box       is          the        same     and       equal     to         W.

 

Nia       knows   the        volume  occupied            by         each     item      on         her        shopping            list:       the        ithitem    has       the        volume  vi.            With      the        new      rules,     she       has to    prioritize the        items     that       she       orders   since     not        everything          can       fit          in            the        two       boxes.   Her       list        is          arranged            in          the        order     of         priority: from       the        most     important           item            to         the        least      important           one       (i.e.,      the        ith          item      is          always   more     important           than      the        i+1st      item).            As she   prepares the        list        to         send     to         the        store,    she       only      orders   the        highest  priority   items     and       as         soon            as         she       comes   to         an         item that is          too        large     to         fit          in          the        remaining           space    in          the            boxes,   she       skips     that       item      and       all         the        items     below.

The       question is          how      many     items     from      her        list        she       will        be         able      to         order     and       which    item      should   be            placed   in          which    box.

Input
The       first       line       contains 2          integers N          and       W,        indicating           the        number  of         items     and       the        capacity of         a            box,      1          <=        N          <=        200,      1          <=        W <=     10000.

The       second  line       contains N          integers, indicating           the        volume  of         items     in          Nia’s     list.       They     are        in          the        order            of         priority   as         described above.

Output
The       first       line       of         output    should   specify   the        number  of         items     that       can       be         ordered.

For       each     item      that       can       be         ordered, output    a          line       containing          "1st"      if          the        item      is          to         be            placed   in          the        1st        box       and       "2nd"     if          the item is          to         be         placed   in          the        2nd       box.      If            several  arrangements     of         the        items     are        possible, any       one       will        do. Example       1

 Input:

5         10

1         2                100           3                4

Output:

2

1st

1st

Page          1/2

Explanation        of         example 1:

Nia       has       to         remove  the        3rd        item      since     it’s        too        large     (this      means   that       the        4th        and       the        5th        items            are        also      removed from      the order,           even     though   they      could     fit          in          the        second  box).

The       first       2          items     will        be         ordered. Any       arrangement       of         the        items     in          boxes    will        do.


 
 
 

Example            2
 

Page          2/2