Thi thử Olympic Miền Trung - Tây Nguyên khối lớp 10 lần 2

Hôm nay thầy giáo quyết định ra một bài tập về tính trung bình công cho cả lớp làm. Đề bài yêu cầu các bạn hãy tìm một dãy con liên tiếp sao cho trung bình cộng của dãy là lớn nhất có thể. T là một là một học sinh trong lớp, vì quá ham chơi, trốn học quá nhiều nên câu ta không giải được bài này nên cậu ấy đã quyết định nhờ các bạn giúp đỡ. Các bạn hãy giúp bạn ấy nhé!

Input

• Dòng đầu tiên gồm một số nguyên dương \(N\) (\(1 ≤ N ≤ 10^5\)).
• Dòng tiếp gồm \(N\) số nguyên dương \(x\) (\(1 ≤ x ≤ 10^5\)).

Output

• Gồm một dòng duy nhất chính là kết quả của bài toán.

Scoring

• Subtask \(1\) (\(70\%\) số điểm): \(n ≤ 5000\)
• Subtask \(2\) (\(30\%\) số điểm): \(n ≤ 10^5\)

Example

6
1 1 1 3 3 3 

3

Lớp \(11\) chuyên Tin có \(n\) học sinh, thầy chủ nhiệm Linh Phan muốn chọn ra một số bạn ở lại trực nhật lớp. Để thêm tính hấp dẫn và công bằng, thầy viết một đoạn code cấp cho mỗi bạn một số tự nhiên ngẫu nhiên và quy định rằng, nếu bạn nào nhận được số có tổng các ước dương của nó nhỏ hơn hai lần số đó thì phải đi trực nhật.

Một lần không may mắn, máy tính của thầy Linh Phan đã sinh ra các số mà sau khi cấp phát cho học sinh thì không có học sinh nào phải ở lại trực nhật. Rút kinh nghiệm từ lần đó, thầy đã chuẩn bị sẵn một dãy số, rồi nhờ các em đội tuyển Tin tính xem có bao nhiêu số có tổng các ước dương nhỏ hơn hai lần số đó, nếu số lượng số này đủ nhiều thì thầy sẽ lấy dãy số đó để cấp cho các bạn trong lớp.

Yêu cầu: Cho số nguyên dương \(n\) và dãy số \(a_1\), \(a_2\),..., \(a_{n – 1}\), \(a_n\). Hãy giúp thầy Linh Phan xác định xem với dãy số này thì có bao nhiêu em học sinh phải làm nhiệm vụ trực nhật.

Input

• Dòng đầu ghi số nguyên dương \(n\), số học sinh trong lớp.
• Dòng thứ hai gồm \(n\) số nguyên dương \(a_1\), \(a_2\),..., \(a_{n–1}\), \(a_n\).

Output

• Gồm một số duy nhất là số học sinh phải ở lại trực nhật tương ứng với dãy số input.

Constraints

• \(N\leq 10^6\)
• \(a_i\leq 5.10^6\)

Scoring

• Subtask \(1\) (\(70\%\) số điểm): \(N\leq 10^3, a_i\leq 10^4\)
• Subtask \(2\) (\(15\%\) số điểm): \(N\leq 10^4, a_i\leq 5.10^6\)
• Subtask \(3\) (\(15\%\) số điểm): Không có ràng buộc gì thêm

Example

5
3 6 9 12 9 

3

Một hôm, Đức nghĩ ra một cách xây dựng một tập hợp số nguyên dương, gọi là \(S\), rồi đố Hân xác định xem một số nguyên dương \(K\) bất kỳ có thuộc tập \(S\) hay không. Biết rằng tập \(S\) của Đức chỉ gồm các số xác định theo hai quy tắc:

• Quy tắc 1: Các số \(a_1\), \(a_2\),..., \(a_n\) thuộc \(S\).
• Quy tắc 2: Nếu \(a\) và \(b\) thuộc \(S\) thì ước số chung lớn nhất của \(a\) và \(b\) cũng thuộc \(S\).
  Vì số phần tử của tập S có thể rất lớn nên Hân đành phải nhờ bạn lập trình tính toán giúp để trả lời câu hỏi của Đức. Bạn hãy giúp Hân nhé!

Input

• Dòng đầu chứa số nguyên dương \(T\) thể hiện số câu hỏi.
• Mỗi nhóm trong \(T\) nhóm dòng tiếp theo mô tả một câu hỏi, gồm:
• Dòng đầu chứa hai số nguyên dương \(n\) và \(K\).
• Dòng tiếp theo chứa \(n\) số nguyên dương phân biệt \(a_1\), \(a_2\),..., \(a_n\).

Output

• Gồm \(T\) dòng, mỗi dòng in ra YES nếu \(K\) nằm trong tập \(S\) tương ứng, hoặc in ra NO trong trường hợp ngược lại.

Constraints

• \(T\leq 5\)
• \(n\leq 20000, a_i\leq 10^{12}, K\leq 10^{12}\)

Scoring

• Subtask \(1\) (\(30\%\) số điểm): \(n\leq 20, a_i\leq 10^6, K\leq 10^6\).
• Subtask \(2\) (\(30\%\) số điểm): \(n\leq 20000, a_i\leq 10^6, K\leq 10^6\).
• Subtask \(3\) (\(40\%\) số điểm): Không có ràng buộc gì thêm

Example

2
5 4
24 2 60 6 40
2 3
9 10 

YES
NO

Tại một buổi tiệc nọ, có \(n\) chàng hoàng tử và \(n\) nàng công chúa. Họ đã chuẩn bị một số món quà để tặng cho nhau. Tuy nhiên, một vấn đề nhỏ nảy sinh: nếu mọi người tặng quà lẫn nhau thì sẽ tốn rất nhiều thời gian. Vì vậy người tổ chức ami nghĩ ra một kế hoạch:

• Mỗi người chỉ tặng quà cho người khác giới. Tức là hoàng tử chỉ tặng quà cho các nàng công chúa, và công chúa chỉ tặng quà cho các chàng hoàng tử.
• Các cặp đôi sẽ trao đổi quà với nhau. Nghĩa là nếu hoàng tử A tặng quà cho công chúa B thì công chúa B cũng sẽ tặng lại cho A.
• Với mỗi cặp đôi, ami sẽ nhờ máy tính quyết định xem họ có trao đổi quà cho nhau không. Bằng kiến thức tin học đỉnh cao của mình, ami đã tạo ra một chương trình nói "Tặng" với xác suất \(\dfrac{1}{k}\) hoặc nói "Không tặng". Tất nhiên, bí kíp lập trình này ami không thể tiết lộ với các bạn.

ami không muốn các vị khách phải buồn, anh muốn rằng mọi người đến đây đều có quà mang về. Vì vậy trước khi quyết định, ami muốn nhờ các bạn tư vấn: Nếu thực hiện theo kế hoạch trên, thì xác suất để mọi người đều có quà là bao nhiêu?

Input

• Gồm một dòng chứa hai số nguyên dương \(n\) và \(k\).

Output

• Gọi \(p\) là xác suất các bạn tính được. Bằng kiến thức toán đỉnh cao của mình, ami đã chứng minh được rằng \(p \times k^{n^2}\) luôn là số nguyên (chứng minh chi tiết nhường lại cho các bạn). Vì vậy ami muốn các bạn hãy in ra một số là số dư của phép tính \(p \times k^{n^2}\) chia cho \(10^9+7\).

Scoring

• Subtask \(1\) (\(20\%\) số điểm): \(1\leq n \leq 4\) và \(k=2\);
• Subtask \(2\) (\(30\%\) số điểm): \(1\leq n \leq 300\) và \(2 \leq k \leq 10^9\);
• Subtask \(3\) (\(30\%\) số điểm): \(1\leq n \leq 3000\) và \(2 \leq k \leq 10^9\);
• Subtask \(4\) (\(20\%\) số điểm): \(1\leq n \leq 300,000\) và \(2 \leq k \leq 10^9\);

Example

2 2 

7

100 100 

828467084