[Solved] Algorithm Homework12- Board Game

Eto and Luna are playing a board game for money. The game is player on an NxN board filled with numbers. In each roundEto picks a row and crosses it off, then Luna picks a column and crosses it off. The value at the intersection of their row andcolumn is Etos winnings. If the value is positive, Luna has to pay that amount of money to Eto. If the value is negative, Etohas to pay that amount of money to Luna.What is the largest amount of money that Eto can win (or, the least amount that she can lose, if she cannot win)?InputThe first line of the input contains a single integer N (1 <= N <= 8), representing the size of the board. The following N linesdescribes the game board M. Each of those lines contains N integers Mi,j(-1000 <= Mi,j <= 1000), indicating the number atthe i-th row and j-th column.OutputPrint one line containing the largest possible score after the game.Example 1Input:210 10-5 -5Output:5Explanation:Eto crosses out first row, and Luna crosses out first column. The value of Mi,jis 10. So Eto gains $10.00.Eto crosses out second row, and Luna crosses out second column (because there are no other options). The value of Mi,jis-5. So Eto has to pay $5.00 to Luna.The balance of Etos winnings is $5.00.Example 2Input:210 -510 -5Output:5Page 2/2Example 3Input:210 -5-5 10Output:-10Page 1/1Desolate NumberGiven two integers A and B, a desolate number N is defined as follows:N is an (A+B)-bit integer;the binary representation of N has exactly A 1s and B 0s (leading zeroes are ok);N has the maximum number of 1s adjacent to at least one 0 in its binary representation.Your task is to find the smallest desolate number up to given A and B.InputThe input consists of a single line, containing two non-negative integers A and B (1 <= A + B <= 50).OutputPrint one line, containing the smallest desolate number.Example 1Input:4 3Output:45Example 2Input:1 1Output:1Example 3Input:3 2Output:13Page 1/2Move Union FindIn this problem you are to implement a variant of Union Find: Move Union Find.The data structure you need to write is also a collection of disjoint sets, supporting 3 operations:operation description1 a b Union the sets containing a and b . If a and b are already in the same set, ignore thiscommand2 a b Move the element a to the set containing b . If a and b are already in the same set, ignorethis command3 a Return the number of elements and the sum of elements in the set containing aInitially, the collection contains n sets: {1}, {2}, {3}, , {n}InputThe first line contains two integer N and M. N is the total number of sets initially, M is the number of commands. 1 <= N, M<= 100,000Each of the next m lines contain a command. For each operation, 1 <= a,b <= N.OutputFor each type-3 command, output 2 integers: the number of elements and the sum of elements.Example 1Input:5 41 1 22 3 41 3 52 4 13 1Output:3 7Explanation:Initial sets: {1}, {2}, {3}, {4}, {5}After 1 1 2 : {1, 2}, {3}, {4}, {5}After 2 3 4 : {1, 2}, {3, 4}, {5}After 1 3 5} : {1, 2}, {3, 4, 5}After 2 4 1 : {1, 2, 4}, {3, 5}Example 2Page 2/2Input:5 61 1 22 3 23 32 1 42 2 43 3Output:3 61 3Page 1/2Follow the PathYou are programming a new robot called Frank to navigate the path through a grid. Frank should be able to adjust todirection it is moving in rather than being pre-programmed. This particular robot needs to navigate through a 2D grid. Ateach grid location Frank receives the instructions for the instructions for its next move. The possible moves are:N move North (or up)S move South (or down)E move East (or right)W move West (or left)Your task now is to calculate what path Frank should take and verify that it actually took that path (otherwise you have a bugin the code that directs Frank through the grid).Example 1:FN E E S<-W Ev<-W<-W W E->S S^ vS N<-W<-W<-W WIf Frank enters this grid at the grid location just below of the position of F, it will move west, then south, then east, thensouth, then west three times, then north and west two more times and finally it will exit the grid.Example 2:FS E S<-W Ev v ^E->E->S N<-Wv ^N W E->E->NN W S W NIf Frank enters this grid at the grid location just below of the position of F, it will move south, then east twice, and then it willenter a loop consisting of 8 moves. Frank will never leave this grid.Input On the first line are three integers separated by blanks: the number of rows in the grid, the number of columns in thegrid, and the number of the column in which the robot enters from the north. The possible entry columns are numberedstarting 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 ofinstructions. The lines of instructions contain only the characters N, S, E, or W with no blanks.OutputThere should be one line of output. Either the robot follows a certain number of instructions and exits the grid on any onethe four sides or else the robot follows the instructions on a certain number of locations once, and then the instructions onsome number of locations repeatedly. The sample input below corresponds to the two grids above and illustrates the twoforms of output. The word step is always immediately followed by (s) whether or not the number before it is 1.Page 2/2Example 1Input:3 6 5NEESWEWWWESSSNWWWWOutput:10 step(s) to exitExample 2Input:4 5 1SESWEEESNWNWEENEWSENOutput:3 step(s) before a loop of 8 step(s)Page 1/2Yet Another Sorting Problem (YASP)It is lovely day for pancakes. Kou thought.As she said that, Kou found yet another sorting problem (yasp). In thisproblem, we are given a stack of integers and we are asked to sort that stackin ascending order from top to bottom. The only allowed operation, denotedby flip(t), is to flip all elements from the t-th elements to the top upside down.Note that the 1st element is the bottom element while the N-th element refersto the top element if the size of the stack is N. For example, consider thefollowing four stacks of integers.4 2 5 1 (top)3 3 4 22 4 3 35 5 2 41 1 1 5(bottom)(a) (b) (c) (d)Performing flip(3) on stack ( a ) will result in stack ( b ). Similarly, by applyingflip(2), stack ( b ) will become stack ( c ). Finally, we can apply flip(1) on stack( c ) and get the stack sorted as shown in stack ( d ).We need to figure out a sequence of flip operations that transforms the given stack into a sorted one.InputThe input consists of a single line. The stack of integers will be given in this line from top to bottom. The size of the stack isbetween 1 and 30, and those integers are between 1 and 100.OutputPrint one line containing (K+1) flip operations:Among the first K integers, the i-th integer specifies the t value of the i-th flip operation.The last, i.e., the (K+1)-th integer should always be 0 .If there are multiple solutions, output any of them.Example 1Input:1 2 3 4 5Output:0Example 2Input:5 4 3 2 1Output:1 0Page 2/2Example 3Input:5 1 2 3 4Output:1 2