trang chủ / đề bài / icpc20_reg_d

Chia 2, nhân 2, nhân 3

Đề bài

Mô tả

Là học sinh năm thứ ba của Trường Phù thủy và Pháp sư Hogwarts, Harry phải học số học (trong thế giới phù thủy gọi là môn Số học huyền bí). Bài học hôm nay xoay quanh phép nhân và phép chia. Vì vậy, bài tập về nhà của Harry là viết ra n số nguyên a1,a2,…,an theo các quy tắc sau:

  • a1=1.
  • Nếu ai là số lẻ, Harry có hai lựa chọn: ai+1=2·ai hoặc ai+1=3·ai.
  • Nếu ai là số chẵn, Harry có ba lựa chọn: ai+1=2·ai, hoặc ai+1=3·ai, hoặc ai+1=ai/2.

Harry đã làm xong bài tập nhưng lại viết n số nguyên theo một thứ tự tùy ý. Là giáo viên của Harry, bạn muốn kiểm tra xem Harry có làm đúng bài tập không, tức là có thể sắp xếp lại n số nguyên này để chúng thỏa mãn các yêu cầu của bài tập hay không.

Dữ liệu vào

Dữ liệu vào gồm nhiều bộ dữ liệu, mỗi bộ có dạng:

  • Dòng đầu tiên chứa số nguyên n.
  • Dòng thứ hai chứa n số nguyên x1,x2,…,xn cách nhau bởi dấu cách.

Dữ liệu vào kết thúc bằng một dòng chứa duy nhất số 0, dòng này không phải là một bộ dữ liệu.

Dữ liệu ra

Với mỗi bộ dữ liệu, nếu không thể sắp xếp lại n số để thỏa mãn yêu cầu của bài tập, in ra NO trên một dòng. Ngược lại, in ra hai dòng:

  • Dòng thứ nhất chứa xâu YES.
  • Dòng thứ hai chứa n số nguyên a1,a2,…,an cách nhau bởi dấu cách, thỏa mãn yêu cầu của bài tập. Dãy a1,a2,…,an phải là một hoán vị của x1,x2,…,xn. Nếu có nhiều đáp án, in ra đáp án bất kỳ.

Ràng buộc

  • 1≤n≤105.
  • 1≤xi≤1018.
  • Tổng n của tất cả các bộ dữ liệu không vượt quá 106.

Ví dụ

Input Output Giải thích
5
1 2 4 4 8
5
1 2 4 8 8
0
YES
1 2 4 8 4
NO
Ở bộ thứ hai, sau khi viết số 8 lần đầu, số tiếp theo chỉ có thể là 16, 24 hoặc 4, và 4 đã được dùng; không có cách nào đặt cả hai số 8.
1
1
1
2
7
1 3 6 3 1 2 3
7
1 3 6 3 9 18 6
0
YES
1
NO
NO
YES
1 3 6 3 6 18 9
Bộ thứ hai không có số 1 để bắt đầu. Ở bộ thứ ba, các số không chia hết cho 3 là 1,1,2 phải đứng trước mọi bội của 3 (không có phép chia cho 3), nên dãy bắt đầu bằng 1 2 1 rồi sang 3; khi đó ba số 3 và số 6 không xếp được: hai số 3 liên tiếp trong dãy phải cách nhau bởi một số 6.

Bình luận

Không có bình luận tại thời điểm này.

gnatmake 12.2.0 a68g 3.1.2 nasm 2.16.1 as_x64 2.47 awk 1.3.4 gcc 16.2.0 dotnet 10.0.402 g++ 16.2.0 g++-themis 16.2.0 g++17 16.2.0 g++20 16.2.0 g++23 16.2.0 clang++ 22.1.8 dmd 2.113.0 dart 3.13.6 gforth 0.7.3 gfortran 15.3.0 go 1.27.3 groovyc 5.1.3 javac 26.0.2.1 node 26.12.1 julia 1.13.2 kotlinc 2.4.21 lean 4.35.0 sbcl 2.2.9 lua 5.5.1 nim 2.2.12 fpc 3.2.2 fpc-themis 3.2.2 perl 5.42.3 php 8.5.12 pike 8.0 swipl 9.0.4 pypy3 7.3.23 python3 3.15.1 racket 8.7 ruby 4.0.8 rustc 1.99.1 csc 5.3.0 ctoj-scratch 0.0.1 sed 4.9 swiftc 6.4.1 tclsh 8.6 bun 1.4.4 deno 2.9.8 v 0.5.2 zig 0.17.0