#00 - Khảo sát đầu vào

Cho một xâu kí tự, hãy kiểm tra tính đối xứng của nó. Một xâu kí tự được gọi là xâu đối xứng nếu ta đọc xâu này từ trái sang phải hoặc từ phải sang trái là như nhau.

Định dạng đầu vào

• Một xâu ký tự \(S\) có độ dài không quá 255 ký tự

Dữ liệu đầu ra

• In ra \(YES\) nếu \(S\) là xâu đối xứng, ngược lại in ra \(NO\).

Ví dụ

abccba 

YES

abcccc 

NO

Cho một tập hợp số \(A\) rỗng.
Bạn được yêu cầu làm một trong ba thao tác sau \(n\) lần:

1. Thêm một số \(X\) vào tập hợp \(A\)
2. In ra số lớn nhất của tập hợp
3. In ra số lớn nhì của tập hợp

Với mỗi yêu cầu thao tác 2 hoặc 3, hãy in ra số lớn nhất hoặc số lớn nhì tương ứng với thời điểm yêu cầu.

Dữ liệu đầu vào

• Dòng đầu tiên chứa số \(n\) \((n \leq 10^6)\) là số lượng thao tác.
• \(n\) dòng tiếp theo, mỗi dòng sẽ có nội dung thuộc một trong ba dạng sau:
  • + X \((-10^9 \leq X \leq 10^9)\) tương ứng với thao tác 1
  • BEST tương ứng với thao tác 2
  • SECOND tương ứng với thao tác 3
• Dữ liệu đảm bảo chỉ đưa ra thao tác 2 sau khi tập hợp không rỗng, và đưa ra thao tác 3 sau khi tập hợp có ít nhất 2 phần tử.

Định dạng đầu ra

• Với mỗi yêu cầu thao tác 2 hoặc thao tác 3, in ra một dòng là kết quả tương ứng với truy vấn.

Điểm số

• Subtask \(1\) (\(45\%\) số điểm): Chỉ tồn tại các thao tác 1 và 2.
• Subtask \(2\) (\(20\%\) số điểm): Mọi thao tác 1 đều nằm trước các thao tác 2 và 3.
• Subtask \(3\) (\(20\%\) số điểm): Chỉ tồn tại duy nhất một thao tác 2 và một thao tác 3.
• Subtask \(4\) (\(15\%\) số điểm): Không có giới hạn nào khác.

Ví dụ

7 

+ 1
BEST
+ 3
SECOND
+ 2
BEST
SECOND

1
1
3
2

Bạn An đang học Toán-ngón-tay, với tuyệt chiêu múa tay tính toán.

Bạn An đang cầm \(X\) viên sỏi đứng trước một dãy vô hạn các ô.
Ô thứ nhất, bạn An rải vào \(b\) viên sỏi.
Từ ô thứ hai trở đi, ô thứ sau sẽ được rải nhiều hơn ô phía trước \(a\) viên sỏi.

Đố các bạn và bạn An, viên sỏi cuối cùng sẽ nằm ở ô số mấy?

À, để làm khó các bạn, thì câu hỏi trên sẽ được hỏi \(t\) lần: giả sử ta thay đổi \(a\), \(b\) và \(X\) trong bài toán trên, thì kết quả tương ứng là bao nhiêu?

Dữ liệu đầu vào

• Dòng đầu tiên chứa số \(t\) \((t \leq 10^5)\), là số lượng câu hỏi.
• \(t\) dòng tiếp theo, từ dòng \(2\) tới dòng \(t+1\), mỗi dòng lần lượt chứa ba số \(a\), \(b\) và \(X\) \((1 \leq a, b \leq 100; X \leq 10^9)\).

Định dạng đầu ra

• In ra \(t\) dòng, dòng thứ \(i\) tương ứng với đáp án của câu hỏi ở dòng \(i+1\) của đầu vào.

Điểm số

• Subtask \(1\) (\(40\%\) số điểm): \(t=1\)
• Subtask \(2\) (\(10\%\) số điểm): \(a = 2; b=1\)
• Subtask \(3\) (\(20\%\) số điểm): cả \(t\) câu hỏi đều có cùng một cặp số \(a\) và \(b\)
• Subtask \(4\) (\(30\%\) số điểm): không có giới hạn gì thêm

Ví dụ

1
2 3 10

3

2
2 3 10
1 1 12

3
5

Cho một dãy gồm \(n+1\) ô xếp liên tiếp nhau từ ô \(0\) tới ô \(n\); trong đó có \(k\) ô \(A_1, A_2, \dots, A_k\) ta không thể bước chân vào (ô bị chặn).
Bạn ban đầu đứng ở ô \(0\), và bạn phải tìm cách di chuyển tới ô \(n\) bằng cách nhảy 1 ô hoặc nhảy 2 ô.
Cụ thể, nếu bạn đang ở ô \(i\), thì bạn có thể nhảy sang một trong hai ô sau, miễn là nơi bạn nhảy tới không phải là ô bị chặn và vẫn chưa nằm ngoài \(n+1\) ô:

• nhảy sang ô \(i+1\), tốn \(a\) calo
• nhảy sang ô \(i+2\), tốn \(b\) calo

Hãy tìm cách nhảy ít tốn sức nhất.

Dữ liệu đầu vào

• Dòng thứ nhất chứa hai số lần lượt là \(n\) và \(k\) \((0 \leq k \leq n \leq 10^9)\).
• Dòng thứ hai chứa hai số lần lượt là \(a\) và \(b\) \((0 \leq a, b \leq 10^9)\).
• Nếu \(k>0\), dòng thứ ba chứa \(k\) số \(A_1, A_2, \dots, A_k\) \((1 \leq A_i < n)\).

Định dạng đầu ra

In ra một số duy nhất là số calo của cách nhảy ít tốn sức nhất.
Trong trường hợp không có cách nhảy nào thỏa mãn, in ra -1.

Điểm số

• Subtask \(1\) (\(10\%\) số điểm): \(n \leq 10^9; k=0\)
• Subtask \(2\) (\(15\%\) số điểm): \(n \leq 10^5; b \geq 2a\)
• Subtask \(3\) (\(20\%\) số điểm): \(n \leq 20\)
• Subtask \(4\) (\(30\%\) số điểm): \(n \leq 10^5\)
• Subtask \(5\) (\(25\%\) số điểm): \(n \leq 10^9; k \leq 10^5\)

Ví dụ

7 2
2 3
1 6

11

Cho dãy \(A\) gồm có \(n\) phần tử: \(A_1, A_2, \dots, A_n\).
Gọi \(f(l) = \sum\limits_{i=1}^l A_i + \max\limits_{i=1}^l A_i\), tức là tổng của \(l\) phần tử đầu tiên cộng cho phần tử lớn nhất trong số \(l\) phần tử đầu tiên. Mặc định \(f(0) = 0\).

Hãy trả lời \(q\) câu hỏi có dạng: tìm \(l\) lớn nhất sao cho \(f(l) \leq X\).

Dữ liệu đầu vào

• Dòng đầu tiên chứa số \(n\) \((n \leq 10^5)\).
• Dòng thứ hai chứa \(n\) số nguyên dương \(A_1, A_2, \dots, A_n\) \((A_i \leq 10^9)\).
• Dòng thứ ba chứa số \(q\) \((q \leq 10^5)\).
• \(q\) dòng tiếp theo, dòng thứ \(i\) chứa số \(X_i\) \((X_i \leq 10^{18})\), biểu thị cho câu hỏi: tìm \(l\) lớn nhất sao cho \(f(l) \leq X_i\).

Định dạng đầu ra

• In ra \(q\) dòng, dòng thứ \(i\) là đáp án cho câu hỏi thứ \(i\).

Điểm số

• Subtask \(1\) (\(30\%\) số điểm): \(n, q \leq 1000\)
• Subtask \(2\) (\(10\%\) số điểm): \(A_i = A_1\) với mọi \(i\).
• Subtask \(3\) (\(15\%\) số điểm): \(A_i \geq A_{i+1}\) với mọi \(i < n\).
• Subtask \(4\) (\(20\%\) số điểm): \(A_i \leq A_{i+1}\) với mọi \(i < n\).
• Subtask \(5\) (\(25\%\) số điểm): không có giới hạn nào khác.

Ví dụ

5
2 1 3 5 4
1
7

2

5
2 1 3 5 4
2
10
7

3
2

Lại tiếp tục cho một dãy gồm \(n+1\) ô xếp liên tiếp nhau từ ô \(0\) tới ô \(n\); trong đó có \(k\) ô \(A_1, A_2, \dots, A_k\) ta không thể bước chân vào (ô bị chặn).
Bạn ban đầu đứng ở ô \(0\), và bạn phải tìm cách di chuyển tới ô \(n\) bằng cách nhảy 1 ô hoặc nhảy 2 ô.
Cụ thể, nếu bạn đang ở ô \(i\), thì bạn có thể nhảy sang một trong hai ô \(i+1\) hoặc \(i+2\), miễn là nơi bạn nhảy tới không phải là ô bị chặn và vẫn chưa nằm ngoài \(n+1\) ô.

Hãy đếm số cách di chuyển từ ô \(0\) tới ô \(n\).

Dữ liệu đầu vào

• Dòng thứ nhất chứa hai số lần lượt là \(n\) và \(k\) \((0 \leq k \leq n \leq 10^5)\).
• Dòng thứ hai chứa \(k\) số \(A_1, A_2, \dots, A_k\) \((1 \leq A_i \leq n)\).

Định dạng đầu ra

• In ra một số duy nhất là số lượng cách nhảy từ ô \(0\) tới ô \(n\), chia lấy dư cho \(998244353\).

Điểm số

• Subtask \(1\) (\(30\%\) số điểm): \(n \leq 20\)
• Subtask \(2\) (\(25\%\) số điểm): \(k = 0\)
• Subtask \(3\) (\(45\%\) số điểm): không có giới hạn nào khác.

Ví dụ

7 2
1 6

3