Bài tập

Trò chơi chọn bóng mà nhóm của Tuấn thiết kế được bạn bè và giáo viên trong trường
đánh giá rất cao. Sau thành công này, Tuấn cùng nhóm bạn tập trung học tập để thi vào lớp
chuyên tin của một trường chuyên danh giá trong tỉnh. Những bài tập mà Tuấn làm đều yêu
cầu kỳ năng thiết kế thuật toán chuyên nghiệp. Một trong các bài tập mà bạn ấy đang xây
dựng thuật toán có nội dung như sau:

Cho chuỗi kí tự \(S\) chỉ gồm các kí tự chữ cái latinh thường từ 'a, ...,'z'. Một chuỗi con \(X\) (gồm các kí tự ở vị trí liên tiếp) của \(S\) được gọi là một chuỗi có mật độ xuất hiện cao nếu trong chuỗi X có một kí tự mà số lần xuất hiện của kí tự đó nhiều hơn số các kí tự còn lại trong chuỗi X.

Vi dụ: chuỗi \(S\) = "abbbabced", chuỗi con \(X\) = "abbbabc" là một chuỗi có mật độ xuất hiện cao, vì có kí tự 'b' xuất hiện \(4\) lần, số các kí tự còn lại bằng \(3\). Nếu \(X\) = "abbbabce",kí tự xuất hiện nhiều lần nhất \(4\) lần (kí tự 'b') và số kí tự còn lại là \(4\). Do vậy chuổi \(X\) = "abbbabce" không phải là một chuỗi có mật độ xuất hiện cao.

Yêu cầu: Tìm một chuỗi con \(X\) (gồm các kí tự ở vị trí liên tiếp) của \(S\) là một chuỗi có mật độ xuất hiện cao và độ dài lớn nhất. Tuấn cũng đã có thuật toán của mình, còn bạn thì
sao? Hãy lập trình giải bài toán trên để đối chiếu kết quả nhé.

Input

Dữ liệu: Vào từ file MATDO.INP gồm một chuỗi kí tự \(S\) chỉ gồm các kí tự chữ cái
latinh thường và có độ dài không lớn hơn \(2 \times 10^5\).

Output

Kết quả: Ghi ra file MATDO.OUT gồm một số nguyên duy nhất là độ dài của chuỗi
\(X\) tìm được.

Example

abbbabced

7

ababab

5

abc

1

Scoring

• Có \(30\%\) số test ứng với \(30\%\) số điểm thỏa mãn: Chuỗi \(S\) chỉ gồm các kí tự thuộc tập
  \(3\) kí tự 'a', 'b', 'c' và độ dài chuỗi \(S\) không quá \(2 \times 10^3\).
• Có \(30\%\) số test ứng với \(30\%\) số điểm thỏa mãn: Chuỗi \(S\) chỉ gồm các kí tự chữ cái
  latinh thường và độ dài chuỗi \(S\) không quá \(2 \times 10^3\).
• Có \(40\%\) số test ứng với \(40\%\) số điểm thỏa mãn: Chuỗi \(S\) chỉ gồm các kí tự chữ cái
  latinh thường và độ dài chuỗi \(S\) không quá \(2 \times 10^5\).

Cho một số nguyên dương \(n\) có độ dài không quá \(10^5\).

Bạn có thể thực hiện thao tác sau vô số lần: chọn một chữ số trong số đó, bình phương nó, và thay chữ số cũ bằng kết quả (kết quả phải là một chữ số nghĩa là nếu chọn một chữ số \(x\) thì \(x^2 < 10\)).

Yêu cầu: Cho số nguyên dương \(n\). Có thể biến đổi để thu được một số chia hết cho \(9\) bằng những thao tác trên không?

Input

Vào từ file BIENDOI.INP:

• Dòng đầu tiên chứa số nguyên \(t\) -- là số lượng bộ truy vấn \((1 \le t \le 10^4)\).
• \(t\) dòng tiếp theo, mỗi dòng chứa số nguyên \(n\) \((1 \le |n| \le 10^5)\).

Dữ liệu đảm bảo rằng tổng độ dài của tất cả các số trong tất cả test không vượt quá \(10^5\).

Output

Ghi ra file BIENDOI.OUT: "YES" nếu có thể và "NO" nếu không.

Example

3
123
322
333333333333

NO
YES
YES

Ở một vùng đất xa xôi, nơi những con số có linh hồn riêng, một nhà giả kim số học tên Linh đã phát minh ra một trò chơi trí tuệ với tên gọi Hợp Nhất Vô Cực.

Linh tạo ra một bảng chứa \(N\) số nguyên dương, được viết thẳng hàng trên mặt phẳng ma thuật. Mỗi số trong bảng mang một nguồn năng lượng đặc biệt, và khi hai số giống nhau đứng cạnh nhau, Linh có thể kết hợp chúng thành một số mới, lớn hơn hai số ban đầu một đơn vị.

Sau khi kết hợp, hai viên đá cũ biến mất, và thay vào ngay điểm đó bằng viên đá mới. Mục tiêu của Linh là kết hợp sao cho, số lớn nhất trên các viên đá trên dãy là lớn nhất.

Input

• Dòng đầu tiên chứa số nguyên \(N\) \((1 \leq N \leq 10^5)\) - số lượng các số trong bảng.
• Dòng thứ hai chứa \(N\) số nguyên dương, mỗi số không vượt quá \(40\) - các số trên bảng.

Output

• Ghi ra một số nguyên duy nhất - số lớn nhất có thể đạt được sau khi thực hiện các phép hợp nhất tối ưu.

Example

3
1 1 2

3

Scoring

• Với \(30\%\) số test, \(N \leq 1000\).
• Với \(70\%\) số test còn lại, không có ràng buộc gì thêm.

Cho ma trận \(n*n\), tính tổng các phần tử nằm trên các cột lẻ và hàng lẻ

Input

• Dòng 1: số \(n\) \((n < 100)\)

• Các dòng tiếp theo gồm các số mô tả bảng \(n*n\), giá trị tuyệt đối của các số không vượt quá 1000

Output

• In ra kết quả

Example

3
1 2 3
2 3 1
2 3 3

9