Khởi động sương sương trước khi thi

Elon Musk mua lại Twitter vào năm \(2022\) và đổi tên thành \(\mathbb{X}\).
Việc đầu tiên ông làm là mã hóa dữ liệu, và để mã hóa thì ông cần tạo ra các khóa có dạng của một số \(\mathbb{X}\).

Số \(\mathbb{X}\) là một số tự nhiên có ít nhất \(2\) chữ số, với chữ số hàng đơn vị lớn hơn hẳn các chữ số còn lại. VD: \(13\), \(102\) là số \(\mathbb{X}\), còn \(53\) và \(202\) thì không phải.

Cho hai số \(L\) và \(R\), hỏi có bao nhiêu số \(\mathbb{X}\) nằm trong khoảng từ \(L\) tới \(R\)?

Input

• Dòng đầu tiên chứa số tự nhiên \(L\).
• Dòng thứ hai chứa số tự nhiên \(R\) \((1 \leq L \leq R \leq 10^{18})\).

Output

• In ra một dòng số lượng số \(\mathbb{X}\) nằm trong khoảng từ \(L\) tới \(R\).

Scoring

• \(30\%\) số điểm có \(r \leq 1\ 000\ 000\).
• \(40\%\) số điểm có \(L=1; R = 10^K\) với \(1 \leq K \leq 18\).
• \(30\%\) số điểm không có ràng buộc gì thêm.

Example

55
105

14

Một dãy ngoặc có thể được gọi là dãy ngoặc đúng nếu nó có thể được xây dựng như sau:

• Dãy ngoặc rỗng là dãy ngoặc đúng.
• Nếu \(A\) là dãy ngoặc đúng thì ( \(A\) ), [ \(A\) ] và { \(A\) } và đều là dãy ngoặc đúng.
• Nếu \(A\) và \(B\) đều là dãy ngoặc đúng thì \(A\) \(B\) là dãy ngoặc đúng.

Ví dụ: ([]) và (){}[] là các dãy ngoặc đúng còn (()( không phải là dãy ngoặc đúng.

Cho một dãy ngoặc \(s\) độ dài \(n\), dấu ngoặc thứ \(i\) \((1 \leq i \leq n)\) của dãy \(s\) là \(s_i\) \((s_i \in \{ \texttt{ (, ), [, ], \{, \} } \})\). Gọi dãy con liên tiếp \([ l, r ]\) \((1 \leq l \leq r \leq n)\) của \(s\) là dãy ngoặc có độ dài \((r - l + 1)\) và dấu ngoặc thứ \(i\) \((1 \leq i \leq r - l + 1)\) của dãy con là \(s_{l + i - 1}\).

Yêu cầu: Hãy tính số dãy con liên tiếp của \(s\) là dãy ngoặc đúng.

Input

• Dòng đầu tiên chứa số nguyên dương \(n\) \((1 \leq n \leq 3 \times {10}^5)\).
• Dòng thứ hai chứa dãy ngoặc \(s\) độ dài \(n\).

Output

• Gồm duy nhất một số nguyên là số dãy con liên tiếp của \(s\) là dãy ngoặc đúng.

Scoring

• Subtask 1 (\(30\%\) số điểm): \(n \leq 100\).
• Subtask 2 (\(20\%\) số điểm): \(n \leq 1000\).
• Subtask 3 (\(30\%\) số điểm): \(n \leq 50000\).
• Subtask 4 (\(20\%\) số điểm): Không có ràng buộc gì thêm.

7
)()[]({

3

Khi các em học sinh chuyên tin bắt đầu tìm hiểu và học về khái niệm đệ quy, hàm đệ quy, không ít bài viết và tài liệu đều lấy ví dụ "tính \(n\) giai thừa bằng hàm đệ quy".

\(n!\) (đọc là \(n\) giai thừa) là phép toán một ngôi trên tập hợp các số tự nhiên. \(n\) giai thừa là tích của \(n\) số nguyên dương đầu tiên, tức là

\(n! = 1 \times 2 \times 3 \times \ldots \times n\).

Từ công thức trên ta nhận ra rằng \(n! = (n-1)! \times n\). Vì thế nếu ta cài đặt hàm \texttt{dq(n)} để tính \(n!\), ta có thể cài đặt như sau:

int dq(int n) {
    if(n == 0)
        return 1;             // 0! = 1
    return dq(n - 1) * n;     // n! = (n - 1)! * n
}

Sau khi đã hiểu và sử dụng thành thạo hàm đệ quy, một thời gian sau giáo viên sẽ cho các em tiếp cận kiến thức số học căn bản. Để tăng sự hứng thú cho học sinh, giáo viên quyết định cho các em làm một bài toán có liên quan đến hàm giai thừa vừa được học.

Cho hai số \(n\) và \(m\) \((1 \leq n \leq {10}^{6}, 1 \leq m \leq {10}^6)\), hãy tính \(\lfloor \frac{n!}{m} \rfloor\). Trong đó \(\lfloor x \rfloor\) là số nguyên lớn nhất không vượt quá \(x\). Vì kết quả có thể rất lớn nên chỉ cần đưa ra số dư khi chia \(\lfloor \frac{n!}{m} \rfloor\) cho \(({10}^9 + 7)\).

Input

• Dòng đầu tiên gồm hai số nguyên \(n\) và \(m\) \((1 \leq n \leq {10}^{6}, 1 \leq m \leq {10}^{6})\).

Output

• Chứa một số nguyên duy nhất là kết quả của bài toán.

Scoring

• Subtask 1 (\(40\%\) số điểm): \(n \leq 20\).
• Subtask 2 (\(40\%\) số điểm): \(n \leq 3000\).
• Subtask 3 (\(20\%\) số điểm): Không có ràng buộc gì thêm.

1 2

0

4 2

12

Ví dụ đầu tiên: ta có \(1! = 1\) nên \(\lfloor \frac{1!}{2} \rfloor = 0\).

Ví dụ thứ hai: ta có \(4! = 24\) nên \(\lfloor \frac{4!}{2} \rfloor = 12\).

Thành muốn vẽ lên \(N\) bức tường liên tiếp nhau. Mỗi bức tường có một giá trị biểu thị độ đẹp nếu được vẽ lên bức tường đó đó. Thế nhưng các bức tường lại bắt đầu bị sụp đổ dần sau những trận lũ lụt gần đây. Vì vậy Thành sẽ vừa vẽ nhanh vừa gia cố bức tường được vẽ đó để nó không bị sụp đổ.

Vào đầu mỗi ngày, Thành sẽ vẽ lên một trong \(N\) bức tường. Ngày đầu tiên Thành có thể chọn bất kỳ bức tường nào. Vào các ngày tiếp theo Thành cần vẽ vào bức tường kế tiếp một bức tường đã vẽ. Vào cuối mỗi ngày, một bức tường bị đổ. Bức tường bị đổ luôn là bức tường chưa được vẽ lên và chỉ kề với duy nhất một bức tường khác.

Tổng độ đẹp cuối cùng nhận được là tổng độ đẹp các bức tường mà Thành vẽ lên. Thành mong muốn tìm cách vẽ là dù những bức tường nào bị đổ đi chăng nữa thì tổng độ đẹp cuối cùng tối thiểu là \(B\).

Yêu cầu: Hãy giúp Thành tìm được giá trị \(B\) lớn nhất có thể.

Input

• Dòng đầu tiên ghi duy nhất một số nguyên \(T\leq 5\) là số lượng trường hợp test. Mỗi nhóm dòng trong số \(T\) nhóm dòng sau có cấu trúc như sau:
  • Dòng thứ nhất gồm một số nguyên: \(N\).
  • Dòng thứ hai chứa một xâu gồm \(N\) chữ số trong khoảng từ \(0\) đến \(9\), chữ số thứ \(i\) biểu thị độ đẹp của bức tường thứ \(i\) nếu được vẽ lên.

Output

• Ghi ra \(T\) dòng, mỗi dòng ghi một số nguyên là giá trị \(B\) lớn nhất tìm được.

Scoring

• Subtask #1 (\(50\%\) số điểm): \(2 \leq N \leq 100\).
• Subtask #2 (\(50\%\) số điểm): \(2 \leq N \leq 10^6\).

Example

1
3
535

8

Mẹ mới mua \(n\) quả táo cho Vũ và Long. Vì là anh nên Vũ sẽ nhường cho Long phần nhiều hơn. Tuy nhiên, Vũ sẽ lợi dụng cơ hội này để ra cho Long một bài toán về chia táo để thử thách Long:

Vũ xếp \(n\) quả táo thành 1 hàng, khối lượng các quả theo thứ tự trên hàng được thể hiện bằng mảng \(a: a_1,a_2,...,a_n\). Long sẽ phải chia những quả táo này thành những nhóm nhỏ, sao cho mỗi nhóm sẽ gồm các quả liền kề nhau trong hàng và có tổng khối lượng của nhóm không được quá \(m\). Với mỗi nhóm, quả có khối lượng lớn nhất sẽ thuộc về Vũ và Long sẽ được những quả còn lại.

Long ham ăn và luôn muốn ăn nhiều nhất có thể, bạn hãy giúp Long tìm ra cách chia như trên mà khối lượng táo Long có thể ăn là lớn nhất.

Input

• Dòng đầu tiên gồm 2 số nguyên \(n\) và \(m\).
• Dòng thứ 2 gồm \(n\) số nguyên dương thể hiện \(a: a_1,a_2,...,a_n\).

Output

• Hãy in ra khối lượng táo lớn nhất mà Long có thể ăn.

Scoring

• Subtask \(1\) (\(30\%\) số điểm): \(n \leq 10^3,m \leq 10^{18}\).
• Subtask \(2\) (\(20\%\) số điểm): \(n \leq 10^5,m \leq 200\).
• Subtask \(3\) (\(50\%\) số điểm): \(n \leq 10^5,m \leq 10^{18}\).
• Mọi test đều có \(a_i \leq min(m,10^6),∀ i\)

Example

8 11
1 1 1 5 1 5 1 2 

9