8 original problems in ICPC format. Mixed topics, calibrated difficulty. Standard input / standard output.
At the ICPC Latin America Regional, teams are ranked first by number of problems solved (descending), then by total penalty time (ascending). The penalty for a solved problem equals the submission time in minutes from the contest start, plus 20 penalty minutes for each wrong attempt submitted before the accepted submission. Problems that are never accepted incur no penalty at all.
You are given the complete submission log of a single team. Each entry records the problem letter, the submission time in minutes, and the verdict: AC for accepted or WA for wrong answer. For each problem, only the first AC matters — all submissions after an accepted one for that same problem are ignored.
Compute the number of problems solved and the total penalty for this team.
The first line contains an integer n (1 ≤ n ≤ 200), the total number of submissions. Each of the following n lines contains a capital letter P (A through L), an integer t (1 ≤ t ≤ 300), and a verdict string (AC or WA), separated by single spaces. Submissions appear in chronological order.
Print two integers on a single line separated by a space: the number of problems solved and the total penalty.
A string of brackets is called balanced if every opening bracket has a matching closing bracket of the same type in the correct nesting order. The three allowed bracket types are (), [], and {}.
Given a string consisting only of these six characters, find the minimum number of bracket characters you must insert anywhere in the string to make it balanced. You may not delete or replace any existing characters.
A single line containing a non-empty string s of length at most 105, consisting only of ( ) [ ] { }.
Print a single integer: the minimum number of insertions needed.
The city of Aguaverde is laid out on an R × C grid. Each cell has an integer elevation. During the annual flood season, water fills the lowlands up to level W.
A cell is called safe if there exists a path of cells leading from it to any cell on the border of the grid, such that every cell on that path — including the cell itself — has elevation strictly greater than W. Cells that are not safe are considered flooded. Movement between cells is allowed in the four cardinal directions only.
Given the elevation map and the water level W, count how many cells are flooded.
The first line contains integers R and C (1 ≤ R, C ≤ 1000) and W (0 ≤ W ≤ 106). Each of the following R lines contains C space-separated non-negative integers: the elevation of each cell (0 ≤ elevation ≤ 106).
Print a single integer: the number of flooded cells.
The city of Metrolandia has N stops and M bidirectional bus lines, each connecting two stops with a travel time in minutes. Some stops are designated transfer hubs; the rest are regular stops.
Every time you use a regular stop as an intermediate stop — meaning you arrive at it and then depart from it — you must pay a transfer fee of F additional minutes. Passing through a hub costs nothing extra. The fee applies only at intermediate stops, not at your origin or destination.
Find the minimum total travel time (including all fees) from stop S to stop T.
The first line contains integers N, M, F, S, T (2 ≤ N ≤ 105, 1 ≤ M ≤ 3·105, 0 ≤ F ≤ 104, 1 ≤ S, T ≤ N, S ≠ T). The second line contains an integer H (0 ≤ H ≤ N) followed by H space-separated hub stop indices. Each of the next M lines contains three integers u, v, w (1 ≤ u, v ≤ N, 1 ≤ w ≤ 104).
Print the minimum travel time. If no path exists from S to T, print -1.
You have N tiles numbered 1 to N. Each tile must be painted exactly one of K colors (numbered 1 to K). You are given M constraints, each of one of two types:
Type 0: tiles i and j must have the same color.
Type 1: tiles i and j must have different colors.
Count the number of valid colorings modulo 109 + 7. If no valid coloring exists, print 0.
The first line contains integers N, K, M (1 ≤ N ≤ 105, 1 ≤ K ≤ 109, 0 ≤ M ≤ 2·105). Each of the following M lines contains an integer t (0 or 1) and two integers i, j (1 ≤ i < j ≤ N), separated by spaces.
Print a single integer: the number of valid colorings modulo 109 + 7.
The kingdom of Pontia has N cities connected by M bidirectional roads. A road is called a bridge if its removal disconnects the road network. The king wants to add the minimum number of new roads so that no bridge remains — that is, every road in the resulting network belongs to at least one simple cycle.
The network is guaranteed to be connected. Find the minimum number of roads to add.
The first line contains integers N and M (2 ≤ N ≤ 3·105, N−1 ≤ M ≤ 5·105). Each of the next M lines contains integers u and v (1 ≤ u, v ≤ N, u ≠ v) denoting a bidirectional road. The graph may have multiple edges between the same pair of cities.
Print a single integer: the minimum number of roads to add.
A vault has a combination lock with N independent dials. Dial i has mi positions labeled 0 to mi − 1. You receive Q clues of the form: "the current position of dial i, taken modulo the prime p, equals r".
For each dial, count how many of its positions are consistent with every clue that mentions it. Print the product of these counts across all dials, modulo 109 + 7.
The first line contains N and Q (1 ≤ N ≤ 105, 0 ≤ Q ≤ 3·105). The second line contains N integers m1, …, mN (1 ≤ mi ≤ 109). Each of the following Q lines contains integers i (1-indexed dial), p (a prime, 2 ≤ p ≤ 107), and r (0 ≤ r < p).
Print a single integer: the total number of valid combinations modulo 109 + 7.
Alice and Bob play a game on N piles of stones, alternating turns with Alice going first. On each turn, the current player selects a non-empty pile i and removes exactly k stones from it. The move is valid only if k is a divisor of the current size of at least one other pile (a pile different from pile i). The player who cannot make any valid move loses.
Given the initial pile sizes, determine who wins with optimal play from both sides.
The first line contains N (1 ≤ N ≤ 5000). The second line contains N space-separated integers a1, …, aN (1 ≤ ai ≤ 106).
Print Alice if Alice wins with optimal play, or Bob if Bob wins.