Ảnh máy tính thông thường là một ma trận các pixel, trong đó mỗi pixel là một hình vuông nhỏ có một màu cụ thể. Khi vẽ những đường không hoàn toàn song song với các trục của ma trận pixel, hình vẽ sẽ xuất hiện sai lệch. Đường tròn là một ví dụ cực đoan của hiện tượng này.

Giả sử ta có một bức ảnh gồm \((2R+1)\times(2R+1)\) pixel. Các hàng và cột được đánh số từ \(-R\) đến \(R\), sao cho pixel ở tâm nằm tại hàng \(0\), cột \(0\). Ban đầu mọi pixel đều màu trắng. Có thể vẽ một đường tròn đen bán kính \(R\), tâm ở giữa ảnh, bằng giả mã sau; set_pixel_to_black(x, y) tô đen pixel tại hàng \(x\), cột \(y\).

draw_circle_perimeter(R):
  for x between -R and R, inclusive {
    y = round(sqrt(R * R - x * x))   # round to nearest integer, breaking ties towards zero
    set_pixel_to_black(x, y)
    set_pixel_to_black(x, -y)
    set_pixel_to_black(y, x)
    set_pixel_to_black(-y, x)
  }

Một số pixel có thể bị tô đen nhiều lần, nhưng thao tác này có tính lũy đẳng: gọi set_pixel_to_black trên một pixel vốn đã đen sẽ không làm thay đổi gì.

Giả mã sau vẽ một hình tròn đặc, bắt đầu từ một ảnh toàn màu trắng.

draw_circle_filled(R):
  for x between -R and R, inclusive {
    for y between -R and R, inclusive {
      if round(sqrt(x * x + y * y)) <= R:
        set_pixel_to_black(x, y)
    }
  }

Cuối cùng, giả mã sau vẽ sai một hình tròn đặc:

draw_circle_filled_wrong(R):
  for r between 0 and R, inclusive {
    draw_circle_perimeter(r)
  }

Cho \(R\), hãy tính số pixel có màu khác nhau giữa bức ảnh gọi draw_circle_filled(R) và bức ảnh gọi draw_circle_filled_wrong(R).

Dữ liệu vào

Dòng đầu chứa số bộ test \(T\). Mỗi bộ test được mô tả trên một dòng chứa số nguyên \(R\), là bán kính đường tròn cần vẽ.

Dữ liệu ra

Với mỗi bộ test, in một dòng theo dạng Case #x: y, trong đó \(x\) là số thứ tự bộ test, bắt đầu từ \(1\), và \(y\) là số pixel có màu khác nhau giữa bức ảnh tạo bởi draw_circle_filled(R) và bức ảnh tạo bởi draw_circle_filled_wrong(R).

Ràng buộc

• \(1\le T\le100\).

Phân nhóm

• Test Set 1 (phán quyết hiển thị): \(1\le R\le100\).
• Test Set 2 (phán quyết ẩn): \(1\le R\le10^5\).

Điểm các phân nhóm

Mỗi Test Set tương ứng với một subtask trên LQDOJ. Bảng dưới đây giữ nguyên điểm chính thức của Google Code Jam và quy đổi tỷ lệ trên tổng điểm của bài.

Ví dụ

3
2
8
50

Case #1: 4
Case #2: 24
Case #3: 812

Nguồn

Google Code Jam 2022, Vòng 2, bài Pixelated Circle.

Nguồn chính thức trên Google Coding Competitions Archive, phát hành theo giấy phép Apache-2.0.