Dãy số của Dima - Chuyên Tin Online Judge

Dãy số của Dima

Nộp bài giải

Danh sách bài nộp

Bài nộp tốt nhất

Điểm: 4,00 (OI)

Giới hạn thời gian: 2.0s

Python 3 5.0s

Giới hạn bộ nhớ: 256M

Đầu vào: stdin

Đầu ra: stdout

Dạng bài

Ngôn ngữ cho phép

C++, Go, Java, Kotlin, Pascal, Python, Scratch

Cho hàm $f$ xác định trên tập số nguyên không âm bằng đệ quy:

$f (0) = 0$ ;
$f (2 x) = f (x)$ ;
$f (2 x + 1) = f (x) + 1$ .

Cho dãy số nguyên dương $a_{1}, a_{2}, \dots, a_{n}$ . Hãy đếm số cặp chỉ số $(i, j)$ với $1 \leq i < j \leq n$ sao cho $f (a_{i}) = f (a_{j})$ .

Dữ liệu vào

Dòng đầu chứa số nguyên $n$ .
Dòng thứ hai chứa $n$ số nguyên dương $a_{1}, a_{2}, \dots, a_{n}$ .

Dữ liệu ra

In ra một số nguyên duy nhất là số cặp chỉ số thoả mãn.

Ràng buộc

$1 \leq n \leq 10^{5}$
$1 \leq a_{i} \leq 10^{9}$

Ví dụ

Input	Output	Giải thích
3 1 2 4	3	$f (1) = f (2) = f (4) = 1$ , do đó cả 3 cặp đều thoả mãn.
3 5 3 1	1	$f (5) = 2$ , $f (3) = 2$ , $f (1) = 1$ . Chỉ có cặp $(1, 2)$ thoả mãn.
6 396640239 62005863 473635171 329666981 510631133 207643327	2	Có $2$ cặp chỉ số $(i, j)$ mà $f (a_{i}) = f (a_{j})$ .

Bình luận

Không có bình luận tại thời điểm này.