CCC-08 (2008) - J5S5 (Nukit)

View as PDF

Submit solution

Points: 50 (partial)
Time limit: 1.0s
Memory limit: 256M

Author:
Problem type
Allowed languages
C, C++, Java, Pascal, Python
Nukit

Οι δύο κορυφαίοι πυρηνικοί επιστήμονες του Καναδά, ο Patrick και ο Roland, μόλις ολοκλήρωσαν την κατασκευή του πρώτου αντιδραστήρα πυρηνικής σχάσης στον κόσμο. Τώρα η δουλειά τους είναι να κάθονται και να λειτουργούν τον αντιδραστήρα όλη μέρα, κάθε μέρα. Όπως είναι φυσικό αφότου το έκαναν αυτό για κάποιο διάστημα, βαρέθηκαν και ως αποτέλεσμα έχουν συμβεί τα εξής δύο πράγματα. Πρώτον, μπορούν πλέον να ελέγξουν τις μεμονωμένες αντιδράσεις που συμβαίνουν μέσα στον αντιδραστήρα. Δεύτερον, για να περάσει η ώρα,εφηύραν ένα νέο παιχνίδι που ονομάζεται Nukit.

Στην αρχή του παιχνιδιού, ένας αριθμός σωματιδίων τοποθετείται στον αντιδραστήρα. Οι παίκτες εναλλάσσουν σειρά, με τον Patrick να ξεκινάει πάντα πρώτος. Στη σειρά του κάθε παίκτης, πρέπει να επιλέξει μερικά από τα εναπομείναντα σωματίδια για να σχηματίσει μία από τις δυνατές αντιδράσεις. Μετά, τα σωματίδια αυτά καταστρέφονται. Κάποια στιγμή θα υπάρχουν τόσο λίγα σωματίδια που καμία αντίδραση δεν θα μπορεί να σχηματιστεί. Σε αυτό το σημείο, το πρώτο άτομο που δεν θα είναι σε θέση να σχηματίσει μια αντίδραση στη σειρά του, θα χάνει.

Στο σύμπαν μας μπορείτε να υποθέσετε ότι υπάρχουν μόνο 4 τύποι σωματιδίων: A, B, C, D. Κάθε αντίδραση είναι μια λίστα σωματιδίων που μπορούν να καταστραφούν στη σειρά ενός παίκτη. Οι πέντε αντιδράσεις είναι:

  1. AABDD
  2. ABCD
  3. CCD
  4. BBB
  5. AD

Για παράδειγμα, η πρώτη αντίδραση "AABDD" σημαίνει ότι επιτρέπεται η καταστροφή δύο σωματιδίων Α, ενός Β και δύο D ταυτόχρονα στη σειρά ενός παίκτη.

Αποδεικνύεται ότι, ανεξάρτητα από το πόσα σωματίδια υπάρχουν στον αντιδραστήρα στο ξεκίνημα, ακριβώς ένας, ο Patrick ή ο Roland, μπορεί να έχει μια τέλεια στρατηγική νίκης. Όταν λέμε πως ο παίκτης X έχει μια τέλεια στρατηγική νίκης, εννοούμε ότι ανεξάρτητα από το τι κάνει ο άλλος παίκτης, ο παίκτης X μπορεί πάντα να κερδίζει επιλέγοντας προσεκτικά τις αντιδράσεις. Για παράδειγμα, εάν ο αντιδραστήρας ξεκινά με ένα σωματίδιο A, πέντε B και τρία D, τότε ο Roland έχει την ακόλουθη τέλεια στρατηγική νίκης: «εάν ο Patrick σχηματίσει ως πρώτη την αντίδραση BBB, τότε πρέπει να σχηματίσεις την αντίδραση AD μετά από εκείνον. Εάν ο Πάτρικ σχηματίσει ως πρώτη την αντίδραση AD, τότε πρέπει να σχηματίσεις μετά από εκείνον την αντίδραση BBB». (Η στρατηγική λειτουργεί γιατί σε κάθε περίπτωση, στη δεύτερη σειρά του Patrick, δεν απομένουν αρκετά σωματίδια για να σχηματιστούν αντιδράσεις.)

Μπορείτε να βρείτε ποιος έχει μια τέλεια στρατηγική νίκης, δεδομένου του αριθμού κάθε τύπου σωματιδίου που βρίσκεται αρχικά στον αντιδραστήρα;

Είσοδος

Η πρώτη γραμμή θα εισόδου περιέχει τον αριθμό, n\;(1 \le n < 100), των αρχείων ελέγχου. Κάθε αρχείο ελέγχου αποτελείται από 4 ακέραιους αριθμούς χωρισμένους με κενά διαστήματα, σε μια γραμμή, που αντιπροσωπεύουν τον αρχικό αριθμό σωματιδίων A, B, Cκαι D. Μπορείτε να υποθέσετε ότι αρχικά υπάρχουν μεταξύ 0 και 30 (συμπεριλαμβανομένων) από κάθε τύπο σωματιδίου.

Έξοδος

Για κάθε αρχείο ελέγχου, εξάγετε "Roland" ή "Patrick"- τον παίκτη που έχει μια τέλεια στρατηγική νίκης.

Παράδειγμα

input

6
0 2 0 2
1 3 1 3
1 5 0 3
3 3 3 3
8 8 6 7
8 8 8 8

output

Roland
Patrick
Roland
Roland
Roland
Patrick
Μερική επεξήγηση του παραδείγματος:

Η πρώτη έξοδος προκύπτει επειδή ο Patrick χάνει αμέσως, αφού δεν μπορεί να σχηματίσει καμία αντίδραση. (Η τέλεια στρατηγική νίκης του Roland είναι «να μην κάνεις τίποτα».) Η δεύτερη έξοδος προκύπτει επειδή ο Patrick έχει την τέλεια στρατηγική νίκης "σχημάτισε την αντίδραση ABCD", που κάνει τον Roland να χάσει από την πρώτη του σειρά στο παιχνίδι. Η τρίτη έξοδος εξηγείται στην περιγραφή του προβλήματος.


Comments

There are no comments at the moment.