trang chủ / đề bài / carousel

Vòng quay ngựa gỗ

Đề bài

Mô tả

Một vòng quay ngựa gỗ gồm n tượng thú xếp thành vòng tròn, đánh số từ 1 đến n theo chiều quay. Sau tượng thứ n là tượng thứ 1.

Mỗi tượng thuộc về một loài vật nào đó: tượng thứ i có loài ti.

Bạn muốn tô màu tất cả các tượng. Cách tô bị coi là nhàm chán nếu có hai tượng kề nhau trên vòng tròn khác loài nhưng lại được tô cùng màu. Hai tượng kề nhau cùng loài thì tô cùng màu hay khác màu đều được.

Hãy tô sao cho số màu khác nhau được dùng là nhỏ nhất có thể và cách tô không nhàm chán. Nếu dùng đúng k màu thì màu của các tượng phải được ghi bằng các số nguyên từ 1 đến k.

Dữ liệu vào

  • Dòng đầu chứa số nguyên q là số bộ dữ liệu.
  • Mỗi bộ dữ liệu gồm hai dòng:
    • Dòng thứ nhất chứa số nguyên n là số tượng trên vòng quay.
    • Dòng thứ hai chứa n số nguyên t1,t2,…,tn là loài của từng tượng.

Dữ liệu ra

Với mỗi bộ dữ liệu, in ra hai dòng:

  • Dòng thứ nhất chứa số nguyên k là số màu ít nhất cần dùng.
  • Dòng thứ hai chứa n số nguyên c1,c2,…,cn với 1≤ci≤k là màu của từng tượng.

Nếu có nhiều đáp án, in ra đáp án bất kỳ.

Ràng buộc

  • 1≤q≤104
  • 3≤n
  • Tổng n trên tất cả các bộ dữ liệu không vượt quá 2·105
  • 1≤ti≤2·105

Ví dụ

Input Output Giải thích
4
5
1 2 1 2 2
6
1 2 2 1 2 2
5
1 2 1 2 3
3
10 10 10		 2
2 1 2 1 1
2
1 2 1 2 1 2
3
1 2 1 2 3
1
1 1 1		 Bộ 1: n lẻ nhưng hai tượng 4,5 cùng loài 2, nên chúng được tô cùng màu 1 và 2 màu là đủ. Bộ 3: mọi cặp kề nhau đều khác loài và n=5 lẻ, không thể tô bằng 2 màu nên cần 3. Bộ 4: cả ba tượng cùng loài, một màu là đủ.
6
3
1 1 1
3
1 1 2
3
1 2 1
3
2 1 1
3
1 2 3
3
5 5 7		 1
1 1 1
2
1 1 2
2
1 2 1
2
2 1 1
3
1 2 3
2
1 1 2		 Với n=3 lẻ, chỉ cần tồn tại một cặp kề nhau cùng loài là hai màu đã đủ, kể cả khi cặp đó vắt qua chỗ nối (bộ 3: tượng 3 và tượng 1 cùng loài 1). Chỉ khi cả ba tượng đôi một khác loài mới phải dùng 3 màu.

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