Thi thử tuyển sinh lớp 10 Chuyên Vĩnh Phúc 2026 - Bộ đề bài

#	Bài tập	Điểm	Thời gian:	Giới hạn bộ nhớ
1	Bài 1: Dãy vô hạn (TS10 Vĩnh Phúc thi thử - 2026)	4 (p)	1.0s	256M
2	Bài 2: Số mềm (TS10 Vĩnh Phúc thi thử - 2026)	3 (p)	1.0s	256M
3	Bài 3: Truy vấn chia hết (TS10 Vĩnh Phúc thi thử - 2026)	2 (p)	1.0s	256M
4	Bài 4: Phần tử nhìn thấy (TS10 Vĩnh Phúc thi thử - 2026)	1 (p)	1.0s	256M

1. Bài 1: Dãy vô hạn (TS10 Vĩnh Phúc thi thử - 2026)

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

Xét một dãy vô hạn \((a_1, a_2, a_3, \dots)\) gồm các số nguyên dương, được xây dựng theo các nhóm liên tiếp như sau:

Nhóm thứ \(1\) gồm \(1\) khối, khối này có \(1\) phần tử mang giá trị \(1\).
Nhóm thứ \(2\) gồm \(2\) khối, mỗi khối có \(2\) phần tử giống nhau, khối đầu chứa giá trị \(2\), khối sau chứa giá trị \(3\).
Nhóm thứ \(3\) gồm \(3\) khối, mỗi khối có \(3\) phần tử giống nhau, giá trị trong các khối lần lượt là \(4, 5, 6\).
Tổng quát, nhóm thứ \(k\) gồm \(k\) khối, mỗi khối có \(k\) phần tử giống nhau, các giá trị là các số nguyên liên tiếp tăng dần tiếp nối từ nhóm trước.

Dãy bắt đầu như sau:
\([1], [2, 2 \mid 3, 3], [4, 4, 4 \mid 5, 5, 5 \mid 6, 6, 6], [7, 7, 7, 7 \mid 8, 8, 8, 8 \mid 9, 9, 9, 9 \mid 10, 10, 10, 10], \dots\)

Yêu cầu: Tìm giá trị của phần tử thứ \(n\) trong dãy.

Input

Một dòng duy nhất chứa số nguyên \(n\) (\(1 \le n \le 10^{18}\)).

Output

In ra một số nguyên duy nhất là giá trị \(a_n\).

Example

Test 1

Input

Output

Note

\(a_3\) là số thứ \(2\) trong khối đầu tiên của nhóm \(2 \implies a_3 = 2\).

Test 2

Input

Output

Note

\(a_{13}\) là số thứ \(2\) trong khối thứ \(3\) của nhóm \(3 \implies a_{13} = 6\).

Scoring

Subtask \(1\) (\(30\%\) số điểm): \(n \le 100\).
Subtask \(2\) (\(25\%\) số điểm): \(n \le 10^6\).
Subtask \(3\) (\(15\%\) số điểm): \(n \le 10^{12}\).
Subtask \(4\) (\(15\%\) số điểm): \(n \le 10^{14}\).
Subtask \(5\) (\(15\%\) số điểm): \(n \le 10^{18}\).

2. Bài 2: Số mềm (TS10 Vĩnh Phúc thi thử - 2026)

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

An có hứng thú với các số nguyên dương có tính chất: trong biểu diễn thập phân của số, hai chữ số liền kề chênh lệch không quá \(1\). An gọi các số như vậy là các số mềm.

Với một số mềm có \(n + 1\) chữ số, An mã hoá nó bằng bộ đôi: chữ số bắt đầu \(d\) và xâu \(S\) độ dài \(n\) chỉ gồm các ký tự +, -, =. Khi đó số mềm được xác định như sau:

Chữ số đầu tiên là \(d\).
Xét lần lượt các ký tự trong xâu:
- Nếu là +, chữ số tiếp theo lớn hơn chữ số trước đó \(1\) đơn vị.
- Nếu là -, chữ số tiếp theo nhỏ hơn chữ số trước đó \(1\) đơn vị.
- Nếu là =, chữ số tiếp theo bằng chữ số trước đó.

An đã quên mất \(d\), chỉ nhớ xâu \(S\). Hãy giúp An tìm số mềm nhỏ nhất có xâu mã hoá là \(S\) hoặc chỉ ra rằng An nhớ nhầm xâu \(S\).

Input

Một dòng duy nhất chứa xâu \(S\) độ dài nhỏ hơn \(100\), chỉ gồm các ký tự: +, -, =.

Output

In ra số mềm tìm được (các chữ số liền nhau, không có khoảng trắng, chữ số đầu tiên khác \(0\)).
Nếu không tồn tại số thỏa mãn (An nhớ nhầm xâu mã hoá), in ra \(0\).

Example

Test 1

Input

+--+=+

Output

Note

Bắt đầu từ \(1\): + \(\to 2\); - \(\to 1\); - \(\to 0\); + \(\to 1\); = \(\to 1\); + \(\to 2\).

Test 2

Input

+++++++++

Output

Note

Dù bắt đầu từ chữ số nào cũng sẽ vượt quá \(9\).

Scoring

Subtask \(1\) (\(50\%\) số điểm): Xâu \(S\) có độ dài không vượt quá \(6\).
Subtask \(2\) (\(50\%\) số điểm): Không có ràng buộc bổ sung.

3. Bài 3: Truy vấn chia hết (TS10 Vĩnh Phúc thi thử - 2026)

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

Cho dãy gồm \(N\) số nguyên dương đôi một phân biệt \(A = (a_1, a_2, \dots, a_N)\).

Hãy trả lời \(Q\) truy vấn, mỗi truy vấn gồm ba số nguyên dương \(l, r, d\), yêu cầu đếm số phần tử \(a_i\) trong \(A\) thoả mãn:

\(l \leq i \leq r\)
\(a_i\) hoặc là ước số của \(d\), hoặc là bội số của \(d\).

Input

Dòng 1: Hai số nguyên \(N, Q\) — số phần tử của dãy \(A\) và số truy vấn (\(1 \leq N, Q \leq 10^5\)).
Dòng 2: \(N\) số nguyên dương đôi một phân biệt \(a_1, a_2, \dots, a_N\) (\(1 \leq a_i \leq 2 \cdot 10^5; a_i \neq a_j, \forall i \neq j\)).
\(Q\) dòng tiếp theo, mỗi dòng chứa ba số nguyên \(l, r, d\) (\(1 \leq l \leq r \leq N, 1 \leq d \leq 2 \cdot 10^5\)).

Output

In ra một dòng gồm \(Q\) số nguyên, số thứ \(i\) là kết quả của truy vấn thứ \(i\).

Example

Test 1

Input

8 5
12 10 3 18 6 72 28 42
1 8 6
3 7 7
2 6 9
1 5 5
4 8 4

Output

6 1 3 1 2

Note

Truy vấn 1: \(Q([12, 10, 3, 18, 6, 72, 28, 42], 6) \implies \{12, 3, 18, 6, 72, 42\}\)
Truy vấn 2: \(Q([3, 18, 6, 72, 28], 7) \implies \{28\}\)
Truy vấn 3: \(Q([10, 3, 18, 6, 72], 9) \implies \{3, 18, 72\}\)
Truy vấn 4: \(Q([12, 10, 3, 18, 6], 5) \implies \{10\}\)
Truy vấn 5: \(Q([18, 6, 72, 28, 42], 4) \implies \{72, 28\}\)

Scoring

Subtask \(1\) (\(40\%\) số điểm): \(N, Q \leq 1000\).
Subtask \(2\) (\(60\%\) số điểm): Không có ràng buộc bổ sung.

4. Bài 4: Phần tử nhìn thấy (TS10 Vĩnh Phúc thi thử - 2026)

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

Cho dãy số nguyên dương \(a_1, a_2, \dots, a_N\).

Với mỗi đoạn con \([l, r]\) (\(1 \le l \le r \le N\)):

Một phần tử \(a_i\) (\(l \le i \le r\)) được gọi là nhìn thấy từ bên trái, nếu không tồn tại phần tử \(a_j\) (\(l \le j < i\)) sao cho \(a_j \ge a_i\).
Một phần tử \(a_i\) (\(l \le i \le r\)) được gọi là nhìn thấy từ bên phải, nếu không tồn tại phần tử \(a_j\) (\(i < j \le r\)) sao cho \(a_j \ge a_i\).

Giá trị của đoạn \([l, r]\), ký hiệu \(f(l, r)\), là số lượng chỉ số \(i\) (\(l \le i \le r\)) khác nhau được nhìn thấy từ ít nhất một trong hai phía.

Yêu cầu: Tính tổng giá trị của tất cả các đoạn con \([l, r]\), nghĩa là tính tổng:

\[\sum_{l=1}^{n} \left( \sum_{r=l}^{n} f(l, r) \right)\]

Input

Dòng 1: số nguyên \(N\) (\(1 \le N \le 10^5\)).
Dòng 2: \(N\) số nguyên \(a_1, a_2, \dots, a_N\) (\(1 \le a_i \le 10^9\)).

Output

In ra một số nguyên — tổng giá trị của tất cả các đoạn con.

Example

Test 1

Input

4
4 2 3 2

Output

Note

\(f(1,1) = 1\), các đoạn độ dài 1 đều có giá trị bằng 1.
\(f(2,2) = 1\).
\(f(3,3) = 1\).
\(f(4,4) = 1\).
\(f(1,2) = 2\), các đoạn độ dài 2 đều có giá trị bằng 2.
\(f(2,3) = 2\).
\(f(3,4) = 2\).
\(f(1,3) = 2\), đoạn \([4, 2, 3]\): chỉ có hai phần tử đầu mỗi phía là nhìn thấy.
\(f(2,4) = 3\), đoạn \([2, 3, 2]\): cả 3 phần tử đều nhìn thấy.
\(f(1,4) = 3\), đoạn \([4, 2, 3, 2]\): phần tử thứ hai không nhìn thấy được từ cả hai phía.

Test 2

Input

8
7 2 3 2 4 3 3 7

Output

Note

Trong số 36 đoạn con của dãy, có:

8 đoạn giá trị bằng 1.
14 đoạn giá trị bằng 2.
11 đoạn giá trị bằng 3.
3 đoạn giá trị bằng 4.

Scoring

Subtask \(1\) (\(20\%\) số điểm): \(N \le 50\).
Subtask \(2\) (\(20\%\) số điểm): \(N \le 300\).
Subtask \(3\) (\(25\%\) số điểm): \(N \le 5000\).
Subtask \(4\) (\(35\%\) số điểm): Không có ràng buộc bổ sung.