LQDOJ contest #11

Vào một tương lai không xa năm 2066, các em học sinh lớp 1 bây giờ đã được tiếp cận với bộ môn toán tổ hợp. Thế nhưng việc giải thích lí thuyết tổ hợp cho các em học sinh tiểu học vẫn là một nhiệm vụ cực kì khó khăn cho các giáo viên tiểu học.

Nhằm xây dựng niềm hứng thú và một chút tư duy căn bản cho các em, giáo viên quyết định giảng dạy một bài toán cơ bản trong lí thuyết tổ hợp.

Cho \(N\) viên kẹo, hỏi rằng có bao nhiêu cách chọn ra \(2\) viên kẹo khác nhau trong \(N\) viên kẹo, hai cách chọn được tính là khác nhau nếu tập hợp các viên kẹo được chọn của hai cách khác nhau.

Input

• Dòng đầu tiên chứa một số nguyên dương \(T\) là số test.

• \(T\) dòng tiếp theo, mỗi dòng chứa một số nguyên dương \(N_i ~ (1 \leq N_i \leq {10}^5)\).

• Đảm bảo rằng tổng các \(N_i\) trong \(T\) test không vượt quá \({10}^5\).

Output

• Gồm \(T\) dòng, dòng thứ \(i\) chứa một số nguyên là số cách chọn ra \(2\) viên kẹo khác nhau trong \(N_i\) viên kẹo.

Scoring

• Subtask 1 (\(10\%\) số điểm): \(T = 1, n \leq 10\).
• Subtask 2 (\(90\%\) số điểm): Không có ràng buộc gì thêm.

Example

3
1
2
3

0
1
3

Bạn đang chơi một trò chơi chiến thuật như sau:

• Có \(N\) quân lính, được đánh số từ \(1\) đến \(N\), quân lính thứ \(i ~ (1 \leq i \leq N)\) được mô tả bởi hai số nguyên \(A_i, B_i\).
• Cần đánh bại một kẻ địch có lượng sinh lực là \(H\).

Mỗi lượt hành động, người chơi có thể thực hiện một trong hai việc sau:

• Chọn một quân lính thứ \(i\) đang còn sống, kích hoạt hành động gây sát thương, khiến lượng sinh lực của kẻ địch giảm một lượng bằng \(A_i\).
• Chọn một quân lính thứ \(i\) đang còn sống, kích hoạt hành động "tự hủy", khiến lượng sinh lực của kẻ địch giảm một lượng bằng \(B_i\). Sau lượt này quân lính thứ \(i\) sẽ "đăng xuất" (không còn sống).

Biết rằng kẻ địch nêu trên bị đánh bại khi và chỉ khi lượng sinh lực của kẻ địch không vượt quá \(0\).

Yêu cầu: Cần thực hiện tối thiểu bao nhiêu lần hành động để đánh bại kẻ địch.

Input

• Dòng đầu tiên chứa hai số nguyên \(N ~ (1 \leq N \leq {10}^5)\) và \(H ~ (1 \leq H \leq {10}^9)\) là số quân lính và lượng sinh lực của kẻ địch.
• \(N\) dòng tiếp theo, dòng thứ \(i\) chứa hai số nguyên \(A_i, B_i ~ (1 \leq A_i < B_i \leq {10}^9)\) mô tả quân lính thứ \(i\).

Output

• Một dòng duy nhất chứa một số nguyên, là số lượt hành động ít nhất cần sử dụng.

Scoring

• Subtask 1 (\(10\%\) số điểm): \(N = 1\).
• Subtask 2 (\(30\%\) số điểm): \(N = 2\).
• Subtask 3 (\(60\%\) số điểm): Không có ràng buộc gì thêm.

Example

1 20
4 8

4

2 12
6 10
1 2

2

Một lớp học gồm \(N\) bạn tổ chức đi dã ngoại. Để thuận tiện cho việc quản lí và tổ chức các hoạt động vui chơi, \(N\) bạn được chia thành không quá \(26\) nhóm.

Vì có không quá \(26\) nhóm nên mỗi nhóm được đặt tên theo một kí tự latin thường, tức là sử dụng các kí tự trong tập \(\{\)'a', 'b', \(\ldots\), 'z' \(\}\).

\(N\) bạn đang xếp thành một hàng dọc để chuẩn bị điểm danh và lên xe, bạn thứ \(i ~ (1 \leq i \leq N)\) thuộc nhóm \(S_i\) (\(S_i\) là một kí tự latin thường). Tưởng rằng chuẩn bị được lên xe và đi chơi liền, nhưng một sự cố đã xảy ra khiến chuyến đi bị delay khoảng 1 tiếng. Trong thời gian này, các bạn quyết định giao lưu làm quen với nhau, nhưng vẫn muốn giữ hàng để có thể lên xe bất cứ lúc nào.

Trước khi đi chơi, các bạn cùng nhóm đã được gặp nhau rất nhiều để thảo luận trước kế hoạch đi chơi sắp tới, vì vậy các bạn muốn tìm một thứ tự xếp hàng khác để được tiếp xúc với các bạn khác nhóm trong thời gian chờ.

Yêu cầu: Tìm một hoán vị có thứ tự từ điển nhỏ nhất của xâu S, sao cho không có hai kí tự liền kề nhau và bằng nhau.

Input

• Dòng đầu tiên chứa một số nguyên dương \(N ~ (1 \leq N \leq 2\times{10}^5)\) là số bạn đi dã ngoại.

• Dòng thứ hai chứa một xâu S gồm \(N\) kí tự, mỗi kí tự là một chữ cái latin thường.

Output

• Một xâu là hoán vị của xâu S thỏa mãn yêu cầu đề bài, hoặc đưa ra \(-1\) nếu không tồn tại xâu thỏa mãn yêu cầu.

Scoring

• Subtask 1 (\(10\%\) số điểm): \(N \leq 10\).
• Subtask 2 (\(30\%\) số điểm): \(S_i \in \{ \text{'a', 'b', 'c'} \}\).
• Subtask 3 (\(60\%\) số điểm): Không có ràng buộc gì thêm.

Example

6
cavaer

acaerv

9
didadiddu

dadididud

3
aaa

-1

Trong chương trình toán lớp 1 năm 2066, sau khi học xong lí thuyết tổ hợp cơ bản, các em học sinh đã hiểu được

số tập con khác rỗng của một tập hợp có \(N\) phần tử là \(2^{N}-1\).

Nếu việc học chỉ dừng lại ở phần đọc, hiểu và nhớ lí thuyết thì chắc chắn sẽ không đem lại sự hứng thú cho các em học sinh và không củng cố được tư duy toán học cho các em học sinh. Vì vậy ở phần bài tập của sách giáo khoa có một bài tập như sau:

Cho \(N\) đồ chơi được sắp xếp thành một hàng ngang, các đồ chơi được đánh số từ \(1\) đến \(N\), đồ chơi thứ \(i ~ (1 \leq i \leq N)\) từ trái sang phải được đánh số là \(i\).

Gọi khoảng cách giữa hai đồ chơi thứ \(i ~ (1 \leq i \leq N)\) và thứ \(j ~ (1 \leq j \leq N)\) là \(\lvert i - j \rvert\). Một cách chọn ra ít nhất một đồ chơi trong \(N\) đồ chơi tương ứng với một tập con khác rỗng của tập hợp \(N\) đồ chơi. Một cách chọn được gọi là \(k\) - xa cách khi và chỉ khi

• có ít nhất một đồ chơi được chọn và
• bất kì hai đồ chơi khác nhau được chọn đều có khoảng cách không bé hơn \(k\).

Với mỗi số nguyên \(k ~ (1 \leq k \leq N)\), bài tập yêu cầu học sinh đưa ra số cách chọn \(k\) - xa cách, lấy phần dư khi chia cho \(({10}^9 + 7)\).

Yêu cầu: Hãy lập trình để tìm ra đáp án chính xác của bài toán, để làm lời giải cho các em học sinh đối chiếu đáp án.

Input

Dòng đầu tiên chứa một số nguyên dương \(N ~ (1 \leq N \leq {10}^5)\).

Output

Gồm \(N\) dòng, dòng thứ \(k ~ (1 \leq k \leq N)\) gồm một số nguyên là số cách chọn \(k\) - xa cách, lấy phần dư khi chia cho \(({10}^9 + 7)\).

Scoring

• Subtask 1 (\(15\%\) số điểm): \(N \leq 20\).
• Subtask 2 (\(15\%\) số điểm): \(N \leq 300\).
• Subtask 3 (\(25\%\) số điểm): \(N \leq 5000\).
• Subtask 4 (\(45\%\) số điểm): Không có ràng buộc gì thêm.

Example

1

1

2

3
2

3

7
4
3

Có một chú tiểu trong một ngôi chùa TLT nọ. Mỗi buổi chiều, chú có một công việc là gánh nước từ con suối gần nhất về để mọi người trong chùa sử dụng.

Cụ thể, chú tiểu cần gánh đầy \(N ~ (1 \leq N \leq 2\times{10}^5)\) gàu nước, gàu nước thứ \(i ~ (1 \leq i \leq N)\) có dung tích là \(A_i ~ (1 \leq A_i \leq {10}^9)\) lít nước. Mỗi lần đi gánh nước, chú tiểu đưa hết \(N\) gàu nước theo. Mọi hôm, chú sẽ múc lần lượt từng gàu nước và gánh hết về. Nhưng hôm nay chú muốn thử chơi một trò chơi thú vị như sau.

Chú tiểu sẽ bố trí các gàu nước sao cho khi gàu nước thứ \(i ~ (1 \leq i < N)\) đã đầy và được đổ thêm nước, số nước dư thừa sẽ được đổ sang gàu nước thứ \(i + 1\) (nếu gàu thứ \(i+1\) cũng đầy thì lượng nước thừa kia sẽ tự động được đổ sang gàu \(i+2\) nếu \(i+2\leq N\) và cứ thế ...). Nếu gàu nước thứ \(N\) đã đầy và được đổ thêm nước thì lượng nước thừa sẽ đổ xuống đất. Một gàu nước được gọi là đầy khi mà lượng nước nó chứa đã bằng dung tích.

Vốn là một người có võ công lợi hại, cậu có thể dùng tay hất nước vào cả \(N\) gàu nước cùng một lần, coi như mỗi giây cậu có thể hất một lít nước vào các gàu. Nhưng tất nhiên hắt nước cả \(N\) gàu một lần rất mất sức, nên cậu muốn chọn ít gàu nước nhất để hất nước vào sao cho cả \(N\) gàu nước đều đầy trong thời gian cho phép, vì đi quá lâu chú tiểu sẽ bị phạt.

Yêu cầu: Cho \(Q\) câu hỏi, câu hỏi thứ \(i\) là để đổ đầy cả \(N\) gàu nước trong thời gian không quá \(v_i\) giây thì phải chọn ít nhất bao nhiêu gàu nước để hất nước vào, nếu không tồn tại phương án thỏa mãn yêu cầu thì đưa ra \(-1\).

Input

• Dòng đầu tiên chứa một số nguyên dương \(N ~ (1 \leq N \leq 2\times{10}^5)\) là số gàu nước.

• Dòng thứ hai chứa \(N\) số nguyên dương, số thứ \(i ~ (1 \leq i \leq N)\) là \(A_i ~ (1 \leq A_i \leq {10}^9)\).

• Dòng thứ ba chứa một số nguyên dương \(Q ~ (1 \leq Q \leq \min(2\times{10}^5, 2N))\) là số câu hỏi.

• \(Q\) dòng tiếp theo, dòng thứ \(i ~ (1 \leq i \leq Q)\) chứa một số nguyên dương \(v_i ~ (1 \leq v_i \leq {10}^9)\) thể hiện câu hỏi thứ \(i\).

Output

• Gồm \(Q\) dòng, dòng thứ \(i ~ (1 \leq i \leq Q)\) chứa một số nguyên duy nhất là số gàu nước ít nhất mà chú tiểu cần liên tục đổ nước vào để cả \(N\) gàu nước đều đầy sau không quá \(v_i\) giây, hoặc đưa ra \(-1\) nếu không tồn tại cách đổ nước thỏa mãn yêu cầu.

Scoring

• Subtask 1 (\(10\%\) số điểm): \(N \leq 20, v_i \leq 1000\).
• Subtask 2 (\(15\%\) số điểm): \(N \leq 5000, v_i \leq 6000\).
• Subtask 3 (\(75\%\) số điểm): Không có ràng buộc gì thêm.

Example

5
4 1 5 4 1
3
5
3
4

3
-1
4