CIRCLES - Đường tròn

Xem dạng PDF
Gửi bài giải
Điểm: 1,00 (OI)
Giới hạn thời gian: 1.0s
Giới hạn bộ nhớ: 256M
Tác giả:
Hieu Nguyen
Dạng bài
Ngôn ngữ cho phép
C, C#, C++, Go, Java, Pascal, Perl, PHP, Python, Ruby, Rust, Scratch, Swift

Bằng các công cụ đồ họa, Rôn vẽ một đường tròn với đường biên đủ mảnh. Đường tròn này chia mặt phẳng thành hai phần. Vẽ thêm một đường tròn nữa, Rôn thấy tối đa có thể chia mặt phẳng thành bốn phần. Với ba đường tròn, số phần mặt phẳng tối đa có thể là ~8~. Công cụ đồ họa dễ dàng cho phép Rôn vẽ ~n~ đường tròn, thay đổi bán kính, kéo dịch chúng về các phía để điều chỉnh số phần bị phân chia của mặt phẳng. Điều Rôn quan tâm bây giờ là số phần tối đa có thể phân chia mặt phẳng bằng ~n~ đường tròn này để biết lúc dừng lại, không điều chỉnh tiếp.

circles.png

Yêu cầu: Cho số nguyên ~n (0 ≤ n ≤ 10^9)~. Hãy xác định số phần tối đa có thể chia mặt phẳng bằng ~n~ đường tròn.

Input

  • Gồm một dòng duy nhất chứa số nguyên ~n~.

Output

  • Ghi ra một số nguyên duy nhất là kết quả bài toán.

Sample

Input #1
3
Output #1
8

Problem source: Kc97ble - Free Contest

Bình luận

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


  • 0
    dinhvantung0611  đã bình luận lúc 14, Tháng 1, 2024, 15:10

    Ý tưởng: trước tiên ta phân tích ví dụ

    0 đường tròn -> chia được 1 mp duy nhất

    1 đường tròn -> được 2 mp

    2 đường tròn -> 4 mp

    3 đường tròn -> 8mp

    Lúc đầu mình nghĩ số lượng mặt phẳng có lẽ là 2^n (n là số đường tròn). Tuy nhiên mình làm theo cách này thi sai. Lúc này mình nghĩ sang phương án khác, cụ thể.

    Cho n đường tròn (ví dụ n = 9 đi) thì bằng một cách vẽ tối ưu nào đó (mình không biết :>) ta sẽ vẽ được 1 đường tròn đẻ lên cả 8 đường tròn còn lại. tương tự với 8 thằng kia, cứ mỗi đường tròn lại phải đè lên 8 đường tròn còn lại. Bạn có thể lấy n = 3 để check

    Vậy rõ ràng số mp phân chia được phải là 8 * 9 + 1 [8 là số lượng đường tròn bị đè bởi 1 đường tròn, còn 9 là cứ 1 đường tròn ta phải đè lên 8 thằng :))) (mà ta có 9 đường tròn lên đè 9 lần) còn 1 là phần bị đẻ bởi cả 9 đường tròn]. Sau đó +1 mp ngoài cùng nữa là ra. Bạn có thể nhìn hình n = 3 và dựa vào phân tích để xem.

    Note: Bạn suy ra công thức nhé. Chú ý trường hợp n = 0.

    CƯỜNG GIẢ HỌ ĐINH. VẠN CỔ TỐI CƯỜNG