Homework 03 Solution

Ho
Description
Worm holes provide connections from one point in the galaxy to another. Unfortunately, they can have instabilities that will cause them to collapse when a ship tries to pass through them. Fortunately, Oganesson Dynamics Inc.'s top engineers have proposed a new way to build worm-hole stabilizers! Even better, these new stabilizers can repair multiple instabilities, if needed, though at an increasing cost for each additional one.

You have access to k stabilizers and there are n instabilities that need to be fixed. Each instability i has a base energy cost of ei terawatts. The first instability fixed by an individual stabilizer has its cost multiplied by × 1, the second by × 2, and so on, so that the kth instability costs × k.

Given n, k, and the base cost for each instability, find and print the minimum total energy (in terawatts) for all of the instabilities to be repaired.

Note: instabilities can be repaired in ANY ORDER.

Input Format

The first line contains two space-separated integers describing the respective values of n and k.
The second line contains n space-separated positive integers describing the respective values of e0, e1, ..., en-1
Constraints

1 ≤ n, k ≤ 100
1 ≤ ei ≤ 106
answer < 231
0 ≤ i < n
Output Format

 Print the total energy required to repair all of the instabilities.

Example 0
Sample Input

3 3
2 5 6
Sample Output

13
Explanation

There are three instabilities and three stabilizers. Since each stabilizer can fix one instability, there is only a mulitple of × 1 for each. The total cost is:

(2 × 1) + (5 × 1) + (6 × 1) = 13

Example 1
Sample Input

7 3
6 1 28 10 15 3 21
Sample Output

105





Description
Portable shield generators can keep ships, buildings, and even people safe from harm. Oganesson Dynamics Inc. has a blueprint that will produce a device with a long series of aegis cells that can be individually turned on to produce a shield. Each cell has an individual contribution to shield strength. The total shield strength is the sum of these individual contributions.

There's a problem though! The cells get very warm when activated, and if you turn on two neighboring ones at the same time, they will overheat. What is the maximum total shield strength possible?

Given a series of N aegis cells where cell i, in order, has a shield strength of Si , determine the maximum total shield strength that can be generated.

HINT: an interactive webpage that will step you through a similar problem can be found at: http://www.cse.msu.edu/~ofria/cse431/DP/

Input Format

The first line provides N, the number of aegis cells in the row.
The second line has N values, separated by spaces, indicating the individual contributions to total shield strength (S0 through SN-1 ).
Constraints

1 ≤ N ≤ 106
1 ≤ Si ≤ 1010
Output Format

A single value indicating the maximum total shield strength possible.

Example 0
Sample Input

5
2 10 1 3 10
Sample Output

20
Explanation

There are five aegis cells, with shield levels of 2, 10, 1, 3, and 10, respectively.

If we activate the second and fifth cells, we will have a total of 20 shield strength (no other legal combination can produce more than 20).

Example 1
Sample Input

5
20 10 1 10 20
Sample Output

41




Description
A set of documents describe how to build a faster-than-light communications system. The only problem is that when a message is sent, its binary representation is encoded and must be decrypted on the other side. The binary string (B ) is of length N. This string is written down K times, shifted respectively by 0, 1, ..., K - 1 bits.

For example, if B = 1001010 and K = 4 it would appear as:

1001010   
 1001010  
  1001010 
   1001010
Next, calculate XOR in every column and write it down. This number representing the encoded message is call S. For example, XOR-ing the numbers in the above example results in:

1110100110
Both the encoded message (S ) and the value K are sent to the recipient.

You must implement a decoding algorithm that will take S and K and reproduce the original bitstring B (in the above case, you would output '1001010').

Input Format

The first line contains two integers, N and K.
The second line contains the received string S of length N + K - 1, consisting of ones and zeros.
Constraints

1 ≤ N,K ≤ 106
Output Format

The decoded message of length N, consisting of ones and zeros.

Example 0
Sample Input

7 4
1110100110
Sample Output

1001010
Explanation

1001010
 1001010
  1001010
   1001010   XOR
----------
1110100110
So, how did we find this solution?






Description
Of all of their discoveries, Oganesson Dynamics is most excited by their new warp engines. The problem is that they go through the quadlithium crystals that power them much too quickly. Can you help figure out how to get the crystals to last for as long as possible?

Warp engines apply one of K different frequencies to a crystal to extract power from it for an hour, after which the crystal breaks into smaller crystals (some of which may be used again!). Each frequency i is associated with a fracture value Fi  indicating the size of the crystals that this one will break into when used.

Frequency i can only be used if S (the size of the crystal) is greater than Fi and can be evenly divided by Fi . The crystal then breaks into P/Fi  crystals each of which is size is size Fi .

Since each application of a frequency to a crystal can power the engine for an hour, what is the LONGEST amount of time (in hours) that the ship can fly given a single starting crystal of size N ?

Input Format

The first line contains an integer, T, denoting the number of tests to be performed. The subsequent T pairs of lines describe each test in the following format:

The first line contains two space-separated integers describing the respective values of S (the size of the initial crystal) and K (the number of available frequencies).
The second line contains K space-separated integers describing the values of F0 through FK-1.
Constraints

1 ≤ T ≤ 10
1 ≤ S ≤ 1012
1 ≤ K ≤ 1000
1 ≤ Fi  ≤ 1012
Output Format

For each test, determine the maximum number of hours that the ship can be powered given the starting crystal; output this value on its own line.

Example 0
Sample Input

1
12 3
2 3 4
Sample Output

4




Description
The individual engineers at Oganesson Dynamics are most excited about the photon swords that they've discovered. Now they want to see just how hot they can make those swords without melting the handles.

Each sword has N buttons, each of which increases the heat by a fixed (integer) amount, to a limit of K (also an integer), beyond which the handle will melt. Given the amount of heat each button produces (B0 through BN-1), determine the maximum heat possible for the sword.

For example, if there were two buttons that put out 9 and 12 units of heat respectively, and the sword could handle a maximum of 31 units, you would be able to produce a maximum of 30 units by pressing the first button twice and the second button once. Any more presses and the device would melt. If there were also a button for 1 unit, you would be able to maximize the heat to a perfect 31.

Input Format

The first line contains T, the number of test cases.
Each test comprises two lines:
The first line contains two integers, N and K, representing the number of buttons and maximum heat, respectively.
The second line consists of space separated integers, B0 through BN-1, representing the heat output of each button.
Constraints

1 ≤ T ≤ 10
1 ≤ N, K ≤ 2000
1 ≤ Bi ≤ 2000
Output Format

Output T lines, the maximum heat that can be produced for each test case which is as near as possible including, but not exceeding, the heat limit ( K ).

Example 0
Sample Input

3
3 12
1 6 9
5 9
3 4 4 4 8
4 11
5 7 8 9
Sample Output

12
9
10




Description
Oganesson Dynamics have blueprints for a carbon sequestration station that will pull carbon out of the atmosphere until it has been reduced to a target level.

Every day a station can pull a configurable number of units of carbon out of the atmosphere. Unfortunately, the amount removed must always be set to a power of two. So, it could pull 1, 2, 4, 8, 16, or 32 units in a day (or more!), but NOT exactly 5 or 20 units.

Given a starting number of units (N) and a goal number (G), can you figure out the fewest number of days it would take to reach the target?

Input Format

The first line will contain a value T indicating the number of planets (the number of test cases).
The next T lines will each contain two integers N, indicating a number of units of carbon in the atmosphere, and G, the goal number of units for when the station is finished.
Constraints

1 ≤ T ≤ 200,000
1 ≤ G ≤ N ≤ 264 - 1
Output Format

N lines, each indicating the number of days it would take to reduce the carbon of a given planet down to the target level.

Example 0
Sample Input

1
12 1
Sample Output

 3




Description
There are many types and sizes of smart bricks; all of them will automatically link together when touching. Given N types of bricks where each brick i has length Li , how many ways are there to lay them in a line with total length Ltotal ?

Input Format

The first line of the input provides T, the total number of test cases.
The next T pairs of lines describe a single test case:
The first line in a test case privides the number of brick types (N) and the total target length ( Ltotal ).
The second line has N values, each indicating the length of each available brick.
Constraints

1 ≤ T ≤ 10
1 ≤ N ≤ 50
1 ≤ Ltotal ≤ 106
1 ≤ Li ≤ 106
Output Format

T lines, one per test case, each indicating the number of combinations possible to make a line of that total length. Some of the values are quite large, so mod your answer by 1000000009.

Example 0
Sample Input

2
2 5
1 2
2 7
1 3
Sample Output

8
9




Description
Oganesson Dynamics have design a new type of modular supercomputer. Each of the computer's modules are able to stack vertically together. All of the modules are rectangular cubes of the same height and depth (1 unit long each), but their widths come in 4 lengths (1, 2, 3, and 4 units long). Each module has input ports on its bottom and output ports on its top. Thus, in order for there to be connectivity between the entire supercomputer, there must NOT be any vertical split that goes through every row in the same position (doing so would partition the computer).

Oganesson Dynamics needs to know how many possible configurations of the supercomputer are possible given a particular set of dimensions (width and height).

Important things to remember:

The assembled computer must be built horizontally, meaning that pieces are laid horizontally, not vertically (i.e., input ports always face up and output ports always face down).
The computer can't have any gaps (i.e., the entire computer must be filled with modules).
The computer can't be vertically partitioned. There cannot be a seam that runs from the top of the computer to the bottom: see the following diagram for some examples of an assembled computer that is two units tall and three unts wide. (note, this diagram does not show all legal configurations, just some of them).
image

Examples:

If the required dimensionality for the computer is 1 unit tall and 1 unit wide, there is only one possible configuration as only 1 module can fit.
If computer must be 2 units tall by 2 units wide, there are 3 possible configurations:
(1) a 2-long module on top of a 2-long module
(2) a 2-long module with 2 1-long modules on top
(3) 2 1-long modules with a 2-long module atop them
NOTE: 2 1-long modules atop 2 1-long modules isn't valid because there would be a vertical seam through the middle.
If the computer must be 3 units tall by 2 units wide, there are 7 configurations: each row can be either a 2-long module or 2 1-long modules. So there are 2 x 2 x 2 possible options. However, 1 configuration (where all of the module are 1-long) results in a vertical seam that goes all the way through (like the previous example).
As the number of configurations possible becomes quite large for large computers, return your result as the number of configurations mod(109 + 7).

Input Format

The first line contains T, the number of test cases.
Each test comprises two values separated by a space:
The first value, H, represents the height of the supercomputer.
The second value, L, represents the length of the supercomputer.
Constraints

1 ≤ T ≤ 10
1 ≤ H, L ≤ 1000
Output Format

Output T lines, the number of legal configurations that can be produced for each test case modulus 1000000007.

Example 0
Sample Input

4
1 1
2 2
3 2
3 3
Sample Output

1
3
7
49
Example 1
Sample Input

7
10 1
5 2
2 5
6 4
4 5
100 100
500 500
Sample Output

1
31
50
250047
35714
928745576
798212178




Description
N of your best robot friends have been invited to participate in a game of 'Hats!'. Can you write the instructions (a program) for each robot to follow that guarantees victory?

In every game of 'Hats!', there are N players and N possible hat colors. At the beginning of the game, each player has a randomly colored hat (one of the known N possible colors) placed on their head. Players can see the hat colors of other players, but CANNOT see their own hat color. Further, no communication is allowed during a game of 'Hats!'. To win, each player must write down which color they think their hat is, and if at least one player is correct, everyone wins. If no one correctly guesses their hat color, everyone loses.

NOTE: not all possible hat colors may be assigned, and multiple players may have duplicate hat colors.

Write a program that, if executed by each of your robot friends, will guarantee they win as a group (i.e., at least one guesses their hat color).

For this problem, your program will be evaluated differently than in previous problems. For every test case, we will run your program N times, once for each robot. Each time, we will provide the following inputs: N (the number of possible colors and the number of players), P (the current player's ID), the set of possible colors, and the hat colors the current player sees. You will pass a test case if, for at least one of the players, your program outputs the correct hat color.

Credit for this problem is all or nothing. You must pass all tests to receive credit.

Input Format

The first line contains two space-separated integers, N and P.
The second line contains a space separated list of strings where each string is a possible hat color.
The third line contains a space separated list of strings where each string represents the hat colors the current player sees.
Constraints

1 ≤ N,P ≤ 865
Output Format

Output the (string) color written down by the current player.

Example 0
In this example, there are five players (robots) and five possible hat colors. Each robot's program (i.e., the program you submit) is run independently and given as input N (the number of hat colors and number of total players), P (the current player's ID), and the current player's view of everyone else's hats.

In this example, the true hat color assignment is as follows:

Robot 0: orange_peel
Robot 1: orange_peel
Robot 2: orange_peel
Robot 3: gainsboro
Robot 4: yellow
Robot 0

5 0
gainsboro orange_peel fawn yellow white_smoke
orange_peel orange_peel gainsboro yellow
Robot 1

5 1
gainsboro orange_peel fawn yellow white_smoke
orange_peel orange_peel gainsboro yellow
Robot 2

5 2
gainsboro orange_peel fawn yellow white_smoke
orange_peel orange_peel gainsboro yellow
Robot 3

5 3
gainsboro orange_peel fawn yellow white_smoke
orange_peel orange_peel orange_peel yellow
Robot 3

5 4
gainsboro orange_peel fawn yellow white_smoke
orange_peel orange_peel orange_peel gainsboro
Explanation