UhWjs3Qz

1Warrior Of Hogwarts
2Memory Limit: 1024MB Runtime Limit: 5sScore: 500
3
4Henry is a curious student, studying at Hogwarts. Being smarter, faster and displaying more zeal for magic than other students, he became popular among three witches at the school. They knew Henry has a secret desire to be a warrior. So each gave him a super power to fight against his enemies.
5The first witch gave Henry the power to reduce the strength of his enemies by 1 unit. 
6The second witch gave Henry the power to divide the strength of his enemies by 2. 
7The third witch gave Henry the power to divide the strength of his enemies by 3.
8
9The witches clearly told him that the strength of every enemy must remain an integer at all times.
10Henry can defeat an enemy when the strength of the enemy equals 1.
11K is the initial strength of his enemy. Help Henry to find the minimum number of times he needs to apply his super powers to defeat the enemy and become a warrior.
12
13Input Specifications
14
15The input consists of the integer N, the initial strength of Henry's enemy.

16Constraints
171 <= N <= 1'000'000'000
18
19Output Specifications
20
21Print the minimum number of hits needed to defeat his enemy by making his strength equal to 1.
22
23Sample Input/Output
24INPUT
255
26OUTPUT
273
28EXPLANATION
29
30Input = 5, Reduce by 1 and then reduce power by half 2 times Answer=3
31
32INPUT
331
34OUTPUT
350
36EXPLANATION
37
38Input = 1, No need to to any operations Answer=0
39
40INPUT
412
42OUTPUT
431
44EXPLANATION
45
46Input = 2, Reduce By half Answer=1
47
48
49
50
51Mother of Dragons
52Memory Limit: 1024MB Runtime Limit: 5sScore: 500
53
54Daenerys Targaryen can rule over 7 kingdoms if she has all her dragons by her side.
55Daenerys has built N dragon-pits in her kingdom. The dragon-pits are located in a straight line at positions  x1, x2, …, xN.
56She has C dragons. The dragons are feisty and don’t like being restrained.  Once they are put into the dragon-pits they try to burn and bite each other.
57Tyrion, being her loyal and intelligent adviser, is given the task of preventing the dragons from hurting each other. To do so Tyrion wants to assign the dragons such that minimum distance between the dragons is as large as possible. 
58Help Tyrion find the largest minimum distance.
59
60Input Specifications
61
62
63*  Line 1: Two space-separated integers: N and C

64
65               N ranges as follows (C <= N <= 20) 
               C ranges such that (2 <= C <= N)

66* Lines 2..N+1: Line i+1 contains an integer which is the position of the dragon-pit (xi)   x1, x2, …, xN (0 <= xi <= 1'000'000'000)  
67
The position of the pits can be given in any order (not necessarily in sorted order)
68
69Output Specifications
70
71Print the largest possible minimum distance between the dragons.
72
73Sample Input/Output
74INPUT
755 3
761
772
788
794
809
81OUTPUT
823
83EXPLANATION
84
85Tyrion can put 3 Dragons in the Dragon-pit at positions 1, 4 and 8, 
86resulting in a minimum distance of 3.
87
88INPUT
894 2
90100000000
91500000000
92900000000
931
94OUTPUT
95899999999
96
97
98
99Forest Party
100Memory Limit: 1024MB Runtime Limit: 5sScore: 900
101
102Together with your friends, you organize a party in the forest. What would a party be without someone making a fool of themselves? To help loosen up the atmosphere and make the evening fun, you decide to create a little game. In this game, everyone has to travel between two places taking up the pre-set challenges as they come, (which were cunningly prepared by you the previous day). For instance, you may have to cross a small river over a fallen tree trunk, or you may have to walk some distance with stilts. To reach the target destination, you might have to use several paths. For every path that you use, you must take up the challenge along that path.
103As you are an absolutely evil person, your goal is not to finish the race first, but to make the others look more foolish than you.  To achieve this, you categorized every path by its potential to make a fool of yourself and gave every path a FI (Foolishness Index) number. A higher number means that you will very likely make a fool of yourself. Your goal is now to find how to reach the destination by keeping the maximum FI number that you encounter as low as possible.  The FI number for a sequence of paths is the maximum FI number of a path of that sequence.
104Unfortunately, you do not know yet where the game will start and where it will end. As you suspect that some configurations are more likely than others (your even more evil friend wants you to fall into the river), you prepared a list of very likely routes. Every route contains the start location and the end location. For every route, you want to find out the minimum FI number over all sequences of paths between the starting location and the ending location.
105
106An empty sequence of paths is considered to have an FI number of 0.   Furthermore, there may be several direct paths between the same locations. There might even be direct paths that loop back to their start location.  All paths can be used in both directions. Finally, at the time that you created the paths and the corresponding challenges, you made sure that it is always possible to reach every location from every location.

107
108
109Input Specifications
110
111The first line contains two space separated integers n and m. Integer n is the number of locations in the forest, and m is the number of paths in the forest. There are at most 100,000 locations and at most 100,000 paths.
112The next m lines contain three space separated integers that represent one path. The first two integers of a path are the two locations that the path links together. Path identifiers are integers between 1 and n. The last integer that describes a path is the FI number, which is at least 0 and at most 1,000,000,000.
113The next lines contain the number of queries you want to answer. The number of queries is at most 10,000.
114Each of the next q lines contains a query. Every query contains two space separated path identifiers.
115
116Output Specifications
117
118For every query, output the minimum FI number of a sequence of paths that links these two locations together followed by a newline character.
119
120Sample Input/Output
121INPUT
1228 11
1237 1 8
1244 8 4
1256 8 0
1265 3 0
1272 2 7
1283 2 5
1291 3 3
1301 6 4
1315 4 6
1321 6 5
1336 2 1
1342
1353 4
1368 8
137
138
139OUTPUT
1404
1410
142EXPLANATION
143
144For the first query, the sequence of paths that minimizes the FI number between locations 3 and 4 is 3, 1, 6, 8, 4. For the second query, we are already at the ending location, thus the best FI number we can get is 0.
145
146
147
148Multiplayer Game
149Memory Limit: 1024MB Runtime Limit: 6sScore: 600
150
151We have two players playing a game on a square grid that contains rewards.
The two players start from the top left cell of the grid and on each move each of them moves down or to the right.
They move at the same time and need to collaborate to collect the most number of rewards.
They can occupy the same cell in the grid at the same time but the reward, if any exists in the cell, is collected only once.
The game finishes when there are no more possible moves.
152
153Input Specifications
154
155The first line of the input contains a single integer N - the size of one side of the square grid.
N lines follow describing a row of the game grid each.
156Each line contains N digits (either 0 or 1) describing  the cells in that row. 0 - meaning an empty cell, and 1 - meaning a cell with reward. There is no whitespace between the digits.

1 <= N <= 100
157
158Output Specifications
159
160Output a single integer - the maximum score that the players can achieve playing together.

161
162Sample Input/Output
163INPUT
1644
1650101
1661000
1670010
1681000
169OUTPUT
1704
171EXPLANATION
172No matter how the two players move, they can not collect all of the rewards.
173
174
175
176
177
178Goodie Collector
179Memory Limit: 1024MB Runtime Limit: 2sScore: 300
180
181The big day has finally arrived, Bloomberg has come to your university and prepared a fun contest for you. To satisfy basic student needs,  Bloomberg has prepared some tables arranged in a row with some different goodies including socks, pens, and other useful items. Due to logistic reasons, there is only a single type of goodie on each table. Two adjacent tables are exactly one metre apart, every table is considered of negligible width for this problem and the tables are numbered from left to right. Of course, you want to maximize the number of different goodies you can get. One restriction applies however: as you do not want to appear greedy to your fellow friends, you want to make sure that between every two tables you take goodies from there is at least some given distance.
182
183Input Specifications
184
185The first line contains the integers n, k and d that are separated by a space. The integer n is the number of tables (1 <= n <= 12), k is the number of different goodies (1 <= k <= 12) and d is the minimum distance in meters between two tables you take goodies from (1 <= d <= n).
186The second line contains n space separated integers. The i-th integer is the goodie that can be picked up on the i-th table. A goodie type is a number between 0 (inclusive) and k (exclusive).
187
188Output Specifications
189
190Print the maximum number of different goodie types you can get.
191
192Sample Input/Output
193INPUT
1948 3 3
1951 2 2 1 0 0 0 0 
196OUTPUT
1972
198EXPLANATION
199
200Here, one can only select two different types of goodies.
201Either select goodie types 0 and 1 by going to the tables (which are assumed to be 1-indexed):
202- 1 4 7
203- or 1 4 8
204- or 1 5 8
205- or 1 5
206- or 1 6
207- or 1 7
208- or 1 8
209- or 4 7
210- or 4 8
211Or select goodie types 0 and 2 by going to the the tables:
212- 2 5 8
213- or 2 5
214- or 2 6
215- or 2 7
216- or 2 8
217- or 3 6
218- or 3 7
219- or 3  
220
221INPUT
2225 4 2
2230 0 3 3 2
224OUTPUT
2253
226EXPLANATION
227
228It is possible to get 3 different types of goodies from tables 1, 3 and 5. This is optimal as goodie type 1 is not available anywhere and this is the only goodie type we do not get.
229
230
231Passport Control
232Memory Limit: 1024MB Runtime Limit: 5sScore: 400
233
234Upon arrival at an international airport, passengers must go through passport control. They are arranged in a line and must go to the lowest numbered available passport control booth, where a border agent will check their travel documents.
235Passengers can come alone or in groups. You should assume that every passenger will get through passport control after 1 minute, so a group of 5 passengers will have all its checks completed after 5 minutes. Each group of passengers will be processed by a single border agent.
236Each passenger group is immediately assigned to the lowest numbered available border agent, so you should assume no time is spent for this.
237Case 1: The group of passengers should go to Booth 2
238                  Booth 1      Booth 2     Booth 3     ...   Booth N
239Passengers ---->  Unavailable  Available   Available   ...   Available
240Case 2: The group of passengers should go to Booth 1
241                  Booth 1    Booth 2     Booth 3       ...   Booth N
242Passengers ---->  Available  Available   Unavailable   ...   Available
243After checking 10 passenger groups (regardless of size), each border agent is allowed to take a break, which will make their respective booth unavailable during 5 minutes.

244Your task is to count how many groups were through each booth.
245
246Input Specifications
247
248* 1 ≤ N ≤ 104
249* 1 ≤ M ≤ 106
250* 1 ≤ groupSizes ≤ 102
251The first line (N) will be the number of available booths at passport control. The second line (M) will contain how many groups are arriving. The next M lines will contain the number of passengers in each group.
252
253Output Specifications
254You should output a space separated list of integers containing how many groups each border agent has processed. Note that the sum of these integers must be equal to M.
255Sample Input/Output
256INPUT
2573
2586
2594
2602
2611
2623
2635
2641
265OUTPUT
2662 2 2
267EXPLANATION
268Agents 1, 2 and 3 will take groups with 4, 2 and 1 passengers at first, respectively. Then, agent 3 will take a group with 3 passengers, agent 2 will process the group with 5 and finally agent 3 will let through the final passenger. Each agent will have processed 2 groups.
269INPUT
2703
2716
2724
2732
2741
2752
2765
2771
278OUTPUT
2791 2 3
280EXPLANATION
281Agents 1, 2 and 3 will take groups with 4, 2 and 1 passengers at first, respectively. Then, agent 3 will take a group with 2 passengers, agent 2 will process the group with 5 and finally agent 2 will let through the final passenger. The final count will be 1, 2 and 3.
282INPUT
28310
28419
2851
28610
28710
28810
28910
29010
29110
29210
29310
29410
2951
2961
2971
2981
2991
3001
3011
3021
3031
304OUTPUT
30510 1 1 1 1 1 1 1 1 1
306EXPLANATION
307Bad luck, Agent #1
308INPUT
30910
31020
3111
31210
31310
31410
31510
31610
31710
31810
31910
32010
3211
3221
3231
3241
3251
3261
3271
3281
3291
3301
331OUTPUT
33210 2 1 1 1 1 1 1 1 1
333EXPLANATION
334Take a rest, Agent #1
335INPUT
33610
33719
33810
33910
34010
34110
34210
34310
34410
34510
34610
3471
3481
3491
3501
3511
3521
3531
3541
3551
3561
357OUTPUT
3581 1 1 1 1 1 1 1 1 10
359EXPLANATION
360Bad luck, Agent #10
361INPUT
3622
36317
3641
36510
3661
3671
3681
3691
3701
3711
3721
3731
3741
3751
3761
3771
3781
3791
3801
381OUTPUT
38211 6
383EXPLANATION
384Agent #1 returns from break
385
386
387
388Tracing Vile Angus
389Memory Limit: 1024MB Runtime Limit: 5sScore: 200
390
391Inspector Catchburgle is on a case! He is chasing a mysterious villain that goes by the name Vile Angus. Fortunately, Angus has a bad memory and tends to write a lot of things down. And Catchburgle just found a pile of the scoundrel's notes! There must be lots of valuable clues in them!
392However, Angus isn't stupid; he was encrypting his messages with some cipher, so that they are not so easy to read.
393Inspector Catchburgle has applied his brilliant logic, and found out that the villain uses some sort of a substitution cipher. It seems that he goes over the text multiple times, and each time swaps two letters in part of the text from a random position to the end.
394But that's not all! The bright detective has even figured out the mechanism by which Angus decides which letters to swap and from which position.
395Well, inspector Catchburgle didn't share the details of this mechanism with you, but before he went on a well deserved coffee break, he wrote down all the substitutions for each encoded message.
396Will you, the inspector's assistant, be able to impress the inspector by decoding the messages before he returns from his coffee break? It will surely help to catch the villain (and you will deserve part of the credit)!
397
398Input Specifications
399
400* First line of input is the message as Vile Angus wrote it. Its length is in the interval 0 ≤ length ≤ 10000. (Yes, there were some blank papers, too. The inspector didn't bother removing them.)
401* Second line is number N, where 0 ≤ N ≤ 1000.
402* The next N lines each contains information about a pair of letters that the inspector found to be swapped. Each line is in the format pos first second, and means that starting at position pos (zero-based), each occurrence of letter first has been replaced by letter second and vice versa. The values of pos form a non-decreasing sequence.
403Note that:
404* There can be multiple swapped pairs starting at the same position.
405* The order of swaps is important. When Angus encrypted his messages, he was applying the substitutions in the order in which you receive them on input.
406* The letters first and second are always lower case letters, but when doing the substitutions, Angus keeps the upper- or lower-case of the original letter. So if the original letter was upper case, the substituted letter will also be upper case.
407* Some positions pos may be past the end of the message. Inspector Catchburgle might have gotten carried away a little...
408
409Output Specifications
410
411Print the villain's message with all the letter swaps undone.
412
413Sample Input/Output
414INPUT
415Vile Angus
4160
417OUTPUT
418Vile Angus
419EXPLANATION
420There are 0 substitutions. The text is not encrypted at all.
421INPUT
422Diury uf Vise Ongal
4233
4240 a u
4256 l s
4266 o u
427OUTPUT
428Diary of Vile Angus
429EXPLANATION
430
431When Angus was encrypting the message, he did 3 passes:
432Diary of Vile Angus
433(from beginning of the text onward, a is swapped with u)
434Diury of Vile Ungas
435(from beginning of second word onward, l is swapped with s)
436Diury of Vise Ungal
437(from beginning of second word onward again, o is swapped with u)
438Diury uf Vise Ongal
439
440INPUT
441The password to my safe is: f1ddler
4425
44328 k f
44428 t d
44528 l e
44628 n e
44728 s r
448OUTPUT
449The password to my safe is: k1ttens
450EXPLANATION
451
452* There are no substitutions until the last word (position 28). From there, f is replaced with k("k1ttens" -> "f1ttens").
453* Also, t is replaced with d ("f1ttens" -> "f1ddens").
454* The order of the following two swaps, l <-> e and n <-> e, is important ("f1ddens" -> "f1ddlns" -> "f1ddles").
455* Finally, s is swapped with r ("f1ddles" -> "f1ddler").
456
457INPUT
458Catdhburgfe has no icea vhav I hate buqiec vhe bocy in vhe gaqcen.
4596
4602 c d
4619 f l
46215 v t
46316 s d
46417 r q
46531 h h
466OUTPUT
467Catchburgle has no idea that I have buried the body in the garden.
468EXPLANATION
469
470INPUT
471Trkin to Viennk: Juexdky, 7:15km, 3rd ajkas
47212
4732 a k
4742 q s
4754 q x
4766 h s
4778 t j
47814 s s
47916 a c
48019 o j
48123 f v
48226 z o
48331 x f
48442 j y
485OUTPUT
486Train to Vienna: Tuesday, 7:15am, 3rd coach
487EXPLANATION
488Swapping s for s from position 14 is actually a no-op. Also, some of the swaps towards the end do not actually swap anything because the letters don't appear in the respective part of the text.
489INPUT
490Angus, on your way fpoa wope, rbkmdk luy ahbe, lpkmg mng rotmtokd. Timned, Kbh.
4917
4927 b l
49315 h i
49415 e k
49517 a m
49618 p r
49722 s g
49834 d g
499OUTPUT
500Angus, on your way from work, please buy milk, bread and potatoes. Thanks, Eli.
501EXPLANATION
502
503INPUT
504People that I have afbushed and mobbed ro wam: Heimy C., Rngflid E., Evaigeunia de M., Aetem A. (tince), pfd thpt gly inth the wlffy soldtpche
50511
5063 w r
50715 m w
50818 w f
50925 r s
51032 u l
51133 i n
51282 a p
51385 s i
51498 f s
515109 f f
516127 d r
517OUTPUT
518People that I have ambushed and robbed so far: Henry C., Sigmund E., Evangelina de R., Peter P. (twice), and that guy with the funny moustache
519EXPLANATION
520
521INPUT
5222
5230 n o
5240 o n
525OUTPUT
526
527EXPLANATION
528This text is empty, there is nothing to swap. The output is empty as well.
529
530
531
532
533
534A Very Odd Problem
535Memory Limit: 1024MB Runtime Limit: 1sScore: 100
536
537As part of his religion, your friend hates odd numbers and empty arrays. He hates odd numbers and empty arrays so much that whenever he encounters an array, he tries to remove some values such that the resulting array has an even sum. Furthermore, the resulting array must contain a non zero even amount of even numbers after the transformation. When your friend can not remove any values from the array such that the array satisfies the conditions given before, he becomes insane. Being a good friend, you decide to check whether it is safe to give your friend an array.
538
539Input Specifications
540
541The first line contains n (1 <= n <= 10'000), the number of values in the array. The next line contains 'n' space separated integers, the n elements of the array. Every value is contained in the closed interval [0; 999'999].
542
543Output Specifications
544
545Print "YES" if it is safe to give your friend the array. Otherwise, print "NO".
546
547Sample Input/Output
548INPUT
5495
5504 4 5 8 1
551OUTPUT
552YES
553EXPLANATION
554
555Your friend can remove all values except 4 and 4. Alternatively, he could have also kept values 4 and 8 or the other 4 and 8.
556
557INPUT
5584
5591 2 3 5
560OUTPUT
561NO
562EXPLANATION
563
564No matter which elements your friend removes, he will never have a non zero even number of even values remaining.