Hexakill

Sau khi chơi chế độ Hexakill xong thì với bản năng của một dân competitive programming, Chuối hỏi rằng làm toán ở hệ cơ số khác thì như thế nào. Chuối giao cho bạn hai số ở hệ cơ số B( B = 16) là X, Y và nhờ bạn giúp Chuối làm những phép toán sau: 1. Tính tích các số từ X đến Y kể cả X và Y. 2. Tính S = tổng các chữ số trong kết quả nhận được. 3. Chừng nào S chưa nhỏ hơn B thì thực hiện lại việc tính tổng các chữ số của S. 4. Đưa ra S.

Input

• Dòng 1 chứa X
• Dòng 2 chứa Y
• X và Y chỉ chứa các kí tự từ '0'-'9', 'a'-'f' và 'A'-'F', ~( 1 \leq len(X), len(Y) \leq 10^{5} )~

Kết quả

• Đưa ra kết quả, nếu kết quả lớn hơn 9 đưa ra dưới dạng ký tự hoa.

Test

• 40d : ~( 1 \leq len(X), len(y) \leq 100 )~
• 60d : ~( 1 \leq len(X), len(y) \leq 10^{5} )~

Sample input 1

1Ba
1Bd

Sample output 1

F

Nguồn đề: HackerEarth https://www.hackerearth.com/problem/algorithm/abcd-strings/description/

Đếm số xâu có độ dài là N, chỉ chứa các kí tự 'a', 'b', 'c', 'd' và không chứa các xâu đặc biệt.

Đáp án có thể rất lớn, hãy chia dư cho 1000000007.

Input

• Dòng đầu tiên chứa T, số testcase. ~( 1 \leq T \leq 200 )~
• Dòng thứ 2 chứa N độ dài của xâu, K số lượng các xâu đặc biệt ~( 1 \leq N \leq 10^{15}, 1 \leq K \leq 50 )~ .
• K dòng tiếp theo mỗi dòng chữa một xâu đặc biệt S. ~( 1 \leq len(S) \leq 3,~ S cũng chỉ chứa các kí tự 'a', 'b', 'c', 'd' )

Output

• Với mỗi testcase, In ra kết quả cần tìm.

Test

• 20đ : ~( 1 \leq N \le 10 )~
• 80đ : ~( 1 \leq N \leq 10^{15} )~

Sample input 1

5
4 8
cac
dbb
abb
ddd
dad
aaa
dbb
cad
3 1
aca
2 7
abb
aac
aab
dcc
bbc
caa
cba
1 4
cbb
ddd
ccb
cdc
5 5
aad
bda
aac
ddb
bdc

Sample output 1

202
63
16
4
789

Fix the palind

Nguồn đề : https://atcoder.jp/contests/abc147/tasks/abc147_b

Hải rất thích các xâu Palindrome. Là một người cầu toàn Hải rất ghét phải thấy các xâu không phải là xâu Palindrome, do vậy Hải đã luyện thành công kĩ năng có thể sửa được 1 kí tự trong một xâu thành một kí tự bất kì khác chỉ với 1 lon cà phê.

Cho một xâu S. Hãy giúp Hải biết số lượng lon cà phê ít nhất để Hải có thể sửa xâu S thành một xâu Palindrome.

Input

• Xâu S ( ~1 \leq len(S) \leq 100~, xâu S chỉ chứa các kí tự chữ thường ('a'->'z').

Output

• Số lượng lon cà phê ít nhất để Hải có thể sửa xâu S thành một xâu Palindrome

Sample input 1

redcoder

Sample output 1

1

Sample input 2

abcdabc

Sample output 2

2

D Range

Nguồn đề : https://codeforces.com/contest/1379/problem/B

Phương muốn gửi một số n nguyên dương khác không cho bạn. Nhưng máy nhắn tin của Phương sử dụng giao thức HTTPFake, lo tin nhắn bị lộ, Phương mã hóa số n như sau, Phương chọn 3 số nguyên ~ l \leq a, b, c \leq r~ và máy gửi m = n*a + b - c. Thật không may một tin tặc đã chặn các giá a, b, c chỉ còn lại l, r, m.

Tóm lại, bạn cần tìm 3 giá trị a, b, c sao cho:

• a, b, c là số nguyên.
• ~ l \leq a, b, c \leq r~.
• Tồn tại một số n nguyên dương khác không sao cho m = n*a + b - c.
• Có thể có nhiều giá trị a, b và c thỏa mãn, bạn cần chọn theo thứ tự ưu tiên như sau.
  1. a bé nhất có thể.
  2. Min(b,c) bé nhất có thể.
  3. b bé nhất có thể.
  4. c bé nhất có thể.

Input

• Dòng đầu tiên chứa một số nguyên t, số lượng test ~( 1 \leq t \leq 20 )~.
• t dòng tiếp theo mỗi dòng chứa 3 số nguyên l, r và m ~( 1 \leq l, r \leq 500000, 1 \leq m \leq 10^{10} )~.

Output

• Với mỗi test case in ra ba số nguyên a, b, c thỏa mãn.

Test

• 10đ : ~( 1 \leq l, r, m \leq 1000 )~.
• 90đ : ~( 1 \leq l, r \leq 500000, 1 \leq m \leq 10^{10} )~.

Sample input 1

2
4 6 13
2 3 1

Sample output 1

4 5 4
2 2 3

Far away

Nguồn đề : https://atcoder.jp/contests/dp/tasks/dp_g

Cho một đồ thị có hướng với N đỉnh và M cạnh, đồ thị không chứa chu trình (cycles). Tìm độ dài của đường đi dài nhất trong đồ thị. Độ dài của một đường đi là số cạnh trên đường.

Hãy tìm độ dài của đoạn đường dài nhất.

Input

• Dòng đầu tiên chứa N, M ~( 2 \leq N \leq 10^5, 1 \leq M \leq 10^5 )~
• M dòng tiếp theo mỗi dòng chứa 2 số nguyên u, v thể hiện 1 cạnh đi từ u đến v ~( 1 \leq u,v \leq N )~.
• Mọi cặp u, v là duy nhất.

Output

• Độ dài của đoạn đường dài nhất.

Test

• 50đ : ~( 2 \leq N \leq 100, 1 \leq M \leq 100 )~
• 50đ : ~( 2 \leq N \leq 10^5, 1 \leq M \leq 10^5 )~

Sample Input 1

4 5
1 2
1 3
3 2
2 4
3 4

Sample Output 1

3

Sample Input 2

6 3
2 3
4 5
5 6

Sample Output 2

2