Thi thử Olympic Miền Trung - Tây Nguyên khối lớp 11

Dạ hội cuối năm (prom) là một sự kiện trọng đại trước khi kết thúc năm học ở trường THPT chuyên Lê Quý Đôn. Vì đã là năm cuối cấp nên Minh Huy quyết tâm mời cho bằng được chị Constant tham gia khiêu vũ cùng mình. Tiếc thay, chị Constant đã nhận lời mời làm bạn nhảy của chuyên gia tin học Flow God (dưới tư cách cựu học sinh) nên đành phải từ chối Minh Huy. Không bỏ cuộc, Minh Huy liên tục đưa ra những hứa hẹn đầy hấp dẫn để lôi kéo khiến chị Constant phải đôi chút xiêu lòng: Chị Constant đồng ý hủy hẹn với Flow God để đi với Minh Huy nếu như cậu có thể tính được số lượng dãy con có độ cồng kềnh nhỏ nhất trong một dãy số.

Với một dãy số nguyên dương gồm \(n\) số \(a_1,a_2,\cdots,a_n\), độ cồng kềnh của một dãy con liên tiếp \(a_i,a_{i+1},\cdots,a_j\) là hiệu của số lớn nhất trong dãy và số nhỏ nhất trong dãy. Ví dụ: độ cồng kềnh của \([1,3,2]\) là \(3−1=2\).

Chị Constant muốn tìm dãy con liên tiếp có độ cồng kềnh nhỏ nhất có thể, và tổng quát hơn, đếm xem có bao nhiêu dãy con liên tiếp có độ cồng kềnh nhỏ nhất như thế. Bạn hãy giúp Minh Huy giải đáp lời thách đố này để được dự prom cùng chị Constant nhé!

Input

• Dòng đầu tiên chứa một số nguyên dương \(n\)
• Dòng thứ hai chứa \(n\) số nguyên dương \(a_1,a_2,\cdots,a_n (1 \leq a_i \leq n)\)

Output

• In ra một số nguyên dương, là số lượng dãy con liên tiếp có độ cồng kềnh nhỏ nhất.

Scoring

• Subtask \(1\) (\(30\%\) số điểm): \(n \leq 300\).
• Subtask \(2\) (\(30\%\) số điểm): \(n \leq 3,000\).
• Subtask \(3\) (\(40\%\) số điểm): \(n \leq 300,000\).

Example

3
1 1 1 

6

\(dungde99\) đang có \(n\) buổi hẹn với \(n\) anh trai đỏ Codeforces vào ngày \(a_1, a_2, a_3,\cdots, a_n\) tương ứng (các ngày có thể trùng nhau). Tiếc là \(dungde99\) chỉ được nghỉ vào \(m\) ngày liên tiếp nên cô ấy muốn tranh thủ gặp càng nhiều anh trai đỏ Codeforces càng tốt.

Thế nhưng cuom1999 lại lên kế hoạch bắt đi mất một anh trai của \(dungde99\). Cụ thể là, cuom1999 sẽ tính toán chọn một người anh trai từ danh sách của \(dungde99\) sao cho số anh trai nhiều nhất \(dungde99\) có thể gặp được sau đi bị bắt mất một anh là ít nhất.

Hãy đưa ra số anh trai nhiều nhất \(dungde99\) có thể gặp được theo tính toán của cuom1999. Biết rằng cuom1999 cũng nick đỏ Codeforces nên luôn tìm cách chọn một anh trai tối ưu nhất.

Input

• Dòng đầu chứa hai số nguyên \(n\), \(m\). Trong đó \(n\) là số buổi hẹn với các anh trai của \(dungde99\), \(m\) là số ngày nghỉ liên tiếp của \(dungde99\).
• Dòng 2 chứa \(n\) số nguyên \(a_i\) là ngày gặp mặt anh trai thứ \(i\). (các số \(a_i\) được sắp xếp theo thứ tự tăng dần).

Ouput

• Một dòng duy nhất đưa ra kết quả của bài toán.

Constraints

• \(1 \leq a_i \leq 10^9\)
• \(1 \leq m \leq 10^9\)

Scoring

• Subtask \(1\) (\(10\%\) số điểm): \(1 \leq n \leq 100\)
• Subtask \(2\) (\(40\%\) số điểm): \(1 \leq n \leq 10^4\)
• Subtask \(3\) (\(50\%\) số điểm): \(1 \leq n \leq 10^6\)

Example

7 5    
1 3 7 10 11 19 20 

2

Ở lớp 10 chuyên Tin, Nhật và Vy tuy là đôi bạn thân nhưng trong chuyện học hành lại cạnh tranh nhau rất khốc liệt. Một hôm, thầy Hùng khen ngợi rằng Vy có khả năng tính nhẩm tốt hơn Nhật làm cậu bạn vô cùng ấm ức và ghen tức. Nhật không chấp nhận thực tế này nên đã mời hai đàn anh, đàn chị là Công Huân và Ly Na đứng ra làm giám khảo cho một cuộc tỉ thí công khai về trình độ tính nhẩm giữa cậu ấy và Vy. Huân và Na quyết định chọn dãy số Catalan nổi tiếng làm đề bài cho cuộc so tài: Số Catalan thứ n được định nghĩa là \(C_n\)= \(\frac{1}{n+1}\)\((_{2n}^{n})\)= \(\frac{(2n)!}{(n+1)!n!}\) và hai bạn thí sinh cần kiểm tra xem với mỗi cặp số nguyên không âm \(m\) và \(K\) thì \(K\) có bằng với \(C_m\) hay không, ai trả lời chính xác và nhanh nhất sẽ giành chiến thắng. Nhật muốn thắng cuộc tỉ thí bằng mọi giá nên đã nhờ các bạn lập trình tính toán giúp câu trả lời. Hãy giúp cậu ấy đạt được thắng lợi nhé!

Input

• Dòng đầu chứa số nguyên dương \(T \leq 100\) là số lượng câu hỏi.

• \(T\) dòng sau, mỗi dòng chứa hai số nguyên không âm \(m\) và \(K\) thể hiện một câu hỏi từ Huân và \(Na\).

Output

• Gồm \(T\) dòng, mỗi dòng in ra YES nếu \(K=C_m\) với \(m\), \(K\) tương ứng, hoặc in ra NO trong trường hợp ngược lại.

Scoring

• Subtask \(1\) (\(30\%\) số điểm): \(m \leq 10\), \(K \leq 20,000\).
• Subtask \(2\) (\(30\%\) số điểm): \(m \leq 5000\), \(K\) có không quá \(5000\) chữ số.
• Subtask \(3\) (\(40\%\) số điểm): \(m \leq 50,000\), \(K\) có không quá \(50,000\) chữ số.

Example

5
0 1
1 1
3 5
5 42
6 130        

YES
YES
YES
YES
NO       

Hiếu vừa khám phá ra một khái niệm mới và khoe ngay với Quý: định nghĩa về xâu đẹp. Theo đó, một xâu \(s\) được gọi là đẹp nếu \(s\) có không quá \(n\) ký tự và \(f(s)\) chia hết cho \(m\), trong đó \(f(s)\) bằng tổng tất cả các \(g(c)\) với \(c\) là một ký tự trong \(s\), quy ước \(g('a')=1\), \(g('b')=2\), \(g('c')=3,\cdots, g('z')=26\). Ví dụ, với \(n=3\) và \(m=9\) thì aap là một xâu đẹp vì \(f("aap")=1+1+16=18\) chia hết cho \(m=9\), còn aah không phải là một xâu đẹp vì \(f("aah")=1+1+8=10\) không chia hết cho \(m=9\). Với xâu rỗng \(s= \emptyset\) thì \(f(s)=0\) (do đó \(s=\emptyset\) cũng là một xâu đẹp với mọi \(m\)).

Quý hiểu ngay khái niệm mới của Hiếu và liền đố ngược lại cậu: hãy tìm ra xâu đẹp có thứ tự từ điển nhỏ thứ \(k\) với \(n\) và \(m\) cho trước. Nhắc lại, xâu \(A\) được xem là có thứ tự từ điển nhỏ hơn xâu \(B\) nếu tồn tại một vị trí \(t\) sao cho \(A[1...t−1]=B[1...t−1]\) và \(A[t]<B[t]\).

Vì số \(k\) của Quý đưa ra quá lớn nên Hiếu chỉ biết ấp úng và nhờ đến các bạn lập trình giải giúp câu đố này cho Hiếu. Hãy giúp Hiếu tìm ra xâu đẹp đó nhé!

Input

• Gồm một dòng duy nhất chứa ba số nguyên dương \(n\), \(m\) và \(k (2 \leq k \leq 10^{15})\).

Output

• In ra xâu đẹp nhỏ thứ \(k\) theo thứ tự từ điển. Nếu số lượng xâu đẹp nhỏ hơn \(k\), in ra \(−1\).

Scoring

• Subtask \(1\) (\(20\%\) số điểm): \(n \leq 4\).
• Subtask \(2\) (\(20\%\) số điểm): \(n \leq 100,m=1\).
• Subtask \(3\) (\(60\%\) số điểm): \(n,m \leq 100\).

Example

3 9 8

ace