Popcount

Το Miniature Algebraic Natural Relay (ονομάζεται επίσης MALNAR) είναι η πιο πρόσφατη τεχνολογική πρόοδος στην ακμάζουσα σφαίρα των μικρών προγραμματιζόμενων συσκευών. Μπορείτε να γράψετε τα δικά σας προγράμματα για αυτήν τη συσκευή χρησιμοποιώντας τη MalnarScript, μια εσωτερική γλώσσα προγραμματισμού με τα ακόλουθα χαρακτηριστικά:

• Η είσοδος στο πρόγραμμα είναι ένας μεμονωμένος μη αρνητικός ακέραιος αυστηρά μικρότερος από ~2^N~.
• Η έξοδος του προγράμματος είναι ένας ενιαίος μη αρνητικός ακέραιος αυστηρά μικρότερος από ~2^N~.
• Κατά τον προγραμματισμό σε MalnarScript, μπορείτε να χρησιμοποιήσετε μόνο μία ακέραια μεταβλητή ~A~ των ~N~-bit χωρίς υπογραφή.
• Ο πηγαίος κώδικας του MalnarScript πρέπει να αποτελείται το πολύ από ~K~ εντολές της μορφής ~A=<expr>~ οι οποίες εκτελούνται με τη σειρά και καθεμία από αυτές πρέπει να αποτελείται από το πολύ χίλιους χαρακτήρες. Το σύμβολο ~<expr>~ ορίζεται αναδρομικά ως εξής:

~<expr> = A | <num> | (<expr><operator><expr>)~

Με άλλα λόγια, το σύμβολο ~<expr>~ μπορεί είτε να είναι μια μεταβλητή ~A~, είτε να συμμορφώνεται με τον ορισμό του συμβόλου ~<num>~ ή μπορεί (μέσα σε παρένθεση) να αντιπροσωπεύει μια διμελή έκφραση μέσα στην οποία κάθε τελεστής συμμορφώνεται με το ίδιο ~<expr>~ ορισμό.

Το σύμβολο ~<num>~ στον παραπάνω ορισμό αντιπροσωπεύει έναν μη αρνητικό δεκαδικό ακέραιο αυστηρά μικρότερο από ~2^N~, ενώ το σύμβολο ~<operator>~ μπορεί να είναι είτε ~+,\;-,\;|,\;\&,\;<<~ ή ~>>~ που αντιπροσωπεύουν (κατά σειρά) τις πράξεις πρόσθεσης, αφαίρεσης, bitwise or, bitwise and, αριστερή μετατόπιση και δεξιά μετατόπιση.

Επίσης ο χαρακτήρας ~A~ μπορεί να εμφανιστεί το πολύ 5 φορές στο σύμβολο ~<expr>~.

Στην περίπτωση υπερχείλισης ή υπορροής κατά την εκτέλεση των πράξεων πρόσθεσης και αφαίρεσης, το MalnarScript θα εκτελέσει αυτές τις λειτουργίες ως το υπόλοιπο ακέραίας διαίρεσης με το ~2^N~ (modulo ~2^N~) . Για παράδειγμα, όταν ~N = 3~ η παράσταση ~(7 + 3)~ θα αξιολογηθεί σε 2 και η παράσταση ~(2 - 5)~ θα εκτιμηθεί σε 5 στο MalnarScript.

Η δεξιά πλευρά της εξίσωσης σε κάθε εντολή αξιολογείται σε έναν μόνο αριθμό ο οποίος στη συνέχεια θα αποθηκευτεί στο ~A~. Για να αξιολογηθεί η έκφραση της δεξιάς πλευράς, το MalnarScript αντικαθιστά πρώτα κάθε εμφάνιση του ~A~ με την τρέχουσα τιμή του. Στη συνέχεια, ο υπολογισμός της έκφρασης προχωρά όπως θα συνέβαινε σε οποιαδήποτε μαθηματική έκφραση, δηλ. οι παρενθέσεις έχουν προτεραιότητα. Σημειώστε ότι οι προτεραιότητες των τελεστών (όσον αφορά τη σειρά λειτουργίας) είναι άσχετες γιατί το τελικό αποτέλεσμα ορίζεται πλήρως με την τοποθέτηση παρενθέσεων.

Ο στόχος σας είναι να γράψετε ένα πρόγραμμα που βγάζει ένα πρόγραμμα στο MalnarScript το οποίο υπολογίζει τον αριθμό των σε μια δυαδική αναπαράσταση της τιμής εισόδου.

Είσοδος

Η πρώτη γραμμή περιέχει τους δύο ακέραιους ~N~ και ~K~.

Έξοδος

Στην πρώτη γραμμή θα πρέπει να εξάγετε τον αριθμό των εντολών του παραγόμενου προγράμματος MalnarScript.

Στις υπόλοιπες γραμμές θα πρέπει να εξάγετε τις εντολές του προγράμματος που αναζητάτε. Κάθε εντολή πρέπει να εκτυπωθεί σε ξεχωριστή γραμμή και πρέπει να ικανοποιεί τη σύνταξη του MalnarScript όπως περιγράφεται στην περιγραφή της εργασίας.

Είναι σημαντικό να μην υπάρχουν περιττές κενές γραμμές ή επιπλέον χαρακτήρες κενού διαστήματος στην έξοδο. Κάθε γραμμή (συμπεριλαμβανομένης της τελευταίας) πρέπει να τερματίζεται με τον χαρακτήρα τέλους γραμμής ('\n').

Βαθμολογία

Υποπρόβλημα	Βαθμοί	Περιορισμοί
1	15	~2 \le N \le 100,\;K = N - 1~
2	15	~N = 500,\;K = 128~
3	35	~1 \le N \le 40,\;K = 7~
4	45	~100 \le N \le 500,\;K = 10~

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

input

2 2

output

1
A=(A-((A&2)>>1))

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

~input = 0\;\rightarrow\;output = (0 - ((0\&2) >> 1)) = (0 - (0 >> 1)) = (0 - 0) = 0~
~input = 1\;\rightarrow\;output = (1 - ((1\&2) >> 1)) = (1 - (0 >> 1)) = (1 - 0) = 1~
~input = 2\;\rightarrow\;output = (2 - ((2\&2) >> 1)) = (2 - (2 >> 1)) = (2 - 1) = 1~
~input = 3\;\rightarrow\;output = (3 - ((3\&2) >> 1)) = (3 - (2 >> 1)) = (3 - 1) = 2~

input

3 5

output

2
A=((A&4)|((A&3)-((A&2)>>1)))
A=((A&3)+((A&4)>>2))