Quantum Operations

Ο κβαντικός υπολογισμός είναι επί του παρόντος ένα καυτό θέμα στην έρευνα. Εάν μπορούν να κατασκευαστούν, οι κβαντικοί υπολογιστές θα έχουν τη δυνατότητα να εκτελούν ορισμένες υπολογιστικές εργασίες πολύ πιο γρήγορα από οποιονδήποτε υπολογιστή που υπάρχει σήμερα. Ευτυχώς, δεν θα χρειαστείτε έναν κβαντικό υπολογιστή για να λύσετε αυτό το ερώτημα.

Μια θεμελιώδης έννοια στον κβαντικό υπολογισμό είναι η ιδέα της κβαντικής λειτουργίας. Μια κβαντική πράξη μπορεί ουσιαστικά να θεωρηθεί ως μήτρα. Επίσης, εάν εκτελείτε δύο κβαντικές πράξεις παράλληλα σε ξεχωριστά κβαντικά δεδομένα, αυτό μπορεί να θεωρηθεί ως μια μεγαλύτερη κβαντική πράξη. Αν σκεφτούμε ξανά αυτές τις πράξεις ως προς τους πίνακες, ο προκύπτων πίνακας από την εκτέλεση δύο πινάκων παράλληλα ονομάζεται "tensor product" των δύο πινάκων (χρησιμοποιώντας το σύμβολο ~\otimes~). Αυτό είναι διαφορετικό από το κανονικό γινόμενο των πινάκων που μπορεί να έχετε μάθει.

Σε ένα tensor product, σας δίνονται δύο πίνακες (οι οποίοι είναι ουσιαστικά δισδιάστατοι πίνακες). Θα τους ονομάσουμε ~A~ και ~B~ και θα αναπαραστήσουμε τα επιμέρους στοιχεία αυτών των δύο πινάκων ως εξής:

~A = \begin{bmatrix} a_{11} & a_{12} & \cdots & a_{1n}\\ a_{21} & a_{22} & \cdots & a_{2n}\\ \cdots & \cdots & \ddots & \cdots\\ a_{m1} & a_{m2} & \cdots & a_{mn}\\ \end{bmatrix}~, ~B = \begin{bmatrix} a_{11} & a_{12} & \cdots & a_{1q}\\ a_{21} & a_{22} & \cdots & a_{2q}\\ \cdots & \cdots & \ddots & \cdots\\ a_{p1} & a_{p2} & \cdots & a_{pq}\\ \end{bmatrix}~

Παρατηρήστε ότι το μέγεθος του πίνακα ~A~ είναι ~m \times n~ (~m~ σειρές και ~n~ στήλες) και το μέγεθος του ~B~ είναι ~p \times q~. Το tensor product αυτών των δύο πινάκων θα είναι ένας πίνακας ~mp \times nq~ (με ~mp~ γραμμές και ~nq~ στήλες) που μοιάζει με:

~A \otimes B = \begin{bmatrix} a_{11}[B] & a_{12}[B] & \cdots & a_{1n}[B]\\ a_{21}[B] & a_{22}[B] & \cdots & a_{2n}[B]\\ \cdots & \cdots & \ddots & \cdots\\ a_{m1}[B] & a_{m2}[B] & \cdots & a_{mn}[B]\\ \end{bmatrix}~

όπου το ~[B]a_{ij}~ απλώς υποδεικνύει ότι κάθε στοιχείο του ~B~ πολλαπλασιάζεται με το ~a_{ij}~.
Τέλος, παρατηρήστε ότι το tensor product δεν είναι αντιμεταθετικό, πράγμα που σημαίνει ότι η αλλαγή της σειράς των πινάκων μπορεί να αλλάξει την απάντηση (~A \otimes B \ne B \otimes A~).

Για περισσότερους από δύο πίνακες, θα ορίσουμε ότι ~A \otimes B \otimes C = (A \otimes B) \otimes C~ αν και δεν το κάνει τεχνικά σημαντικό, καθώς το tensor product είναι προσεταιριστικό.

Το καθήκον σας είναι να υπολογίσετε και να τυπώσετε το tensor product δύο ή περισσότερων δεδομένων πινάκων.

Είσοδος

Η πρώτη γραμμή εισόδου περιέχει τον αριθμό των πινάκων, ~N~, έναν θετικό ακέραιο. Στη συνέχεια, υπάρχουν ~N~ μπλοκ γραμμών που περιγράφουν τους πίνακες με τη σειρά.

Σε κάθε μπλοκ, η πρώτη γραμμή θα περιέχει δύο θετικούς ακέραιους αριθμούς, τον ~r~ και τον ~c~, χωρισμένους με ένα κενό, υποδεικνύοντας τον αριθμό των γραμμών και των στηλών, αντίστοιχα. Στη συνέχεια, οι επόμενες γραμμές ~r~ θα υποδηλώνουν τις σειρές, με τη σειρά. Κάθε γραμμή θα περιέχει ~c~ ακέραιους, χωρισμένους με κενά.

Έξοδος

Η έξοδος (στην οθόνη) θα είναι ~6~ ακέραιοι με την ακόλουθη σειρά:

• το μεγαλύτερο στοιχείο του tensor product
• το ελάχιστο στοιχείο του tensor product
• το μέγιστο άθροισμα σειρών (δηλαδή, άθροισμα εγγραφών σε κάθε σειρά)
• το ελάχιστο άθροισμα σειρών
• το μέγιστο άθροισμα στηλών
• το ελάχιστο άθροισμα στηλών

Μπορείτε να υποθέσετε ότι ο πίνακας tensor product δεν θα έχει περισσότερες από ~1024~ σειρές και περισσότερες από ~1024~ στήλες.

Παραδείγματα

input

2
2 2
1 1
1 -1
2 2
1 0
0 1

output

1
-1
2
0
2
0

Επεξήγηση του 1ου παραδείγματος:

Πίνακας tensor product:

1 0 1 0
0 1 0 1
1 0 -1 0
0 1 0 -1

input

3
2 2
1 0
0 3
2 2
1 1
1 -1
2 2
1 0
0 1

output

3
-3
6
0
6
0

Επεξήγηση του 2ου παραδείγματος:

Πίνακας tensor product:

1 0 1 0 0 0 0 0
0 1 0 1 0 0 0 0
1 0 -1 0 0 0 0 0
0 1 0 -1 0 0 0 0
0 0 0 0 3 0 3 0
0 0 0 0 0 3 0 3
0 0 0 0 3 0 -3 0
0 0 0 0 0 3 0 -3