Contest ôn thi HSG 9-10 (số 7)

Khi truy cập trang web, máy chủ thường trả về các mã trạng thái gồm ba chữ số để thông báo kết quả. Các mã này được chia thành năm nhóm:

• \(100 - 199\): Phản hồi thông tin (Informational responses)
• \(200 - 299\): Phản hồi thành công (Successful responses)
• \(300 - 399\): Thông điệp chuyển hướng (Redirection messages)
• \(400 - 499\): Lỗi phía người dùng (Client error).
• \(500 - 599\): Lỗi phía máy chủ (Server error).

Yêu cầu: Cho một mã trạng thái \(n\). Hãy kiểm tra xem \(n\) có phải là mã lỗi hay không.

Input

• Đọc vào từ tệp văn bản HTTP.INP:
  • Dòng duy nhất chứa số nguyên \(n\) (dữ liệu vào đảm bảo \(100 \le n \le 599\)).

Output

• Ghi ra tệp văn bản HTTP.OUT:
  • In ra YES nếu \(n\) là mã lỗi, ngược lại in ra NO.

Example

200

NO

404

YES

Cho một dãy số nguyên \(a\) gồm \(n\) phần tử \(a_1, a_2, \ldots, a_n\). Xét bộ ba các chỉ số \(i, j, k\) với \(1 \le i < j < k \le n\). Một bộ ba được gọi là “thú vị” nếu trong \(a_i, a_j, a_k\) có đúng hai phần tử bằng nhau, phần tử còn lại có giá trị khác biệt. Thí dụ, các bộ ba giá trị \((3,6,3)\) và \((1,1,5)\) là “thú vị”, trong khi \((9,9,9)\) và \((1,2,3)\) thì không.

Yêu cầu: Cho dãy \(a\), hãy đếm số lượng bộ ba “thú vị” có trong dãy.

Input

• Dòng đầu tiên chứa số nguyên dương \(n\) \((1 \le n \le 3 \cdot 10^5)\).
• Dòng thứ hai chứa \(n\) số nguyên \(a_1, a_2, a_3, \ldots, a_n\) \((1 \le a_i \le 10^6)\).

Output

• Một số nguyên duy nhất là số lượng bộ ba đếm được.

Example

4
1 1 1 2

3

Scoring

• Subtask \(1\) (\(30\%\) số điểm): \(n \le 100\).
• Subtask \(2\) (\(30\%\) số điểm): \(n \le 3000\).
• Subtask \(3\) (\(25\%\) số điểm): \(a_i \le 3000\).
• Subtask \(4\) (\(15\%\) số điểm): không có ràng buộc thêm.

Về bản chất, hệ cơ số liên quan đến việc biểu diễn một số nguyên dưới dạng tổng các lũy thừa. Hệ số thông dụng và được sử dụng phổ biến hiện nay là hệ thập phân. Ví dụ, số \(1432\) được viết dưới dạng \(1432 = 2 \cdot 10^0 + 3 \cdot 10^1 + 4 \cdot 10^2 + 1 \cdot 10^3\).

Cho trước số nguyên dương \(X\). Bạn cần chỉ ra một dãy số nguyên \(a_1, a_2, \ldots, a_n\) độ dài \(n\) thỏa mãn toàn bộ các điều kiện:

• \(n \leq 20\)
• \(a_i \geq 0\)
• \(3^{a_1} + 3^{a_2} + \cdots + 3^{a_n} = X\)

Input

• Dòng duy nhất chứa số \(X\) (\(1 \leq X \leq 10^5\)).
• Dữ liệu vào đảm bảo luôn tồn tại dãy số nguyên \(a\) hợp lệ.

Output

• Dòng đầu tiên chứa số nguyên dương \(n\).
• Dòng tiếp theo chứa \(n\) số nguyên \(a_1, a_2, a_3, \ldots, a_n\).
• Bạn được điểm nếu \(n\) và dãy \(a\) thỏa mãn các điều kiện, dù có in ra bất kỳ giá trị nào.

Example

13

5
1 1 0 1 1

Scoring

• Subtask 1 (\(20\%\) số điểm): \(X \leq 20\).
• Subtask 2 (\(20\%\) số điểm): tồn tại số nguyên \(a, b \leq 10\) sao cho \(X = 3^a + b\).
• Subtask 3 (\(30\%\) số điểm): tồn tại đáp án với \(n \leq 10\) và \(a_i \leq 4\).
• Subtask 4 (\(30\%\) số điểm): không có ràng buộc gì thêm.