Invitation for CodeCraft 2008 - IIIT Hyd's Online Programming Contest

troy

A  Arranging Amplifiers - 100 points

B  Building Beacons - 200 points

C  Calculate 'd' Cost - 150 points

D  Distinct Subsequences - 150 points

E  Eliminate 'd' Enimies - 300 points

F  Flying Frogs - 200 points

G  G-Line Grid - 200 points

H  Hospital at Hands - 250 points

I  Incrementing Integers - 250 points

J  Jazzy Job - 150 points

troy

A:
Arranging Amplifiers

Scientists at the TIFR, Mumbai, are doing some cutting edge research on the Propagation of Signals. A young researcher comes up with a method of progressively amplifying signals, as they progress along a path. The method involves the placing of Amplifiers at regular distances along the line. Each amplifier is loaded with a number a(i), which is called its amplification factor. The method of amplification is simple: an amplifier which recieves a signal of strength X, and has Y loaded in it, results in a signal of strength Y^X [ Y to the power X]. In course of his research, the young scientist tries to find out, that given a set of n amplifiers loaded with a(0), a(1), a(2), ...., a(n-1), which particular permutation of these amplifiers, when placed at successive nodes, with the initial node given a signal of strength 1, produces the strongest output signal.
this is better illustrated by the following example : 5 6 4
4^(5^(6^1)) is the strength of the strongest signal, which is generated by putting amplifier loaded with 6 in first place, 5 in second place and 4 in third place.
Given a list of integers specifying the set of amplifiers at hand, you must find out the order in which they must be placed,to get the highest signal strength. In case their exist multiple permutations with same output, you should print the one which has bigger amplifiers first.

Input Desciption

First line of input contains T, the number of test cases. For each test case first line contains a number ni, which is equal to the number of amplifiers available. Next line contains n integers, separated by spaces which denote the values with which the amplifiers are loaded.
Output Description

Output contains T lines, one for each test case. Each line contains ni integers, denoting the order in which the amplifiers should be kept such that the result is strongest.

Sample Input

2
3
5 6 4
2
2 3

Sample Output
6 5 4
2 3

Constraints And Limits

Dataset 1: T ≤ 20, Ni ≤ 10^5, Each amplifier will be loaded with a positive integer p, 0 < p ≤ 10^9.No two amplifier > 1shall be loaded with the same integer., Memory Limit: 128 MB. Time Limit: 1 sec. 100 points.

troy

B:
Building Beacons

A Millionaire Eccentric Mathematician purchases a small Island, to build his residence. In order to keep away Trespassers, he decides to Build some Beacons (Towers) on the perimeter of the Island. To build these Beacons, he visits the Mainland to purchase Stone.

Being obsessed with Prime Numbers, the stone blocks he orders are all Regular Tridecagons (13 Sides). However, their heights are variable. On delivery of the Blocks, he orders them to be flattened perfectly from the top and the bottom, so that the Tridecagonal shape is viewable from the Top (or Bottom), in such a way that the Height of each block measures to a power of 2. The stones, procured from various sources, are of Variable strength. He intends to build the Beacons by placing Stone Blocks one over the other. The heights of the Towers are specified by the Mathematician, and they are also Prime Numbers. He instructs the Architect to make sure that once the Beacons are complete, the strengths of the used stones add up to the Maximum Possible Number.

The Architect, not knowing how the job can be done, or even whether it CAN be done, with such complicated restrictions, approaches you to find this out for him.
Input
First line of input contains a positive integer T, the number of test cases. The first line of each test case contains a positive integer K, equal to the total number of stones available. This line is followed by K lines, each containing a pair of positive integers X,Y. Here X denotes the height of that stone (here the height would be 2X) and Y denotes its value. Followed is a line containing an integer N, the number of towers. Each of the next N lines contain a single positive number, which is the height H of the corresponding tower the mathematician wants to build.
Output
Output contains T lines, one for each test case, containing a number denoting the maximum sum total of strengths of rocks used to construct the Beacons if solution is possible, else the message "Plan Failed!".
Sample Input
1
2
2 3
0 4
1
5

Sample Output
7

Constraints And Limits
Dataset 1: T ≤11,H <10^18,0 ≤ X ≤977,0 < Y ≤977,0 ≤ k ≤977,N ≤ 97 . Memory Limit: 128 MB. Time Limit: 4 sec. 100 points.
Dataset 2: T ≤11,H <10^281,0 ≤ X ≤977,0 < Y ≤977,0 ≤ k ≤977 ,≤ 97. Memory Limit: 128 MB. Time Limit: 4 sec. 100 points.

troy

C:
Calculate The Cost


In a small Village near the Himalayas, there is a rich Land-Owner, in Possession of a vast, rectangular tract of land. Unknown to him, a Major Oil Corporation has verified the existence of a vast Oil Resource beneath the land owned by him.
The Oil Company sends a Man to negotiate the purchase of a rectangular field from within the landowner's land, with sides parallel to those of his area. The Landowner, valuing his land according to the trees growing in it and the area to be purchased, gives the company man a Map of his Land, marking the location of trees of different types, and a list of the worth of each type of tree.

To ensure the most economic purchase of land with the required dimensions, the Company Man provides you with the data in his possession, and alongwith that, a list of the land areas that he considers good by his judgement.
You must provide, for each land area that he has listed, the Sum Total of the values of the Trees that lie Within or On the Boundary of that land area.


Input Description

The first line of the input contains an integer T, which is the number of test cases. For each test case, the first line contains an integer n, equal to the number of trees in the area. This line is followed by n lines each containing 3 integers separated by spaces which are coordinate of the tree ( x, y ) and value of that tree. Following this is an integer R, equal to the number of proposols of land areas given by the Company Man. Next R lines contain 4 integers each (x1, y1, x2, y2) which are the coordinates of lower left ( x1,y1 ) and upper right ( x2, y2 ) corner of the rectangular area.

Output Description

For each test case, your program should output R lines containing the sum of values of the Trees which lie inside or on the corresponding rectangular plot. There should NOT BE any blank lines between output of different test cases.

Sample Input
1
3
1 1 2
2 2 3
3 3 4
2
1 1 1 2
0 0 5 5

Sample Output
2
9

Constraints And Limits
Dataset 1: T≤10, n ≤ 10^5, r ≤ 50000, 0 ≤ x,y ≤ 10^7, value of any tree ≤ 10^4.
For any rectangular area 0 ≤ x1 ≤ x2 ≤ 10^7, 0 ≤ y1 ≤ y2 ≤ 10^7 . Memory Limit: 128 MB. Time Limit: 1 sec. 150 points.
Note 1: There can be more than one trees at the same point.
Note 2: The input data is large ( about 15 MB ), be careful about your input output routines.
.

troy

D:
Distinct Subsequences

Given a string, count the number of distinct subsequences of it ( including e mpty subsequence ). For the uninformed, A subsequence of a string is a new string which is formed from the original string by deleting some of the characters without disturbing the relative positions of the remaining characters.
For example, "agh" is a subsequence of "abcdefgh" while "ahg" is not.

Input Desciption

First line of input contains an integer T which is equal to the number of test cases. You are required to process all test cases. Each of next T lines contains a string s.
Output Description

Output consists of T lines. Ith line in the output corresponds to the number of distinct subsequences of ith input string. Since, this number could be very large, you need to output ans%1000000007 where ans is the number of distinct subsequences.

Sample Input

3
AAA
ABCDEFG
CODECRAFT

Sample Output
4
128
496

Constraints And Limits

Dataset 1: T ≤ 100, length(S) ≤ 15 Memory Limit: 128 MB. Time Limit: 4 sec. 25 points.
Dataset 2: T ≤ 100, length(S) ≤ 1000 Memory Limit: 128 MB. Time Limit: 2 sec. 25 points.
Dataset 3: T ≤ 20, length(S) ≤ 100000 Memory Limit: 128 MB. Time Limit: 2 sec. 100 points.

troy

E:
Eliminate The Enemies

In a modification of the popular game 'Pacman', the player has to move in a two-dimensional grid. Several cells of the grid are blocked. The player can start from any cell that is not blocked and can move in any of the directions, i.e. north, west, south or east, provided that the cells are unblocked.
As soon as the player passes a cell, an enemy is generated in that cell, making it impossible for the player to pass through that cell again. Thus, the player can pass through any given cell only once. The player has to traverse all the unblocked cells in the grid in order to win .
The player can begin at any free cell. Note that the same path with different starting points and even with the same starting point but with different paths of traversal is treated as different routes. The problem requires you to print the total number of all such possible routes.

Input Desciption

Each test case starts with a line containing two integers, m and n. Each of the next m lines contain a string of n characters describing the configuration of the grid. '*' denotes a blocked cell and '.' denotes unblocked cells. The input ends with a case having m = 0 and n = 0 and this case need not be processed.
Output Description

For each test case, print one line containing the total number of possible routes for the corresponding case. As this number can be quite large, you should print ans%1000000007 where ans is the required result.

Sample Input

3 3
...
.*.
...
3 7
...*...
.*.*.*.
.......
3 3
***
*.*
***
0 0

Sample Output
16
8
1

Constraints And Limits

Dataset 1: m ≤ 100, n ≤ 7, number of test cases ≤ 50, Time Limit : 3 seconds. 300 points.

troy

F:
Flying Frogs

WiseFrog, The King of FrogLand is on his Deathbed. He has 2 Sons, SensibleFrog and SmartFrog. Both of them are "Infinitely Intelligent". To decide who will succeed him as King, he devises a Strategy Game for the two Sons-

An Arena is constructed, in the form of a Rectangle, having m X n Square Areas. They are labelled as (i,j), starting from the Upper Left extremity of the Arena [i=0,1,2...n-1; j=0,1,2...m-1]. The Squares in the Arena are filled with Flying Frogs, in a Random Manner, such that there can be any number of Frogs in each square.

Once the Arena is ready, the 2 Frog Princes begin to play the Game, which is played in the following manner: SensibleFrog, being the King's favourite, starts the Game.

Each Prince takes his turn alternately. In his turn, he is permitted a maximum of K moves, and a minumum of 1 move. A "Move" is defined as the Issuing of an Order to any Frog of his choice. The "order" consists of the Direction to jump in, and the Number of Squares to Cover ( which should be positive ), the directions of movement permitted being Up and Left Only. However, the Order must not be such that it causes the Frog to land outside the Arena. Being Flying Frogs, the frogs in the Arena can jump any distance without trouble.

If there arrives a situation where the Prince having his turn does not have ANY move Possible ( that is, ALL the Flying Frogs are already at the top-left most square of the arena ), the other Prince is declared the Winner. Given all the Starting Conditions, your task is to find out who becomes the King of FrogLand.


Input Desciption

First line of input contains an integer T, equal to the number of test cases. Followed is the description of each of the T test cases and you are required to process all test cases. First line of each test case contains three integers m,n,k ( in this order ). Each of the next m lines contain n integers separated by spaces. Jth integer in ith line corresponds to the number of Flying Frogs in Square (i,j) in the arena.
Output Description

Output contains one line for each test case. You have to output "SensibleFrog Wins!." if SensibleFrog wins and "SmartFrog Wins!." otherwise.

Sample Input

3
1 1 1
837465
2 2 1
0 0
0 1
2 2 2
0 0
0 2

Sample Output
SmartFrog Wins!.
SmartFrog Wins!.
SensibleFrog Wins!.

Constraints And Limits

Dataset 1: T ≤ 20, 1 ≤ m,n ≤ 1000, m*n ≤ 10^5, 1 ≤ k ≤ 10^9 , 0 ≤ Number of Frogs in a square ≤ 10^8. Time Limit : 4 seconds, 100 Points.
Dataset 2: T ≤ 20, 1 ≤ m,n ≤ 1000, m*n ≤ 10^5, 1 ≤ k ≤ 10^9 , 0 ≤ Number of Frogs in a square ≤ 10^100. Time Limit : 4 seconds 100 Points.
The total input data in each of the input file doesn't exceed 5 MB.

troy

G:
G-Line Grid

The 21st century introduces the multicores. As a result a research is going on in parallel Computing. With time the number of processor would grow very large. As of now , Professor Biloo at IIIT asks a student to implement the following code on multiple G-line processors.


        for(i=1;i<=x;i++){
                for(j=1;j<=x;j++){
                        for(k=1;k<=a;k++){
                                z=z%y;
                        }
                }
                for(j=1;j<=b;j++){
                        z=z/y;
                }
        }
        for(i=1;i<=c;i++){
                z=z%y;
        }



The students experiments and finds that the only significant operations are the modulus(%) and division(/) operation which take almost equal time. The time taken by other operations may be ignored in the order analysis. He finds a algorithm to solve the problem in which these operations can be carried out in random order. For his testing he chooses M processors . Each processor will carry out exactly M operations (% or /) .The performance is optimal when such a scheme exactly covers all the operations.

Puzzled, the student finds that this can only be done for some specific values of x for given a,b and c. He wants to trick the professor, so he needs few values of x for which his algorithm works. However, to make the professor feel that he manually did it these values of x need to be as small as possible.

Given the values of a,b,c and k, output the first k values of x, for which the student's algorithm works.
Note: The value of x should be greater than or equal to 0.


Input Desciption

The first line of input contains an integer t , the number of testcases. For each testcase , there is exactly one line which contains 4 space separated a,b,c and k.

Output Description

For each test case , output the corresponding k values of x , each in successive different lines.

Sample Input

1
1 2 1 4

Sample Output
0
1
2
3

Constraints And Limits

Dataset 1: t ≤ 10 .The values in the output vi ≤ 10^12. Each of the intermediate values will fit in a 64 bit variable. The values a,b,c would be such that 0 ≤ a,b,c ≤ 100 and b^2-4ac ≥ 0. k ≤ 1000. Time Limit : 3 seconds. 200 points.

troy

H:
Hospital at Hands

In a remote part of the Country, there lies a group of towns, quite far from any other areas. These towns are connected by a set of roads, having the property that there is exactly one path connecting any two towns, and every town is connected.

Apollo Hospitals Ltd. decides to invest in this area, and build some Hospitals. Their analyst has a monumental task ahead of him. His job is to find out a Set of continuous towns, from among them, to build one hospital in each. The path connecting the first town to the last town in the set (which obviously passes through all the remaining ones) should not be more than length L, to avoid inconvenience to the visiting doctors. Also, the analyst has to make sure that his selection of target towns is such that the people of the area have to cover the least distance to reach the hospital closest to them.

Thus, the towns where Hospitals will be built have to be chosen keeping in mind that the sum of distances that people from each town will need to cover, in order to reach the Hospital closest to them, should be Minimum. You have to find this mimumum sum.


Input Desciption

First line of input contains an integer T which is equal to the number of test cases. You are required to process all test cases.Each test case starts with 2 space separated integers N,L. N denotes the number of towns and L is the length of path connecting first and last town in the set. Next N-1 lines follow each containd two space separated interges a and b denoting a road between A and B. A and B are 0 based.
Output Description

Output consists of T lines. Ith line in the output corresponds to the minimum sum total of the distances of all the towns with the nearest hospital for thr Ith test case.

Sample Input

2
3 1
0 1
1 2
4 1
0 1
1 2
2 3

Sample Output
1
2

Constraints And Limits

Dataset 1: T ≤ 30, n ≤ 10000 , 0 < L ≤100 Memory Limit: 128 MB. Time Limit: 4 sec. 250 points.

troy

I:
Incrementing Integers

Starting from the number '1', every time you can choose a digit from the current number and add it to the number itself. 23, for example, could be changed into 25 or 26. To get 100, using the above scheme, paths A and B are both possible. A requires 21 steps, but B needs only 17 (which is also the minimum)

A. 1-2-4-8-16-17-18-19-20-22-24-28-36-39-48-56-62-68-76-83-91-100
B. 1-2-4-8-16-17-24-28-36-39-48-56-62-68-76-83-91-100

C is another 17 step solution for 100.

C. 1-2-4-8-16-22-24-28-36-39-48-56-62-68-76-83-91-100

Now, you are given several numbers, for each number, print the minimum steps S and number of solutions T.
As T could be quite large, you should print T%1000000007 instead.


Input Desciption

Each line of input contains a integer K as a test case. Input ends with End Of File.
Output Description

For each test case print the minimum steps and solutions in a single line. If it's impossible to get the number, print "IMPOSSIBLE" instead. ( without the quotes ).

Sample Input

16
100
87

Sample Output
4 1
17 2
IMPOSSIBLE

Constraints And Limits

Dataset 1: Number of test cases ≤ 100, 1 ≤ K ≤ 10^9. 250 Points. Time Limit: 6 seconds.