trang chủ / đề bài / icpcwf15_h

Kênh ngầm qanat

Đề bài

Mô tả

Qanat là một hệ thống thủy lợi được dùng rộng rãi để dẫn nước ở những vùng khí hậu nóng và khô hạn. Kỹ thuật này do người Ba Tư phát triển từ hơn 2000 năm trước. Ở Maroc, qanat được gọi là khettara và đến nay vẫn còn được sử dụng ở miền nam nước này.

Thành phần cơ bản của một qanat là một kênh gần như nằm ngang, dẫn nước từ một nguồn nước ngầm tới một cửa ra gần khu dân cư. Ngoài ra còn có một giếng đứng gọi là giếng mẹ, đi thẳng từ nguồn nước ngầm lên tới mặt đất trên sườn núi hoặc đồi. Xây dựng một hệ thống như vậy cực kỳ tốn kém, nhất là vào thời xưa, vì toàn bộ đất đá đào ra từ kênh và giếng mẹ đều phải được mang lên mặt đất, qua cửa ra của kênh hoặc qua miệng giếng mẹ. Để hỗ trợ việc xây dựng, người ta thường đào thêm một hoặc nhiều giếng đứng ở những vị trí được chọn kỹ phía trên kênh ngầm. Các giếng này cũng phải được đào, nhưng chúng cho phép đưa thêm đất từ kênh ngang lên mặt đất.

Trong bài này, mặt cắt của qanat được mô hình hóa như sau: cửa ra của kênh ở điểm (0,0), nguồn nước ở điểm (w,0) và miệng giếng mẹ ở điểm (w,h), với w>h. Mặt sườn núi là đoạn thẳng nối (w,h) với (0,0). Kênh ngầm là đoạn từ (0,0) tới (w,0), giếng mẹ là đoạn thẳng đứng từ (w,0) tới (w,h).

graph
3
1 2
2 3
3 1
pos 1 0 100
pos 2 360 100
pos 3 360 0
label 1 (0, 0)
label 2 (w, 0)
label 3 (w, h)

Mỗi qanat phải có giếng mẹ thẳng đứng từ nguồn nước lên tới mặt sườn núi, cùng với n giếng đứng bổ sung. Kênh và mọi giếng đều được mô hình hóa là các đoạn thẳng. Nhiệm vụ của bạn là chọn vị trí cho các giếng bổ sung để tổng chi phí đào là nhỏ nhất. Chi phí này bằng tổng quãng đường mà mỗi phần đất đào ra phải được vận chuyển để lên tới mặt đất (có thể kết hợp tùy ý di chuyển theo phương ngang và phương thẳng đứng). Ví dụ, chi phí đào một đoạn đất liên tục bắt đầu từ mặt đất và đi theo một đường có độ dài ℓ (có thể có chỗ rẽ) là ∫0ℓxdx=12ℓ2.

Dữ liệu vào

Một dòng duy nhất gồm ba số nguyên w, h và n. Giá trị w là khoảng cách theo phương ngang từ nguồn nước tới cửa ra của qanat. Giá trị h là khoảng cách theo phương thẳng đứng từ nguồn nước tới mặt sườn núi. Giá trị n là số giếng đứng phải dùng ngoài giếng mẹ.

Dữ liệu ra

Đầu tiên, in ra chi phí đào nhỏ nhất. Tiếp theo, in ra hoành độ x của n giếng đứng được đặt tối ưu, theo thứ tự tăng dần, mỗi số trên một dòng. Nếu n>10, chỉ in 10 hoành độ đầu tiên. Mỗi số được chấp nhận nếu sai số tuyệt đối hoặc sai số tương đối không vượt quá 10−4.

Bạn có thể giả sử lời giải tối ưu là duy nhất. Không có test nào mà lời giải tối ưu có một giếng cách cửa ra của kênh hoặc cách một giếng khác không quá 0,001 đơn vị.

Ràng buộc

  • 1≤w≤10000.
  • 1≤h<w.
  • 1≤n≤1000.

Ví dụ

Input Output Giải thích
8 4 1 31.500000
3.000000
Giếng duy nhất đặt tại x=3, cao 1,5.
195 65 2 12220.000000
48.000000
108.000000
Hai giếng đặt tại x=48 và x=108.
10000 1 1000 30141.885677
9.956721
19.913443
29.870164
39.826887
49.783610
59.740334
69.697060
79.653786
89.610515
99.567245
n=1000>10 nên chỉ in hoành độ của 10 giếng đầ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