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 milimét ( 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 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 , , , 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 .
Sau bộ test cuối cùng là một dòng chứa duy nhất số nguyên .
Dữ liệu ra
Với mỗi bộ test, in ra số thứ tự của bộ test (bắt đầu từ ), 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
- , các số đều nguyên.
- Mỗi file có không quá bộ test.
- Đường kính chính xác của mỗi bộ test cách mốc làm tròn ít nhất .
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 . Bộ 2: ba dây lớn tiếp xúc nhau từng đôi, đường kính , 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à . Bộ 3: , làm tròn thành . Bộ 4: khe giữa hai dây trong ống chứa vừa hình tròn đường kính . |
Bình luận