26ος ΠΔΠ Καμπ (seniors)
Παιχνίδι μη αρνητικών (nonneg)
Έστω ένας τετραγωνικός πίνακας \(A\) μεγέθους \(N \times N\). Τα στοιχεία του πίνακα είναι είτε ακέραιοι αριθμοί (θετικοί ή αρνητικοί) είτε η ειδική τιμή \(\infty\) (άπειρο). Γνωρίζουμε ότι σε κάθε γραμμή του πίνακα, υπάρχουν το πολύ \(13\) στοιχεία που περιέχουν αριθμούς — για συντομία θα τα ονομάζουμε «αριθμητικά στοιχεία».
Παίζουμε το εξής παιχνίδι: Σε κάθε κίνηση επιλέγουμε πρώτα έναν αριθμό \(K\) (όπου \(1 \leq K \leq N\)) και έναν ακέραιο αριθμό \(X\) και στη συνέχεια: − προσθέτουμε το \(X\) σε όλα τα αριθμητικά στοιχεία της \(K\)-οστής γραμμής του \(A\), και − αφαιρούμε το \(X\) από όλα τα αριθμητικά στοιχεία της \(K\)-οστής στήλης του \(A\).
Κερδίζουμε το παιχνίδι αν βρούμε μία ακολουθία κινήσεων που, αφού εκτελεστούν με τη σειρά, όλα τα αριθμητικά στοιχεία του πίνακα θα περιέχουν μη αρνητικές τιμές.
Αρχεία Εισόδου (nonneg.in):
Η πρώτη γραμμή της εισόδου θα περιέχει δύο φυσικούς αριθμούς \(T\) και \(N\), χωρισμένους με ένα κενό διάστημα. Ο πρώτος θα δηλώνει το πλήθος των πινάκων που θα ακολουθήσουν και ο δεύτερος τη διάσταση των πινάκων. Στις επόμενες \(T \times N\) γραμμές της εισόδου θα δίνονται διαδοχικά τα στοιχεία \(T\) πινάκων \(A_1, A_2,\ldots A_T\) ως εξής: οι γραμμές από \(2\) έως και \(N+1\) θα αντιστοιχούν στον πίνακα \(A_1\), οι γραμμές από \(N+2\) έως και \(2 \times N + 1\) θα αντιστοιχούν στον πίνακα \(A_2\), κ.ο.κ. Η γραμμή εισόδου που αντιστοιχεί στην \(i\)-οστή γραμμή του πίνακα \(A_k\) θα περιέχει πρώτα έναν αριθμό \(M_i\), που θα παριστάνει το πλήθος των αριθμητικών στοιχείων της γραμμής (\(0 \leq M_i \leq 13\)). Στη συνέχεια, θα περιέχει \(M_i\) ζεύγη αριθμών \(j\), \(v\), κάθε ένα από τα οποία σημαίνει ότι το στοιχείο \(Α_k[i, j]\) του πίνακα περιέχει την τιμή \(v\). Θα είναι \(1 \leq j \leq N\) και \(\lvert v \rvert \leq 10^6\). Οι αριθμοί κάθε γραμμής θα χωρίζονται ανά δύο με ένα κενό διάστημα.
Αρχεία Εξόδου (nonneg.out):
Η έξοδος πρέπει να αποτελείται από \(T\) γραμμές, κάθε μία από τις οποίες θα περιέχει μία από τις λέξεις «true» ή «false». Η \(k\)-οστή γραμμή της εξόδου θα περιέχει «true» αν και μόνο αν υπάρχει ακολουθία κινήσεων που κερδίζει το παιχνίδι για τον πίνακα \(A_k\).
Παράδειγμα Αρχείου Εισόδου - Εξόδου:
| nonneg.in | nonneg.out |
|---|---|
| 2 4 2 1 8 3 -2 2 2 2 3 5 2 2 0 4 4 2 1 -1 3 7 2 2 -1 4 -1 0 2 2 9 4 -2 1 1 0 |
true false |
Εξήγηση παραδείγματος: Το παράδειγμα περιέχει τους δύο πίνακες, \(A_1\) και \(A_2\) που δίνονται παραπάνω. Για τον \(A_1\) μπορούμε να κερδίσουμε το παιχνίδι, π.χ. με την ακολουθία κινήσεων \([(1, 2), (4, 3)]\). Αντίθετα, για τον \(A_2\) δεν είναι δυνατό να κερδίσουμε το παιχνίδι με οποιαδήποτε ακολουθία κινήσεων. (Δοκιμάστε!)
\[A_1 = \begin{bmatrix} 8 & \infty & -2 & \infty \\ \infty & 2 & 5 & \infty \\ \infty & 0 & \infty & 4 \\ -1 & \infty & 7 & \infty \end{bmatrix} \qquad A_2 = \begin{bmatrix} \infty & -1 & \infty & -1 \\ \infty & \infty & \infty & \infty \\ \infty & 9 & \infty & -2 \\ 0 & \infty & \infty & \infty \end{bmatrix}\]Περιορισμοί
- \(1 \leq T \leq 10\).
- \(2 \leq N \leq 1.000\).
- Όριο χρόνου εκτέλεσης: \(1\) sec.
- Όριο μνήμης: \(64\) MB.