\(Kaninho\) có \(n\) bóng đèn được xếp thành một hàng ngang và chúng được đánh số từ \(1\) đến \(n\). Ban đầu, tất cả các bóng đèn đều tắt và \(Kaninho\) có \(n\) thao tác thực hiện trên các bóng đèn như sau:
Hỏi sau khi thực hiện xong \(n\) thao tác, bóng đèn thứ \(n\) có trạng thái gì ? Nếu bóng đèn thứ \(n\) ở trạng thái bật ta in ra \(1\) ngược lại in ra \(0\)
Input:
Dòng thứ nhất chứa số \(t(1\le t\le 50)\) thể hiện số testcase
\(t\) dòng tiếp theo, mỗi dòng chứa số nguyên dương \(n(1\le n\le 10^5)\)
Output:
Ví dụ:
Input:
1
4
Output:
1
Giải thích:
Ban đầu ta có \(4\) bóng đèn ở trạng thái như sau: \(0,0,0,0\)
Sau phép toán thứ \(1\): \(1,1,1,1\)
Sau phép toán thứ \(2\): \(1,0,1,0\)
Sau phép toán thứ \(3\): \(1,0,0,0\)
Sau phép toán thứ \(4\): \(1,0,0,1\)
Do đó đáp án là \(1\)
Subtask:
\(37,5\text{%}\) : $1\le n\le 20 $
\(62,5\text{%}%\) : Không có điều kiện gì
Nhân dịp \(Henry\) qua nhà chơi, \(Kaninho\) đã rủ \(Henry\) chơi một trò chơi như sau:
Bắt đầu trò chơi, \(Kaninho\) sẽ có một số nguyên \(n\) \((1\le n \le 10^9)\) và \(Henry\) cũng có một số nguyên \(k\) \((1\le k\le n)\). Ở mỗi lượt, nếu \(n\) > 0, một người chơi có thể chọn một số nguyên \(x\) \((1\le x\le max(1,n-k))\) bất kì và gán \(n=n-x\). Người chơi nào không thể chơi được nữa thì được xem là thua cuộc.
Nếu \(Henry\) bắt đầu trước, và giả sử rằng, cả hai đều chơi một cách tối ưu, thì ai là người thắng cuộc ?
Dòng thứ nhất chứa số \(t(1\le t\le 10^4)\) - Thể hiện số lượng testcase
\(t\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(n,k(1\le k\le n\le 10^9)\)
Subtask \(1\) (\(37.5\%\) số điểm): \(1\le k\le n\le 50\).
Subtask \(2\) (\(62.5\%\) số điểm): không có điều kiện gì đặc biệt.
Test 1
2
2 1
4 1Kaninho
HenryTối đến, nhân trời trăng thanh gió mát, nhìn lên trời, \(Kaninho\) bỗng nảy ra một bài toán hay và muốn đố các bạn như sau:
Đặt \(M=a_1^{b_1}a_2^{b_2}...a_n^{b_n}\)
Yêu cầu: Tìm số nguyên dương \(x\) nhỏ nhất sao cho \(x!\) chia hết cho \(M\).
Dòng thứ nhất chứa số \(t\) \((1\le t\le 50)\) - Thể hiện số testcase
\(t\) test tiếp theo, mỗi test có dạng như sau:
Dòng đầu tiên chứa số \(n(1\le n\le 100)\)
\(n\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(a_i\), \(b_i\) \((1\le a_i\le 100,1\le b_i\le 10^{13})\)
Subtask \(1\) (\(37.5\%\) số điểm): \(1\le n\le 10 ; 1\le a_i\le 10; 1 \le b_i \le 5\)
Subtask \(2\) (\(62.5\%\) số điểm): không có ràng buộc nào thêm.
Test 1
1
2
3 2
4 16Sáng hôm nay, \(Kaninho\) được cô giáo khen vì đã làm được một bài toán hóc búa và để chia sẻ niềm vui này cho nhiều người, cậu ấy quyết định đăng bài toán này lên đây để mọi người cùng thử sức. Bài toán có đề bài như sau:
Kí hiệu \(u(n)\) là số nguyên nhỏ nhất có tổng các chữ số bằng \(n\).
Kí hiệu \(g(k)=\sum\limits_{n=1}^{k}u(n)\).
Gọi \(f_i\) là phần tử thứ \(i\) của dãy fibonacci, trong đó: \(f_0=0,f_1=1\) và \(f_{i}=f_{i-2}+f_{i-1}\) với mọi \(i\ge 2\)
Yêu cầu: Tính \(z(q)=\sum\limits_{i=2}^{q}g(f_i)\) với số \(q\) nguyên dương cho trước. Vì đáp án có thể lớn, nên ta cần mod \(10^9+7\) trước khi in ra.
Dòng thứ nhất chứa số \(t(1\le t\le 50)\) - Thể hiện số lượng testcase của bài toán
\(t\) dòng tiếp theo, mỗi dòng chứa số nguyên dương \(q(2\le q\le 90)\)
Subtask \(1\) (\(37,5\%\) số điểm): \(2\le q\le 10\)
Subtask \(2\) (\(62,5\%\) số điểm): Không có điều kiện gì
Test 1
2
2
31
4Hôm qua là bữa kiểm tra kiến thức tổng hợp để chuẩn bị đi thi HSG, vì nhận thấy \(Kaninho\) còn yếu về phần mảng, nên hôm nay bố của \(Kaninho\) quyết định ra một bài toán nhằm củng cố kiến thức cho Kaninho như sau:
Cho mảng \(a\) gồm \(n\) phần tử, và chỉ số của mảng bắt đầu từ \(1\).
Yêu cầu: Với mỗi phần tử \(i\) \((1\le i\le n)\) tìm phần tử \(a[j]\) thoả mãn:
\(1\) < \(i\) < \(j\le n\)
\(a[i]\) < \(a[j]\)
\(j\) - \(i\) là nhỏ nhất.
Nếu không tồn tại \(a[j]\) thoả mãn in ra \(-1\)
Dòng thứ nhất chứa số \(t\) \((1\le t\le 10)\) - Thể hiện số lượng testcase
\(t\) test tiếp theo, mỗi test có dạng như sau:
Dòng thứ nhất chứa số \(n\) \((1\le n\le 10^5)\)
Dòng thứ hai chứa \(n\) số nguyên \(a_i\) \((1\le a_i\le 50)\)
Subtask \(1\) (\(37.5\%\) số điểm): \(1\le n\le 20\).
Subtask \(2\) (\(62.5\%\) số điểm): không có điều kiện gì thêm.
Test 1
2
5
2 3 1 9 4
7
5 7 9 3 2 1 43 9 9 -1 -1
7 9 -1 4 4 4 -1 \(Kaninho\) được cho một xâu \(S\) chỉ gồm các kí tự latin thường, và nhiệm vụ của anh ấy là đếm xem có bao nhiêu xâu con (gồm những phần tử liên tiếp) thoả mãn số lần xuất hiện của mỗi kí tự trong xâu con đó không lớn hơn \(K\)
Dòng thứ nhất chứa số \(t(1\le t\le 100)\) - Thể hiện số testcase
\(t\) test tiếp theo, mỗi dòng chứa một test có dạng như sau:
Dòng thứ nhất chứa xâu \(S\) - Biết rằng, độ dài xâu \(S\) không vượt quá \(10^5\)
Dòng thứ hai chứa số \(K\) \((1\le K\le 10^5)\)
Subtask \(1\) (\(37.5\%\) số điểm): \(1\) \(\le\) |S| \(\le 20\) ,\(1\) \(\le\) \(K\) \(\le 5\).
Subtask \(2\) (\(62.5\%\) số điểm): không có điều kiện gì thêm.
Test 1
1
abc
16