ALGORITHM HOMEWORK 8 Solved

Find  Root
Find      the        root       for        the        equation:

 

Where   x          is          a          real       number  in          [0,1]      (i.e.,      0          ≤          x          ≤          1)

Input
 

Output
The       output    should   be         a          single    line       containing          the        value     x          of         the        root       for        the        above    equation, correct   up         to         4          decimal  places (there       should   be         exactly   4          digits     after      the        decimal  point),    or         the        string     ‘No solution’, whichever          is          applicable.

You       can       assume that       there     will        be         only      one       root       in          [0,1]      if          it          exists.

Example            1
 

Example            2
 

Example            3
 

Kou   Sort
Kou       just       finished  her        first       algorithm            class     and       designed            a          new      sorting   algorithm:           given     an         array     of N          distinct   numbers,           the algorithm       sorts     them     in          ascending          order     by         performing          the        minimum            number  of swaps   required. A          swap     is          an         exchange           of two    adjacent elements            in          the        array.

For        example,            if          the        array     is          [9,         1,         0,         5,         4],         the        smallest number  of         required swaps   to produce the        array     [0,         1,         4,         5,         9]         is          6.

0:          [9,         1,         0,         5,         4]         (original array)

1:          [1,         9,         0,         5,         4]         (swap    1)

2:          [1,         0,         9,         5,         4]         

3:          [1,         0,         5,         9,         5]         

4:          [1,         0,         5,         4,         9]         

5:          [0,         1,         5,         4,         5]         

6:          [0,         1,         4,         5,         9]         (swap    6)         

(Note     that       there     may      be         other     sequences         of         swaps   that       lead      to         the        minimum            number  of         swaps.)

Now      Kou       wants    to         determine           if          her        algorithm            always   performs as         she       claims   it          does.     Given    an         array of         N          distinct   integers, your      task      is          to         figure    out        the        minimum            number  of         swaps   required to         sort       it. Kou       will        then      make     sure      that       her        algorithm performs           exactly   that       number  of         swaps.

Input
The       first       line       of         the        input     contains a          single    integer   N          (1         <=        N          <=        500,000),           the        size       of that       array.    The       following N          lines represent    the        content  of         the        input     array.    Each     of         these     N          lines      contains a single    integer   between 0          and       999,999,999.      It          is guaranteed      that       the        array     contains no         duplicates.

Output

You       should   print      one       line       containing          a          single    integer:  the        minimum            number  of         swaps   required to         sort       the given     array.

Example            1
 

Example            2
 

Load Balance
You       are        an         operator of         a          super    computing          center    and       in          control   of         M         nodes.   One      day,      a research institute  from      Light Kingdom     submitted           N          computational     tasks.    Given    the        computational     power    needed  for        each     task, you       are        to         distribute            the tasks            among   the        available nodes.   Restriction:         every     node     can       process up         to         two tasks.    You       also      want      to         distribute            the workload       as         evenly   as         possible, i.e.        minimize the        following imbalance          value

 

where    Avg       is          average load      per        node     and       Loadi     is          the        load      of         the        i-th        node.

Input
The       first       line       of         the        input     contains two       integers M         (1         <=        M         <=        5)         and       N          (1         <=        N <=        2M),      indicating           the        number  of         nodes    you control         and       the        number  of         tasks,    respectively.

The       second  line       contains N          integers, each     of         which    represents          the        computational     power    required for        a          task. Numbers            on these line       are        between 1          and       1000.

Output


 
 
 

Print                       one            line IMBALANCE                                                  =            I           where    I           is          the        minimum            imbalance          value                          rounded          to      5                                     decimal   places.

Example            1
 

Example            2
 

Example            3

Nucleic      Acids
For        a          string     S          of         length    N,         we        can       define    inversion            as         follows:  If          for        an         integer   pair       (i,j), we        have     0          ≤          i           <          j           <          N,         and       S[i]S[j], then      (i,j)        is          a          inversion            for        S.

Define    a          function Count(S),           which    returns   the        number  of         distinct   inversions          in          S.

For        example,            Count("ABC")      =          0          since     "ABC"    is          sorted,   and       Count("DAABEC")            =          5,         since     D          is greater  than      four       letters    to         its right  and       E          is          greater  than      one       letter     to         its         right.

You       are        responsible         for        cataloging          a          sequence           of         nucleic   acid      strings,  which    are        strings   containing          only the        four       letters    A,         C, G,     and       T.         The       Count(S)            is          a          measure of         "unsortedness"    for        S.         You       want to         catalog  them     in          order     of         "unsortedness",   from "most          sorted"   to         "least     sorted".  All         the        strings   are        of         the same     length.

Input
 

Output
Output   m         lines,     the        list        of         input     strings,  arranged            from      "most    sorted"   to         "least     sorted".  If          two       or         more strings   are        equally sorted,    list        them     in          the        same     order     they      are        in          the        input     file.

Example            1
 

Party Fee
Saya     just       graduated          from      her        high      school!  She       and       her        classmates         rented   a          ballroom and       held      a          party to         celebrate            their graduation.  They     realized that       the        room     fee        was       not        split       evenly   since     some     of         them     did not        bring     enough  money.  After going         home,    they      decided to         re-split   the        fee.       However,           the        payment app       they      use only      allows    transfers between friends.  As a      kind      person,  you       want      to         help      them     out.

You       will        be         given     information         about    how      much     money   each     of         them     owes     or         is          owed     and       whom    the friends   are.       Your      task      is to      figure    out        if          it          is          possible for        them     to         redistribute         the        party     fee evenly.

Input
The       first       line       of         the        input     contains two       integers N          (2         <=        N          <=        10,000)  and       M         (0         <=        M <=        50,000), representing       the        number  of students         and       the        number  of         friendships,         respectively.

Each     of         the        following N          lines      contains a          single    integer   d          (-10,000 <=        d          <=        10,000), indicating           how      much            that       student  owes     (if d                0)         or         is          owed     (if         d          <          0).        The       student  had       already  paid      the            right      amount  of         the        party     fee        if          d          is          0.         It          is          guaranteed         that       sum of   all         d’s        is            0.

The       following M         lines      describe friendships.         Each     of         these     M         lines      contains two       integers a          and       b          (0         <= a          <          b          <          N),        meaning that       the        a-th       and       the        b-th       student  are        friends.  Note      that       a          friendship may      appear   more     than      once     and       it          is          also      possible that someone      is          friends   with       themselves.

Output
You       should   print      one       line       containing          POSSIBLE or         IMPOSSIBLE ,        indicating           if          it          is          possible for        them     to redistribute         the party fee        only      by         sending money   to         their      friends.

Example            1
 

Example            2