| Nộp bài | Các bài nộp | Làm tốt nhất | Về danh sách bài |
TFIELD - VOI 2015 Day 1 - Ruộng bậc thang |
Ở các vùng cao hiếm đất cùng mặt bằng để canh tác, khi tiến hành trồng trọt trên các sườn đồi núi có đất màu, người ta phải bạt tam cấp để tạo thành những vạt đất bằng. Khu vực đất dốc dùng để canh tác như vậy gọi là ruộng bậc thang. Hình ảnh các khu ruộng bậc thang vẫn luôn là một hình ảnh đẹp ở các vùng cao khiến du khách và các nhà nhiếp ảnh đam mê và tốn không ít phim ảnh. Gia đình Hoàng có một khu ruộng bậc thang bao quanh một ngọn đồi được chia thành các khoang bậc thang, mỗi khoang trồng một loại cây. Khi nhìn từ trên cao xuống, ta thấy các khoang bậc thang này có hình dạng của các đa giác lồi lồng nhau. Ngoại trừ khoang chứa đỉnh đồi có biên là một đa giác lồi chứa đỉnh đồi, mỗi khoang còn lại được xác định bởi hai đa giác lồng nhau: đa giác có diện tích lớn hơn được gọi là biên ngoài của khoang còn đa giác có diện tích nhỏ hơn được gọi là biên trong của khoang. Mỗi khoang có màu đặc trưng của loại cây được trồng ở khoang đó. Vốn là một người say mê chụp ảnh, muốn có một bức ảnh đẹp, Hoàng tìm cách thay đổi không quá k loại cây được trồng ở k khoang để khi nhìn từ trên cao xuống sẽ thấy một vùng cùng màu có diện tích lớn nhất. Hoàng đã ghi nhận được danh sách m đa giác lồi mô tả biên ngoài của m khoang và màu tương ứng của chúng. Do sơ xuất, Hoàng đã để các thông tin về các khoang trong danh sách bị xáo trộn, không còn được liệt kê theo đúng trình tự từ khoang trong đến khoang ngoài.
Yêu cầu: Cho biết thông tin về danh sách mà Hoàng đã ghi nhận và số nguyên k, hãy tìm cách thay đổi không quá k loại cây được trồng ở k khoang để khi nhìn từ trên cao xuống sẽ thấy một vùng cùng màu có diện tích lớn nhất.
Dữ liệu vào:
- Dòng đầu chứa hai số nguyên dương m, k (k ≤ m);
- Dòng thứ i trong số m dòng tiếp theo chứa thông tin về khoang thứ i trong danh sách mà Hoàng ghi nhận bao gồm:
- Đầu tiên là số nguyên ni là số đỉnh của đa giác lồi mô tả biên ngoài của khoang;
- Tiếp theo là số nguyên ci thể hiện màu của khoang (1 ≤ ci ≤ m);
- Cuối cùng là ni cặp số nguyên, mỗi số có trị tuyệt đối không quá 109, là tọa độ của một đỉnh của đa giác. Các đỉnh của đa giác được liệt kê theo thứ tự ngược chiều kim đồng hồ.
Hai số liên tiếp trên cùng dòng được ghi cách nhau bởi dấu cách.
Dữ liệu ra:
- Ghi ra một số thực là diện tích vùng cùng màu lớn nhất sau khi thay đổi không quá k loại cây được trồng ở k khoang (kết quả đưa ra với độ chính xác 1 chữ số sau dấu chấm thập phân).
Ràng buộc:
- Có 40% số test ứng với 40% số điểm của bài thỏa mãn điều kiện: m ≤ 10; k = 1; các đa giác mô tả biên ngoài của các khoang là hình chữ nhật;
- Có 40% số test khác ứng với 40% số điểm của bài thỏa mãn điều kiện: m ≤ 10; các đa giác mô tả biên ngoài của các khoang là tam giác;
- Có 20% số test còn lại ứng với 20% số điểm của bài thỏa mãn điều kiện: m, ni ≤ 1000.
Ví dụ:
Input:
3 1
4 1 0 0 1 0 1 1 0 1
4 1 -2 -3 5 -3 5 5 -2 5
3 2 -1 -1 4 -1 -1 4 Output:56.0
| Được gửi lên bởi: | VOJ Team |
| Ngày: | 2015-01-13 |
| Thời gian chạy: | 1s |
| Giới hạn mã nguồn: | 50000B |
| Memory limit: | 1536MB |
| Cluster: | Cube (Intel G860) |
| Ngôn ngữ cho phép: | Tất cả ngoại trừ: ASM64 GOSU JS-MONKEY PERL6 PYPY RUST SED |
| Nguồn bài: | VOI15 day 1 |
hide comments
|
||||||
|
2020-06-27 13:34:52
Tham khảo: Solution: http://megaurl.in/0eFT Code: http://megaurl.in/SU0uQqY |
||||||
|
2019-11-22 14:40:59
test yếu 5 1 4 1 0 -1 1 0 1 1 2 1 4 1 -2 -1 4 -3 4 5 -2 5 3 2 -1 -1 4 -1 -1 4 2 1 1 1 -1 2 4 2 1 -1 2 0 3 2 1 4 test này ra 41.5, code t ra 42 vẫn full |
||||||
|
2019-09-06 10:56:37
Ý tưởng khá đơn giản vét đến khi gặp test lớn cout random ;)) |
||||||
|
2019-09-06 10:51:14
bai nay minh nghi nen lam theo do thi rat de |
||||||
|
2019-09-06 10:49:56
1 dam AC |
||||||
|
2018-12-02 15:55:21
O(n*m) khong can cau truc du lieu. BestYasuoVN2508 |
||||||
|
2017-12-13 08:54:48
một bài thật sự cơ bản về cây bit . hân hạnh đc tài trợ chương trình giọng hát việt nhí . i am bu1th4nh |
||||||
|
2017-11-29 09:28:17
bà mẹ đứa nào dịch sang tiếng việt mới thế :) |
||||||
|
2017-11-27 15:12:29
TFIELZ - VOI 2015 Zay 1 - Zuộq bậk waq Zới hạn Wời zan: 1.0s Bộ n'ớ: 1536MB Mã quồn: 50000 bytes Ở kák vùq kao hiếm dất kùq mặt bằq dể kan' ták, xi tiến hàn' cồq cọt cên kák sườn dồi núi kó dất màu, qười ta fải bạt tam kấp dể tạo wàn' n'ữq vạt dất bằq. Xu vựk dất zốk zùq dể kan' ták n'ư vậy gọi là zuộq bậk waq. Hìn' ản' kák xu zuộq bậk waq vẫn luôn là một hìn' ản' dẹp ở kák vùq kao xiến zu xác và kák n'à n'iếp ản' dam mê và tốn xôq ít fim ản'. Za dìn' Hoàq kó một xu zuộq bậk waq bao kuan' một qọn dồi dượk cia wàn' kák xoaq bậk waq, mỗi xoaq cồq một loại kây. Xi n'ìn từ cên kao xuốq, ta wấy kák xoaq bậk waq này kó hìn' zạq kủa kák da zák lồi lồq n'au. Qoại cừ xoaq cứa dỉn' dồi kó biên là một da zák lồi cứa dỉn' dồi, mỗi xoaq kòn lại dượk xák dịn' bởi hai da zák lồq n'au: da zák kó ziện tíc lớn hơn dượk gọi là biên qoài kủa xoaq kòn da zák kó ziện tíc n'ỏ hơn dượk gọi là biên coq kủa xoaq. Mỗi xoaq kó màu dặk cưq kủa loại kây dượk cồq ở xoaq dó. Vốn là một qười say mê cụp ản', muốn kó một bứk ản' dẹp, Hoàq tìm kác way dổi xôq kuá k loại kây dượk cồq ở k xoaq dể xi n'ìn từ cên kao xuốq sẽ wấy một vùq kùq màu kó ziện tíc lớn n'ất. Hoàq dã gi n'ận dượk zan' sác m da zák lồi mô tả biên qoài kủa m xoaq và màu tươq ứq kủa cúq. Zo sơ xuất, Hoàq dã dể kák wôq tin về kák xoaq coq zan' sác bị xáo cộn, xôq kòn dượk liệt kê weo dúq cìn' tự từ xoaq coq dến xoaq qoài. Yêu kầu: Co biết wôq tin về zan' sác mà Hoàq dã gi n'ận và số quyên k , hãy tìm kác way dổi xôq kuá k loại kây dượk cồq ở k xoaq dể xi n'ìn từ cên kao xuốq sẽ wấy một vùq kùq màu kó ziện tíc lớn n'ất. Zữ liệu vào: Zòq dầu cứa hai số quyên zươq m , k ( k ≤ m ); Zòq wứ i coq số m zòq tiếp weo cứa wôq tin về xoaq wứ i coq zan' sác mà Hoàq gi n'ận bao gồm: Dầu tiên là số quyên n i là số dỉn' kủa da zák lồi mô tả biên qoài kủa xoaq; Tiếp weo là số quyên k i wể hiện màu kủa xoaq (1 ≤ k i ≤ m ); Kuối kùq là n i kặp số quyên, mỗi số kó cị tuyệt dối xôq kuá 10 9 , là tọa dộ kủa một dỉn' kủa da zák. Kák dỉn' kủa da zák dượk liệt kê weo wứ tự qượk ciều kim dồq hồ. Hai số liên tiếp cên kùq zòq dượk gi kác n'au bởi zấu kác. Zữ liệu za: Gi za một số wựk là ziện tíc vùq kùq màu lớn n'ất sau xi way dổi xôq kuá k loại kây dượk cồq ở k xoaq (kết kuả dưa za với dộ cín' xák 1 cữ số sau zấu cấm wập fân). Zàq buộk: Kó 40% số test ứq với 40% số diểm kủa bài wỏa mãn diều kiện: m ≤ 10; k = 1; kák da zák mô tả biên qoài kủa kák xoaq là hìn' cữ n'ật; Kó 40% số test xák ứq với 40% số diểm kủa bài wỏa mãn diều kiện: m ≤ 10; kák da zák mô tả biên qoài kủa kák xoaq là tam zák; Kó 20% số test kòn lại ứq với 20% số diểm kủa bài wỏa mãn diều kiện: m , n i ≤ 1000. |
||||||
|
2017-11-09 04:56:55
ngàn đấm AC -_- cda.dev |
||||||
RSS