Description

As every cow does occasionally, Bessie has lost herself in the woods! She desperately needs to get back to the barn but has no idea where to go.

The woods can be thought of as an R x C grid (1 <= R <= 5; 1 <= C <= 5). Bessie is located in the lower left corner at row 1, column 1; the barn is located in the upper right corner at in row R, column C.  Each square in the grid is either empty (denoted by '.') or blocked by a tree (denoted by 'T'). Bessie's square and the barn will always be empty.

From a given square, Bessie may move to any adjacent square (one that shares a long edge with Bessie's current square) as long as it is empty. As Bessie is quite a smart cow, she never visits a square twice on the way back to the barn.

Determine the number of different ways Bessie can take that lead her from her initial position back to the barn while visiting at most K different squares (1 <= K <= R * C).
By way of example, consider this forest:

        ....
        .T..
        ....

Bessie has a number of ways to get to the upper right corner, here are all seven of them and their path lengths (the number of squares visited):

         cdef  ...f  ..ef  ..gh  cdeh  cdej  ...f 
         bT..  .T.e  .Td.  .Tfe  bTfg  bTfi  .Tde 
         a...  abcd  abc.  abcd  a...  a.gh  abc. 
Length:    6     6     6     8     8    10    6

Input

* Line 1: Three space-separated integers: R, C, and K
* Lines 2..R+1: Line i+1 contains the C characters representing row R+1-i of the forest (with no spaces)

Output

* Line 1: A single integer that is the number of different paths, visiting at most K squares, that Bessie can take to get back to the barn. Note that this number will always fit into a signed 32-bit integer.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

FJ is going to teach his cows how to play a song. The song consists of N (1 <= N <= 100) notes, and the i-th note lasts for B_i (1 <= B_i <= 100) beats. The cows will begin playing the song at time 0; thus, they will play note 1 from time 0 to time B_1 - 1, note 2 fromtime B_1 to time B_1 + B_2 - 1, etc.

The cows have lost interest in the song, as they feel that it is long and boring. Thus, to make sure his cows are paying attention, FJ asks them Q (1 <= Q <= 1,000) questions of the form, "During the beat at time T_i (0 <= T_i < length of song), which note should you be playing?" The cows need your help to answer these questions.

By way of example, consider a song with these specifications: note 1 for length 2, note 2 for length 1, and note 3 for length 3:

NOTES    1   1   2   3   3   3
       +---+---+---+---+---+---+
TIME     0   1   2   3   4   5

Input

* Line 1: Two space-separated integers: N and Q
* Lines 2..N+1: Line i+1 contains a single integer: B_i
* Lines N+2..N+Q+1: Line N+i+1 contains a single integer: T_i

Output

* Lines 1..Q: Line i contains the a single integer that is the note the cows should be playing at time T_i

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Bessie, always wishing to optimize her life, has realized that she really enjoys visiting F (1 <= F <= P) favorite pastures F_i of the P (1 <= P <= 500; 1 <= F_i <= P) total pastures (conveniently numbered 1..P) that compose Farmer John's holdings.

Bessie knows that she can navigate the C (1 <= C <= 8,000) bidirectional cowpaths (conveniently numbered 1..C) that connect various pastures to travel to any pasture on the entire farm. Associated with each path P_i is a time T_i (1 <= T_i <= 892) to traverse that path (in either direction) and two path endpoints a_i and b_i (1 <= a_i <= P; 1 <= b_i <= P).

Bessie wants to find the number of the best pasture to sleep in so that when she awakes, the average time to travel to any of her F favorite pastures is minimized.

By way of example, consider a farm laid out as the map below shows, where *'d pasture numbers are favorites. The bracketed numbers are times to traverse the  cowpaths.

            1*--[4]--2--[2]--3
                     |       |
                    [3]     [4]
                     |       |
                     4--[3]--5--[1]---6---[6]---7--[7]--8*
                     |       |        |         |
                    [3]     [2]      [1]       [3]
                     |       |        |         |
                    13*      9--[3]--10*--[1]--11*--[3]--12*

The following table shows distances for potential 'best place' of pastures 4, 5, 6, 7, 9, 10, 11, and 12:

                       * * * * * * Favorites * * * * * *
 Potential      Pasture Pasture Pasture Pasture Pasture Pasture     Average
Best Pasture       1       8      10      11      12      13        Distance
------------      --      --      --      --      --      --      -----------
    4              7      16       5       6       9       3      46/6 = 7.67
    5             10      13       2       3       6       6      40/6 = 6.67
    6             11      12       1       2       5       7      38/6 = 6.33
    7             16       7       4       3       6      12      48/6 = 8.00
    9             12      14       3       4       7       8      48/6 = 8.00
   10             12      11       0       1       4       8      36/6 = 6.00 ** BEST
   11             13      10       1       0       3       9      36/6 = 6.00
   12             16      13       4       3       0      12      48/6 = 8.00

Thus, presuming these choices were the best ones (a program would have to check all of them somehow), the best place to sleep is pasture 10.

Input

* Line 1: Three space-separated integers: P, F, and C
* Lines 2..F+1: Line i+2 contains a single integer: F_i
* Lines F+2..C+F+1: Line i+F+1 describes cowpath i with three space-separated integers: a_i, b_i, and T_i

Output

* Line 1: A single line with a single integer that is the best pasture in which to sleep. If more than one pasture is best, choose the smallest one.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Farmer John always wants his cows to have enough water and thus has made a map of the N (1 <= N <= 700) water pipes on the farm that connect the well to the barn. He was surprised to find a wild mess of different size pipes connected in an apparently haphazard way. He wants to calculate the flow through the pipes.

Two pipes connected in a row allow water flow that is the minimum of the values of the two pipe's flow values. The example of a pipe with flow capacity 5 connecting to a pipe of flow capacity 3 can be reduced logically to a single pipe of flow capacity 3:

  +---5---+---3---+    ->    +---3---+

Similarly, pipes in parallel let through water that is the sum of their flow capacities:

    +---5---+
 ---+       +---    ->    +---8---+
    +---3---+

Finally, a pipe that connects to nothing else can be removed; it contributes no flow to the final overall capacity:

    +---5---+
 ---+               ->    +---3---+
    +---3---+--

All the pipes in the many mazes of plumbing can be reduced using these ideas into a single total flow capacity.

Given a map of the pipes, determine the flow capacity between the well (A) and the barn (Z).

Consider this example where node names are labeled with letters:

                 +-----------6-----------+
        A+---3---+B                      +Z
                 +---3---+---5---+---4---+
                         C       D

Pipe BC and CD can be combined:

                 +-----------6-----------+
        A+---3---+B                      +Z
                 +-----3-----+-----4-----+
                             D

Then BD and DZ can be combined:

                 +-----------6-----------+
        A+---3---+B                      +Z
                 +-----------3-----------+

Then two legs of BZ can be combined:

                 B
        A+---3---+---9---+Z

Then AB and BZ can be combined to yield a net capacity of 3:

        A+---3---+Z

Write a program to read in a set of pipes described as two endpoints  and then calculate the net flow capacity from 'A' to 'Z'. All networks in the test data can be reduced using the rules here.

Pipe i connects two different nodes a_i and b_i (a_i in range 'A-Za-z'; b_i in range 'A-Za-z') and has flow F_i (1 <= F_i <= 1,000). Note that lower- and upper-case node names are intended to be treated as different.

The system will provide extra test case feedback for your first 50 submissions.

Input

* Line 1: A single integer: N
* Lines 2..N + 1: Line i+1 describes pipe i with two letters and an integer, all space-separated: a_i, b_i, and F_i

Output

* Line 1: A single integer that the maximum flow from the well ('A') to the barn ('Z')

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

The cows have a new laser-based system so they can have casual conversations while out in the pasture which is modeled as a W x H grid of points (1 <= W <= 100; 1 <= H <= 100).

The system requires a sort of line-of-sight connectivity in order to sustain communication. The pasture, of course, has rocks and trees that disrupt the communication but the cows have purchased diagonal mirrors ('/' and '' below) that deflect the laser beam through a 90 degree turn. Below is a map that illustrates the problem.

H is 8 and W is 7 for this map.  The two communicating cows are notated as 'C's; rocks and other blocking elements are notated as '*'s:

7 . . . . . . .         7 . . . . . . .
6 . . . . . . C         6 . . . . . /-C
5 . . . . . . *         5 . . . . . | *
4 * * * * * . *         4 * * * * * | *
3 . . . . * . .         3 . . . . * | .
2 . . . . * . .         2 . . . . * | .
1 . C . . * . .         1 . C . . * | .
0 . . . . . . .         0 . -------/ .
  0 1 2 3 4 5 6           0 1 2 3 4 5 6

Determine the minimum number of mirrors M that must be installed to maintain laser communication between the two cows, a feat which is always possible in the given test data.

Input

* Line 1: Two space separated integers: W and H
* Lines 2..H+1: The entire pasture.

Output

* Line 1: A single integer: M

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Wisconsin has had an earthquake that has struck Farmer John's farm!
The earthquake has damaged some of the pastures so that they are unpassable. Remarkably, none of the cowpaths was damaged.

As usual, the farm is modeled as a set of P (1 <= P <= 30,000) pastures conveniently numbered 1..P which are connected by a set of C (1 <= C <= 100,000) non-directional cowpaths conveniently numbered 1..C. Cowpath i connects pastures a_i and b_i (1 <= a_i <= P; 1 <= b_i <= P). Cowpaths might connect a_i to itself or perhaps might connect two pastures more than once. The barn is located in pasture 1.

A total of N (1 <= N <= P) cows (in different pastures) sequentially contact Farmer John via moobile phone with an integer message report_j (2 <= report_j <= P) that indicates that pasture report_j is undamaged but that the calling cow is unable to return to the barn from pasture report_j because she could not find a path that
does not go through damaged pastures.
After all the cows report in, determine the minimum number of pastures (including ones that are uncrossable) from which it is not possible to return to the barn.

Note: Feedback on some of the test data will be provided on the first 50 submissions

Input

* Line 1: Three space-separated integers: P, C, and N
* Lines 2..C+1: Line i+1 describes cowpath i with two integers: a_i and b_i
* Lines C+2..C+N+1: Line C+1+j contains a single integer: report_j

Output

* Line 1: A single integer that is the minimum count of pastures from which a cow can not return to the barn (including the damaged pastures themselves)

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Following up on a journal article about increasing milk production, Bessie has become the Baric Bovine by studying atmospheric pressure in order to curry favor with Farmer John.

She takes N (1 <= N <= 100) measurements conveniently named M_1 through M_N during the day (1 <= M_i <= 1,000,000); these measurements are numbered in the order in which Bessie observed them.

In order to characterize the day's atmospheric pressure readings, she is interested in finding a subset of the measurements (given by the K (1 <= K <= N) indices s_j where 1 <= s_1 < s_2 < ... < s_K <= N) that accurately reflects the entire set, i.e., limits the error as described below.

In any subset of measurements, an error is incurred for each measurement (1) before the first member of the subset, (2) between two consecutive measurements in the subset, and (3) after the last member of the subset. The total error value for a given set of s_j values is the sum of each of the individual errors.

Specifically, for all measurements whose index i is not one of the s_j values:

* if i is less than s_1, then the sample error is:
             2 * | M_i - M_(s_1) |

* if i is between s_j and s_(j+1), then the sample error is
            | 2 * M_i - Sum(s_j, s_(j+1)) |  
  where Sum(x, y) = M_x + M_y;

* if i is greater than s_K, then the sample error is
             2 * | M_i - M_(s_K) |

Given a maximum error value E (1 <= E <= 1,000,000), determine the  size of the smallest subset of measurements that produces an error of at most E.

Input

* Line 1: Two space-separated integers: N and E
* Lines 2..N+1: Line i+1 contains a single integer: M_i

Output

* Line 1: Two space-separated integers: the size of the smallest subset of measurements that produces an error of at most E and the least possible error for the subset of that size.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Gremlins have infested the farm. These nasty, ugly fairy-like creatures thwart the cows as each one walks from the barn (conveniently located at pasture_1) to the other fields, with cow_i traveling to from pasture_1 to pasture_i. Each gremlin is personalized and knows the quickest path that cow_i normally takes to pasture_i. Gremlin_i
waits for cow_i in the middle of the final cowpath of the quickest route to pasture_i, hoping to harass cow_i.

Each of the cows, of course, wishes not to be harassed and thus chooses an at least slightly  different route from pasture_1 (the barn) to pasture_i.

Compute the best time to traverse each of these new not-quite-quickest routes that enable each cow_i that avoid gremlin_i who is located on the final cowpath of the quickest route from pasture_1 to pasture_i.

As usual, the M (2 <= M <= 200,000) cowpaths conveniently numbered 1..M are bidirectional and enable travel to all N (3 <= N <= 100,000) pastures conveniently numbered 1..N. Cowpath i connects pastures a_i (1 <= a_i <= N) and b_i (1 <= b_i <= N) and requires t_i (1 <= t_i <= 1,000) time to traverse. No two cowpaths connect the same two pastures, and no path connects a pasture to itself (a_i != b_i). Best of all, the shortest path regularly taken by cow_i from pasture_1
to pasture_i is unique in all the test data supplied to your program.

By way of example, consider these pastures, cowpaths, and [times]:

      1--[2]--2-------+
      |       |       |
     [2]     [1]     [3]
      |       |       |
      +-------3--[4]--4

   TRAVEL     BEST ROUTE   BEST TIME   LAST PATH
p_1 to p_2       1->2          2         1->2
p_1 to p_3       1->3          2         1->3
p_1 to p_4      1->2->4        5         2->4

When gremlins are present:

   TRAVEL     BEST ROUTE   BEST TIME    AVOID
p_1 to p_2     1->3->2         3         1->2
p_1 to p_3     1->2->3         3         1->3
p_1 to p_4     1->3->4         6         2->4

Input

* Line 1: Two space-separated integers: N and M
* Lines 2..M+1: Three space-separated integers: a_i, b_i, and t_i

Output

* Lines 1..N-1: Line i contains the smallest time required to travel from pasture_1 to pasture_i+1 while avoiding the final cowpath of the shortest path from pasture_1 to pasture_i+1. If no such path exists from pasture_1 to pasture_i+1, output -1 alone on the line.

Sample Input  Download

Sample Output  Download

Tags

Discuss