trang chủ / đề bài / icpc21_bt_f

Tiệm cắt tóc

Đề bài

Mô tả

Uiharu và Misaka cùng mở một tiệm cắt tóc. Mỗi ngày có N khách hàng. Mỗi người muốn một kiểu tóc khác nhau nên khối lượng công việc wi cũng khác nhau. Uiharu và Misaka có những kỹ năng riêng để tăng tốc công việc: Uiharu có thể lập trình cho tông đơ chạy nhanh hơn, cô làm được U đơn vị công việc mỗi giây; Misaka có thể điều khiển dòng điện để vận hành tông đơ mà không cần dùng tay, cô làm được M đơn vị công việc mỗi giây.

Mỗi khách hàng chỉ được phục vụ bởi một thợ cắt tóc. Uiharu và Misaka muốn tan làm cùng nhau: họ về nhà sau khi khách hàng cuối cùng rời đi. Vì vậy họ cần phân chia công việc thật đều. Hãy giúp họ tìm thời gian ít nhất để hoàn thành công việc trong ngày. Nếu khách hàng cuối cùng rời đi giữa một giây, ta coi công việc kết thúc vào cuối giây đó.

Dữ liệu vào

  • Dòng đầu tiên chứa số nguyên T là số bộ dữ liệu.
  • Mỗi bộ dữ liệu gồm hai dòng: dòng đầu chứa ba số N, U, M; dòng thứ hai chứa N số w1,w2,…,wN.

Dữ liệu ra

Với mỗi bộ dữ liệu, in ra một số là thời gian ít nhất (tính bằng giây) để hoàn thành công việc.

Ràng buộc

  • 1≤T≤100.
  • 1≤N≤10000.
  • 1≤U≤10000.
  • 1≤M≤10000.
  • 1≤wi≤100 với mọi i∈{1,2,…,N}.

Ví dụ

Input Output Giải thích
1
5 2 3
2 7 3 6 6
5 Uiharu phục vụ hai khách 7 và 3 (tổng 10, mất 5 giây), Misaka phục vụ ba khách còn lại (tổng 14, mất ⌈14/3⌉=5 giây).
2
1 1 1
5
3 10 1
1 1 1
5
1
Bộ thứ hai: Uiharu phục vụ cả ba khách, tổng 3 đơn vị công việc xong trong giây đầu tiên.

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