trang chủ / đề bài / icpc25_mn_e

Xóa dãy số

Đề bài

Mô tả

Cho một dãy gồm n số nguyên dương a1,a2,…,an xếp từ trái sang phải. Bạn được thực hiện các thao tác sau:

  • Thao tác 1: Nếu hai số đầu tiên của dãy hiện tại nguyên tố cùng nhau, hoặc một trong hai số là bội của số còn lại, xóa cả hai số đó.
  • Thao tác 2: Nếu không thể áp dụng Thao tác 1 cho hai số đầu tiên, chọn một số nguyên x>1, tăng số đầu tiên thêm x (tức là a1←a1+x) và thêm x vào cuối dãy.

Mục tiêu của bạn là làm cho dãy trở thành rỗng (xóa cả các số ban đầu lẫn mọi số được thêm vào) với số thao tác ít nhất.

Dữ liệu vào

Dòng đầu tiên chứa số nguyên t: số bộ dữ liệu. Mỗi bộ dữ liệu gồm:

  • Dòng đầu tiên chứa số nguyên n (1≤n).
  • Dòng thứ hai chứa n số nguyên a1,a2,…,an (2≤ai≤106).

Dữ liệu ra

Với mỗi bộ dữ liệu, in ra một số nguyên: số thao tác ít nhất cần để xóa toàn bộ dãy.

Ràng buộc

  • 1≤t≤106
  • Tổng n qua tất cả các bộ dữ liệu không vượt quá 106.
  • 2≤ai≤106

Ví dụ

Input Output Giải thích
2
2
28 30
1
30
4
2
Bộ thứ nhất: một cách tối ưu là (28,30)→(31,30,3)→(3)→(5,2)→(), dùng 4 thao tác. Bộ thứ hai: (30)→(37,7)→().
3
3
6 3 10
4
4 6 9 15
5
2 4 6 9 7
3
5
4
Ví dụ bổ sung (không có trong đề gốc). Bộ thứ nhất: xóa (6,3) vì 6 là bội của 3, còn lại (10) cần 2 thao tác.

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