JOI 2026 - Distance
Xem PDFCó \(N\) quả bóng được xếp thành một hàng, gọi là bóng \(1,2,\ldots,N\) theo thứ tự từ trái sang phải. Bóng \(i\) được tô màu \(C_i\).
Với mỗi \(i=1,2,\ldots,N\), hãy tính tổng khoảng cách từ bóng \(i\) đến tất cả các bóng có cùng màu với nó. Khoảng cách giữa bóng \(i\) và bóng \(j\) được định nghĩa là \(|i-j|\).
Dữ liệu vào
- Dòng đầu chứa \(N\).
- Dòng thứ hai chứa dãy \(C\).
Dữ liệu ra
In \(N\) dòng. Dòng thứ \(i\) (\(1 \le i \le N\)) chứa tổng khoảng cách từ bóng \(i\) đến tất cả các bóng có cùng màu với nó.
Chỉ in đáp án, không in lời nhắc nhập dữ liệu hoặc nội dung khác.
Ràng buộc
- \(1\le N\le100\).
-
\(1\le C_i\le100\).
-
Mọi giá trị số trong đầu vào đều là số nguyên.
Ví dụ
Ví dụ 1
Input
4
1 2 1 1Output
5
0
3
4Giải thích
Bóng \(1\) có màu \(1\), bóng \(2\) có màu \(2\), bóng \(3\) có màu \(1\) và bóng \(4\) có màu \(1\).
- Với \(i=1\), các bóng cùng màu là \(1,3,4\), cách bóng \(1\) lần lượt \(0,2,3\), nên in ra \(0+2+3=5\).
- Với \(i=2\), chỉ có bóng \(2\) cùng màu, cách chính nó \(0\), nên in ra \(0\).
- Với \(i=3\), các bóng cùng màu là \(1,3,4\), cách bóng \(3\) lần lượt \(2,0,1\), nên in ra \(2+0+1=3\).
- Với \(i=4\), các bóng cùng màu là \(1,3,4\), cách bóng \(4\) lần lượt \(3,1,0\), nên in ra \(3+1+0=4\).
Ví dụ 2
Input
1
100Output
0Giải thích
Bóng \(1\) có màu \(100\). Với \(i=1\), chỉ có bóng \(1\) cùng màu, cách chính nó \(0\), nên in ra \(0\).
Ví dụ 3
Input
8
1 3 9 7 3 3 7 9Output
0
7
5
3
4
5
3
5Ví dụ 4
Input
10
1 1 1 1 1 1 1 1 1 1Output
45
37
31
27
25
25
27
31
37
45Nguồn
JOI 2025/2026, vòng loại thứ nhất, đợt 2, ngày 2025-10-12. Đề gốc tiếng Nhật của Ủy ban Olympic Tin học Nhật Bản. Bản dịch theo giấy phép CC BY-SA 4.0.
Kỳ thi:
- JOI 2026 - Vòng loại 1 - Đợt 2 (12 Tháng 10., 2025)
Bình luận