trang chủ / đề bài / icpcwf09_d

Xếp dây vào ống

Đề bài

Mô tả

Công ty Allied Conduit Manufacturing (ACM) sản xuất các ống luồn dây bằng kim loại có tiết diện tròn, bên trong chứa nhiều loại dây điện khác nhau. Tiết diện của mỗi sợi dây là một hình tròn có đường kính tối đa 20 milimét (20000 micromét). ACM cần một chương trình tính đường kính nhỏ nhất của một ống có thể chứa 4 sợi dây với đường kính cho trước.

Hình 1 minh họa các cách xếp bốn sợi dây có kích thước khác nhau vào những ống có đường kính nhỏ nhất.

Hình 1: Xếp các sợi dây vào ống

Chương trình của bạn nhận đường kính của các sợi dây và phải xác định đường kính trong nhỏ nhất của ống có thể chứa được các sợi dây đó. Nói cách khác, cần đặt bốn hình tròn có đường kính cho trước vào bên trong một hình tròn sao cho chúng không chồng lên nhau (được phép tiếp xúc), và tìm đường kính nhỏ nhất có thể của hình tròn bao ngoài.

Dữ liệu vào

Dữ liệu vào gồm nhiều bộ test. Mỗi bộ test là một dòng chứa bốn số nguyên d1, d2, d3, d4 là đường kính của các sợi dây, tính bằng micromét. Các số thỏa mãn 20000≥d1≥d2≥d3≥d4>0.

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

Dữ liệu ra

Với mỗi bộ test, in ra số thứ tự của bộ test (bắt đầu từ 1), tiếp theo là đường kính nhỏ nhất của ống tính bằng micromét, làm tròn tới số nguyên gần nhất. Làm theo đúng định dạng trong ví dụ.

Ràng buộc

  • 20000≥d1≥d2≥d3≥d4>0, các số đều nguyên.
  • Mỗi file có không quá 200 bộ test.
  • Đường kính chính xác của mỗi bộ test cách mốc làm tròn x.5 ít nhất 0.01.

Ví dụ

Input Output Giải thích
10000 10000 10000 10000
10000 10000 10000 3000
12000 12000 3600 3600
0
Case 1: 24142
Case 2: 21547
Case 3: 24000
Ba bộ test ứng với ba hình trong Hình 1. Bộ 1: bốn dây bằng nhau xếp thành hình vuông, đường kính 10000(1+2)≈24142.1. Bộ 2: ba dây lớn tiếp xúc nhau từng đôi, đường kính 10000(1+2/3)≈21547.0, dây nhỏ nằm vừa trong khe giữa hai dây lớn và ống. Bộ 3: hai dây lớn nằm dọc một đường kính của ống, hai dây nhỏ nằm trong hai khe.
20000 20000 20000 20000
20000 1 1 1
1 1 1 1
20000 20000 7000 6000
0
Case 1: 48284
Case 2: 20001
Case 3: 2
Case 4: 40000
Bộ 2: hai dây lớn nhất nằm dọc một đường kính, hai dây còn lại vừa trong khe nên đáp án là d1+d2=20001. Bộ 3: 1+2≈2.414, làm tròn thành 2. Bộ 4: khe giữa hai dây 20000 trong ống 40000 chứa vừa hình tròn đường kính 40000/3≈13333.

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