LQDOJ AoZ Contest #1

ABNL đang trong hành trình leo rank Thách đấu LQDOJ Arena (thể thức solo code 1vs1 ở một vũ trụ nào đó). Trước khi "xuất khẩu lao động" sang Úc, anh ấy quyết tâm đạt được rank Thách đấu, bất chấp được bạn thân rủ đi chơi đêm Noel. Hiện tại, ABNL đã thắng được \(W\) trận và thua \(L\) trận. Để leo rank thành công, anh ấy cần đạt tỉ lệ thắng ít nhất \(X\%\) (tức là \(\frac{W}{W + L} \geq \frac{X}{100}\)).

Với quyết tâm cao độ, ABNL tin rằng mình sẽ thắng tất cả các trận đấu tối nay. Hãy giúp anh ấy tính số trận đấu tối thiểu cần thắng thêm để đạt được tỉ lệ thắng mong muốn.

Input

• Một dòng chứa ba số nguyên dương \(W\), \(L\), \(X\) \((1 \leq W, L \leq 10^9, 1 \leq X \leq 99)\) lần lượt là số trận thắng, số trận thua hiện tại và tỉ lệ thắng cần đạt (tính theo phần trăm).

Output

• In ra một số nguyên duy nhất là số trận ít nhất cần thắng thêm để đạt được tỉ lệ thắng mong muốn.

Example

3 2 75

3

2 4 20

0

Giáng Sinh sắp đến gần, trưởng thôn Minh quyết định chuẩn bị tổ chức một buổi tặng quà đặc biệt cho \(N\) bạn coder trong thôn. Các bạn sẽ ngồi thành một vòng tròn để nhận quà từ trưởng thôn Minh. Tuy nhiên, Minh muốn đảm bảo rằng không có hai bạn ngồi cạnh nhau nhận được cùng một món quà giống nhau, để tránh các bạn ganh tị hoặc chia sẻ quà.

Ban đầu, trưởng thôn Minh chuẩn bị \(N\) món quà khác nhau được đánh dấu bằng các chữ cái từ \(A, B, C, D, \ldots\) Minh nhận ra rằng với \(N\) bạn coder và \(N\) loại quà khác nhau, mỗi bạn coder không chỉ có thể nhận một món quà mà còn có thể nhận nhiều món quà, miễn là tất cả các quy tắc sau đây được đảm bảo:

• Mỗi bạn coder đều nhận được số lượng quà giống nhau.
• Mỗi món quà xuất hiện với số lần bằng nhau.
• Không có hai bạn coder ngồi cạnh nhau nhận được cùng một món quà giống nhau.
• Có \(N\) loại quà khác nhau có thể dùng, được đánh dấu bởi \(N\) chữ cái in hoa đầu tiên từ \(A\) đến \(Z\)
• Mỗi bạn coder có thể nhận tối đa 1 món quà cho mỗi loại quà từ \(1\) đến \(N\)

Với tư cách là trợ lý trưởng thôn, bạn hãy giúp trưởng thôn Minh tìm ra số lượng quà tối đa mà mỗi bạn coder có thể nhận, đồng thời đưa ra cách phân phối quà để đảm bảo các quy tắc trên.

Input

• Dữ liệu vào gồm một dòng duy nhất chứa số nguyên \(N\) \((1 \leq N \leq 26)\) là số lượng bạn coder (cũng là số lượng món quà ban đầu).

Output

• Dòng đầu tiên in ra một số nguyên \(1 \leq M \leq N\), là số lượng quà tối đa mà mỗi bạn có thể nhận.
• In ra \(N\) dòng tiếp theo, mỗi dòng chứa \(M\) chữ cái viết hoa, biểu thị các món quà mà bạn nhỏ thứ \(i\) nhận được. Mỗi chữ cái phải nằm trong \(N\) chữ cái viết hoa đầu tiên trong bảng chữ cái từ \(A\) đến \(Z\). Đảm bảo các món quà được phân phối thỏa mãn cả ba quy tắc. Nếu có nhiều cách in thỏa mãn, in ra một cách bất kì.

Example

1

1
A

2

1
B
A

4

2
DA
BC
AD
CB

Sau khi leo rank Thách đấu thành công trong LQDOJ Arena, ABNL đã quyết định dành một đêm Giáng Sinh thật đặc biệt. Anh rủ AKA và trưởng thôn Minh đi dạo phố để tận hưởng không khí Noel.

AKA là một người rất yêu thích mọi thứ đối xứng, giống như cái tên của anh ấy. Trưởng thôn Minh cũng rất thích đối xứng, bởi vì Minh thích mọi điều bắt đầu bằng chữ M, chẳng hạn như Man Utd, Mordekaiser, Manbo, và đặc biệt chữ cái M cũng mang tính đối xứng. Để tặng món quà trước khi qua Úc, ABNL quyết định tạo ra một món quà đặc biệt mang tính đối xứng từ những quả cầu tuyết trên phố.

Dọc theo con đường, có rất nhiều quả cầu tuyết với kích thước \(a_i\). ABNL muốn gom chúng lại để tạo thành một dãy đối xứng hoàn hảo. Trong một lần gộp, ABNL có thể chọn hai quả cầu tuyết liền kề và gộp chúng lại thành một quả cầu mới, với kích thước bằng tổng kích thước của hai quả cầu ban đầu.

Vì số quả cầu quá nhiều, hãy giúp ABNL tính số lần gộp tối thiểu cần thiết để biến dãy ban đầu thành một dãy đối xứng.

Input

• Một dòng chứa một số nguyên dương \(N\) \((1 \leq N \leq 10^3)\) là số lượng quả cầu tuyết.
• Dòng thứ hai chứa \(N\) số nguyên \(a_i\) \((1 \leq a_i \leq 10^6)\), là kích thước của các quả cầu tuyết.

Output

• In ra một số nguyên duy nhất là số lần gộp tối thiểu cần thực hiện để biến dãy cầu tuyết thành một dãy đối xứng.

Example

5
3 10 6 4 3

1

3
2 1 4

2

Vào dịp Giáng Sinh, Phúc quyết định đi làm thêm để giao quà cho các em nhỏ. Vì phải giao hàng bằng xe đạp, Phúc chỉ có thể mang tối đa một món quà mỗi lần. Do đó, cậu phải liên tục di chuyển từ điểm tập kết quà đến các vị trí giao quà khác nhau.

Hãy tưởng tượng thành phố nơi Phúc sống được mô phỏng như một lưới tọa độ 2D. Có \(N\) món quà cần được giao, mỗi món nằm tại tọa độ nguyên \((x, y)\) trên lưới. Ngoài ra, điểm tập kết - nơi Phúc cất giữ các món quà trước khi giao - cũng nằm tại một tọa độ cụ thể trên lưới. Lưu ý, điểm tập kết và vị trí giao hàng có thể trùng nhau.

Phúc bắt đầu hành trình từ điểm tập kết. Mỗi giây, cậu có thể di chuyển một ô theo hướng lên, xuống, trái hoặc phải. Khi đến một vị trí giao quà, Phúc sẽ giao món quà ngay lập tức, sau đó phải quay lại điểm tập kết để lấy món quà tiếp theo. Quá trình này lặp lại cho đến khi tất cả các món quà được giao xong.

Hiện tại, Phúc đang xem xét nhiều vị trí khác nhau để đặt điểm tập kết. Vì vậy, với mỗi vị trí tập kết được đề xuất, hãy tính thời gian tối thiểu cần thiết để Phúc giao hết tất cả món quà và trở về điểm tập kết, giả sử cậu làm việc nhanh nhất có thể.

Input

• Dòng 1: số nguyên dương \(N (1 \leq N \leq 10^5)\) - số lượng món quà
• \(N\) dòng tiếp theo: mỗi dòng chứa hai số nguyên \(x_i, y_i (1 \leq x_i, y_i \leq 10^5)\) - tọa độ điểm giao quà thứ \(i\)
• Dòng tiếp: số nguyên dương \(Q (1 \leq Q \leq 10^5)\) - số lượng truy vấn
• \(Q\) dòng cuối: mỗi dòng chứa hai số nguyên \(x_j, y_j (1 \leq x_j, y_j \leq 10^5)\) - tọa độ của một vị trí tập kết được xem xét

Output

• \(Q\) dòng: mỗi dòng là thời gian tối thiểu (tính bằng giây) để giao hết tất cả các món quà với vị trí tập kết tương ứng

Example

2
2 2
1 1
3
1 2
1 1
3 3

4
4
12

Sau khi hoàn thành việc xây dựng một dãy cầu tuyết đối xứng tuyệt đẹp, ABNL quyết định tiếp tục sáng tạo với tuyết. Lần này, anh ấy muốn xây dựng một lâu đài tuyết hoành tráng trên một khoảng đất trống. Khu vực đất trống này được chia thành \(N\) ô vuông, ban đầu toàn bộ đều có độ cao là \(0\).

ABNL đã nghĩ ra một thiết kế hoàn hảo cho lâu đài này: một dãy số \(a\) biểu thị chiều cao của từng ô trong lâu đài. ABNL tin rằng nếu mỗi ô đạt đúng chiều cao tương ứng trong dãy \(a\), lâu đài sẽ trở thành tác phẩm tuyết đẹp nhất thế giới từng xây dựng.

Vì không có đủ dụng cụ xây dựng phức tạp, ABNL chỉ có thể sử dụng một xẻng tuyết. Mỗi lần sử dụng xẻng, anh ấy có thể xúc tuyết và rải vào đúng \(K\) ô liên tiếp (có thể rải tràn ra ngoài khu vực nếu cần). Mỗi lần xúc và rải, độ cao của mỗi ô trong \(K\) ô liên tiếp sẽ tăng thêm \(1\) đơn vị.

ABNL đang bận xúc tuyết, do đó hãy giúp ABNL tìm ra cách xây dựng lâu đài với số lần tối thiểu cần sử dụng xẻng tuyết để đạt được chiều cao theo yêu cầu của dãy \(a\). Nếu không thể xây lâu đài với yêu cầu này, hãy báo cho ABNL rằng điều đó là không thể.

Input

• Dòng đầu tiên chứa hai số nguyên \(N\) và \(K\) \((1 \leq K \leq N \leq 2×10^5)\): số ô đất và chiều dài tối đa mà xẻng tuyết có thể rải trong một lần.
• Dòng thứ hai chứa N số nguyên \(a[1], a[2], ..., a[N]\) \((1 \leq a[i] \leq 10^9)\): chiều cao mong muốn của từng ô để hoàn thiện lâu đài.

Output

• In ra số lần tối thiểu cần sử dụng xẻng tuyết nếu có thể xây dựng lâu đài.
• In ra \(-1\) nếu không thể.

Example

5 3
1 1 1 1 2

3

5 3
1 2 3 2 1

3

3 2
1 3 1

-1

5 3
1 1 0 1 1

2

Sau một ngày Giáng Sinh đầy niềm vui với những trò chơi và thử thách thú vị, ABNL muốn kết lại ngày lễ bằng một hoạt động thật đặc biệt: trượt tuyết. Sau một hồi tìm kiếm, ABNL đã phát hiện ra một sân trượt tuyết tuyệt đẹp – một mạng lưới \(N \times N\) được phủ đầy tuyết trắng. Nhưng chơi một mình không vui, ABNL quyết định rủ tất cả coder đến trượt tuyết cùng.

Sân trượt tuyết này có cấu trúc thú vị:

• Các ô tuyết bình thường là khoảng trống, được ký hiệu là .
• Một số ô đặc biệt được gọi là nền trượt tuyết (ký hiệu P), nơi các coder có thể đứng và bắt đầu cuộc hành trình lướt đi trên mặt tuyết.

ABNL đề xuất một luật chơi: mỗi người chơi sẽ chọn một nền trượt tuyết làm điểm xuất phát, và từ đó, họ sẽ trượt sang phải hoặc trượt xuống dưới đến các nền trượt tuyết khác. Để tăng thêm phần thú vị, ABNL đặt thêm một quy tắc "quay đầu là bờ": nếu một coder trượt ra khỏi mép sân, họ sẽ quay ngược lại từ mép đối diện và tiếp tục trượt theo hướng ban đầu. Đồng thời, người chơi không thể nhảy vượt qua một nền trượt tuyết để đến một nền khác. Xem hình minh họa:

Vì tất cả các coder đều rất hào hứng, mỗi nền trượt tuyết P ban đầu sẽ có đúng một coder đứng sẵn. Nhưng sau khi trượt, nếu hai người chơi cùng trượt đến một nền trượt tuyết, họ sẽ va vào nhau, khiến cuộc chơi bị gián đoạn. Để tránh điều này, ABNL quyết định đặt mũi tên chỉ hướng trên mỗi nền trượt tuyết P để điều chỉnh hướng di chuyển của các người chơi. Các coder phải tuân thủ hướng mũi tên để trượt, và không được chọn hướng khác. Ở mỗi lượt chơi, các coder trượt lần lượt theo thứ tự ABNL chỉ định, coder đứng ở một nền tuyết sẽ trượt theo hướng mũi tên được chỉ định của ô đó và dừng ở ô đầu tiên họ gặp (xem hình minh họa ở trên). Hai coder sẽ va chạm nhau chỉ khi hai bạn đó cùng dừng chân ở chung một nền trượt tuyết trong lượt đó.

Vì đang bận sắp xếp vị trí cho mọi người, ABNL nhờ bạn giúp tính toán: có bao nhiêu cách khác nhau để đặt mũi tên chỉ hướng (chỉ sang phải hoặc xuống dưới) cho tất cả các nền trượt tuyết P sao cho không có hai coder nào va vào nhau?

Input

• Dòng đầu tiên chứa số nguyên \(N\) \((1 \leq N \leq 800)\) là kích thước sân trượt tuyết
• \(N\) dòng tiếp theo, mỗi dòng chứa \(N\) ký tự:
  • . đại diện cho tuyết bình thường
  • P đại diện cho nền trượt tuyết
• Dữ liệu đảm bảo sẽ luôn có ít nhất một nền trượt tuyết P trong sân.

Output

• In ra một số nguyên duy nhất: số cách khác nhau để gắn mũi tên chỉ hướng cho tất cả các nền trượt tuyết P mà không để xảy ra va chạm giữa các coder. Mặc dù đáp án có thể rất lớn, dữ liệu đảm bảo đáp án nằm trong phạm vi của một số nguyên có dấu 64-bit (giúp ABNL có thể dễ dàng lưu trữ và phân tích hơn).

Example

6
P.P...
.P...P
P.P.P.
.P..P.
..P..P
......

8

3
...
.P.
...

2

Đêm Giáng Sinh đang đến rất gần, và sau nhiều trò chơi hôm nay, ABNL muốn dành tặng phần quà đặc biệt cho các bạn đã đến được map cuối này. ABNL đã mời đến nhà ảo thuật gia J99, cùng với nhiều hộp quà thú vị.

Nhưng trước đó, ảo thuật gia J99 muốn thực hiện một màn ảo thuật gửi tặng các bạn. J99 đem ra một nhóm hộp quà bí ẩn. Những chiếc hộp này không được đánh dấu, và một số trong chúng chứa các món quà giống hệt nhau. Đặc biệt, có những vị trí trên sàn chỉ là chỗ trống – không có hộp nào cả. J99 quyết định biến tình huống này thành một trò chơi thử thách.

J99 chơi một trò chơi bằng cách nhặt \(K\) hộp quà ngẫu nhiên trên sàn, tráo đổi vị trí của chúng và đặt lại xuống. Tuy nhiên, không hộp nào được đặt lại vị trí cũ, và sau khi tráo đổi, trạng thái cuối cùng của sàn phải trông giống hệt như ban đầu.

J99 sẽ thưởng cho các bạn một ngôi sao tinh tú nếu giải được bài toán này. Hãy tính xác suất mà ảo thuật gia J99 có thể thực hiện được trò chơi này. Nếu xác suất đó có thể tính được, biểu diễn nó dưới dạng \(p \cdot q^{-1} \pmod{998244353}\), trong đó \(\frac{p}{q}\) là xác suất dưới dạng phân số tối giản.

Input

• Dòng đầu tiên chứa hai số nguyên \(N\) \((2 \leq N \leq 1000000)\) và \(K\) \((1 \leq K < N)\) - số lượng vị trí trên sàn và số lượng hộp quà sẽ được nhặt.
• Dòng thứ hai chứa một chuỗi độ dài \(N\), gồm các ký tự:
• '.' đại diện cho vị trí trống
• 'a'-'z' và '0'-'9' đại diện cho các loại hộp quà

Output

• Một số nguyên duy nhất là \(p \cdot q^{-1} \pmod{998244353}\), trong đó \(\frac{p}{q}\) là xác suất thành công

Example

10 1
..a.r3o...

0

4 2
qq..

1

10 2
..i.c.p.c.

166374059