trang chủ / đề bài / icpc25_mn_a

Hai mảng

Đề bài

Mô tả

Cho hai mảng số nguyên a và b, mỗi mảng gồm n phần tử: a1,a2,…,an và b1,b2,…,bn.

Bạn được thực hiện thao tác sau với số lần tùy ý:

  • Chọn một chỉ số i (1≤i≤n) và tăng cả ai lẫn bi thêm một đơn vị.

Cho hai số nguyên C và D, hãy xác định số thao tác ít nhất cần thực hiện để hai mảng thỏa mãn:

max(a)−min(a)≤Cvàmax(b)−min(b)≤D.

Trong đó max(a) và min(a) lần lượt là phần tử lớn nhất và nhỏ nhất của mảng a; tương tự với max(b) và min(b).

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 ba số nguyên n, C, D (1≤n≤105, 0<C,D≤109).
  • Dòng thứ hai chứa n số nguyên a1,a2,…,an (−109≤ai≤109).
  • Dòng thứ ba chứa n số nguyên b1,b2,…,bn (−109≤bi≤109).

Tổng n qua tất cả các bộ dữ liệu không vượt quá 105.

Dữ liệu ra

Với mỗi bộ dữ liệu, in ra trên một dòng một số nguyên: số thao tác ít nhất cần thực hiện để cả hai mảng thỏa mãn điều kiện. Nếu không có cách nào thỏa mãn điều kiện, in ra −1.

Ràng buộc

  • 1≤n≤105, tổng n qua tất cả các bộ dữ liệu không vượt quá 105.
  • 0<C,D≤109.
  • −109≤ai,bi≤109.

Ví dụ

Input Output Giải thích
2
4 2 3
-1 -2 -3 -4
-1 -2 -3 -4
5 2 1
-1 0 1 2 3
2 2 2 2 2
1
-1
Bộ thứ nhất: tăng a4 và b4 một lần, được a=b=(−1,−2,−3,−3), độ chênh lệch của cả hai mảng là 2. Bộ thứ hai: hiệu bi−ai không đổi khi thực hiện thao tác, và các hiệu 3,2,1,0,−1 không thể cùng đạt khi C=2, D=1.
1
3 1 1
0 0 0
0 1 2
1 Ví dụ bổ sung (không có trong đề gốc). Tăng chỉ số 1 một lần: a=(1,0,0), b=(1,1,2).

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