Cerinta completa

Given an cube, let (where ) denote the value stored in cell .

A sub-cube (where ) of an cube is considered to be special if the maximum value stored in any cell in the sub-cube is equal to .

For each in the inclusive range , calculate the number of special sub-cubes. Then print each as a single line of space-separated integers (i.e., ).

Input Format

The first line contains an integer, , denoting the number of queries. The subsequent lines describe each query over two lines:

  1. The first line contains an integer, , denoting the side length of the initial cube.
  2. The second line contains space-separated integers describing an array of integers in the form . The integer in some cell is calculated using the formula .

Constraints

  • where

Output Format

For each query, print space-separated integers where the integer denotes the number of special sub-cubes for .

Sample Input

2
2
2 1 1 1 1 1 1 1
2
1 1 1 1 2 1 1 2

Sample Output

7 1
6 1

Explanation

We must perform the following queries:

  1. We have a cube of size and must calculate the number of special sub-cubes for the following values of :

    • : There are sub-cubes of size and seven of them have a maximum value of written inside them. So, for , the answer is .
    • : There is only one sub-cube of size and the maximum number written inside it is . So, for , the answer is .

    We then print the respective values for each as a single line of space-separated integers (i.e., 7 1).

  2. We have a cube of size and must calculate the number of special sub-cubes for the following values of :

    • : There are sub-cubes of size and six of them have a maximum value of written inside them. So, for , the answer is .
    • : There is only one sub-cube of size and the maximum number written inside it is . So, for , the answer is .

    We then print the respective values for each as a single line of space-separated integers (i.e., 6 1).

Limbajul de programare folosit: java8

Cod:

import java.io.*;

public class Solution {
    private static class FastScanner {
        private final InputStream in;
        private final byte[] buffer = new byte[1 << 16];
        private int ptr = 0, len = 0;
        FastScanner(InputStream is) { this.in = is; }
        private int read() throws IOException {
            if (ptr >= len) {
                len = in.read(buffer);
                ptr = 0;
                if (len <= 0) return -1;
            }
            return buffer[ptr++];
        }
        int nextInt() throws IOException {
            int c;
            do { c = read(); } while (c <= ' ' && c != -1);
            int sign = 1;
            if (c == '-') { sign = -1; c = read(); }
            int val = 0;
            while (c > ' ') {
                val = val * 10 + (c - '0');
                c = read();
            }
            return val * sign;
        }
    }

    static int idx(int x, int y, int z, int n) {
        return (x * n + y) * n + z;
    }

    public static void main(String[] args) throws Exception {
        FastScanner fs = new FastScanner(System.in);
        int q = fs.nextInt();
        StringBuilder out = new StringBuilder();

        while (q-- > 0) {
            int n = fs.nextInt();
            int total = n * n * n;

            int[] prev = new int[total];
            long[] ans = new long[n + 1];

            for (int i = 0; i < total; i++) {
                int v = fs.nextInt();
                prev[i] = v;
                if (v == 1) ans[1]++;
            }

            int sidePrev = n;
            for (int s = 2; s <= n; s++) {
                int side = n - s + 1;
                int[] cur = new int[side * side * side];
                long cnt = 0;

                for (int x = 0; x < side; x++) {
                    for (int y = 0; y < side; y++) {
                        for (int z = 0; z < side; z++) {
                            int m = prev[idx(x, y, z, sidePrev)];
                            int t;
                            t = prev[idx(x + 1, y, z, sidePrev)]; if (t > m) m = t;
                            t = prev[idx(x, y + 1, z, sidePrev)]; if (t > m) m = t;
                            t = prev[idx(x, y, z + 1, sidePrev)]; if (t > m) m = t;
                            t = prev[idx(x + 1, y + 1, z, sidePrev)]; if (t > m) m = t;
                            t = prev[idx(x + 1, y, z + 1, sidePrev)]; if (t > m) m = t;
                            t = prev[idx(x, y + 1, z + 1, sidePrev)]; if (t > m) m = t;
                            t = prev[idx(x + 1, y + 1, z + 1, sidePrev)]; if (t > m) m = t;

                            cur[idx(x, y, z, side)] = m;
                            if (m == s) cnt++;
                        }
                    }
                }

                ans[s] = cnt;
                prev = cur;
                sidePrev = side;
            }

            for (int s = 1; s <= n; s++) {
                if (s > 1) out.append(' ');
                out.append(ans[s]);
            }
            out.append('\n');
        }

        System.out.print(out);
    }
}

Scor obtinut: 1.0

Submission ID: 464617843

Link challenge: https://www.hackerrank.com/challenges/counting-special-sub-cubes/problem

Counting Special Sub-Cubes