Διαχωρισμός Πινάκων
Εκφώνηση:
Ο Τηλέμαχος έχει πίνακα A, N ακεραίων. Ορίζουμε το min(l, r) ως το ελάχιστο των ακεραίων Al, Al+1, …, Ar και το min(l, r) ως το μέγιστο των ακεραίων Al, Al+1, …, Ar. Βοηθήστε τον Τηλέμαχο να βρει 3 θετικούς ακεραίους x, y, z τέτοιους ώστε: x + y + z = N και max(1, x) = min(x+1, x+y) = max(x+y+1, N)
Με άλλα λόγια, ο Τηλέμαχος πρέπει να χωρίσει τον πίνακα Α σε τρία διαδοχικά, μη κενά μέρη που αθροιστικά εκτείνονται σε όλο τον πίνακα Α, με το μέγιστο στο πρώτο μέρος να ισούται με το ελάχιστο στο δεύτερο μέρος και με το μέγιστο στο τρίτο μέρος (ή να διαπιστώσει πως αυτό δεν είναι εφικτό). Κάθε διαχωρισμός που ικανοποιεί την παραπάνω συνθήκη είναι αποδεκτός. Θα πρέπει να απαντήσετε για t ανεξάρτητους πίνακες.
Μορφή εισόδου:
Η πρώτη γραμμή της εισόδου περιέχει έναν ακέραιο Ν (3 ≤ N ≤ ) – το μήκος του πίνακα Α
Η δεύτερη γραμμή της εισόδου περιέχει Ν ακεραίους A1, A2, …, AN (
≤ Ai ≤
), όπου Αi το i-οστό στοιχείο του πίνακα Α.
Μορφή εξόδου:
Πρέπει να τυπώνεται η λέξη NO, αν δεν υπάρχει διαχωρισμός που να ικανοποιεί τη δοθείσα συνθήκη. Διαφορετικά, πρέπει να τυπώνεται η λέξη YES στην πρώτη γραμμή και οι τρεις ακέραιοι x, y, z στη δεύτερη γραμμή. Όλοι οι δυνατοί συνδυασμοί x, y, z είναι αποδεκτοί.
Παραδείγματα:
Είσοδος 1:
11
1 2 3 3 3 4 4 3 4 2 1
Έξοδος 1:
YES
6 1 4
Είσοδος 2
8
2 9 1 7 3 9 4 1
Έξοδος 2
NO
Comments