Contest ôn tập THT bảng C2 - 2023 #03

_minhduc là một người rất giàu có. _minhduc sở hữu một con heo tiết kiệm có khả năng đặc biệt là vào ngày thứ \(i\) thì con heo đó sẽ có thêm \(i\) đồng.

Vào mỗi buổi tối, _minhduc sẽ đến kiểm tra một lần.

Yêu cầu: Bạn hãy lập chương trình nhập vào một số nguyên dương \(N\) và xác định xem sau bao nhiêu ngày thì số tiền trong con heo lớn hơn hoặc bằng \(N\) đồng. Biết rằng con heo sẽ bắt đầu từ ngày thứ \(1\).

Input

• Chứa một số nguyên dương duy nhất \(N\) \((1 \le N \le 10^{18})\).

Output

• In ra kết quả bài toán sau khi thực hiện yêu cầu đề bài.

Scoring

• Subtask \(1\) (\(50\%\) số điểm): Có \(N \le 10^9\).
• Subtask \(2\) (\(50\%\) số điểm): Không có ràng buộc gì thêm.

Example

13

5

Dạo này, shiba có thói quen thích nghe nhạc. Cậu ấy quyết định mua một máy nghe nhạc (loại cũ) để thử cảm giác nghe nhạc của cuối những thập niên 90 :Đ.

Có tất cả \(n\) bài nhạc, bài nhạc thứ \(i\) dài đúng \(a_{i}\) phút. Máy nghe nhạc mà shiba mua ghi được tối đa \(m\) phút. Hỏi có bao nhiêu cách ghi nhạc khác nhau lên máy nghe nhạc, biết rằng mỗi bài nhạc chỉ được phép ghi một lần lên máy?

Input

• Dòng thứ nhất chứa hai số nguyên dương \(n,m\) (\(n \le 1000, m \le 1000\)).
• Dòng thứ hai chứa \(n\) số nguyên dương \(a_{i}\) (\(a_{i} \le 1000\)).

Output

• Một số nguyên duy nhất là cách ghi nhạc lên máy nghe nhạc mà shiba có thể thực hiện, lấy phần dư cho \(10^9+7\).

Scoring

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

Example

3 4
1 5 6

1

Định nghĩa: Một tên \(a\) được gọi là tiền tố của tên \(b\) nếu \(a\) xuất hiện ở phần đầu tiên của \(b\).

Sau khi vất vả ngồi gõ code, shiba được giao thêm nhiệm vụ đó là nhập tên các học sinh của lớp học vào máy tính.

Ban đầu, công việc rất nhàm chán vì chỉ có gõ lại tên từ đầu đến cuối. Tuy nhiên trong quá trình gõ, shiba nhận ra một điều, đó là có thể có một vài học sinh có tên trùng nhau phần đầu (nói cách khác có các cặp tên sao cho tên này nằm ở vị trí đầu tiên của tên kia), cậu ấy có thể lợi dụng điều đó để nhập tên được nhanh hơn. Sẽ chẳng có gì đáng nói nếu chỉ có nhập vài cái tên trùng nhau, tuy nhiên shiba lại muốn biết thêm một điều đó là có bao nhiêu cặp tên là tiền tố của một tên khác.

Yêu cầu: Xác định số cặp tên, trong đó tên này là tiền tố của tên kia.

Input

• Dòng thứ nhất chứa một số nguyên dương \(n\) (\(n \le 5 \times 10^4\)).
• \(n\) dòng tiếp theo, mỗi dòng chứa một xâu kí tự là tên học sinh.
• Tổng độ dài của các xâu không vượt quá \(5 \times 10^6\).

Output

• Một dòng duy nhất chứa một số nguyên dương là số cặp tên học sinh trùng nhau phần đầu.

Scoring

• Subtask \(1\) (\(70\%\) số điểm): \(n \le 1000\).
• Subtask \(2\) (\(30\%\) số điểm): không có ràng buộc gì thêm.

Example

3
a
ab
abc

3

shiba đang phát triển một robot chuyên xử lí chuỗi. Khi robot được _minhduc đưa cho một chuỗi chỉ gồm các chữ cái tiếng anh viết thường, nó sẽ xử lí chuỗi theo quy trình sau:

• Bước \(1\): Tìm \(i\) là chỉ số vị trí nhỏ nhất sao cho \(S_i = S_{i+1}\) . Nếu không tồn tại \(i\) thỏa mãn điều đó, robot sẽ chấm dứt quy trình.

• Bước \(2\): Nếu \(S_i\) là z thì ta xóa \(S_i\) và \(S_{i+1}\) và trong chuỗi \(S\) . Nếu không phải là z : Gọi \(change\) là chữ cái tiếp theo của \(S_i\) theo alphabet, ta thay thế \(S_i\) và \(S_{i+1}\) bằng chữ cái \(change\) (tất nhiên là \(length(s)\) sẽ bị giảm đi \(1\) đơn vị).

• Bước \(3\): Quay lại bước \(1\).

Ví dụ: Khi robot được giao cho chuỗi axxxxza thì con robot sẽ thực hiện theo quy trình theo như sau: axxxxza \(\rightarrow\) ayxxza \(\rightarrow\) ayyza \(\rightarrow\) azza \(\rightarrow\) aa \(\rightarrow\) b.

Yêu cầu: Cho một chuỗi \(S\) và \(Q\) truy vấn. Mỗi truy vấn có câu hỏi như sau và bạn hãy trả lời nó:

• Cho hai số nguyên dương \(l\) và \(r\) và gọi \(T\) là chuỗi con được ghép từ các chữ cái \(S_l\) đến \(S_r\). Nếu ta thực hiện quy trình giống con robot thì liệu có thể biến chuỗi \(T\) thành một chuỗi rỗng được không? Biết rằng vị trí của xâu bắt đầu từ \(1\) (bắt đầu từ \(S_1\)).

Input

• Dòng đầu tiên chứa chuỗi \(S\) \((1 \le length(S) \le 5 \times 10^5)\).
• Dòng tiếp theo chứa số nguyên dương \(Q\) \((1 \le Q \le 10^5)\).
• \(Q\) dòng còn lại mỗi dòng chứa hai số nguyên dương \(l\) và \(r\) ứng với mỗi truy vấn \((1 \le l \le r \le length(S))\)

Output

• Ứng với mỗi truy vấn in ra Yes nếu có thể biến chuỗi \(T\) thành chuỗi rỗng theo câu hỏi, nếu không thể thì in ra No.

Scoring

• Subtask \(1\) (\(30\%\) số điểm): Có \(Q \le 5\).
• Subtask \(2\) (\(70\%\) số điểm): Không có ràng buộc gì thêm.

Example

axxxxza
2
1 7
2 6

No
Yes