Euclid  Problem

The Problem

From Euclid it is known that for any positive integers A and B there exist such integers X and Y that AX+BY=D, where D is the greatest common divisor of A and B. The problem is to find for given A and B corresponding X, Y and D.

The Input

The input will consist of a set of lines with the integer numbers A and B, separated with space (A,B<1000000001).

The Output

For each input line the output line should consist of three integers X, Y and D, separated with space. If there are several such X and Y, you should output that pair for which |X|+|Y| is the minimal (primarily) and X<=Y (secondarily).

Sample Input

4 6
17 17

Sample Output

-1 1 2
0 1 17

Robot Motion

Source file:	robot.{c, cpp, java, pas}
Input file:	robot.in
Output file:	robot.out

A robot has been programmed to follow the instructions in its path. Instructions for the next direction the robot is to move are laid down in a grid. The possible instructions are
N north (up the page)
S south (down the page)
E east (to the right on the page)
W west (to the left on the page)
For example, suppose the robot starts on the north (top) side of Grid 1 and starts south (down). The path the robot follows is shown. The robot goes through 10 instructions in the grid before leaving the grid.
Compare what happens in Grid 2: the robot goes through 3 instructions only once, and then starts a loop through 8 instructions, and never exits.
You are to write a program that determines how long it takes a robot to get out of the grid or how the robot loops around.
There will be one or more grids for robots to navigate. The data for each is in the following form. On the first line are three integers separated by blanks: the number of rows in the grid, the number of columns in the grid, and the number of the column in which the robot enters from the north. The possible entry columns are numbered starting with one at the left. Then come the rows of the direction instructions. Each grid will have at least one and at most 10 rows and columns of instructions. The lines of instructions contain only the characters N, S, E, or W with no blanks. The end of input is indicated by a row containing 0 0 0.
For each grid in the input there is one line of output. Either the robot follows a certain number of instructions and exits the grid on any one the four sides or else the robot follows the instructions on a certain number of locations once, and then the instructions on some number of locations repeatedly. The sample input below corresponds to the two grids above and illustrates the two forms of output. The word "step" is always immediately followed by "(s)" whether or not the number before it is 1.
Example input:

3 6 5
NEESWE
WWWESS
SNWWWW
4 5 1
SESWE
EESNW
NWEEN
EWSEN
0 0 0

Example output:

10 step(s) to exit
3 step(s) before a loop of 8 step(s) 

Find the Winning Move : 

Source file:	win.{c, cpp, java, pas}
Input file:	win.in
Output file:	win.out

4x4 tic-tac-toe is played on a board with four rows (numbered 0 to 3 from top to bottom) and four columns (numbered 0 to 3 from left to right). There are two players, x and o, who move alternately with x always going first. The game is won by the first player to get four of his or her pieces on the same row, column, or diagonal. If the board is full and neither player has won then the game is a draw.
Assuming that it is x's turn to move, x is said to have a forced win if x can make a move such that no matter what moves o makes for the rest of the game, x can win. This does not necessarily mean that x will win on the very next move, although that is a possibility. It means that x has a winning strategy that will guarantee an eventual victory regardless of what o does.
Your job is to write a program that, given a partially-completed game with x to move next, will determine whether x has a forced win. You can assume that each player has made at least two moves, that the game has not already been won by either player, and that the board is not full.
The input file contains one or more test cases, followed by a line beginning with a dollar sign that signals the end of the file. Each test case begins with a line containing a question mark and is followed by four lines representing the board; formatting is exactly as shown in the example. The characters used in a board description are the period (representing an empty space), lowercase x, and lowercase o. For each test case, output a line containing the (row, column) position of the first forced win for x, or '#####' if there is no forced win. Format the output exactly as shown in the example.
For this problem, the first forced win is determined by board position, not the number of moves required for victory. Search for a forced win by examining positions (0, 0), (0, 1), (0, 2), (0, 3), (1, 0), (1, 1), ..., (3, 2), (3, 3), in that order, and output the first forced win you find. In the second test case below, note that x could win immediately by playing at (0, 3) or (2, 0), but playing at (0, 1) will still ensure victory (although it unnecessarily delays it), and position (0, 1) comes first.
Example input:

?
....
.xo.
.ox.
....
?
o...
.ox.
.xxx
xooo
$

Example output:

#####
(0,1)

The Problem :

You may have solved linear equation early in the school. Problems involving solving sets of linear equation are very important in the field of Engineering and Mathematics. 
Let us consider that we have a system of linear equations 
                 a₁₁x₁ + a₁₂x₂ + a₁₃x₃ = c₁ 
                 a₂₁x₁ + a₂₂x₂ + a₂₃x₃ = c₂ 
                 a₃₁x₁ + a₃₂x₂ + a₃₃x₃ = c₃ 
We can solve it by reducing technique: 
            Step 1: 
            x₁ + a₁₂/a₁₁x₂ + a₁₃/a₁₁x₃ = c₁/a₁₁ 
            a₂₁x₁ + a₂₂x₂ + a₂₃x₃ = c₂ 
            a₃₁x₁ + a₃₂x₂ + a₃₃x₃ = c₃
            Step 2:
            x₁ + a₁₂/a₁₁x₂ + a₁₃/a₁₁x₃ = c₁/a₁₁
                    (-a₂₁* a₁₂/a₁₁)a₂₂x₂ +  (-a₂₁* a₁₃/a₁₁)a₂₃x₃ =  (-a₂₁* c₁/a₁₁)c₂
                    (-a₃₁* a₁₂/a₁₁)a₂₂x₂ +  (-a₃₁* a₁₃/a₁₁)a₂₃x₃ =  (-a₃₁* c₁/a₁₁)c₂
Now do as step 1 for second row and so on.
This can be made more effective using matrix method. The set of equation for `n' unknowns can be written as
                 a₁₁x₁ + a₁₂x₂ + a₁₃x₃ + ... + a_1nx_n = c₁
                 a₂₁x₁ + a₂₂x₂ + a₂₃x₃ + ... +  a_2nx_n = c₂
                 a₃₁x₁ + a₃₂x₂ + a₃₃x₃ + ... +  a_3nx_n  = c_{3
                         ...   ...   ...   ...   ...   ...   ...   ...   ...   ...   ...   ...   ...   ...}
                 a_m1x₁ + a_m2x₂ + a_m3x₃ + ... +  a_mnx_n  = c_n
In matrix form

Compactly        [A] * {X} = {C}
From this we can solve values of X's. The matrix [AC] is called an augmented (see example below) matrix. If after elimination process the rank of matrix [A] and rank of matrix [AC] not equals, the system is called inconsistent and it does not have a solution. If the matrix is consistent and number of unknowns is greater then rank of matrix then the matrix system has arbitarily many solutions containing (NumberOfUnknowns-rank) arbitary constants. Rank of a matrix is defined as the number of non zero rows of a matrix system. Otherwise if the rank and number of unknows equals then the system has been solved.
For example let a system of equations be
                  9x₁ + 4x₂ + x₃ = -17
                  x₁ - 2x₂ - 6x₃ = 14
                  x₁ + 6x₂  = 4
This sets of equation can be written as
9    4      1   -17
1  -2   -6      14
1    6      0        4
So the steps involving the solution is
Step : 1
              1             -2             -6             14
              1              6              0              4
              9              4              1            -17
Step : 2
              1             -2             -6             14
              0              8              6            -10
              0             22             55           -143
Step : 3
              1             -2             -6             14
              0              1              3/4             -5/4
              0              0             77/2           -231/2
Step : 4
              1             -2             -6             14
              0              1              3/4             -5/4
              0              0              1             -3
Step : 5
              1             -2              0             -4
              0              1              0              1
              0              0              1             -3
Step : 6
              1              0              0             -2
              0              1              0              1
              0              0              1             -3
x₁ = -2
x₂ = 1
x₃ = -3
Again consider this system
        2x₁ + 2x₂ + 2x₃ = 2
        4x₁ + 4x₂ + 4x₃ = 4
        16x₁ + 16x₂ + 16x₃ = 16
Steps are:
Step : 1
              2              2              2              2
              4              4              4              4
             16             16             16             16
Step : 2
              1              1              1              1
              0              0              0              0
              0              0              0              0
This system has number of unknowns 3 and rank is 1. So this system has arbitarily many solutions containing (3-1) = 2 arbitary constants.
Another system
x + y = 10
x + y = 20
x + y = 50
Steps are:
Step : 1
              1              1             10
              1              1             20
              2              2             50
Step : 2
              1              1             10
              0              0             10
              0              0             30
Step : 3
              1              1             10
              0              0             10
              0              0             30
Step : 4
              1              1             10
              0              0             10
              0              0              1
Step : 5
              1              1              0
              0              0              0
              0              0              1
Step : 6
              1              1              0
              0              0              0
              0              0              1
As rank of [A] (in this case: rank(A) = 1) is not equal to the rank of augmented matrix [AC] (in this case: rank(AC) = 2) , the system has no solution.
However though there are other methods to compute this solution for the matrix system, the main problem occurs are
        1. Round off errors or computational error due to the use of floating point number
        2. Error due to wrong order of the given equation.
To prevent round off error due to floating point number an approach can be used, similar to the process of doing fractional number. So we may use 1/3 as a expression of two integer, the numerator and the denominator, instead of .333333 (with loss of precision). Thus we can prevent this kind of error.
Consider this set of equations
                  5x₃ = 10
                  3x₂ - 3x₃ = 3
                  2x₁ - x₂ + 2x₃ = 7
This set of equations can be written as
0     0     5    10
0     3   -3     3
2   -1     2     7
Now how will you evaluate this matrix without ordering?

The Input

The first line of input is the number of the problem. The next line contains two integers - NumberOfUnknowns and NumberOfEquations (none of these is less then or equal to 0 and greater then 50). The next lines contains the matrix for the system of linear equations. There are number of rows equal to the NumberOfEquations and number of column equal to the NumberOfUnknowns+1. The numbers may be fractional, that is there may be numbers like 1/3 or 6/8. An problem number zero indicates the end of input.

The Output : 

First print (without the quotation mark)

"Solution for Matrix System # N"

Here `N' is the problem number as taken from input. Then on the next line, for each system of equations output the solution (if exists) expressed in the fractional form in each line. You may assume each of the numerator and denominator part will not exceed the limit of data type long long (64 bit). If there are many solutions as described above print (without the quotation mark)

"Infinitely many solutions containing n arbitrary constants."

(here `n' is the number as described above) , and if there is no solutions print (without the quotation mark)

"No Solution."

.Print a blank line between two systems of linear equations.

Sample Input : 

1
3 3
9  4  1 -17
1 -2 -6 14
1  6  0  4

2
3 3
2 2 2 2
4 4 4 4
16/1 16/1 16/1 16/1

3
2 3
1 1 10
1 1 20
2 2 50

4
1 1
3 10

0

Sample Output : 

Solution for Matrix System # 1

x[1] = -2
x[2] = 1
x[3] = -3

Solution for Matrix System # 2
Infinitely many solutions containing 2 arbitrary constants.

Solution for Matrix System # 3
No Solution.

Solution for Matrix System # 4

x[1] = 10/3

The  Problem : 

Median holds an vital role in the world of statistics. By definition, it is a value which divides an array into two equal parts. In this  problem you are to determine the current median of some long integers.
Suppose, we have five numbers {1,3,6,2,7}. In this case, 3 is the median as it has exactly two numbers on its each side. {1,2} and {6,7}.
If there are even number of values like {1,3,6,2,7,8}, only one value cannot split this array into equal two parts, so we consider the average of the middle values {3,6}. Thus, the median will be (3+6)/2 = 4.5. In this problem, you have to print only the integer part, not the fractional. As a result, according to this problem, the median will be 4!

Input : 

The input file consists of series of integers X ( 0 <= X < 2^31 ) and total number of integers N is less than 10000. The numbers may have leading or trailing spaces.

Output :

For each input print the current value of the median.

Sample Input :

1

3
4
60
70
50
2

Sample Output :

1
2
3
3
4
27
4