Homework 02 Solution

Description
Millenium Jackson has a flood of infestation reports coming in, and he needs to decide which ones to deal with first. Can you examine the size of each report and let him know which infestations are the largest?

Input Format

The first line has two values N and K. N is the number of reports coming in, and K is the number that Millenium can deal with this month.

The next N lines indicate the size of each infestation.

Constraints

1 ≤ N ≤ 107
1 ≤ K ≤ 1000
1 ≤ infestation size ≤ 109
Output Format

 K values, indicating the K largest infestations in order (each on a new line).

Example 0
Sample Input

5 2
6
7
11
6
17
Sample Output

17
11
Explanation

There are five infestations, and we need to identify the largest two. They are size 17 and size 11.

Example 1
Sample Input

10 2
7
3
19
5
3
11
13
10
3
6
Sample Output

19 
13

Description
Dakota Smith keeps finding new and interesting artifacts, each of which she sends off to ATOM labs for analysis. As ATOM finishes analyzing the artifacts, it sends them back to her.

Strangely, ATOM works on a Last-In-First-Out system, so Dakota either gets results back about an artifact immediately, or else she needs to wait a while to hear anything. As such, she always wants to know what the most valuable artifact she is waiting for is.

Input Format

The first line is an integer N, indicating the number of interactions Dakota will have with ATOM labs. The next N lines contain a number and possibly an item value (x) in the format:

1 x - Send an artifact of value x to the lab.
2   - Receive the most recent artifact back from the lab.
3   - Print the value of the most valuable item still at the lab.
Constraints

1 ≤ N ≤ 105
1 ≤ x ≤ 109
Output Format

 For each type 3 action, print the value of the most valuable artifact still in the lab, on a new line.

Example 0
Sample Input

10
1 97
2
1 20
2
1 26
1 20
2
3
1 91
3
Sample Output

26
91





Description
ATOM labs has a regular inflow of priceless relics, some thought to have mystical powers. Dr. Malcolm Niacal is very interested in getting his hands on some of these relics and wants to keep track of how many are being studied in each lab location... just in case he wants to procure them for himself.

Input Format

The first line contains a single value N, indicating the number of relics being sent to labs to be studied.

The next N lines each contain the ID number of the research lab that each relic was sent to. Note that ID numbers may not be consecutive and can be large values.

Constraints

1 ≤ N ≤ 106
0 ≤ lab ID ≤ 1012
1 ≤ number of unique lab IDs ≤ 1000
Output Format

Print the ID number of the lab that has the most relics. If two labs have the same number of relics, just print the one with the lowest ID.

Example 0
Sample Input

8
63
63
63
8
3
8
63
3
Sample Output

63




Description
Queen Mellifluous has positioned her primary hive securely in a mountain pass, surrounded by N evenly-spaced outposts, all in a line. She has positioned K guards in a subset of those outposts, but is still concerned about an infiltrator sneaking in. Given a set of guard positions, can you identify the distance of the outpost furthest from the nearest guard?

Input Format

The first line has two values: N (the number of outposts, labeled 0 through N-1) and K (the number of guards on duty). The next K values indicate the outpost numbers where each guard is patrolling. For example, if there are 100 outposts and three guards at outposts 10, 60, 95, then an infiltrator coming in at the outpost 35 would be 25 outposts away from the nearest guard.

Constraints

1 ≤ k ≤ 109
1 ≤ N ≤ 105
0 ≤ guard positions ≤ k
Output Format

Output a single number indicating the farthest an infiltrator can be to the nearest guarded outpost as they try to sneak in.

Example 0
Sample Input

5 2
0 4
Sample Output

2




Description
The Indrassi Carnivorous Katydid (ICK for short) is an insect species whose colonies grow by one member an hour until they meet their growth goal; then everyone but the queen flies away, the colony size reduces to one, and they start over. In the first round the colony grows to size K. In the next round they will keep growing to 2K. Then 4K, then 8K, and so on, doubling their goal each time.

Specifically, if we track a colony hour-by-hour where k=3, we would see colony sizes of:

Hour 1: 1
Hour 2: 2
Hour 3: 3 (Goal met, two fly away!)
Hour 4: 1
Hour 5: 2
Hour 6: 3
Hour 7: 4
Hour 8: 5
Hour 9: 6 (Goal met, five fly away!)
Hour 10: 1
Hour 11: 2
...

The next goal will be met at hour 21 with 12 individuals; then at hour 22, the colony will be back to only 1.

Given that Millenium will arrive at hour H, can you warn him what colony size he will be facing?

Input Format

Two values, K (the starting growth goal) and H (the time, in hours, until Millinium will arrive at the planet).

Constraints

K ≤ 1000
H ≤ 1012
Output Format

A single value indicating the colony size at hour H.

Example 0
Sample Input

3 5
Sample Output

2
Explanation

Number of ICKs:

1: 1
2: 2
3: 3 (hit cap! Start over...)
4: 1
5: 2
Example 0
Sample Input

3 12
Sample Output

3





Description
In looking through her previously-sorted files, Dakota has realized that they are out of order. Fortunately the sabatour made only a quick change to each set of files, either turning around a whole segment of them (so that they are in the reverse order of what is expected) or by swapping two entires. Can you find a single reverse or swap operation that will restore her files to sorted order?

Input Format

The file line contains a value N, indicating how many files there are in this set.

The next N values (on the next line) indicate the IDs of each file.

Constraints

2 ≤ N ≤ 105
0 ≤ file id ≤ 106
Output Format

If the array is already sorted OR Dakota can fix it with a single "swap" or "reverse" operation, write "yes" on the first line. Otherwise write "no" on the first line.

If a single operation needs to be performed, begin the second line with "swap" or "reverse" indicating either the two file positions to swap -or- the first and last positions that need to all be reversed. (if both are possible provide the "swap" option)

NOTE: You should assume the first position is 1 for the purposes of this question.

Example 0
Sample Input

2
4 2
Sample Output

yes
swap 1 2
Explanation

The two files are numbered 4 and 2. These are out of order, but can clearly be fixed by swapping the two values. As such we print "yes" since it's possible to fix, and indicate that the needed fix is swapping position 1 and positions 2 (remember, that indexing starts at 1).

Example 1
Sample Input

3
3 1 2
Sample Output

no
Example 2
Sample Input

6
1 5 4 3 2 6
Sample Output

yes
reverse 2 5






Description
Dr. Malcolm Niacal has simplified people down to their basic traits: height, weight, political leanings, conviviality, etc, each assigned a number. As he adds and removes numbers from his system, can you keep track of what the median value is? Warning, you might be working with a LOT of data!

The median of M numbers is defined as the middle number after sorting them in order if M is odd. Or it is the average of the middle two numbers if M is even. You start with an empty number list. Then, you can add numbers to the list, or remove existing numbers from it. After each add or remove operation, output the median.

Input Format

The first line is an integer, N, that indicates the number of operations. Each of the next N lines is either "a x" or "r x", with 'x' being an integer. An "a x" indicates that the value x is inserted (added) into the set, and "r x" indicates that the value x is removed from the set.

Constraints

1 ≤ N ≤ 106
-2,147,483,649 ≤ x ≤ 2,147,483,648
Output Format

For each operation:

If the operation is remove and the number x is not in the list, output "Wrong!" in a single line.
If the operation is remove and the number x is in the list, output the median after deleting x in a single line.
NOTE: If your median is 3.0, print only 3. And if your median is 3.50, print only 3.5. Whenever you need to print the median and the list is empty, print "Wrong!".

Example 0
Sample Input




Description
Queen Mellifluous has found a neighboring planet with a series of hives around its equator. You must help her determine which hive to initiate the invasion from such that she will be able to sweep around the planet and have enough warriors to win each battle.

She knows how many warriors she will gain for winning each hive and how many warriors she will need to then expend to claim the next hive. She can conquor the first hive from orbit (without expending warriors)-- can you identify which hive she must begin the invasion with in order to have enough troops to defeat each of the others as she reaches them?

Input Format

The first line will contain the number of hives on the planet(N).
The next N lines will each contain a pair of integers, indicating the number of warriors that the queen will gain if she wins (or chooses as her starting point) that hive and how many warriors she needs to defeat next hive.

Constraints

1 ≤ N ≤ 105
1 ≤ warriors gained, warriors needed ≤ 109
We guarantee that there is a solution.
Output Format

 A single value indicating the lowest position of a hive where she can start her attacks.

Example 0
Sample Input

3
1 5
10 3
3 4
Sample Output

1
Explanation

There are three hives available here. The hive at position 0, provides only one warrior, but we need five just to get to the next hive so we can't start there.

We CAN, however, start at position 1. This hive would give 10 warriors, three of whom would be used to take hive 2. That leaves us with 7 warriors, plus we would get three more at hive 2, for a total of 10 again. Now we need to use four of those to get hive 0 (looping back around). We've now claimed all three hives!

As such hive 1 is the first one we can start at to claim all of the other hives as well.

Example 1
Sample Input

1
Example 2
Sample Input

20
1 11
2 12
3 13
4 14
5 15
6 16
7 17
8 18
9 19
10 20
11 1
12 2
13 3
14 4
15 5
16 6
17 7
18 8
19 9
20 10
Sample Output

10
Example 3
Sample Input

20
5 15
16 6
2 12
3 13
14 4
7 17
1 11




Description
The ICKs (Indrassi Carnivorous Katydid) have gotten out of control and Millennium Jackson wants to wipe them all out. He realizes that the best way to do this is to get colonies wiped out as fast as possible. Given a series of jobs, how can he get each job done as quickly as possible?

You will be provided with a list of job requests, with the time each request arrives and how long the job will take to complete. Every time Millennium finishes a job, he should start on the SHORTEST one that he knows about. The completion time of a job is measured from the time the request comes in to the time Millennium has completed the job. You must output the AVERAGE completion time (rounded down to the nearest integer) that Millennium took to complete all jobs.

For example, assume three job requests come in at time 0, time 1, and time 2, and they will take Millennium 3, 9, and 6 hours respectively. Millennium will start on the first job at time zero, taking 3 hours to finish it. At time 3 he'll start on the third job (since it's the shortest one) and finish it at time 9 (3+6). Since this job came in at time 2, he would have taken 7 hours to complete it (9-2). Finally at time 9 he start on the second job, finishing it at time 18, for a total of 17 hours spent on it (18-1).

Given that the completion times for the three jobs were 3 hours, 7 hours, and 17 hours, he would have spend an average of (3+7+17)/3 = 9 hours per job, which is what you would output.

Input Format

The first line provides the value N, the total number of job request coming in.
The next N lines each have two values: the time the job arrives (Ti) and how long the job will take (Li)
Note that the job list may be unsorted.

Constraints

1 ≤ N ≤ 105
0 ≤ Ti ≤ 109
1 ≤ Li ≤ 109
Output Format

Display the integer part of the minimum average time that the job took.

Example 0
 Sample Input

5
961148050 385599125
951133776 376367013
283280121 782916802
317664929 898415172
980913391 847912645
Sample Output

1418670047
Example 1
Sample Input

50
137857688 413115088
679783990 171274023
783725811 742261681
238387441 531682046
683427743 559301752
843391076 398722857
593760457 2628387
441381803 788912528
771854880 916901718
976015955 978145894
235492265 264125858
866638949 551120745
238176883 201620672
254029772 950305054
356294983 203393748
291672611 722032663
560013448 126478507
929678215 321924654
737812220 884493567
388266395 252551113
79292652 229453232
367753702 242882326
930211560 461283594
955372388 594944846
506995906 872449795
538015463 457419763
950540066 820099707
823860276 896193555
538832788 47584891
88242680 700680580
196842555 623621497
700528228 610051112
668066226 170226832
522278872 914689320
375621149 336628938
418416931 270027322
179882058 480538711
540671906 215602397
201411561 930064341
36616963 35887002
772894889 944088968
891134170 633761602
975099001 434725536
926070958 326905396
727328509 867529847
340789259 890185621
923620442 986091986
747688776 107231383
38070714 495529501
610348800 235616181
Sample Output

8485548331