trang chủ / đề bài / icpcwf25_c

Cô dâu của dòng ống

Đề bài

Mô tả

Câu chuyện vẫn tiếp diễn! Đã vài năm nay, thị trấn của bạn được "ban tặng" một lượng dồi dào Flubber, một hóa chất nhân tạo đáng yêu nhưng hơi dễ cháy, độc hại, có tính axit, có tri giác và khá tinh nghịch. Người ta vẫn đang tìm thêm công dụng (hay nói đúng hơn là bất kỳ công dụng nào) cho chất này. Trong lúc đó, nhà máy Flubber vẫn chạy hết công suất. Mọi nỗ lực đóng cửa nhà máy đều thất bại, một phần vì chẳng ai chắc ai mới thực sự là người điều hành nó.

Bạn được giao nhiệm vụ chứa dòng Flubber chảy không ngừng vào các bể chứa Flubber để dùng sau này (hoặc ít ra là để nó khỏi làm phiền mọi người). Để làm việc này, bạn có một mạng lưới phức tạp gồm các ống dẫn Flubber nối các trạm Flubber và các bể chứa.

Mỗi trạm Flubber có một hoặc nhiều ống dẫn đi ra, và có các cửa chắn có thể nâng lên hạ xuống để Flubber chảy vào trạm được chia vào các ống ra theo bất kỳ tỉ lệ nào bạn muốn. Chẳng hạn, bạn có thể cho toàn bộ Flubber đi vào một ống, hoặc chia cho hai ống theo tỉ lệ 25 và 75, v.v.

Ngược lại, một ống dẫn chảy xuống một hoặc nhiều trạm hoặc bể chứa ở thấp hơn, nhưng Flubber trong ống được chia cho chúng theo một tỉ lệ cố định mà bạn không điều khiển được. Có thể một phần Flubber bị thất thoát ra môi trường, nhưng đó là vấn đề của người kế nhiệm bạn chứ không phải của bạn.

Bạn muốn làm đầy tất cả các bể chứa nhanh nhất có thể. Cụ thể, trong mọi cách cấu hình việc chia Flubber ở các trạm, bạn muốn cực đại hóa lượng Flubber nhỏ nhất chảy vào một bể chứa.

Ở ví dụ thứ nhất, trạm 1 có hai ống ra. Ống thứ nhất đưa 80% lượng Flubber vào nó tới bể 3 và 10% tới bể 4; ống thứ hai đưa 40% tới trạm 2 và 30% tới bể 4. Trạm 2 có một ống đưa 100% tới bể 5. Bạn được chọn tùy ý tỉ lệ Flubber trạm 1 chia cho hai ống của nó, nhưng mỗi ống chia Flubber theo đúng các phần trăm đã ghi.

Dữ liệu vào

Dòng đầu tiên chứa ba số nguyên s, r và d, trong đó s (1≤s≤10000) là số trạm, r (1≤r≤3) là số bể chứa, và d (s≤d≤20000) là số ống dẫn. Các trạm được đánh số từ 1 đến s và các bể chứa được đánh số từ s+1 đến s+r, theo thứ tự độ cao giảm dần. Flubber của nhà máy ban đầu chảy vào trạm 1.

Mỗi dòng trong d dòng tiếp theo bắt đầu bằng hai số nguyên i và n, trong đó i (1≤i≤s) là trạm có thể xả vào ống này, và n (1≤n≤10) là số đầu ra của ống. Phần còn lại của dòng gồm n cặp số nguyên o và p, trong đó o (i<o≤s+r) là một trạm hoặc bể chứa mà ống này chảy vào, và p (1≤p≤100) là phần trăm lượng Flubber đi vào ống sẽ chảy tới o. Các giá trị o của cùng một ống đôi một khác nhau. Mỗi trạm có ít nhất một ống mà nó có thể xả vào. Tổng các phần trăm của các đầu ra của một ống không vượt quá 100.

Dữ liệu ra

In ra một số phần trăm f, là giá trị lớn nhất sao cho với một cách cấu hình việc chia Flubber ở các trạm nào đó, mọi bể chứa đều nhận được ít nhất f% lượng Flubber nhà máy sản xuất ra. Đáp án của bạn được chấp nhận nếu sai số tuyệt đối không quá 10−6.

Ràng buộc

  • 1≤s≤10000, 1≤r≤3, s≤d≤20000.
  • Với mỗi ống: 1≤i≤s, 1≤n≤10; mỗi đầu ra có i<o≤s+r và 1≤p≤100; các o của một ống đôi một khác nhau; tổng các p của một ống không vượt quá 100.
  • Mỗi trạm có ít nhất một ống.

Ví dụ

Input Output Giải thích
2 3 3
1 2 3 80 4 10
1 2 2 40 4 30
2 1 5 100
24.0 Trạm 1 cho 30% vào ống thứ nhất và 70% vào ống thứ hai. Bể 3 nhận 0,8·30=24%, bể 4 nhận 0,1·30+0,3·70=24%, trạm 2 nhận 0,4·70=28% và chuyển hết cho bể 5.
1 2 3
1 1 2 50
1 1 3 50
1 2 2 40 3 60
42.8571428571 Chỉ có trạm 1 với ba ống. Cho 27 vào ống thứ nhất và 57 vào ống thứ ba: bể 2 nhận 17+27=37, bể 3 nhận 37, tức khoảng 42,857%.

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