ICPC 2023 miền Bắc - E: Pizza

Xem dạng PDF
Gửi bài giải
Điểm: 0,70
Giới hạn thời gian: 1.0s
Giới hạn bộ nhớ: 256M
Nguồn bài:
ICPC 2023 miền Bắc
Dạng bài
Ngôn ngữ cho phép
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

Trong trường hợp đề bài hiển thị không chính xác, bạn có thể tải đề bài tại đây: Đề bài

Bình luận

Hãy đọc nội quy trước khi bình luận.


  • -7
    monke_bi_bai_nao  đã bình luận lúc 11, Tháng 10, 2023, 4:04

    Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.


  • 17
    hungntils  đã bình luận lúc 8, Tháng 10, 2023, 8:44

    Công thức bài này là:

    (n - 1) * (n - 2) * (~n^2~ - 3 * n + 12) / 24


    • -2
      leminhtuanils27  đã bình luận lúc 10, Tháng 10, 2023, 2:28

      làm sao để có công thức này á b ơi


      • 11
        hungntils  đã bình luận lúc 10, Tháng 10, 2023, 2:40 ← chỉnh sửa

        Xét lần lượt" từng đường chéo. Với mỗi đường chéo, nếu nó cắt K đường chéo trước nó thì số phần được chia ra sẽ tăng thêm K+1.


        • 9
          hungntils  đã bình luận lúc 10, Tháng 10, 2023, 2:58

          => số phần sẽ là (số đường chéo) + (số giao điểm) + 1. Với đa giác n cạnh: số đường chéo là n*(n-3) / 2. Do không có 3 đường chéo nào đồng quy => số giao điểm n * (n - 1) * (n - 2) * (n - 3) / 24. Ta có công thức 1 + n * (n-3) / 2 + n * (n - 1) * (n - 2) * (n - 3) / 24. Rút gọn công thức trên ta có công thức: (n - 1) * (n - 2) * (~n^2~ - 3 * n + 12) / 24