TLE '17 Contest 3 P5 - Hypercube Hotel

View as PDF

Submit solution



Points: 17 (partial)
Time limit: 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 as an unusual way of numbering its rooms. Each room has an N digit number so that the i-th digit (from the left) is between 1 and A_i. 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 i-th 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 x_m. 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

1\le N \le 9

1\le A_i \le 5

0\le x_m \le 10^{14}

SubtaskPointsAdditional Constraints
15N=2
25A_i\le 2
35N \le 5, A_i \le 4, x_m\le 100
415N \le 7, A_i\le 4, x_m\le 100
570None

Input Specification

The first line contains the integer N.

The next line contains N integers A_1,A_2,\dots,A_N.

The next A_1\times A_2\times\cdots\times A_N lines each contain a single integer x_m. 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

2
2 3
1
2
3
4
5
6

Sample Output

11
19
13
8
16
10

Comments


  • 0
    1yangdan  commented on Dec. 6, 2017, 11:24 p.m. edited

    I think the memory restriction is a bit too strict on java submissions


    • 0
      bruce  commented on Dec. 7, 2017, 10:59 p.m.

      Java can pass. Mem complexity is O(5^N) and time complexity is O(N*5^N)


  • 1
    1yangdan  commented on Nov. 26, 2017, 9:34 p.m.

    Will there be an editorial for this question?


    • 9
      Eliden  commented on Nov. 27, 2017, 10:52 a.m. edited

      The original draft of my editorial has suffered a tragic accident, so the editorial will unfortunately be delayed. I plan to write something up soon, though. Edit: the editorial is up now.


      • 0
        ryx  commented on Dec. 1, 2017, 11:32 p.m.

        Could you provide some high level ideas, if not editorial? Thanks


        • 1
          1yangdan  commented on Dec. 6, 2017, 4:46 p.m. edit 2

          here's some idea ryx might be interested. Note this is idea only, so please don't delete this post.

          public static void update1D(int x, long nb1d[]) {
              if (x - 1 != 0) {
                  nb1d[x - 1] += val;
              }
              nb1d[x] += val;
              if(x + 1<=A9)
              nb1d[x + 1] += val;
          }
          
          public static void update2D(int x, int y, long nb2d[][]) {
              if (x - 1 != 0) {
                  update1D(y, nb2d[x - 1]);
              }
              update1D(y, nb2d[x]);
              if(x + 1<=A8)
              update1D(y, nb2d[x + 1]);
          
          }