Mô tả đề bài

Cho 2 bức ảnh cùng kích thước được biểu diễn dưới dạng ma trận 1 chiều, với mỗi điểm ảnh được biểu diễn bởi mã màu Hex. Màu Hex là cách thể hiện màu thông qua các giá trị thập lục phân và theo định dạng #RRGGBB, trong đó RR là màu đỏ, GG là màu xanh lá và BB là màu xanh lam. Các số nguyên thập lục phân này có thể nằm trong phạm vi từ 00 đến FF để chỉ định cường độ của màu.

Một phép biến đổi được áp dụng để tăng cường độ mỗi màu lên ~delta~ = (~x, y, z~), với ~x, y, z~ là có số nguyên dương nhỏ nhất có thể biến đổi từ điểm ảnh ở bức ảnh 1 sáng điểm ảnh ở bức ảnh 2 tương ứng có giá trị màu đỏ, màu xanh lá và màu xanh lam lần lượt là (RR + ~x~) % 256, (GG + ~y~) % 256 và (BB + ~z~) % 256.

Nga muốn viết một chương trình kiểm tra độ tương đồng của 2 bức ảnh bằng cách tính phần trăm số lượng điểm ảnh nhiều nhất có cùng mức độ tăng cường ~delta~. Hãy giúp Nga tính giá trị này nhé.

Input format

• Dòng đầu là một số nguyên dương ~n~ (~1 \le n \le 10^5~) thể hiện số lượng điểm ảnh.
• ~n~ dòng sau mỗi dòng gồm 1 chuỗi có dạng mã màu Hex của bức ảnh 1, ~n~ dòng tiếp theo mỗi dòng gồm 1 chuỗi có dạng mã màu Hex của bức ảnh 2 (dữ liệu luôn đảm bảo đúng định dạng mã màu Hex đã cho và chỉ gồm các ký tự số và ký tự in hoa).

Output format

Gồm 1 dòng duy nhất là độ tương đồng của 2 bức ảnh làm tròn đến 2 chữ số thập phân.

Sample Input

5
#0E217A
#9A8456
#C0BA06
#0FA5D4
#870191
#0E217F
#9A845A
#C0BA0A
#0FA5D6
#880197

Sample Output

40.00%

Giải thích ví dụ

Như vậy ~delta~ = (0,0,4) xuất hiện nhiều nhất nên được chọn để tính mức độ tương đồng ~2 \div 5 \times 100~ = 40%

Mô tả đề bài

Cho một sàn nhà hình chữ nhật kích thước ~n \times m~. Hãy tính số lượng gạch lục giác cần dùng để lát sao cho cạnh của viên gạch phải nằm song song với cạnh của sàn nhà như một trong 2 hình dưới.

Input format

• Dòng đầu là một số nguyên không âm ~t~ (~1 \le t \le 1000~) thể hiện số testcase.
• Ứng với mỗi test case là bộ 3 số nguyên không âm ~n~, ~m~ và ~x~ với ~1 \le x \le n, m \le 10^9~ với ~n~, ~m~ là kích thước sàn nhà và ~x~ là độ dài một cạnh của viên gạch

Output format

Gồm ~t~ dòng, mỗi dòng là số lượng viên gạch ít nhất được dùng.

Sample Input

2
3 3 2
10 8 2

Sample Output

3
10

Giải thích ví dụ

Testcase 1

Testcase 2

Mô tả đề bài

Trò chơi đẩy bi là một trò chơi trên lưới ô vuông vô hạn. Các dòng và cột của lưới được đánh số theo thứ tự bởi các số nguyên … -3 -2 -1 0 1 2 3 … Các cột được đánh số theo thứ tự từ trái sang phải, còn các dòng theo thứ tự từ dưới lên trên. Ô nằm trên giao của dòng ~x~ và cột ~y~ được gọi là ô ~(x, y)~. Trên lưới có một số ô cấm, các ô còn lại là tự do. Khi bắt đầu trò chơi, một số viên bi sẽ xuất hiện trên lưới, mỗi viên bi sẽ nằm gọn trong một ô và không có ô nào chứa nhiều hơn một viên bi. Người chơi sẽ phải chọn một ô tự do trên lưới để làm cái hố, nếu ô được chọn làm cái hố có chứa bi thì viên bi đó sẽ biến mất. Ở mỗi bước, người chơi có thể chọn một ô chứa bi và đẩy viên bi đó sang một trong bốn ô chung cạnh (hiện đang không có bi), nếu viên bi bị đẩy vào cái hố thì viên bi này sẽ biến mất. Nhiệm vụ của người chơi là đẩy hết tất cả các viên bi trên lưới vào cái hố với số bước ít nhất. Yêu cầu: Cho biết vị trí các ô cấm trên lưới và vị trí các ô có chứa bi. Hãy chọn một ô tự do làm cái hố và tìm cách đẩy tất cả các viên bi trên lưới vào cái hố với số bước ít nhất.

Input format

• Dòng thứ nhất ghi số nguyên dương ~n~ là số ô cấm.
• Dòng thứ ~i (i = 1, 2, …, n)~ trong ~n~ dòng tiếp theo, mỗi dòng chứa hai số nguyên ~x_i, y_i~ mô tả ô ~(x_i, y_i)~ là ô cấm.
• Dòng tiếp theo ghi số nguyên dương ~m~ là số ô chứa bi.
• Dòng thứ ~j (j = 1, 2, …, m)~ trong ~m~ dòng tiếp theo, mỗi dòng chứa hai số nguyên ~u_j, v_j~ mô tả ô ~(u_j, v_j)~ là ô chứa bi.

Output format

In ra một số nguyên là số bước ít nhất cần thiết để đẩy tất cả các viên bi trên lưới vào cái hố. In ra ~-1~ nếu không tồn tại cách chọn cái hố để đẩy hết tất cả các viên bi trên lưới vào hố.

Sample Input 1

1
2 2
2
1 2
3 2

Sample Output 1

4

Sample Input 2

0
2
1 1
5 5

Sample Output 2

8

Subtasks

• Có ~15\%~ số lượng test thỏa mãn điều kiện: ~n = 0, m = 2~ và các số ~u_j, v_j~ là số nguyên dương không vượt quá ~100~;
• Có ~15\%~ số lượng test khác thỏa mãn điều kiện: ~n = 1, m = 2~ và các số ~x_i, y_i, u_j, v_j~ là số nguyên dương không vượt quá ~100~;
• Có ~20\%~ số lượng test khác thỏa mãn điều kiện: ~n = 0, m \leq 100~ và các số ~x_i, y_i, u_j, v_j~ là số nguyên dương không vượt quá ~100~;
• Có ~20\%~ số lượng test khác thỏa mãn điều kiện: ~n \leq 1000, m \leq 100~ và các số ~x_i, y_i, u_j, v_j~ là số nguyên dương không vượt quá ~100~;
• Có ~30\%~ số lượng test còn lại thỏa mãn điều kiện: ~n = 0, m \leq 100~ và các số ~u_j, v_j~ là số nguyên dương không vượt quá ~10^9~;

Mô tả đề bài

Trên dãy số nguyên ~a_1, a_2,..., a_n~ và với hai số nguyên, ~w_1, w_2~ ta định nghĩa một bộ năm chỉ số ~i_1, i_2, i_3, i_4, i_5~ sao cho: ~1 \leq i_1 < i_2 < i_3 < i_4 < i_5 \leq n~ được gọi là một bộ năm và có trọng số được tính bằng: $$ (w_1 \times a_{i_1}) + (w_2 \times a_{i_2}) + a_{i_3} + (w_2 \times a_{i_4}) + (w_1 \times a_{i_5}) $$ Ví dụ, trên dãy gồm ~7~ số nguyên ~2, 8, 1, 9, 1, -1, 8~ và ~w_1 = 1, w_2 = -1~ thì bộ năm chỉ số ~2, 3, 4, 6, 7~ là một bộ năm và có trọng số bằng: ~(1 \times 8) + (-1 \times 1) + 9 + (-1 \times -1) + (1 \times 8) = 25~, đây cũng là bộ năm có trọng số lớn nhất trong tất cả các bộ năm.

Yêu cầu: Cho dãy số nguyên ~a_1, a_2,..., a_n~ và hai số nguyên ~w_1, w_2~. Hãy tìm bộ năm có trọng số lớn nhất.

Input format

• Dòng đầu chứa ba số nguyên ~n, w_1, w_2~ ~(n \geq 5, |w_1|, |w_2| \leq 100)~.
• Dòng thứ hai chứa ~n~ số nguyên ~a_1, a_2,..., a_n~ ~(a_i \leq 10^9~ với ~i = 1,...,n)~.

Output format

Một số nguyên là trọng số của bộ năm lớn nhất tìm được.

Sample Input 1

7 0 0
2 8 1 9 1 -1 8

Sample Output 1

9

Sample Input 2

7 1 -1
2 8 1 9 1 -1 8

Sample Output 2

25

Subtasks

• Có ~20\%~ số lượng test thỏa mãn điều kiện: ~n \leq 100~;
• Có thêm ~20\%~ số lượng test khác thỏa mãn điều kiện: ~n \leq 10^5, w_1 = w_2 = 0~;
• Có thêm ~20\%~ số lượng test khác thỏa mãn điều kiện: ~n \leq 5000, w_1 = 0, w_2 < 0~;
• Có thêm ~20\%~ số lượng test khác thỏa mãn điều kiện: ~n \leq 10^5, w_1 = 0, w_2 < 0~;
• Có ~20\%~ số lượng test còn lại thỏa mãn điều kiện: ~n \leq 10^5~.

Mô tả đề bài

Alice và Bob là 1 cặp đôi yêu xa bởi Alice phải làm việc ở trong 1 khu rừng bí ẩn cách biệt với thành phố nơi mà Bob đang sinh sống. Hằng ngày Alice đều muốn gửi tới Bob những dòng tin nhắn đầy yêu thương, nhưng máy gửi tin của Alice đã bị hỏng do ngày ngày tháng tháng ở trong rừng, nhiều vi mạch đã bị chạm vì ẩm ướt. May thay, không phải máy truyền tin của Alice hoàn toàn không truyền tin được mà nó chỉ bị nhiễu trong quá trình truyền tín hiệu. Cơ chế của máy gửi tin mà Alice có là như sau:

• Khi Alice muốn gửi 1 từ là 1 chuỗi ký tự Alphabet thì Alice phải tự mình mã hóa chúng thành 1 chuỗi nhị phân gồm ~n~ chữ số 0 hoặc 1 rồi gửi cho máy gửi tin để phát sóng, biết máy gửi tin này có đúng n vị trí phát sóng.
• Máy gửi tin nhận được chuỗi ký tự nhị phân, nguyên tắc nếu không bị hỏng thì sẽ gửi tín hiệu đúng chuỗi nhị phân đó cho Bob. Tuy nhiên, vì máy gửi tin của Alice bị chạm nên một số bít trong chuỗi nhị phân sẽ không truyền được và mặc định sẽ truyền ký tự chữ số 0, cho dù bít đó thể là 0 hay là 1. Đương nhiên là Alice biết được vị trí bít bị trục trặc của máy truyền tin của mình trước khi truyền tin bằng một số cách thức nào đó.
• Sau khi gửi xong 1 chuỗi ký tự nào đó, vị trí bít bị trục trặc của máy gửi tin có thể bị thay đổi khi truyền chuỗi ký tự tiếp theo.

Bob, thì đương nhiên ở thành phố nên máy nhận tin của Bob sẽ không hề bị trục trặc như máy gửi tin của Alice. Vấn đề được đặt ra là khi nhận tin, Bob cần 1 đoạn code giải mã một cách hoàn hảo dòng tin nhắn của Alice cho dù các tín hiệu nhận được có bị thay đổi do máy gửi tin của Alice hay không. Vì thế Alice và Bob cần bạn mách bảo giúp cách thức mã hóa cho Alice và đoạn code giải mã cho Bob để họ có thể liên lạc với nhau 1 cách thuận tiện nhất. Yêu cầu, đoạn code giải mã phải được viết bằng Python không quá 1000 ký tự, không sử dụng bất kỳ thư viện nào và phải giải mã chính xác được tất cả các chuỗi ký tự mà Alice muốn gửi. Hãy giúp họ nhé!

Input format

• Dòng đầu là hai số nguyên ~m \; (1 \leq m \leq 1000)~ và ~n \; (1 \leq n \leq 200)~ lần lượt thể hiện số lượng chuỗi ký tự mà Alice muốn gửi và, số lượng vị trí phát sóng hay chiều dài chuỗi nhị phân mà Alice mã hóa.

• ~2 \times m~ dòng tiếp theo là các thông tin lúc Alice gửi các chuỗi ký tự alphabet, cụ thể như sau:

  • Dòng thứ ~2 \times i~ là chuỗi alphabet thứ ~i~ mà Alice muốn gửi. Chuỗi này có thể viết hoa hoặc viết thường, mỗi chuỗi không quá 10 ký tự.
  • Dòng thứ ~2 \times i + 1~ gồm các số nguyên dương thể hiện số lượng và vị trí bít bị trục trặc trong máy phát khi gửi chuỗi ký tự thứ ~i~. Số nguyên đầu tiên ~k_i~ là số lượng bít bị trục trặc, ~k_i~ số nguyên tiếp theo là các vị trí trục trặc ~x_{i,j}~. Biết, ~0 \leq k_i \leq n, \; 0 \leq k_i \leq 70~ và ~1 \leq x_{i,j} < x_{i, j+1} \leq n,\; 1 \leq j \leq k_i~.

    Ràng buộc

• Có 20% số testcase thỏa mãn với mọi ~k_i = 1~ và ~n = 120~.

• Có 20% số testcase thỏa mãn với mọi ~k_i \leq 2,\; n \geq 175~.
• Có 30% số testcase thỏa mãn với mọi ~2 < k_i \leq 40,\; n = 200~.
• Có 30% số testcase còn lại luôn thỏa mãn ~3 \times (k_i + 58) \leq 2 \times n~.

Output format

• ~m~ dòng đầu là các chuỗi nhị phân mà Alice mã hóa được từ các ký tự muốn gửi. Lưu ý, chuỗi nhị phân này có thể bị thay đổi như trong đề bài khi Bob nhận được.
• Các dòng tiếp theo là đoạn code giải mã dành cho Bob. Đoạn code này phải chứa hàm với tên là GiaiMa(x) được định nghĩa bởi ngôn ngữ lập trình Python với định dạng như sau, biết x là chuỗi nhị phân mà Bob nhận được và giá trị trả về là chuỗi ký tự sau khi giải mã

def GiaiMa(x):
    ...
  return ...

Biết ký tự tab có thể được thể hiện bằng 2 dấu cách.

Sample Input

3 120
I
0
Love
1 1
You
1 26

Sample Output

010001100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
010011000111101011000010100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
011001100111101010100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000

def binToChar(binary):
    sum = 0
    for b in binary:
        sum = sum * 2 + ord(b) - ord('0')
    if sum == 0:
        return ''
    if sum <= 26:
        return chr(ord('a')+sum-1)
    if sum <= 52:
        return chr(ord('A')+sum-27)
def GiaiMa(x):
    i = 1
    s = ""
    while i <= len(x) - 6:
        s = s + str(binToChar(x[i:i+6]))
        i += 6
    return s

Giải thích ví dụ

Để ý trong testcase ví dụ, ta thấy trong tất cả quá trình gửi tín hiệu, chỉ có vị trí bít thứ 1 và bít thứ 26 bị trục trặc, vì thế Alice chỉ cần không sử dụng 2 bít đó để truyền thông tin là được. Vì số lượng chữ cái viết hoa và viết thường tối đa chỉ là 52 nên Alice chỉ cần sử dụng 6 bít để mã hóa cho mỗi ký tự:

• a: 000001
• ...
• z: 011010
• A: 011011
• ...
• Z: 110100

Đoạn code giải mã dựa vào cách thức mã hóa trên để giải mã.

Lưu ý, đoạn mã trong ví dụ chỉ giải quyết được đối với trường hợp đặc biệt của ví dụ này, nó không giải quyết được cho tất cả trường hợp của bài toán.