2025 THT bảng B - Buổi 6

Từ một số nguyên dương \(k\) ban đầu, ta thực hiện biến đổi số \(k\) theo quy tắc biến đổi sau đây:

Nếu \(k\) chia hết cho \(6\) thì thay số \(k\) bởi thương \(k:6\); còn nếu \(k\) không chia hết cho \(6\) thì thay số \(k\) bởi tích \(3 \cdot k\).

Yêu cầu: Hãy xác định số lần biến đổi theo quy tắc trên để \(k\) bằng \(1\). Trong trường hợp không thể biến đổi \(k\) bằng \(1\) thì in ra kết quả \(-1\).

Input

• Một dòng chứa số nguyên \(k\) (\(k \le 10^9\)).

Output

• Số nguyên \(m\) là số lần biến đổi để \(k\) bằng \(1\).

Example

12 

3

10

-1

Một số tự nhiên được gọi là số Py−ta−go là số được tạo thành từ việc ghép \(3\) số tự nhiên \(a, b, c\) theo một trật tự bất kì với nhau (không thay đổi trật tự các chữ số trong mỗi số \(a, b, c\)), trong đó \(3\) số \(a, b, c\) thỏa mãn điều kiện tổng bình phương của \(2\) số nào đó trong \(3\) số này bằng bình phương của số còn lại.

Ví dụ: Với \(3\) số \(a = 6, b = 8, c = 10\), ta có \(6^2 + 8^2 = 10^2\) và nếu ghép chúng lại với nhau theo một trật tự bất kì thì ta có được tất cả \(6\) số Py−ta−go như sau: \(6810, 6108, 8610, 8106, 1068, 1086\).

Yêu cầu: Cho \(x\) là một số Py−ta−go được ghép từ bộ ba số \(a, b, c\) như đã trình bày ở trên. Hãy tìm số lớn nhất trong \(3\) số \(a, b, c\).

Input

• Một dòng chứa số nguyên dương \(x\) có ít nhất \(3\) chữ số và có nhiều nhất \(24\) chữ số.

Output

• Ghi ra số nguyên dương cần tìm theo yêu cầu của đề. Nếu có nhiều kết quả thì chỉ ghi ra số lớn nhất trong các kết quả tìm được.

Example

6810

10

Cho một lưới hình vuông chứa rất nhiều ô vuông nhỏ. Mỗi ô vuông trong lưới hình vuông này được xác định vị trí bởi một cặp số \((i,j)\), trong đó \(i\) là chỉ số hàng và \(j\) là chỉ số cột. Các hàng được đánh chỉ số bởi các số tự nhiên bắt đầu từ \(1, 2, 3, \dots\) kể từ trên xuống dưới; các cột được đánh chỉ số bởi các số tự nhiên bắt đầu từ \(1, 2, 3, \dots\) kể từ trái sang phải. Các ô vuông trong lưới hình vuông được ghi một số tự nhiên bằng tích của chỉ số hàng và chỉ số cột của ô vuông đó.

Chọn ra hình vuông chứa \(K \times K\) ô vuông trong lưới hình vuông đã cho. Gọi \(T\) là tổng các số trong các ô vuông có trong hình vuông đã chọn.

Yêu cầu: Hãy tìm số dư trong phép chia \(T : 20192020\).

Ví dụ: Cho lưới hình vuông, ta chọn một hình vuông gồm \(3 \times 3\) ô vuông, trong đó ô vuông ở góc bên trái có chỉ số hàng bằng \(2\) và chỉ số cột bằng \(1\) (hình minh họa).

Input

• Một dòng duy nhất chứa 3 số nguyên \(i, j, K\) (\(1 \leq i \leq 1000; 1 \leq j \leq 1000; 1 \leq K \leq 10^8\)). Trong đó \(i\) và \(j\) lần lượt là chỉ số hàng và chỉ số cột của ô vuông ở góc bên trái của hình vuông được chọn; \(K\) là số ô vuông trên một hàng (và là số ô vuông trên một cột) của hình vuông được chọn.

Output

• Số dư của phép chia \(T : 20192020\).

Example

2 1 3 

54

Phú hộ qua đời để lại cho 4 người con một mảnh đất hình vuông có kích thước \(n × n\), trên đó có trồng một số cây gỗ quí. Theo di chúc, mảnh đất sẽ được chia thành 4 phần, mỗi phần là một hình chữ nhật. Để tiết kiệm chi phí chia đất nên chỉ có thể thực hiện cắt mảnh đất bởi một nhát cắt theo chiều ngang và một nhát cắt theo chiều dọc. Các con của phú hộ đều thích có nhiều cây gỗ quí vì vậy họ sẽ chọn phần đất có nhiều cây gỗ quí hơn. Thứ tự nhận đất sẽ từ lớn tới nhỏ, người em út sẽ nhận phần có ít cây gỗ quí nhất.

Yêu cầu:

• Hãy chỉ cách chia đất để chênh lệch giữa số cây gỗ quí của người anh cả và của người em út là ít nhất.

Input

• Dòng thứ nhất ghi số nguyên dương \(n (2 ≤ n ≤ 500)\)
• Tiếp theo là \(n\) dòng, mỗi dòng ghi \(n\) số, số 0 hoặc số 1. Số 0 thể hiện vị trí không có cây gỗ quí, số 1 thể hiện vị trí có cây gỗ quí.

Các số ghi trên cùng một dòng cách nhau bởi ít nhất một kí tự trắng.

Output

• Một dòng ghi một số nguyên là số lượng chênh lệch cây gỗ quí ít nhất trên phần đất của người anh cả và của người em út.

Constants

• Có 50% số test tương ứng 50% số điểm có \(2 ≤ n ≤ 150\)
• Có 50% số test tương ứng 50% số điểm có \(150 < n ≤ 500.\)

Example

Nguồn: Olympic 30/4 năm 2018.