trang chủ / đề bài / icpcwf16_a

Chế độ ăn cân bằng

Đề bài

Mô tả

Mỗi ngày, Danny mua một chiếc kẹo ở cửa hàng và ăn nó. Cửa hàng có m loại kẹo, đánh số từ 1 đến m. Danny biết rằng một chế độ ăn cân bằng là quan trọng và áp dụng điều đó vào việc mua kẹo của mình. Với mỗi loại kẹo i, anh gán một tỉ lệ mục tiêu là một số thực fi (0<fi≤1). Anh muốn tỉ lệ kẹo loại i trong số tất cả kẹo đã ăn xấp xỉ bằng fi. Chính xác hơn, gọi si là số kẹo loại i Danny đã ăn và n=∑i=1msi. Tập kẹo được gọi là cân bằng nếu với mọi i ta có

nfi−1<si<nfi+1.

Danny đã mua và ăn kẹo được một thời gian, và trong suốt thời gian đó tập kẹo luôn cân bằng. Bây giờ anh tự hỏi mình còn có thể mua thêm bao nhiêu chiếc kẹo nữa mà vẫn giữ được điều kiện này. Cho các tỉ lệ mục tiêu fi và dãy kẹo anh đã ăn cho tới nay, hãy xác định anh có thể mua và ăn thêm nhiều nhất bao nhiêu chiếc kẹo sao cho tại mọi thời điểm tập kẹo đều cân bằng.

Dữ liệu vào

Dữ liệu vào gồm ba dòng:

  • Dòng đầu tiên chứa hai số nguyên m là số loại kẹo và k là số kẹo Danny đã ăn.
  • Dòng thứ hai chứa m số nguyên dương a1,…,am. Các số này tỉ lệ với f1,…,fm, tức là fi=ai/∑j=1maj.
  • Dòng thứ ba chứa k số nguyên b1,…,bk, trong đó bi là loại kẹo Danny đã mua và ăn vào ngày thứ i (dòng này rỗng khi k=0).

Dữ liệu ra

In ra số kẹo nhiều nhất Danny có thể mua và ăn thêm mà chế độ ăn vẫn luôn cân bằng. Nếu số kẹo không có giới hạn trên, in ra từ forever.

Ràng buộc

  • 1≤m≤105, 0≤k≤105.
  • ai≥1 và ∑j=1maj≤105.
  • 1≤bi≤m.
  • Mọi tiền tố của dãy b (kể cả toàn bộ dãy) đều cân bằng.

Ví dụ

Input Output Giải thích
6 5
2 1 6 3 5 3
1 2 5 3 5
1 Tổng các aj là 20, đã ăn s=(1,1,1,0,2,0). Khi n=7 cần s3>7·620−1=1,1, s4>0,05 và s6>0,05, tức là cần thêm ít nhất 3 chiếc kẹo trong khi chỉ có 2 ngày (n=6 và n=7). Vậy chỉ ăn thêm được 1 chiếc.
6 4
2 1 6 3 5 3
1 2 5 3
forever Từ trạng thái này Danny có thể ăn tiếp mãi mà tập kẹo luôn cân bằng.

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