Algorithm-Engineering Homework 1 Solution

All questions within this homework assignment were included in one file (each question is labeled as Q1, Q2, Q3, etc.).
# Question prompts:
# Q1) 
Complete the function adder to compute the sum of two integers and return the result. You can write your solution in either Python or C++. Python starter code is provided in a file called code.py. If you wish to use C++, delete code.py and create a file called code.cc or code.cpp.

We'll test your code via command-line IO to make sure it works! Make sure to write your code so that it takes in input from the command line and prints output in the following format:

Sample Input:
2
3

Sample Output:
5

Explanation:
The sum of the two integers a and b is computed as: 2 + 3 = 5.
<br />
<br />
<br />
<br />
<br />
# Q2)
In the year 2086, the eccentric trillionaire Octavian Heximus founded the Martian Olympics. Below are a series of events that he included.  Your job is to write programs to help players strategize the best moves to make in the different games.

In the betting game "Discordian Poker", the level of each player's bet changes every round until one player wins.

1. If your current bet is odd, it goes down by $15, but the remaining amount must be doubled.

2. If your current bet is even, it goes down by $99, but the remaining amount must be tripled.

3. If your bet that would pass $1,000,000, it loops back around (so a bet of $1,000,007 just becomes $7). Likewise, any bet that goes below $0 ALSO loops around (so a bet of -$7 would become a bet of $999,993).

Given a starting bet ( S ) and a specified number of rounds played ( k ), determine what your final bet will be at the end of the game.

Input Format

The first line is a number ( T ), indicating the number of Test cases. The next T lines each have two values, S and k, indicating the starting bet and the number of rounds the game goes, respectively.

Constraints

1 ≤ T ≤ 100
0 ≤ S ≤ 1,000,000
0 ≤ k ≤ 100
Output Format

T lines, each indicating the final bet in the associated game.

Example 0
Sample Input

3
1000 1
1000 2
1000 5
Sample Output

2703
5376
94599
Explanation

Three test cases are provided. Each starts with $1,000.

In the first case, only a single round is played. Since the starting bet is even, $99 is subtracted from it (leaving $901) and this result is tripled, producing $2703.

The second test case goes two rounds. The first round results in $2703 (as above), but the bet is now odd; as such, the second round subtracts $15 (brining it to $2688) and then doubles the bet to $5376.

The third test case goes three more rounds. Since the value after two rounds is even, $99 is subtracted (putting it at $5277) and the value is tripled to $15,831. Next $15 is subtracted ($15,816) and the bet is doubled ($31,632). Finally $99 us subtracted again ($31,533) and the bet is tripled to $94,599.

Example 1
Sample Input

5
1 5
10 5
100 5
1000 5
10000 5
Sample Output

994624
987679
997399
94599
66599
Explanation

Five test cases. The first one is described below.

$1 is odd, so we subtract $15, which results in a bet of -$14, which loops around to $999,986, but then we double it giving us $1,999,972 and loops back to $999,972.

$999,972 is even, so we subtract $99 (getting $999,873) and triple it (getting $2,999,619, looping back to $999,619).

$999,619 is odd, so we subtract $15 ($999,604) and double it ($1,999,208 looping to $999,208).

$999,208 is even, so we subtract $99 ($999,109) and multiply by 3 ($2,997,327 looping to $997327).

$997,327 is odd, so we subtract $15 ($997,312) and multiply by 2 ($1,994,624 looping to $994,624), which we output as the final answer.
<br />
<br />
<br />
<br />
<br />
# Q3)
In the Atlas Lift event, contestants must lift a giant stone replica of the Earth over their heads and hold it for as long as possible.  Every second the replica gets slightly heavier.

You are given the number of seconds each contestant can last.  You must output the number of starting contestants and, every time a contestant falls, the number of contestants that remain.

Suppose there are six contestants that are able to last the following number of seconds.:

5 4 4 2 2 8

The first contests fall after two seconds and we are left with four others; the times remaining for those four are:

3 2 2 _ _ 6

The above step is repeated until no opponents are left (see Example 0 below)

Input Format

The first line contains a single integer N indicating the number of contestants.

The next line contains N integers: a0 , a1 , ..., aN-1  separated by spaces, where ai  represents how many seconds the i th contestant can last.

Constraints

1 ≤ N ≤ 1000
1 ≤ ai ≤ 1000
Output Format

At the start and each time at least one contestant falls, print the number of contestants that remain.

Example 0
Sample Input

6
5 4 4 2 2 8
Sample Output

6
4
2
1
Explanation

In the first round, there are six contestants (provided in the input file).

At 2 seconds, two contestants fall, leaving four others with 3 2 2 and 6 seconds left respectively.

After 2 more seconds, two more contestants fall. The last two have 1 and 4 seconds left.

After 1 more second, a fifth contestant falls, leaving just one who can hold for another three seconds.

Finally the last opponent is eliminated and the game ends (do not output 0).

Example 1
Sample Input

8
1 2 3 4 3 3 2 1
Sample Output

8
6
4
1
Example 2
Sample Input

8
8 8 14 10 3 5 14 12
Sample Output

8
7
6
4
3
2
<br />
<br />
<br />
<br />
<br />
# Q4)
In Nortia Racing contestants ride in robotic chariots that have two buttons, each representing a distance that it should move forward.  When a race starts contestants must quickly press a series of buttons to get as close to a target as possible, so they want to know their options ahead of time.

You are given the distance forward that each button will take the chariot (x and y) and the number of times buttons must be pressed (n).  You should come up with the set of all possible distances that a contestant can travel after exactly n presses.

Input Format

The first line contains an integer T indicating the number of test cases.

The next T lines each describe a test case with three integers: x, y, and n.

Constraints

1 ≤ T ≤ 10
1 ≤ x, y, n ≤ 1000
Output Format

Space-separated list of numbers which are the possible total scores in increasing order.

Example 0
Sample Input

2
1 2 2
10 100 3
Sample Output

2 3 4
30 120 210 300
Explanation

Two test cases.

In the first, chariots can move a distance of either 1 or 2 and two buttons must be pressed. As such, there are three possible totals: 2 (if the '1' button is pressed twice), 3 (if each button is pressed once), or 4 (if the '2' button is pressed twice).

In the second test case, buttons move the chariots a distance of either 10 or 100 and three buttons are pressed. If 10 is pressed all three times, the final movement is 30. If 100 is pressed once, it will be 120; if 100 is pressed twice, it will be 210, and if 100 is pressed all three times, it will be 300.
<br />
<br />
<br />
<br />
<br />
# Q5)
In the Opis Climb contestants must use a limited supply of fuel to drive a fuel-cell powered climbing vehicle as far up Olympus Mons (the largest mountain in the solar system!) as possible. Every full fuel cell will allow one mile of climb.

Contestants start with n gallons of fuel.  Each fuel cell requires m gallons to reach a full charge (partially charged fuel cells cannot be used).  Whenever a fuel cell drops too low to power the vehicle, it still has some fuel left in it and c used fuel cells can be combined to form one more full fuel cell.

For example, assume a contestant starts with n=4 gallons, needs only one gallon per fuel cell (m = 1), and for every two empty fuel cells, she can combine them into one full fuel cell (c = 2). The contestant can drive up 4 miles with the initial fuel cells, and then (after using up those first fuel cells) she can combine their leftovers into two new fuel cells. When those new fuel cells finish (after another two miles), she can use them to generate yet another 1 fuel cell, for a grand total of 7 miles climbed.

Input Format

The first line contains a single integer T indicating the number of test cases.

The next T lines each have three integers, separated by spaces, indicating n, m, and c for that test case.

Constraints

1 ≤ T ≤ 1000
2 ≤ n ≤ 105
1 ≤ m ≤ n
2 ≤ c ≤ n
Output Format

For each test case, print the number of miles that can be traveled during that race.

Example 0
Sample Input

3
10 2 5
12 4 4
6 2 2
Sample Output

6
3
5
Explanation

Three climbing sessions:

Session one: 10 gallons to start with and each fuel cell needs 2 gallons, so five fuel cells can initially be made. For every 5 fuel cells used, one new fuel cell can be filled, so only one additional mile can be added this way, for a total of six miles climbed.

Session two: 12 gallons to start with and each fuel cell needs 4 gallons. As such, three fuel cells are initially filled. Since four used fuel cells are needed to fill a new one, we don't have enough and the initial three miles climbed are all there will ever be.

Session three: 6 gallons to start with, and each fuel cell needs 2 gallons, so three fuel cells can be initially filled. For every two used fuel cells, we can fill a new one. This means that in round two, we can fill one new fuel cell, with one empty fuel cell left over. However, in round three, we can use the leftover fuel cell AND the newly empty one to full yet another fuel cell. This process gives a grand total of 5 miles climbed.
<br />
<br />
<br />
<br />
<br />
# Q6)
In this challenge participants must think of a number with certain qualities and their opponents must guess what that number must be.  This year the rules are:

All numbers must be a multiple of 12.
All numbers must be a perfect square.
All numbers must be with boundaries (minimums and maximums) that are provided for the values.
So is the boundaries were that it have to be between 10 and 100, the number 36 would be allowed, but 49 would not (it is not a multiple of 12) nor would 60 (it is not a perfect square), or 144 (it is greater than the maximum).

Given the minimum value ( x ) and the maximum value ( y ) you must calculate how many of these values are divisible by 12 (d ), how many are perfect squares ( s ), and how many values have both qualities ( b ).

Write a program to perform these calculations.

Input Format

The first line contains T, the number of test cases to follow, each on a new line.

Each test contains two space-separated integers denoting the minimum ( x ) and the maximum ( y ) values allowed, inclusive.

Constraints

1 ≤ T ≤ 100
1 ≤ x ≤ y ≤ 109
Output Format

With each test case on a new line, print out d, s, and b (where d is the number of values divisible by 12, s is the number of perfect squares, and b is the number of values that meet both criteria).

Example 0
Sample Input

2
6 12
25 37
Sample Output

1 1 0
1 2 1
Explanation

Two test cases are provided.

The first case allows values from 6 to 12. Of those, only one possibility is a multiple of 12 (12 itself), one is a perfect square (9), and none meet both criteria.

The second case allows values from 25 to 37. Of those, one is a multiple of 12 (36), two are perfect squares (25 and 36) and one meet both criteria (36).