Champion Contest (Div 1)

bin9638 nổi tiếng là 1 người đẹp trai còn hơn cả Sơn Tùng, tài hoa, lãng tử, là ước mơ của biết bao cô gái. Không những chỉ đẹp trai mà anh còn rất thông minh. bin9638 có 1 sở thích là ra những bài toán. Hôm nay bin9638 thách đố mọi cô gái trong vùng giải 1 bài toán, nếu ai giải được sẽ làm vợ của bin9638. Lisa là 1 cô gái xinh đẹp, tài giỏi, sinh ra trong đại gia tộc “Blinkpack”, hơn nữa cô đã crush bin9638 từ lâu. Lần này là cơ hội tốt để làm vợ bin9638, mỗi tội thế mạnh của cô là nhảy hát chứ không phải giải toán nên Lisa muốn nhờ các bạn giải bài toán này hộ cô ấy.

Bài toán là cho 2 số tự nhiên \(l,r(l\leq r \leq10^{18})\), hãy đếm số lượng hình chữ nhật có 2 cạnh nằm trong khoảng từ \(l\) đến \(r\). 2 hình chữ nhật được tính là khác nhau nếu chiều rộng hoặc chiều dài của chúng khác nhau.

Vì kết quả có thể rất lớn nên hãy in ra phần dư khi chia cho \(10^9+7.\)

Yêu cầu: Hãy đếm số lượng hình chữ nhật thỏa mãn đề bài.

Input

• \(1\) dòng duy nhất lần lượt là 2 số \(l,r(l\leq r \leq10^{18})\).

Output

• \(1\) số duy nhất là kết quả bài toán.

Scoring

• Subtask \(1\) (\(50\%\) số điểm): \(l\leq r \leq10^6\).*
• Subtask \(2\) (\(50\%\) số điểm): không có ràng buộc gì thêm.*

Example

1 2

3

2 4

6

Hôm nay algorit và bin9638, \(2\) nam thần của làng K-pop đang đi chơi với nhau. May mắn thay họ gặp 1 cô em gái xinh đẹp tên là Jennie. Jennie vốn đã hâm mộ \(2\) người từ lâu nên đã đố họ \(1\) bài toán. Ai giải ra trươc là sẽ là người được đi chơi, hẹn hò với Jennie.

Bài toán là cho 1 dãy số nguyên dương \(A_1, A_2,…,A_n (n≤10^6, A_i≤10^9)\). 1 dãy con liên tiếp không rỗng của \(A\) được xem là dãy “ngu ngốc“ khi tổng phần tử của dãy con đó chia hết cho số nguyên dương \(k (1≤ k ≤10^6)\). Jennie đố algorit và bin9638 hãy tìm cách chia dãy \(A\) thành \(2\) dãy con “ngu ngốc” không giao nhau sao cho tổng độ dài \(2\) dãy là lớn nhất. bin9638 rất muốn được hẹn hò với Jennie nhưng vì mải ngắm nhìn nhan sắc tuyệt trần của cô nên anh không có tâm trí nào mà giải toán nữa. Bạn hãy giúp bin9638 nhé !

Yêu cầu:

• Hãy tìm tổng độ dài lớn nhất.

Input:

• Dòng đầu tiền lần lượt là \(n\) và \(k\), dòng thứ \(2\) là các số \(A_i\).

Output:

• \(1\) số duy nhất là kết quả, nếu không có cách chia thì in ra \(0\).

Scoring:

• Subtask \(1\) (\(50\%\) số điểm): có \(n≤10^4\).

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

Example:

3 2
1 2 3

0

4 2
1 2 3 4

4

Một hôm algorit và bin9638 đang đi chơi thì bị lạc vào một khu rừng tăm tối , đi được một hồi thì gặp người đàn ông , \(2\) người hỏi lối ra của khu rừng thì ông ta nói rằng nếu giải được bài toán này thì cả hai người đều được chỉ lối thoát , còn không thì một trong hai người phải ở lại . Vì tính đoàn kết nên hai người này nhất quyết phải thoát ra ngoài cùng nhau . Hãy giúp hai anh chàng này thoát ra khỏi khu rừng nhé !

Bài toán như sau : Cho một dãy số nguyên \(A\) gồm \(n\) phần tử và một số nguyên \(k\) , hãy chia dãy số thành các dãy con không giao nhau sao cho các dãy con có tổng bằng \(k\) là nhiều nhất .

Ví dụ : Dãy số là { 2 , 1 , 1 , 1 , 1 , 2 } và \(k =\) 4 ;
Chúng ta sẽ chia dãy thành {2,1,1} và {1,1,2} => có hai dãy con có tổng bằng k.

Yêu cầu : Hãy đưa ra số lượng dãy có tổng bằng \(k\) khi chia tối ưu.

Input

• Dòng thứ nhất gồm \(2\) số nguyên \(n\) và \(k\) (\(1 \leq |k| \leq\) \(10^{15}\))
• Dòng tiếp theo là dãy số (\(|A_i|\) \(\leq\) \(10^9\))

Output

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

Scoring

• Subtask \(1\) (\(20\%\) số điểm): \(n \leq\) \(10^2\) , \(|A_i| \leq 10^3\) .
• Subtask \(2\) (\(20\%\) số điểm): \(n \leq\) \(10^3\) , \(|A_i| \leq 10^6\) .
• Subtask \(3\) (\(60\%\) số điểm): \(n \leq\) \(10^6\) , \(|A_i| \leq 10^9\) .

Example

6 4
2 1 1 1 1 2

2

7 3
1 3 2 1 1 1 2

3

Hôm nay bin9638, người mạnh nhất dòng họ Joseph, đang có trận chiến với boss cuối Dio để giải cứu crush của anh là Jisoo, để đánh bại Dio thì bin9638 phải giải bài toán sau.
Bài toán là cho \(1\) dãy số nguyên dương \(A_1, A_2,….,A_n (A_i≤10^6, n≤10^5)\). Bộ chỉ số “The world” của dãy A là bộ các chỉ số \(i_1<i_2<i_3…<i_k\) \((2 ≤ k ≤ 10,i_j ≤ n)\) sao cho \(A_{i1}<A_{i2}, A_{i2}>A_{i3}, A_{i3}<A_{i4}, A_{i4}>A_{i5},….\) Cụ thể là \(A_{ij} < A_{ij+1}\) với \(j\) lẻ và ngược lại với \(j\) chẵn. bin9638 cần bạn giúp đếm tất cả bộ chỉ số “The world” của dãy \(A\), hai bộ chỉ số sẽ khác nhau nếu có 1 vị trí trong hai bộ có chỉ số khác nhau. bin9638 tuy rằng có stand mạnh nhất thế giới nhưng cậu ấy lại khá ngu toán. Hãy giúp cậu ấy nhé !

Vì kết quả có thể rất lớn nên hãy in ra phần dư khi chia cho \(10^9+7\).

Yêu cầu: đếm số lượng bộ chỉ số “The world” của dãy \(A\).

Input

• Dòng đầu tiên lần lượt là \(n, k\).

• Dòng tiếp theo là dãy \(A\).

Output

• 1 số duy nhất là kết quả.

Scoring

• Subtask \(1\) (\(40\%\) số điểm): \(k=2, n \le 1000\).

• Subtask \(2\) (\(60\%\) số điểm) không có ràng buộc gì thêm.

Example

4 3
1 2 1 5

1

Giới hạn:

• 40% test có \(k=2, n≤1000\).

• 60% test không có ràng buộc gì thêm.

Trong một lần tham gia chương trình "Ai thông minh hơn học sinh mẫu giáo", bin9638 và algorit cùng chơi trò rút bài với nhau, trò chơi có luật như sau:

-Bộ bài có các lá bài được xếp theo thứ tự, không quá \(400\) lá, mỗi lượt chơi mỗi người sẽ rút \(1\) lá bài ở \(2\) đầu bộ bài.

-Bộ bài gồm những lá sau:

• Lá bình thường, kí hiệu là "#".
• Lá cộng điểm , mỗi lần rút lá này người rút sẽ được cộng thêm số điểm nguyên \(x\) ghi trên lá bài (\(1 \leq x \leq9\)), được kí hiệu \("1","2",...,"9"\) ứng với số điểm trên lá.
• Lá chìa khóa, gồm các màu xanh, đỏ, tím, vàng dùng để mở các lá cửa cùng màu, được kí hiệu lần lượt là \(“G”, “R”, “P”, “Y”\). \(1\) lá chìa khóa có thể mở nhiều lá cửa cùng màu tương ứng.
• Lá cửa gồm các màu xanh, đỏ, tím, vàng; người bốc phải có lá chìa khóa cùng màu mới được bốc lá này. Kí hiệu lần lượt là \(“g”, “r”, “p”, “y”\).

-Trò chơi sẽ kết thúc khi có \(1\) người không thể rút bài nữa hoặc khi hết bài (nếu có thể rút được thì bắt buộc phải rút).

-Người chiến thắng sẽ là người có số điểm cao hơn.

Trong trò chơi này bin9638 là người bốc trước. Biết cả \(2\) người đều chơi tối ưu ( tối ưu ở đây là làm sao cho mình hơn điểm số đối phương nhiều nhất), hãy xác định xem ai là người chiến thắng nhé!

Yêu cầu: xác định xem ai là người chiến thắng.

Input

• Gồm \(1\) dòng duy nhất là xâu \(S\) biểu thị bộ bài \((|S|\leq400)\)

Output

• Gồm \(2\) dòng, dòng thứ nhất in ra “bin9638” nếu bin9638 thắng hoặc “algorit” nếu ngược lại, trường hợp cả \(2\) người hòa thì in ra \(“draw”\). Dòng thứ \(2\) in ra hiệu số điểm của \(2\) người khi kết thúc trò chơi (điểm bin9638 trừ điểm algorit)

Scoring

• Subtask \(1\) (\(40\%\) số điểm): \(|S|\leq20\).
• Subtask \(2\) (\(60\%\) số điểm): test không có ràng buộc gì thêm.

Example

#4##

bin9638
4

1g11g

bin9638
1

Gr#1#gR

algorit
-1

Gy9gg

draw
0

bin9638, người sẽ trở thành hokage vĩ đại nhất, vua hải tặc tương lai, kẻ thừa kế hơi thở mặt trời, mang trong mình sức mạnh của titan thủy tổ, người sở hữu dàn harem khủng nhất vũ trụ anime hiện đang có \(1\) kèo solo yasuo 20 ngày đêm với algorit. Sau \(1\) thời gian dài giao chiến nhưng vẫn chưa phân định thắng thua thì cả \(2\) quyết định phân biệt thắng thua bằng cách giải \(1\) bài toán.

Bài toán là cho \(1\) xâu \(S\) chỉ gồm các chữ cái latinh viết thường \(([S]\leq5000)\) và \(q\) truy vấn \((q\leq10^5)\), với mỗi truy vấn bạn phải trả lời xem đoạn \([l,r]\) của xâu \(S\) có bao nhiêu cặp xâu con bằng nhau. Xâu con của dãy \(S\) là \(1\) dãy kí tự liên tiếp không rỗng.

bin9638 sau cuộc chiến đã cạn hết sức lực nên đành nhờ các bạn giải giùm vậy. Hãy giúp bin9638 nhé !

Yêu cầu: hãy giải bài toán.

Input

• Dòng đầu là xâu \(S\), dòng thứ \(2\) là số \(q\).
• \(q\) dòng tiếp theo mỗi dòng là \(2\) số \(l,r\) \((1 \leq l \leq r \leq [S])\).

Output

• Gồm \(q\) dòng với mỗi dòng là đáp án cho truy vấn tương ứng.

Scoring

• Subtask \(1\) (\(30\%\) số điểm): \([S], q\leq100\).
• Subtask \(2\) (\(30\%\) số điểm): \([S], q\leq2000\).
• Subtask \(3\) (\(40\%\) số điểm): không có ràng buộc gì thêm.

Example

abcabc
2
1 4
1 6

1
6

aaa
1
1 3

4