COCI 2019/2020 - Contest 2 - Popcount

View as PDF

Submit solution

Points: 1.50 (partial)
Time limit: 1.0s
Memory limit: 512M

Suggester:
Problem source:
COCI 2019/2020 - Contest 2
Problem type
Allowed languages
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

Miniature Algebraic Natural Relay (còn gọi là MALNAR) là tiến bộ công nghệ mới nhất trong lĩnh vực phát triển các thiết bị nhỏ có thể lập trình được. Bạn có thể viết các chương trình của riêng mình bằng cách sử dụng MalnarScript, một ngôn ngữ lập trình bao gồm các tính năng sau:

• Đầu vào chương trình là một số nguyên không âm nhỏ hơn ~2^{n}~.

• Đầu ra của chương trình là một số nguyên không âm nhỏ hơn ~2^{n}~.

• Khi lập trình trong MalnarScript, bạn chỉ có thể sử dụng một biến ~A~ duy nhất kiểu unsigned integer gồm ~N-bit~. Tại đầu chương trình, biến này chứa dữ liệu đầu vào và giá trị của nó ở cuối chương trình được coi là đầu ra của chương trình.

• Mã nguồn của MalnarScript có tối đa ~K~ lệnh có dạng ~A~ = <expr> được thực hiện theo thứ tự và mỗi lệnh chứa tối đa một nghìn ký tự. Các ký hiệu <expr> được định nghĩa một cách đệ quy như sau:

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

Nói cách khác, <expr> có thể là một biến ~A~ hoặc nó có thể tuân theo định nghĩa của <num>, hoặc nó có thể (bên trong dấu ngoặc đơn) đại diện cho một biểu thức có hai toán hạng trong đó mỗi toán hạng tuân theo định nghĩa <expr>.

<num> trong định nghĩa ở trên đại diện cho một số nguyên không âm nhỏ hơn ~2^{n}~, <operator> có thể là +, -, |, &, << hoặc >> lần lượt đại diện cho phép cộng, phép trừ, bitwise or, bitwise and, dịch trái và dịch phải.

Ngoài ra, ký tự ~A~ có thể xuất hiện nhiều nhất 5 lần trong <expr>.

Trong trường hợp tràn hoặc thiếu khi thực hiện các phép toán cộng và trừ, MalnarScript sẽ thực hiện mod ~2^{n}~. Ví dụ, khi ~N = 3~, biểu thức ~(7 + 3)~ sẽ được coi là ~2~ và biểu thức ~(2 - 5)~ sẽ được coi là ~5~ trong MalnarScript.

Vế phải của phương trình trong mỗi lệnh sau khi được thực hiện sẽ cho ra một số duy nhất và được lưu trữ trong ~A~. Để đánh giá biểu thức bên vế phải, MalnarScript trước tiên sẽ thay thế mỗi lần xuất hiện của ~A~ với giá trị hiện tại của nó. Việc tính toán biểu thức sau đó sẽ tiến hành như bất kỳ biết thức toán học nào, điều đó có nghĩa là các dấu ngoặc đơn được ưu tiên. Lưu ý rằng ưu tiên về toán tử (về thứ tự thực hiện) không liên quan vì kết quả cuối cùng được xác định hoàn toàn bằng cách đặt dấu ngoặc đơn.

Nhiệm vụ của bạn là lập trình sao cho output là công thức lập trình tính số lượng số 1 trong biểu diễn nhị phân của giá trị input bằng ngôn ngữ MalnarScript

Input

Dòng đầu chứa 2 số nguyên ~N~ và ~K~

Output

Dòng đầu tiên, xuất ra số lượng lệnh của chương trình MalnarScript được tạo ra.

Các dòng còn lại, xuất ra các lệnh của chương trình. Mỗi lệnh phải được in trên một dòng riêng biệt và phải đúng cú pháp của MalnarScript như được mô tả ở phía trên, không có dòng trống hoặc các khoảng trắng thừa. Mỗi dòng (bao gồm cả dòng cuối cùng) phải được kết thúc bằng (\n).

Đoạn mã in ra sẽ được chạy thử qua các bộ số đủ nhỏ, và một vài bộ số lớn. Kết quả được cho là đúng nếu đoạn mã cho đáp án đúng với các bộ số mà checker thử

Sample Input 1

2 2

Sample Output 1

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

Sample Input 2

3 5

Sample Output 2

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

Giải thích cho ví dụ đầu

input = 0 ⇒ output = (0 - ((0&2) >> 1)) = (0 - (0 >> 1)) = (0 - 0) = 0
input = 1 ⇒ output = (1 - ((1&2) >> 1)) = (1 - (0 >> 1)) = (1 - 0) = 1
input = 2 ⇒ output = (2 - ((2&2) >> 1)) = (2 - (2 >> 1)) = (2 - 1) = 1
input = 3 ⇒ output = (3 - ((3&2) >> 1)) = (3 - (2 >> 1)) = (3 - 1) = 2

Subtask

  • ~15\%~ số test có ~2\le N \le 100, K=N-1~
  • ~15\%~ số test tiếp theo có ~N=100, K=128~
  • ~35\%~ sô test tiếp theo có ~1 \le N \le 40, K=7~
  • ~40\%~ số test còn lại ~100\le N \le 500, K=10~

Comments

Please read the guidelines before commenting.


There are no comments at the moment.