TLE '17 Contest 3 P5 - Hypercube Hotel

View as PDF

Submit solution


Points: 17 (partial)
Time limit: 1.0s
Java 2.0s
Python 2.0s
Memory limit: 256M

Author:
Problem types
The Hypercube Hotel game is also very popular and universally acclaimed. Get it for the Phillips CD-i while it lasts!

The Hypercube Hotel is a strange new mathematically themed hotel, a competitor to Hilbert's Hotel. The hotel has an unusual way of numbering its rooms. Each room has an N digit number so that the ith digit (from the left) is between 1 and Ai. Conversely, every number in this form has a corresponding room. Room numbers are unique.

Two different rooms are called neighbours if for every i, the ith digit of the two room numbers differ by at most 1. For example, the rooms with numbers 213 and 222 are neighbours but the rooms with numbers 111 and 131 are not neighbours. A room is not a neighbour of itself.

All the rooms in the hotel are occupied, so each room generates a certain amount of noise. If a room has number m, call this quantity xm. For each room, the noise level of that room is the sum of the amounts of noise generated by its neighbours. Given the amount of noise generated by each room, find the noise level of each room.

Constraints

1N9

1Ai5

0xm1014

SubtaskPointsAdditional Constraints
15N=2
25Ai2
35N5, Ai4, xm100
415N7, Ai4, xm100
570None

Input Specification

The first line contains the integer N.

The next line contains N integers A1,A2,,AN.

The next A1×A2××AN lines each contain a single integer xm. The lines are given in increasing order of the room number m.

Output Specification

For each room, output a line containing a single integer, the noise level of that room. Do this in increasing order of room number.

Sample Input

Copy
2
2 3
1
2
3
4
5
6

Sample Output

Copy
11
19
13
8
16
10

Comments

There are no comments at the moment.