New Server Div 1

ami lại cho các bạn một xâu kí tự \(S\) gồm \(N\) chữ cái tiếng Anh in thường và một số nguyên dương \(k\). Các bạn có thể áp dụng thao tác sau không quá \(k\) lần:

• Chọn ra một số \(i\) với \(0 \leq i \lt N\) và đổi \(S_i\) thành một kí tự bất kì.

Đặt \(F(S)\) là độ dài đoạn con dài nhất của \(S\) chỉ chứa các kí tự giống nhau.

Hãy áp dụng thao tác trên một cách tối ưu để \(F(S)\) là lớn nhất và in ra giá trị này.

Input

• Dòng đầu tiên chứa 1 xâu kí tự \(S\).

• Dòng tiếp thao chứa một số nguyên dương \(k\).

Output

• Một số nguyên dương là \(F(S)\) lớn nhất sau khi thực hiện thao tác không quá \(k\) lần.

Scoring

• Subtask \(1\) (\(60\%\) số điểm): \(1\) \(\leq\) \(k\) , \(N\) \(\leq\) \(100\).
• Subtask \(2\) (\(40\%\) số điểm): \(1\) \(\leq\) \(k\) , \(N\) \(\leq\) \(10^5\).

Example

cuomquaga
1 

3

Cho phân số có dạng \(\frac{p}{q}\) trong đó \(p,q\) là các số nguyên dương. Và người ta chứng minh được rằng, luôn tồn tại duy nhất một bộ giải mã \((a_1,a_2,...,a_n)\) của phân số \(\frac{p}{q}\)thoả mãn các điều kiện sau:

• \(a_i\in \mathbb{N}^{*}\text{ } (\forall i=\overline{1,n})\)

• \(a_n=1\)

• \(\frac{p}{q}=a_1+\frac{1}{a_2+\frac{1}{a_3+\frac{1}{...+\frac{1}{a_n}}}}\)

Yều cầu: Cho trước hai số nguyên dương \(p,q\). Hãy in ra bộ giải mã của \(\frac{p}{q}\) dưới dạng như sau:

• Những kí tự trống ta in ra dấu ".".

• Đối với thanh ngang của phân số ta sử dụng các chuỗi các dấu "-".

• Tử số phải nằm tương ứng với điểm chính giữa của thanh ngang phân số.

• Thanh ngang phân số phải có độ dài vừa đủ bao phủ phần mẫu bên dưới.

(Để hiểu rõ hơn, các bạn có thể xem ví dụ bên dưới).

Input

• Dòng thứ nhất chứa số \(t(1\le t\le 30)\) - Thể hiện số testcase.

• \(t\) dòng tiếp theo, mỗi dòng chứa hai số nguyên dương \(p,q(0<q<p<10^{18})\) và đề bài ra đảm bảo \(p>q\).

Output

• Ứng với mỗi testcase, in ra kết quả có dạng như sau:

• Dòng thứ nhất ghi: Case i: với \(1\le i\le t\).

• Block tiếp theo, biểu diễn bộ giải mã của phân số tương ứng.

Scoring

• Subtask \(1\) (\(20\%\) số điểm): \(50>p>q>0\).

• Subtask \(2\) (\(80\%\) số điểm): \(10^{18}>p>q>0\).

Example

3
39 16
39 19
1002 1001 

Case 1:
..........1......
2.+.-------------
............1....
....2.+.---------
..............1..
........3.+.-----
................1
............1.+.-
................1
Case 2:
......1...
2.+.------
.........1
....18.+.-
.........1
Case 3:
.......1....
1.+.--------
...........1
....1000.+.-
...........1

ami có một dãy số \(A\) độ dài \(N\) và một dãy số \(B\) gồm \(N\) số \(0\). Các bạn có thể thực hiện thao tác sau trên dãy \(B\) để biến dãy \(B\) thành \(A\):

• Chọn một cặp \((l, r)\) với \(1 ≤ l ≤ r ≤ n\) và một số nguyên \(k\). Sau đó, gán \(a_i = max(a_i , k)\) với mọi \(l ≤ i ≤ r\).

Định nghĩa "giá trị cuogma" của dãy số \(A\) chính là số thao tác ít nhất cần thực hiện lên dãy \(B\) để biển \(B\) thành \(A\). Ví dụ, nếu dãy \(A\) là [1 2 3] thì giá trị cuogma của dãy số này là 3:

• Chọn cặp (1, 1) và \(k\) = 1, dãy \(B\) trở thành [1 0 0].
• Chọn cặp (2, 3) và \(k\) = 2, dãy \(B\) trở thành [1 2 2].
• Chọn cặp (3, 3) và \(k\) = 3, dãy \(B\) trở thành [1 2 3] - chính là dãy \(A\).

Các bạn cũng có thể thực hiện thao tác sau trên dãy \(A\):

• Chọn một chỉ số \(i\) với \(1 ≤ i ≤ n\) và một số nguyên \(x ≥ a_i\). Sau đó, gán \(a_i = x\).

Hãy tìm cách thực hiện thao tác trên dãy \(A\) không quá 1 lần để giá trị cuogma của dãy kết quả là nhỏ nhất có thể và hãy in ra kết quả này.

Input

• Dòng đầu tiên chứa 1 số nguyên dương \(t\) là số lượng test case.

• Mỗi test case có dạng sau:

  • Dòng đầu tiên chứa 1 số nguyên dương \(N\) là số phần tử của \(A\).
  • \(N\) dòng tiếp theo chứa, mỗi dòng chứa 1 số nguyên dương biểu thị dãy số \(A\).

Output

• Giá trị cuogma nhỏ nhất của dãy \(A\) sau khi thực hiện biến đổi.

Scoring

• Tất cả test có \(1 \leq t \leq 3000\).
• Subtask \(1\) (\(50\%\) số điểm): \(\sum {N} \leq 100\) và \(a_i\) \(\leq\) \(3000\).
• Subtask \(2\) (\(50\%\) số điểm): \(\sum {N} \leq 3000\) và \(a_i\) \(\leq\) \(3000\).

Example

2
3
1
2
3
5
2 
2 
5 
2
4

2
3

Cho \(n\) đồng xu xếp thành một hàng (và đánh số từ \(1\) đến \(n\)) trên cỗ máy kỳ diệu, mỗi đồng xu đều đang được đặt ngửa lên trên hoặc úp xuống dưới. Có \(m\) nút bấm, bấm vào nút thứ \(i\) thì cỗ máy kỳ diệu sẽ lật ngược \(l_i\) đồng xu \(b_1\), \(b_2\),..., \(b_{l_i}\). Hãy lập trình tìm một cách bấm để đưa tất cả các đồng xu về mặt úp. Dữ liệu đảm bảo luôn tồn tại một cách bấm thỏa mãn.

Input

• Dòng đầu chứa hai số nguyên dương \(n\) và \(m\).
• Dòng tiếp theo chứa \(n\) số \(0\) hoặc \(1\) mô tả trạng thái ngửa hay úp của từng đồng xu. \(0\) thể hiện trạng thái ngửa, \(1\) thể hiện trạng thái úp.
• Dòng thứ \(i\) trong \(m\) dòng tiếp theo bắt đầu bằng \(l_i\) và theo sau bởi các chỉ số phân biệt \(b_1\), \(b_2\),..., \(b_{l_i}\).

Output

• Dòng đầu in ra \(k\) là số lượng thao tác.
• Dòng tiếp theo in ra \(k\) số nguyên lần lượt là số hiệu của nút mà ta cần bấm.
• Bài làm của bạn sẽ bị tính là "Kết quả sai" / "Wrong answer" nếu \(k > m\).

Constants

• \(n\leq 10^4\).
• \(m\leq 25\).
• \(l_i\leq n\) với mọi \(1\leq i\leq m\).

Example

6 5
0 0 0 0 0 0
3 2 4 6
5 1 2 3 4 5
3 2 3 5
2 1 2
2 2 6

3
3 4 1

Bạn được cho một số nguyên dương \(N\) \((N > 1).\)

Nhiệm vụ của bạn là tìm số lượng dãy gồm \(k\) phần tử thỏa mãn :

• \(a_i \geq 2\) \((∀ i = 1, 2, 3, \dots, k)\).

• \(a_1 \times a_2 \times \dots \times a_k = N\).

• \(a_{i + 1}\) chia hết cho \(a_i\). \((∀ i = 1, 2, 3, \dots, k - 1)\).

• Số \(k\) lớn nhất có thể.

Input

• Một dòng duy nhất chứa số nguyên dương \(N\) \((2 ≤ N ≤ 10^{12})\).

Output

• Gồm một dòng duy nhất là số lượng dãy gồm \(k\) phần tử thỏa mãn đề bài.

Scoring

• Subtask \(1\) (\(20\%\) số điểm): \(N\) là số nguyên tố.

• Subtask \(2\) (\(30\%\) số điểm): \(N ≤ 10 ^ {6}\).

• Subtask \(3\) (\(50\%\) số điểm): \(N ≤ 10 ^ {12}\).

Example

180 

3

17

1