PMCA Friday 19:00 Python Homework 20.10.23.

24 Oct PMCA Friday 19:00 Python Homework 20.10.23.

Question 1:

This question involves calculating the value of aromatic numbers which are a combination of Arabic digits and Roman numerals.

An aromatic number is of the form ARARAR…AR, where each A is an Arabic digit, and each R is a Roman numeral. Each pair AR contributes a value described below, and by adding or subtracting these values together we get the value of the entire aromatic number.

An Arabic digit A can be 0, 1, 2, 3, 4, 5, 6, 7, 8 or 9. A Roman numeral R is one of the seven letters I, V, X, L, C, D, or M. Each Roman numeral has a base value:

The value of a pair AR is A times the base value of R. Normally, you add up the values of the pairs to get the overall value. However, wherever there are consecutive symbols ARA′R′ with R′ having a strictly bigger base value than R, the value of pair AR must be subtracted from the total, instead of being added.

For example, the number 3M1D2C has the value 3×1000+1×500+2×100=3700 and 3X2I4X has the value 3×10−2×1+4×10=68.

Write a program that computes the values of aromatic numbers.

Input Specification
The input is a valid aromatic number consisting of between 2 and 20 symbols.

Output Specification
The output is the decimal value of the given aromatic number.

Sample Input 1
3M1D2C

Output for Sample Input 1
3700

Sample Input 2
2I3I2X9V1X

Output for Sample Input 2
-16

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.