trang chủ / đề bài / icpcwf23_i

Thế giới nước

Đề bài

Mô tả

Trong những năm gần đây, người ta đã phát hiện hàng nghìn hành tinh bên ngoài Hệ Mặt Trời. Một yếu tố quan trọng cho khả năng duy trì sự sống là sự có mặt của nước ở dạng lỏng. Phát hiện nước trên những hành tinh xa xôi không hề dễ dàng.

Với các hành tinh tự quay, một công nghệ hoàn toàn mới sử dụng quang phổ phân cực lượng tử tương đối tính có thể giúp ích. Nó hoạt động như sau (đây là mô tả đã được đơn giản hóa, vì chỉ có ba người trên hành tinh này hiểu nó thực sự hoạt động thế nào).

Hình trên minh họa các vùng của một bước (tô đỏ), với d=12∘ và n=10.

Giả sử kính thiên văn quan sát hành tinh sao cho trục quay của nó thẳng đứng và đường xích đạo nằm ngang. Chỉ đường thẳng đứng ở chính giữa ảnh (đường chứa trục quay) được phân tích, vì nó cho độ phân giải bề mặt hành tinh cao nhất.

Quá trình phân tích diễn ra theo từng bước d độ. Trong một bước, dữ liệu được tích lũy trong lúc hành tinh quay thêm d độ, nên mỗi bước cho thông tin về một múi d độ của bề mặt hành tinh. Ảnh được chia thành n đoạn có chiều cao bằng nhau, được phân tích riêng rẽ. Như vậy múi d độ được chia thành n vùng A1,…,An. Với mỗi vùng Ai, việc phân tích ảnh cho ra một số là phần trăm diện tích của Ai được nước bao phủ. Các vùng Ai của một bước được tô sáng trong hình trên.

Có thể coi bề mặt hành tinh là một mặt cầu. Điều này có nghĩa mỗi vùng A2,…,An−1 là một tứ giác cầu: nó có bốn đỉnh, hai cạnh song song với xích đạo (tức là nằm trong các mặt phẳng song song với mặt phẳng xích đạo) và hai cạnh nằm trên các đường tròn lớn đi qua hai cực của hành tinh, hai đường tròn lớn này cách nhau d độ. Ở mỗi cực, hai trong bốn đỉnh trùng vào cực, nên A1 và An là các tam giác cầu chỉ có một cạnh song song với xích đạo. Do độ cong của bề mặt, cạnh song song với xích đạo càng gần xích đạo thì càng dài, còn cạnh nằm trên đường tròn lớn càng gần các cực thì càng dài.

Quá trình trên được lặp lại cho d độ quay tiếp theo, và cứ thế, tổng cộng m lần, cho tới khi toàn bộ bề mặt hành tinh được bao phủ (tức là md=360 độ). Nhiệm vụ của bạn là từ dữ liệu đã cho, tính phần trăm diện tích bề mặt hành tinh được nước bao phủ.

Dữ liệu vào

Dòng đầu tiên chứa hai số nguyên n và m (2≤n,m≤1000). Mỗi dòng trong n dòng tiếp theo chứa m số nguyên ai,j (0≤ai,j≤100 với 1≤i≤n và 1≤j≤m). Mỗi cột của ma trận này mô tả các phép đo của một bước, tức là một lần quay d độ. Số ai,j là phần trăm diện tích của vùng Ai được nước bao phủ ở bước thứ j.

Dữ liệu ra

In ra phần trăm diện tích bề mặt hành tinh được nước bao phủ. Đáp án được chấp nhận nếu sai số tuyệt đối không quá 10−6.

Ràng buộc

  • 2≤n,m≤1000.
  • 0≤ai,j≤100.

Ví dụ

Input Output Giải thích
3 7
63 61 55 54 77 87 89
73 60 38 5 16 56 91
75 43 11 3 16 20 95
51.809523810 Hành tinh được chia thành 7 múi, mỗi múi d=360/7 độ, mỗi múi gồm 3 vùng.
4 3
10 10 10
10 10 10
10 10 10
10 10 10
10.000000000 Mọi vùng đều có 10% diện tích là nước, nên 10% bề mặt hành tinh là nước.

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