Ngủ Trong Lớp (Khó)

Điểm: 1,00 (OI)

Giới hạn thời gian: 3.0s

Python 3 5.0s

Giới hạn bộ nhớ: 256M

Đầu vào: stdin

Đầu ra: stdout

Tác giả:

huunguyen

Dạng bài

Ngôn ngữ cho phép

C++, Go, Java, Kotlin, Pascal, Python, Scratch

Bessie hay ngủ gật trong lớp, và bạn thân Elsie đã ghi lại nhật ký theo dõi gồm $N$ tiết học, trong đó tiết thứ $i$ Bessie ngủ gật $a_{i}$ lần.

Elsie muốn chỉnh sửa nhật ký theo hai loại thao tác:

Gộp: Chọn hai tiết liền kề, gộp thành một tiết duy nhất có số lần ngủ gật bằng tổng hai tiết cũ (số tiết giảm đi 1).
Tách: Chọn một tiết có giá trị $v$ , tách thành hai tiết liền kề với giá trị lần lượt là $x$ và $v - x$ (với $1 \leq x \leq v - 1$ , số tiết tăng lên 1).

Cho $Q$ truy vấn. Với mỗi truy vấn có giá trị $d$ , hãy tìm số thao tác tối thiểu để làm cho tất cả các tiết học đều có số lần ngủ gật đúng bằng $d$ , hoặc in ra $- 1$ nếu không thể.

Dữ liệu vào

Dòng 1: Số nguyên $N$ ( $2 \leq N \leq 10^{5}$ )
Dòng 2: $N$ số nguyên $a_{1}, a_{2}, \dots, a_{N}$ ( $1 \leq a_{i} \leq 10^{18}$ , tổng $\sum a_{i} \leq 10^{18}$ )
Dòng 3: Số nguyên $Q$ ( $1 \leq Q \leq 10^{5}$ )
$Q$ dòng tiếp theo: Mỗi dòng chứa số nguyên $d_{i}$ ( $1 \leq d_{i} \leq 10^{18}$ )

Dữ liệu ra

Với mỗi truy vấn, in ra một số nguyên trên một dòng — số thao tác tối thiểu, hoặc $- 1$ nếu không thể.

Ràng buộc

$2 \leq N \leq 10^{5}$ , $1 \leq Q \leq 10^{5}$
$1 \leq a_{i} \leq 10^{18}$ , tổng $S = \sum_{i = 1}^{N} a_{i} \leq 10^{18}$
$1 \leq d_{i} \leq 10^{18}$
Test 2-4: $N, Q \leq 5000$
Test 5-7: tất cả $a_{i} \leq 10^{9}$
Test 8-26: không có ràng buộc thêm

Ví dụ

Input	Output	Giải thích
6 1 2 3 1 1 4 7 1 2 3 4 5 6 12	6 6 4 5 -1 4 5	Với $d = 3$ : gộp tiết 1,2 thành 3; gộp tiết 5,6 thành 5; gộp tiết 4,5 thành 6; tách tiết 6 thành 3,3. Tổng cộng 4 thao tác. Với $d = 5$ : tổng $S = 12$ không chia hết cho 5 nên trả về $- 1$ .
4 3 6 2 1 5 4 3 6 12 7	5 2 4 3 -1	Với $d = 3$ : tổng $S = 12$ , $k = 4$ . Tiền tố $[3, 9]$ chia hết cho 3 nên $x = 2$ , đáp án $= 4 + 4 - 2 - 4 = 2$ . Với $d = 7$ : 12 không chia hết cho 7 nên $- 1$ .

Ghi chú

Không thể đạt $d = 5$ trong ví dụ 1 vì tổng $S = 12$ không chia hết cho 5 — dù có bao nhiêu thao tác cũng không thể chia đều.

Một thao tác tách hoặc gộp đều được tính là 1 thao tác.

Bình luận

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