trang chủ / đề bài / icpcwf07_i

Các bể nước

Đề bài

Mô tả

Công ty Aqua Container Management quản lý các cơ sở chứa nước. Họ đang xem xét một hệ thống chứa nước gồm một dãy các bể thẳng đứng được nối với nhau. Mỗi bể có tiết diện ngang là một mét vuông, nhưng các bể có chiều cao khác nhau. Đáy của mọi bể nằm ở mặt đất. Mỗi bể được nối bằng một ống với bể đứng trước nó trong dãy và bằng một ống khác với bể đứng sau nó trong dãy. Các ống nối nằm ngang và ở độ cao tăng dần (tức là ống nối bể i với bể i+1 nằm cao hơn ống nối bể i với bể i−1). Bể 1 để hở ở phía trên nên không khí và nước có thể tự do đi vào. Mọi bể còn lại đều kín, không khí và nước chỉ có thể vào hoặc ra qua các ống nối. Các ống nối đủ lớn để nước và không khí chảy qua tự do và đồng thời, nhưng đủ nhỏ để có thể bỏ qua kích thước của chúng trong bài toán này.

Dãy bể được đổ đầy bằng cách rót nước thật chậm vào miệng bể 1, tiếp tục cho đến khi mực nước chạm tới đỉnh bể 1. Khi mực nước dâng lên quá các ống nối, nước chảy giữa các bể.

Aqua Container Management cần một chương trình tính số mét khối nước có thể rót vào dãy bể trước khi mực nước chạm tới đỉnh bể 1.

Hình dưới đây minh hoạ một trường hợp đơn giản chỉ có hai bể. Sau khi rót xong, không khí ở phần trên của bể thứ hai bị nén (áp suất của nó lớn hơn một atmosphere), nên mực nước trong bể thứ hai thấp hơn mực nước trong bể thứ nhất.

Các bể trước khi rót nước (trái) và sau khi rót nước (phải).

Các nguyên lý vật lý sau có ích khi giải bài này (một số là xấp xỉ được chấp nhận trong phạm vi bài toán):

  • Nước chảy từ cao xuống thấp.
  • Trong không gian hở, áp suất không khí bằng một atmosphere.
  • Không khí nén được (thể tích của một lượng không khí phụ thuộc vào áp suất). Nước không nén được (thể tích của một lượng nước không đổi, không phụ thuộc áp suất).
  • Áp suất không khí như nhau tại mọi điểm trong một không gian kín. Nếu thể tích của không gian kín thay đổi, tích của thể tích và áp suất không khí trong đó không đổi. Ví dụ, một khoảng không khí kín ban đầu có thể tích V1 và áp suất P1; nếu thể tích đổi thành V2 thì áp suất mới P2 thoả mãn P1V1=P2V2.
  • Trong một cột nước bên dưới một khoảng không khí, áp suất nước tại độ sâu D mét dưới mặt nước bằng áp suất không khí tại mặt nước cộng 0.097·D atmosphere. Điều này đúng bất kể khoảng không khí là hở hay kín.
  • Trong một khối nước liền nhau (ví dụ khi hai hay nhiều bể được nối bằng các ống nằm dưới mặt nước), áp suất nước như nhau tại mọi điểm cùng độ cao.

Dữ liệu vào

Dữ liệu vào gồm nhiều bộ test, mỗi bộ mô tả một dãy bể nước và gồm ba dòng. Dòng thứ nhất chứa số nguyên N là số bể. Dòng thứ hai chứa N số thực dương là chiều cao (tính bằng mét) của các bể 1 đến N. Dòng thứ ba chứa N−1 số thực: số thứ k là độ cao so với mặt đất của ống nối bể k với bể k+1. Các số trên dòng thứ ba tăng dần (mỗi số lớn hơn số đứng trước nó).

Sau bộ test cuối cùng là một dòng chứa số nguyên 0.

Dữ liệu ra

Với mỗi bộ test, in một dòng gồm số thứ tự của bộ test (bắt đầu từ 1) và lượng nước, tính bằng mét khối, có thể rót vào bể 1 trước khi mực nước chạm tới đỉnh bể 1. In kết quả với đúng ba chữ số sau dấu chấm thập phân.

In một dòng trống sau kết quả của mỗi bộ test. Làm theo đúng định dạng trong ví dụ.

Ràng buộc

  • 2≤N≤10.
  • Chiều cao các bể nằm trong (0,100], độ cao các ống nằm trong [0,100); mọi số thực có không quá ba chữ số sau dấu chấm thập phân.
  • Ống nối bể k với bể k+1 nằm thấp hơn hẳn đỉnh của bể k và đỉnh của bể k+1.
  • Mỗi file có không quá 1000 bộ test.
  • Trong mọi test, đáp án chính xác cách mọi ngưỡng làm tròn x+0.0005 (x là bội của 0.001) ít nhất 10−6.

Ví dụ

Input Output Giải thích
2
10.0 8.0
4.0
0
Case 1: 15.260

Ví dụ trong hình: bể 2 dâng tới khoảng 5.260 m khi bể 1 đầy 10 m.
3
5.0 8.0 5.0
3.0 4.0
4
12.0 6.0 7.0 9.0
1.0 3.0 5.0
0
Case 1: 8.936

Case 2: 21.644

Bộ 1: khi ống ở độ cao 3 bị ngập, không khí của bể 2 và bể 3 bị nhốt chung; bể 1 đầy khi bể 2 mới dâng tới khoảng 3.936 m, chưa tới ống ở độ cao 4, nên bể 3 không nhận được nước. Bộ 2: nước tràn sang cả bốn bể; mực nước cuối cùng là 12, khoảng 3.806, 5 (bể 3 đang tràn sang bể 4) và khoảng 0.838 m.

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