[Học thêm HSG9] Ngày 24/7/2024

Bộ đề bài

Trở lại kỳ thi
# Bài tập Điểm Thời gian: Giới hạn bộ nhớ
1 Căn bậc K của N 100 (p) 1.0s 1G
2 Dãy số 100 (p) 1.0s 1G
3 Danh sách phát 100 (p) 1.0s 1G

1. Căn bậc K của N

Điểm: 100 (p) Thời gian: 1.0s Bộ nhớ: 1G Input: bàn phím Output: màn hình

Cho một số nguyên \(N\) và số nguyên dương \(K\), hãy tìm số nguyên dương \(x\) sao cho \(x^k=N\).

Input

  • Dòng thứ nhất chứa số nguyên dương \(t\) - Là số lượng số nguyên \(N\) cần tìm.
  • \(t\) dòng tiếp theo, với mỗi dòng chứa hai số nguyên dương \(N\) và \(k\).

Output

  • Gồm \(t\) dòng, mỗi dòng chứa số nguyên dương \(x\) cần tìm, nếu không tồn tại giá trị \(x\) thỏa mãn, in ra \(-1\).

Giới hạn

  • \(t \leq 10^5\).
  • \(2 \leq k \leq 5\)
  • \(N \leq 10^{18}\)
  • Có \(30\%\) số test tương ứng với \(30\%\) số điểm có \(k=2\)
Sample
CANBACK.INP 
5 
100 2
27 3
81 2
4 3
27 2
CANBACK.OUT 
10
3
9
-1
-1

2. Dãy số

Điểm: 100 (p) Thời gian: 1.0s Bộ nhớ: 1G Input: bàn phím Output: màn hình

Bob gửi cho Alice một dãy số nguyên gồm \(N\) phần tử: \(A_1,A_2,...,A_N\) đây là thông tin về một kho báu. Một đoạn con \((L,R)\) của dãy là một dãy gồm các phần tử liên tiếp \(A_L,A_{L+1},...,A_R\) với \(1\leq L < R \leq N\), đoạn con \((L,R)\) được gọi là chứa thông tin quan trọng nhất nếu:

  • Phần tử đầu tiên bằng phần tử cuối cùng\((A_L = A_R)\)
  • Tổng các phần tử của đoạn là lớn nhất có thể.

Yêu cầu

Hãy giúp Alice tìm đoạn con chứa thông tin quan trọng nhất.

Input

  • Dòng thứ nhất chứa số nguyên dương \(N(N \leq 10^5)\).
  • Dòng thứ hai chứa \(N\) số nguyên \(A_1,A_2,...,A_N)(|A_i| \leq 10^9, 1 \leq i \leq N)\)

Ràng buộc

  • Subtask \(1(40\%\) số điểm\()\): \(N\leq 10^2\)
  • Subtask \(2(30\%\) số điểm\()\): \(N \leq 10^3\)
  • Subtask \(3(30\%\) số điểm\()\): \(N\leq 10^5\)
Sample
Input 
7
3 3 3 3 1 11 1
Output 
13

3. Danh sách phát

Điểm: 100 (p) Thời gian: 1.0s Bộ nhớ: 1G Input: bàn phím Output: màn hình

Cho biết danh sách phát của một đài phát thanh kể từ khi thành lập. Danh sách phát có tổng cộng \(𝑛\) bài hát.
Dãy các bài hát liên tiếp dài nhất, mà mỗi bài trong đó đều độc nhất là dãy nào?

Input

Dòng đầu tiên chứa số nguyên dương \(n\): Số lượng bài hát
Dòng tiếp theo có \(n\) số nguyên \(k_1,k_2,k_3,...,k_n\): Mã số mỗi bài hát

Output

In độ dài của dãy dài nhất mà mỗi bài hát là duy nhất.

Constraints

  • \(1 \leq n \leq 2.10^5\)
  • \(1 \leq k \leq 10^9\)

Subtask

  • Subtask \(1(40\%\) số điểm\():(1 \leq n \leq 100)\)
  • Subtask \(2(30\%\) số điểm\(): (100 < n \leq 10^3)\)
  • Subtask \(3(30\%\) số điểm\()\): Không có ràng buộc gì thêm
Sample
Input 
8
1 2 1 3 2 7 4 2
Output 
5