PMCA Friday 19:00 Python Homework 20.11.06.

08 Nov PMCA Friday 19:00 Python Homework 20.11.06.

Question 1:
Jack has an LED clock radio, which is a 12-hour clock, displaying times from 12:00 to 11:59. The hours do not have leading zeros but minutes may have leading zeros, such as 2:07 or 11:03.

When looking at her LED clock radio, Jack likes to spot arithmetic sequences in the digits. For example, the times 12:34 and 2:46 are some of her favourite times, since the digits form an arithmetic sequence.

A sequence of digits is an arithmetic sequence if each digit after the first digit is obtained by adding a constant common difference. For example, 1,2,3,4 is an arithmetic sequence with a common difference of 1, and 2,4,6 is an arithmetic sequence with a common difference of 2.

Suppose that we start looking at the clock at noon (that is, when it reads 12:00) and watch the clock for some number of minutes. How many instances are there such that the time displayed on the clock has the property that the digits form an arithmetic sequence?

Input Specification
The input contains one integer D (0≤D≤1000000000), which represents the duration that the clock is observed.

Output Specification
Output the number of times that the clock displays a time where the digits form an arithmetic sequence starting from noon (12:00) and ending after D minutes have passed, possibly including the ending time.

Sample Input 1
34

Sample Output 1
1

Explanation for Sample Output 1
Between 12:00 and 12:34, there is only the time 12:34 for which the digits form an arithmetic sequence.

Sample Input 2
180

Sample Output 2
11

Explanation for Sample Output 2
Between 12:00 and 3:00, the following times form arithmetic sequences in their digits (with the difference shown):

12:34 (difference 1),
1:11 (difference 0),
1:23 (difference 1),
1:35 (difference 2),
1:47 (difference 3),
1:59 (difference 4),
2:10 (difference -1),
2:22 (difference 0),
2:34 (difference 1),
2:46 (difference 2),
2:58 (difference 3).

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.