1185 - Cub2

Sărbătorile de iarnă tocmai s-au încheiat. Florinel dorește să-și ajute părinții la despodobirea bradului. Tubul luminos pe care l-au folosit anul acesta este mai special. Are N3 becuri luminoase numerotate de la 1 la N3, iar fiecare bec care este inscripționat cu un număr prim, va rămâne mereu aprins. Cutia în care trebuie strâns tubul este un cub de latură N. Becul cu numărul 1, trebuie pus în colțul de coordonate (1,1,1), restul în spirală până la umplerea nivelului, apoi nivelul următor în sens invers, ș.a.m.d.

Exemplu – N = 3

Nivel 1

1 2 3
8 9 4
7 6 5

Nivel 2

18 17 16
11 10 15
12 13 14

Nivel 3

19 20 21
26 27 22
25 24 23

Fața 1 (spate)

21, 20, 19,
16, 17, 18,
 3,  2,  1

Fața 2 (dreapta)

23, 22, 21
14, 15, 16,
 5,  4,  3,

Fața 3 (frontal)

25, 24, 23,
12, 13, 14,
 7,  6,  5,

Fața 4 (stânga)

19, 26, 25,
18, 11, 12,
 1,  8,  7,

Cerința

Cunoscând latura N a cubului, să se umple cubul cu tubul luminos (becurile fiind legate crescător), apoi să se determine:

1. Coordonatele (x,y,z) ale becului cu numărul V. (x-linia, y-coloana, z-înălțimea)

2. Numărul de becuri luminoase situate pe fiecare față a cubului.

Date de intrare

Fişierul de intrare cub2.in conţine pe prima linie un număr natural p. Pentru toate testele de intrare, numărul p poate avea doar valoarea 1 sau valoarea 2.

Pe a doua linie a fișierului de intrare, sunt scrise două numere naturale N și V separate printr-un spațiu reprezentând dimensiunea cubului și valoarea becului pentru care trebuie determinate coordonatele.

Date de ieșire

Dacă valoarea lui p este 1, se va rezolva numai cerinţa 1. În acest caz, în fişierul de ieşire cub2.out se vor scrie trei numere naturale x y z, separate prin câte un spațiu, reprezentând coordonatele becului cu valoarea V.

Dacă valoarea lui p este 2, se va rezolva numai cerinţa 2. În acest caz, fişierul de ieşire cub2.out va conține 4 linii. Pe fiecare linie i, se va scrie câte un număr natural fi, reprezentând numărul de becuri inscripționate cu numere prime de pe fața i.

natural fi, reprezentând numărul de becuri inscripționate cu numere prime de pe fața i.

Restricții și precizări

• 1 ≤ N ≤ 200
• 1 ≤ V ≤ N3
• Pentru rezolvarea corectă a primei cerinţe se acordă 20 de puncte, iar pentru cerința a doua se acordă 80 de puncte.
• Pentru 20% dintre teste: 1 ≤ N ≤ 20
• Pentru 30% dintre teste: 21 ≤ N ≤ 100
• Pentru 50% dintre teste: 101 ≤ N ≤ 200

Exemple

cub2.in

1
3 10

cub2.out

2 2 2

Explicație

Atenție! Pentru acest test se rezolvă doar cerința 1).

linia 2, coloana 2, nivel 2 – este becul 10

cub2.in

2
3 10

cub2.out

4
3
4
3

Explicație

Atenție! Pentru acest test se rezolvă doar cerința 2).

4 – becuri inscripționate cu numere prime pe fața 1: 2, 3, 17, 19

3 – becuri inscripționate cu numere prime pe fața 2: 3, 5, 23

4 – becuri inscripționate cu numere prime pe fața 3: 5, 7, 13, 23

3 – becuri inscripționate cu numere prime pe fața 4: 7, 11, 19

def generate_spiral_layer(n, start_val):
    """ Generate a spiral layer of size n x n starting from start_val """
    layer = [[0] * n for _ in range(n)]
    num = start_val
    for layer_idx in range((n + 1) // 2):
        for i in range(layer_idx, n - layer_idx):
            layer[layer_idx][i] = num
            num += 1
        for i in range(layer_idx + 1, n - layer_idx):
            layer[i][n - layer_idx - 1] = num
            num += 1
        for i in range(n - layer_idx - 2, layer_idx - 1, -1):
            layer[n - layer_idx - 1][i] = num
            num += 1
        for i in range(n - layer_idx - 2, layer_idx, -1):
            layer[i][layer_idx] = num
            num += 1
    return layer

def generate_cube(N):
    """ Generate a cube of size N x N x N filled in spiral order """
    cube = [[[0] * N for _ in range(N)] for _ in range(N)]
    num = 1
    for z in range(N):
        layer = generate_spiral_layer(N, num)
        for y in range(N):
            for x in range(N):
                cube[z][y][x] = layer[y][x]
        num += N * N
    return cube

def find_coordinates(cube, V):
    """ Find coordinates (x, y, z) of the value V in the cube """
    N = len(cube)
    for z in range(N):
        for y in range(N):
            for x in range(N):
                if cube[z][y][x] == V:
                    return (x + 1, y + 1, z + 1)
    return None

def count_lights_on_faces(cube):
    """ Count the number of lights on each face of the cube """
    N = len(cube)
    counts = {'front': 0, 'back': 0, 'left': 0, 'right': 0, 'top': 0, 'bottom': 0}
    
    # Counting lights on each face
    for z in range(N):
        counts['top'] += N
        counts['bottom'] += N
    
    for y in range(N):
        counts['front'] += N
        counts['back'] += N
    
    for x in range(N):
        counts['left'] += N
        counts['right'] += N
    
    return counts

# Example Usage
N = 3
V = 7  # Example value to find coordinates for
cube = generate_cube(N)

coordinates = find_coordinates(cube, V)
face_counts = count_lights_on_faces(cube)

print(f"Coordinates of the light with number {V}: {coordinates}")
print(f"Number of lights on each face: {face_counts}")