CCC-22 (2022) - S3 (Good Samples) - DMOJ: Modern Online Judge

CCC-22 (2022) - S3 (Good Samples)

View as PDF

Submit solution

All submissions

Best submissions

Points: 20 (partial)

Time limit: 1.0s

Memory limit: 256M

Author:

CEMC

Problem type

Allowed languages

C, ~~C++~~, ~~Java~~, ~~Pascal~~, ~~Python~~

Good Samples

Συνθέτετε μουσική για τον διαγωνισμό Cool Clarinet Competition (CCC). Σας έχει δοθεί η οδηγία να συνθέσετε ένα μουσικό κομμάτι με ακριβώς $N$ ~N~ νότες. Μια νότα αναπαρίσταται ως ένας θετικός ακέραιος αριθμός, ο οποίος υποδηλώνει τον τόνο της νότας.

Θα ονομάζουμε μια μη κενή ακολουθία από διαδοχικές νότες στο κομμάτι, δείγμα. Για παράδειγμα, $(3,\;4,\;2)$ ~(3,\;4,\;2)~, $(1,\;2,\;3,\;4,\;2)$ ~(1,\;2,\;3,\;4,\;2)~ και $(4)$ ~(4)~ είναι δείγματα της $1$ ~1~, $2$ ~2~, $3$ ~3~, $4$ ~4~, $2$ ~2~. Σημειώστε ότι το $(1,\;3)$ ~(1,\;3)~ δεν είναι δείγμα της $1$ ~1~, $2$ ~2~, $3$ ~3~, $4$ ~4~, $2$ ~2~. Ονομάζουμε δύο δείγματα διαφορετικά αν αρχίζουν ή τελειώνουν σε διαφορετική θέση στο κομμάτι.

Ονομάζουμε ένα δείγμα καλό, όταν δεν υπάρχουν δύο νότες στο δείγμα με τον ίδιο τόνο.

Οι παίκτες του κλαρινέτου είναι επιλεκτικοί με δύο τρόπους. Πρώτον, δεν θα παίξουν καμία νότα σε τόνο μεγαλύτερο από $M$ ~M~. Δεύτερον, θέλουν ένα κομμάτι με ακριβώς $K$ ~K~ καλά δείγματα.

Μπορείτε να συνθέσετε ένα κομμάτι που να ικανοποιεί τους παίκτες του κλαρίνου;

Είσοδος

Η πρώτη και μοναδική γραμμή εισόδου θα περιέχει $3$ ~3~ ακέραιους αριθμούς, $N$ ~N~, $M$ ~M~ και $K$ ~K~.

Για $3$ ~3~ από τους $15$ ~15~ διαθέσιμους βαθμούς, $1 \le N \le 16$ ~1 \le N \le 16~, $M = 2$ ~M = 2~ και $1 \le K \le 1000$ ~1 \le K \le 1000~.

Για επιπλέον $3$ ~3~ από τους $15$ ~15~ διαθέσιμους βαθμούς, $1 \le N \le 10^{6}$ ~1 \le N \le 10^{6}~, $M = 2$ ~M = 2~ και $1 \le K \le 10^{18}$ ~1 \le K \le 10^{18}~.

Για επιπλέον $4$ ~4~ από τους $15$ ~15~ διαθέσιμους βαθμούς, $1 \le N \le 10^{6}$ ~1 \le N \le 10^{6}~, $M = N$ ~M = N~ και $1 \le K \le 10^{18}$ ~1 \le K \le 10^{18}~.

Για επιπλέον $5$ ~5~ από τους $15$ ~15~ διαθέσιμους βαθμούς, $1 \le N \le 10^{6}$ ~1 \le N \le 10^{6}~, $1 \le M \le N$ ~1 \le M \le N~ και $1 \le K \le 10^{18}$ ~1 \le K \le 10^{18}~.

Έξοδος

Αν υπάρχει ένα μουσικό κομμάτι που να ικανοποιεί τους δεδομένους περιορισμούς, εξάγετε $N$ ~N~ ακέραιους αριθμούς μεταξύ $1$ ~1~ και $M$ ~M~, που να αντιπροσωπεύουν τους τόνους από τις νότες του μουσικού κομματιού. Εάν υπάρχουν περισσότερα από ένα τέτοια μουσικά κομμάτια, μπορείτε να εξάγετε οποιοδήποτε από αυτά.

Διαφορετικά, εξάγετε $-1$ ~-1~.

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

input

3 2 5

output

1 2 1

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

Παρατηρήστε ότι το κομμάτι αποτελείται από $N = 3$ ~N = 3~ νότες, καθεμία από τις οποίες είναι σε έναν από τους $M = 2$ ~M = 2~ πιθανούς τόνους, $1$ ~1~ και $2$ ~2~. Αυτό το μουσικό κομμάτι έχει συνολικά $6$ ~6~ δείγματα, αλλά μόνο $K = 5$ ~K = 5~ καλά δείγματα: $(1)$ ~(1)~, $(1,\;2)$ ~(1,\;2)~, $(2)$ ~(2)~, $(2,\;1)$ ~(2,\;1)~, $(1)$ ~(1)~. Παρατηρήστε ότι τα δύο καλά δείγματα $(1)$ ~(1)~ είναι διαφορετικά, αφού ξεκινούν από δύο διαφορετικές θέσεις.

Σημειώστε ότι το κομμάτι $2$ ~2~ $1$ ~1~ $2$ ~2~ είναι η μόνη εναλλακτική έγκυρη έξοδος για αυτή την είσοδο.

Ένα παράδειγμα εξόδου που θα ήταν λανθασμένο είναι το $3$ ~3~ $2$ ~2~ $3$ ~3~, αφού έχει νότες σε τόνους μεγαλύτερους από $2$ ~2~. Μια άλλη λανθασμένη έξοδος θα ήταν η $1$ ~1~ $1$ ~1~ $2$ ~2~, αφού έχει μόνο τέσσερα καλά δείγματα: $(1)$ ~(1)~, $(1)$ ~(1)~, $(2)$ ~(2)~ και $(1,\;2)$ ~(1,\;2)~.

input

5 5 14

output

1 5 3 2 1

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

Τα $14$ ~14~ καλά δείγματα είναι: $(1)$ ~(1)~, $(1,\;5)$ ~(1,\;5)~, $(1,\;5,\;3)$ ~(1,\;5,\;3)~, $(1,\;5,\;3,\;2)$ ~(1,\;5,\;3,\;2)~, $(5)$ ~(5)~, $(5,\;3)$ ~(5,\;3)~, $(5,\;3,\;2)$ ~(5,\;3,\;2)~, $(5,\;3,\;2,\;1)$ ~(5,\;3,\;2,\;1)~, $(3)$ ~(3)~, $(3,\;2)$ ~(3,\;2)~, $(3,\;2,\;1)$ ~(3,\;2,\;1)~, $(2)$ ~(2)~, $(2,\;1)$ ~(2,\;1)~, $(1)$ ~(1)~.