Description

Bessie was teaching Jessie, her protege interesting in programming contests the binary facts of life. She explained that computers work in binary (base 2) and that all computer numbers in general are stored as 0's and 1's. Jessie was a bit unclear on the concept, so Bessie made her an exercise, shown below.

Write a program that converts an unsigned hexadecimal number to octal (base 8) form. Hexadecimal number can have at most 100,000 digits and is composed of digits and capital letters from A to F.

Note: a hexadecimal number is a special way of representing numbers in base 16. The digits 0-9 still correspond to 0-9, and then A (capital A!) corresponds to 10, B to 11, etc. (F stands for 15).

For example, the hexadecimal number A10B corresponds to the (decimal) number 10*16^3 + 1*16^2 + 0*16^1 + 11*16^0 = 41227. The corresponding octal (base 8) number would be 120413, since 1*8^5 + 2*8^4 + 0*8^3 + 4*8^2 + 1*8^1 + 3*8^0 = 41227.

Hint: there is an easier way to convert from hexadecimal to octal than by converting hexadecimal -> decimal -> octal. It might help to think about the numbers in binary (base 2).

Input

* Line 1: A single hexadecimal number. Multidigit numbers will have no leading zeroes (i.e., A1 instead of 00A1). 0 (by itself) is a valid input.

Output

* Line 1: The octal value with no leading zeros. If the input is 0,the output should also be 0.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Jessie was learning about programming contests at Bessie's knee. "Do they play games?" she asked.
"Oh yes," Bessie nodded sagely. "Here's a classic."
MasterMind is a classic two player game. One of the players is the 'codemaker'; she picks a four digit secret number S (1000 <= S <= 9999). The other player is the 'codebreaker' who repeatedly guesses four digit numbers until she solves the code.

The codemaker provides feedback that comprises two integers for each codebreaker guess G_i (1000 <= G_i <= 9999). For each codebreaker guess, the codemaker's feedback comprises two integers:
* The first integer C_i (0 <= C_i <= 4) specifies how many of the
guess's digits are correct and in their correct location in the
secret number
* The second integer W_i (0 <= W_i <= 4-C_i) specifies how many of
the remaining digits (i.e., those not described by C_i) are correct
but in the wrong location.

For example, suppose codemaker's secret number is 2351. If codebreaker guesses 1350, the codemaker provides the feedback "2 1", since 3 and 5 are in correct locations in the number, and 1 is in the wrong location. As another example, if the secret number is 11223 (in a five-digit version of mastermind) and the guess is 12322, then the feedback would be "2 2".

Below is a sample game where the secret number is 2351:

        Correct digits in correct location
        | Correct digits in wrong location
Guess   | |
3157    1 2
1350    2 1
6120    0 2
2381    3 0
2351    4 0

For this task, you are given N (1 <= N <= 100) guesses with their feedback in the middle of a game. You are asked to output the smallest four digit number which can be a candidate for codemaker's
secret code (i.e., which satisfies all the constraints).

If there are no such numbers, output "NONE" (without the quotes).

Input

* Line 1: A single integer: N
* Lines 2..N+1: Line i+1 contains guess i and its two responses expressed as three space-separated integers: G_i, C_i, and W_i

Output

* Line 1: A single integer that is the smallest four-digit number (same range as the secret integer: 1000..9999) which could be the secret code. If there are no such numbers, output a single line containing the word "NONE" (without quotes).

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Bessie's friend Jessie wanted to enter a programming contest. "What are the tasks like?" she asked.

Bessie, known to be knowledgeable about so many things, said "Here is a typical problem that folks solve early in their competitive career. See if you can solve it."

Perhaps you can solve it, too.

You are given two sequences of integers, S1 and S2. S1 has length L1 (1 <= L1 <= 180) and S2 has length L2 (1 <= L2 <= 180). Your job is to print out the length of the longest contiguous subsequence of numbers common to both S1 and S2. Ordered sequence S1 has elements S1_1, S1_2, ..., S1_L1 (-100 <= S1_i <= 100); S2 has elements S2_i (-100 <= S2_i <= 100).

A contiguous subsequence is a consecutive run of numbers in that sequence. The subsequences of 1 2 3 1 are: the empty sequence, "1", "1 2", "1 2 3", "1 2 3 4", "2", "2 3", "2 3 1", "3", "3 1", and a repeat occurrence of "1".

Input

* Line 1: Two space-separated integers: L1 and L2
* Lines 2..L1+1: Line i+1 contains a single integer: S1_i
* Lines L1+2..L1+L2+1: Line L1+i+1 contains a integer: S2_i

Output

* Line 1: A single integer, the length of the longest contiguous subsequence of S1 and S2

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Farmer John has to take his annual farming license test. The test comprises N (1 <= N <= 1,000,000) true/false questions. After FJ's dismal performance on last year's test Bessie wishes to help him.

Bessie has inside information that the number of questions whose answer is true will be one of t_1, t_2, t_3,..., or t_K (0 <= t_i <= N; 0 <= K <= 10,000) -- even though Bessie has no information about any answer to any specific question. Bessie wants to know the best score that FJ is guaranteed achieve by exploiting this information carefully, even if he doesn't know the actual answers to any test questions.

To demonstrate Bessie's idea, consider a license test with N=6 questions where Bessie knows that the number of questions with the answer 'true' is either 0 or 3. FJ can always get at least 3 answers correct using logic like this: If FJ answers 'false' on every question and there are 0 questions with the answer 'true' then he will get all 6 correct. If there are 3 questions with the answer 'true' then he will get 3 answers correct. So as long as he marks every answer as 'false' he is guaranteed to get at least 3 correct without knowing any answer to the test questions.

On the other hand, consider what happens if FJ chooses an inferior strategy: he guesses that some 3 answers are 'true' and the other 3 are 'false'. If it turns out that NO answers are 'true' then FJ will get 3 answers correct, the ones he guessed were false. If 3 answers are 'true' then FJ could get as few as 0 answers correct. If he answered incorrectly on all 3 of that answers for which he guessed 'true', and the other 3 (for which he guessed 'false') are true, then he gets 0 correct answers. Even though FJ could get 3 correct in this case by guessing 'false' every time, he can not always guarantee even 1 correct by guessing some 3 answers as 'true', so this strategy can not guarantee getting any answer correct. FJ should use the previous paragraph's strategy.

Given Bessie's inside information, determine the number of answers FJ can always get correct using this information assuming he uses it optimally.

Input

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

Output

* Line 1: A single integer, the best score FJ is guaranteed to achieve

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Bessie is preparing her race car for the upcoming Grand Prix, but she wants to buy some extra parts to improve the car's performance. Her race car currently has mass M (1 <= M <= 1,000) and is able to push itself forward with a force of F (1 <= F <= 1,000,000). The Race Car Performance Store has N (1 <= N <= 10,000) parts conveniently numbered 1..N. Bessie can buy as many or as few parts as she wishes though the store stocks no more than one instance of each part.

Part P_i adds force F_i (1 <= F_i <= 1,000,000) and has mass M_i (1 <= M_i <= 1,000). Newton's Second Law decrees that F = MA, where F is force, M is mass, and A is acceleration. If Bessie wants to maximize the total acceleration of her race car (and minimize the mass otherwise), which extra parts should she choose?

Consider a race car with initial F=1500 and M=100. Four parts are available for enhancement:
          i  F_i  M_i
          1  250   25
          2  150    9
          3  120    5
          4  200    8
Adding just part 2, e.g., would result in an acceleration of (1500+150)/(100+9) = 15.13761.

Below is a chart of showing the acceleration for all possible combinations of adding/not-adding the four parts (in column one, 1=part added, 0=part not added):

Parts   Aggregate   Aggregate       
1234        F           M       F/M
0000      1500         100    15.0000
0001      1700         108    15.7407
0010      1620         105    15.4286
0011      1820         113    16.1062
0100      1650         109    15.1376
0101      1850         117    15.8120
0110      1770         114    15.5263
0111      1970         122    16.1475 <-- highest F/M
1000      1750         125    14.0000
1001      1950         133    14.6617
1010      1870         130    14.3846
1011      2070         138    15.0000
1100      1900         134    14.1791
1101      2100         142    14.7887
1110      2020         139    14.5324
1111      2220         147    15.1020
Thus, the best additional part combination is parts 2, 3, and 4.

Input

* Line 1: Three space-separated integers: F, M, and N
* Lines 2..N+1: Line i+1 contains two space separated integers: F_i and M_i

Output

* Lines 1..P: The index values of P extra parts, one per line, that Bessie should add to her racecar. If she should not add any, output 'NONE' (without quotes). The output should be given in increasing order, so if the optimal set of parts is {2,4,6,7}, then the output should be in the order 2,4,6,7 and not, for example, 4,2,7,6. Solutions will be unique.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Bessie is planning the annual Great Cow Gathering for cows all across the country and, of course, she would like to choose the most convenient location for the gathering to take place.

Each cow lives in one of N (1 <= N <= 100,000) different barns (conveniently numbered 1..N) which are connected by N-1 roads in such a way that it is possible to get from any barn to any other barn via the roads. Road i connects barns A_i and B_i (1 <= A_i <= N; 1 <= B_i <= N) and has length L_i (1 <= L_i <= 1,000). The Great Cow Gathering can be held at any one of these N barns. Moreover, barn i has C_i (0 <= C_i <= 1,000) cows living in it.

When choosing the barn in which to hold the Cow Gathering, Bessie wishes to maximize the convenience (which is to say minimize the inconvenience) of the chosen location. The inconvenience of choosing barn X for the gathering is the sum of the distances all of the cows need to travel to reach barn X (i.e., if the distance from barn i to barn X is 20, then the travel distance is C_i*20). Help Bessie choose the most convenient location for the Great Cow Gathering.

Consider a country with five barns with [various capacities] connected by various roads of varying lengths. In this set of barns, neither barn 3 nor barn 4 houses any cows.
      1     3     4     5
      @--1--@--3--@--3--@[2]
     [1]    |
            2
            |
            @[1]
             2
Bessie can hold the Gathering in any of five barns; here is the table of inconveniences calculated for each possible location:

  Gather      ----- Inconvenience ------
  Location    B1  B2  B3  B4  B5   Total
     1         0    3   0   0   14     17
     2         3    0   0   0   16     19
     3         1    2   0   0   12     15
     4         4    5   0   0   6      15
     5         7    8   0   0   0      15
If Bessie holds the gathering in barn 1, then the inconveniences
from each barn are:
      Barn 1     0 -- no travel time there!
      Barn 2     3 -- total travel distance is 2+1=3  x 1 cow = 3
      Barn 3     0 -- no cows there!
      Barn 4     0 -- no cows there!
      Barn 5    14 -- total travel distance is 3+3+1=7 x 2 cows = 14
So the total inconvenience is 17.

The best possible convenience is 15, achievable at by holding the Gathering at barns 3, 4, or 5.

Input

* Line 1: A single integer: N
* Lines 2..N+1: Line i+1 contains a single integer: C_i
* Lines N+2..2*N: Line i+N+1 contains three integers: A_i, B_i, and L_i

Output

* Line 1: The minimum inconvenience possible

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Farmer John recently opened up a new barn and is now accepting stall allocation requests from the cows since some of the stalls have a better view of the pastures.

The barn comprises N (1 <= N <= 100,000) stalls conveniently numbered 1..N; stall i has capacity C_i cows (1 <= C_i <= 100,000). Cow I may request a contiguous interval of stalls (A_i, B_i) in which to roam (1 <= A_i <= N; A_i <= B_i <= N), i.e., the cow would like to wander among all the stalls in the range A_i..B_i (and the stalls must always have the capacity for her to wander).
Given M (1 <= M <= 100,000) stall requests, determine the maximum number of them that can be satisfied without exceeding stall capacities.

Consider both a barn with 5 stalls that have the capacities shown and a set cow requests:

Stall id:      1   2   3   4   5
             +---+---+---+---+---+
Capacity:    | 1 | 3 | 2 | 1 | 3 | 
             +---+---+---+---+---+
Cow 1         XXXXXXXXXXX             (1, 3)
Cow 2             XXXXXXXXXXXXXXX     (2, 5)
Cow 3             XXXXXXX             (2, 3)
Cow 4                     XXXXXXX     (4, 5)

FJ can't satisfy all four cows, since there are too many requests for stalls 3 and 4.

Noting that Cow 2 requests an interval that includes stalls 3 and 4, we test the hypothesis that cows 1, 3, and 4 can have their requested stalls. No capacity is exceeded, so the answer for this set of data is 3 -- three cows (1, 3, and 4) can have their requests satisfied.

Input

* Line 1: Two space-separated integers: N and M
* Lines 2..N+1: Line i+1 contains a single integer: C_i
* Lines N+2..N+M+1: Line i+N+1 contains two integers: A_i and B_i

Output

* Line 1: The maximum number of requests that can be satisfied

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

The beta version of StarCowraft II is ready! Farmer John and Bessie are testing it, trying different strategies in one-on-one battles against each other's armies. The goal in StarCowraft II is to defeat your opponent's army in a battle.
Each player's army fights in a battle. An army comprises as many as three different types of 'units' with respective strengths denoted by constant positive real numbers unknown to the players: cattlebruisers with strength S1, cow templars with strength S2, and ultracows with strength S3. The only given bounding information is that no unit is more than 100 times as strong as any another unit.
An army's total strength is the sum of the individual strengths of each of its units. An army that has, among others units, 23 cattlebruisers would gain 23*S1 strength just from the cattlebruisers.
When two opposing armies fight in a battle, the army with a higher total strength value wins.  If the armies have exactly equal strength values, one of the players randomly wins.
Farmer John and Bessie played N (0 <= N <= 300) "test battles". In the i-th test battle, FJ's army had J1_i cattlebruisers, J2_i cow templars, and J3_i ultracows (0 <= J1_i + J2_i + J3_i <= 1,000). Similarly, Bessie's army had B1_i cattlebruisers, B2_i cow templars, and B3_i ultracows (0 <= B1_i + B2_i + B3_i <= 1,000). After their armies fought against each other, FJ and Bessie recorded the winner as a single 'victory letter' V_i: "J" if Farm John won the battle; "B" if Bessie won.
Although these victory results are the only information that they have, they hope to predict some of the results of additional battles if they are given the unit compositions of two opposing armies. For some battles, though, they know it might not be possible to determine the winner with certainty.
Given the results of the N test battles that Farmer John and Bessie already played, write a program that decides the winner (if possible) for M (1 <= M <= 2,000) new battles.
The results reported for the test battles are correct; there exists at least one set of strength values which are consistent with the results.
For purposes of demonstrating the army strength evaluation functions, consider these test battles fought in a game where we (but neither FJ nor Bessie) know that S1=9.0, S2=7.0, and S3=4.0:
   ---- Farmer John ----    ------- Bessie ------    Battle
   J1  J2  J3 J_Strength    B1  B2  B3 B_Strength   Outcome
    6   5   4    105           5   4   7    101          J
    5   4   2     81           3   5   5     82          B
    9   0  10    121           8   2   7    114          J

These results connote the following deduced results for the reasons
shown:

   ---- Farmer John ----    ------- Bessie ------    Battle
   J1  J2  J3 J_Strength    B1  B2  B3 B_Strength   Outcome
    6   6   4    112        5   4   7      101          J
              FJ's army is even stronger than in test battle 1
    9   0  10    121        8   2   6      110          J
              Bessie's army is even weaker than in test battle 3

Input

* Line 1: Two space-separated integers: N and M
* Lines 2..N+1: Line i+1 describes a test battle with seven space-separated items -- a victory letter and six space-separated integer  unit counts: V_i, J1_i, J2_i, J3_i, B1_i, B2_i, and B3_i
* Lines N+2..N+M+1: Line i+N+1 describes a "new battle" using six space-separated integers: J1_i, J2_i, J3_i, B1_i, B2_i, and B3_i

Output

* Lines 1..M: Line i contains the outcome of the i-th new battle: "J" if Farmer John definitely wins, "B" if Bessie definitely wins, and "U" (undecidable) if it is impossible to decide the winner with the given information.

Sample Input  Download

Sample Output  Download

Tags

Discuss