Markham Saturday 14:00 Java Homework 20.10.31.

Question 1:

Most likely, you will notice that you have a mouse attached to your computer, which lets you move the cursor around the screen. Your job is to get between the mouse and the cursor.

Suppose that the bottom left-hand corner of your screen is (0,0), and all points on the screen are given by integer co-ordinates (x,y) where 0≤x≤c and 0≤y≤r. Thus, the top-right corner of the screen is at position (c,r), bottom-right corner is (c,0), and top-left corner is (0,r).

When a mouse is moved, it sends a pair of integers (a,b), indicating that the cursor should be moved a units in the x-direction and b units in the y-direction. It is worth noting that this is relative motion (i.e., how far to move) rather than absolute motion (i.e., where to move). It is also worth noting that a and b may be positive, negative or zero.

You can assume the mouse starts at position (0,0). Your job is to read input messages (i.e., relative motion positions sent by the mouse) and update the cursor to the new position on the screen. Your output (to the screen) will be the position of the mouse after each move.

If the mouse hits the screen boundary, it stops moving in that direction. For example, if the mouse is supposed to move (−100,−10) from its current position (30,40), the final positions will be (0,30): the mouse will hit the left-hand side boundary, but still manages to move down.

Input is listed as pairs, the first pair being (c,r), followed by the relative motion pairs (x,y). The input is terminated when the mouse moves (0,0).

Sample Input 1
100 200
10 40
-5 15
30 -30
0 0


Sample Output 1
10 40
5 55
35 25

Sample Input 2
30 40
30 40
-100 -10
0 0

Sample Output 2
30 40
0 30

Question to Think:

You and a friend are playing the classic game of Battleships. You each have a grid consisting of M rows of N cells (1≤N,M≤2000). Each cell is either empty or contains a player’s ship (in this version of the game, all ships are the size of one cell). The goal of the game is to destroy all of the opponent’s ships by hitting individual cells.

You and your friend have bet tons of CompSci points on this game. Unfortunately, your friend is completely owning you. So desperate times call for desperate measures.

You know for a fact that you can distract your friend for a brief moment by telling him that a famous programmer is behind him, but this trick will only work exactly once (programmers are so predictable). While he isn’t looking, you’ll have time to snatch up some of his ships with one hand. Your hand can cover a square of exactly S×S cells (1≤S≤N,M), and you can gather all the ships within such a square at once.

Of course, your friend is no fool, so he’s got his grid well concealed. As such, you don’t know anything about it except its size, so when the time comes, you’ll just choose a random square of size S×S that’s completely within the grid.

As usual, these bets attract large crowds. One of the bystanders who can see your opponent’s grid knows your plan, and is curious as to the expected number of ships that you will grab (in other words, the average number of ships out of all the possible snatches you could make). Nerdy though he is, he can’t calculate it in his head, so he runs to a computer and codes up a program…

Input Specification
Line 1: 3 integers – M, N, and S
The next M lines: N characters each, representing your opponent’s grid – an X represents a ship, while a . represents an empty cell.

Output Specification
A single number – the expected number of ships that you’ll grab. It must be within 10−8 of the correct answer.

Sample Input
3 4 2
XX.X
XX..
.X..

Sample Output
2

Explanation
There are 6 possible areas you could pick, yielding this many ships each:
4 2 1
3 2 0
This is a total of 12 ships, for an average of exactly 2.