Ois_grid, "Output is malformed"

Aiuto
1

Link al problema

immagine
immagine1536×1294 102 KB

immagine
immagine1506×1208 96.3 KB

Faccio 44/100 a causa di questi output “malformati”.
Tuttavia, non ho capito che cosa significhi.
Gli altri testcase sono corretti.

Ho notato che il template originale è fatto così:

N, M, R, G, B = map(int, input().strip().split())

grid = [['R'] * M for _ in range(N)]

mentre io l’ho modificato in

N, M, R, G, B = map(int, input().strip().split())

grid = [[' '] * M for _ in range(N)]

Il template originale restituisce output errato al posto di malformato, però non ne trovo comunque il senso, dal momento che nella mia implementazione ogni cella viene rimpiazzata sicuramente, rendendo quindi irrilevante la configurazione iniziale.

Qualche delucidazione?
Grazie :smiley:

2

Evidentemente la tua soluzione non sovrascrive effettivamente tutte le celle.
In ogni caso è molto difficile riuscire ad ottenere del valido aiuto senza inviare il codice per intero.

3

Pensavo fosse uno di quei problemi stupidi che si risolvono anche senza codice, tipo da int a long long.
Ti allego subito il codice allora:

#!/usr/bin/env python3
# NOTE: it is recommended to use this even if you don't understand the following code.

import sys
import math

# uncomment the two following lines if you want to read/write from files
# sys.stdin = open('input.txt')
# sys.stdout = open('output.txt', 'w')

N, M, R, G, B = map(int, input().strip().split())

grid = [[' '] * M for _ in range(N)]
possible = True


def va_bene(lettera, x, y):
    if x > 0:
        if grid[y][x - 1] == lettera:
            return False

    if y > 0:
        if grid[y - 1][x] == lettera:
            return False

    return True


massimo = math.ceil((N * M) / 2)
vals = [["R", R], ["G", G], ["B", B]]

if not (R > massimo or B > massimo or G > massimo):
    for y in range(N):
        for x in range(M):
            vals = sorted(vals, key=lambda v: v[1], reverse=True)

            for i in vals:
                if va_bene(i[0], x, y):
                    grid[y][x] = i[0]
                    i[1] -= 1
                    break

else:
    possible = False


if possible:
    print('YES')
    for i in range(N):
        print(''.join(grid[i]))
else:
    print('NO')

sys.stdout.close()

Grazie :)

4

Ciao, prova con quest’input:
2 5 3 4 3

5

Posso aggiungere che utilizzando il tuo algoritmo in c++ la risposta, all’esempio di @Doxeno , viene corretta.

6

Provando il testcase fornitomi, ho capito che il mio algoritmo non funziona in tutti i casi, lasciando infatti una cella vuota. Dovrei quindi provare a scriverne uno che utilizzi backtracking, come il comune algoritmo di risoluzione del sudoku.
Tuttavia, non mi è chiaro come la stessa implementazione in c++ possa risolvere correttamente.

7

Non avendo un ambiente di sviluppo python sul computer per testare il tuo codice, l’algoritmo in c++ dovrebbe essere :

    vector<pair<int,char>> vals = {{R, 'R'}, {G, 'G'}, {B, 'B'}};

    grid.resize(N, string(M, ' '));

    for(int i=0; i<N; i++)
        for(int j=0; j<M; j++) {
            sort(rbegin(vals), rend(vals));
            for(auto& [k,l] : vals)
                if(va_bene(l, i, j)) {
                    grid[i][j] = l;
                    k--;
                    break;
                }
        }

Con questo codice l’esempio di @doxeno viene corretto.

8

questo codice non fa esattamente la stessa cosa di quello in python, ma trovare perché é un esercizio lasciato al lettore.

9

Conoscendo pochissimo il python, che non sia la stessa cosa lo si evidenzia perché in c++ viene un risultato, comunque, corretto per l’input proposto mentre in python no.

Questo per considerare:

    vals = [["R", R], ["G", G], ["B", B]]

pensando di essere nel giusto, come un array di tuple in c++ invece di un array di struct com’è corretto in python.
E quindi il risultato del sort() che ne deriva è diverso tra un linguaggio e l’altro.

10

A parte il disguido tra python e c++ un hint per la risoluzione del task è quello di scorrere la matrice non RxC ma x diagonale.