LQDOJ contest #14

Nay ngày của các mỹ nhân
Chàng được cho dãy nhị phân dài \(n\)
Chàng ngồi chàng đảo hàng giờ
Lấy dãy toàn 1 làm thơ tặng nàng
Vì chàng vốn rất yêu nàng
Dãy càng nhiều 1, thơ càng thêm sang
Nhờ thí sinh đảo giúp chàng
Cho nhiều số 1 để chàng tặng em

Yêu cầu: Cho một xâu nhị phân độ dài \(n\), hãy giúp chàng trai chọn một đoạn liên tiếp của xâu và đảo ngược các kí tự trong đoạn đó (0 thành 1, 1 thành 0) để sau cùng xâu có nhiều kí tự 1 nhất.

Input

• Dòng đầu tiên gồm một số nguyên dương \(n\).
• Dòng thứ hai gồm một xâu nhị phân độ dài \(n\).

Output

• Gồm một số nguyên duy nhất là số kí tự 1 nhiều nhất có thể sau khi thực hiện một lần đảo ngược một đoạn liên tiếp.

Scoring

• Subtask 1 (\(50\%\) số điểm): \(n \leq 1000\).
• Subtask 2 (\(50\%\) số điểm): \(n \leq 10^5\).

Example

5
10101

4

Cho một ma trận gồm \(n\) hàng, \(m\) cột. Các hàng được đánh số từ \(1\) đến \(n\), các cột được đánh số từ \(1\) đến \(m\). Ô nằm trên hàng \(i\), cột \(j\) được kí hiệu là ô \((i, j)\). Bảng con \((x, y, u, v)\) là tập hợp các ô \((i, j)\) thỏa mãn \(x \leq i \leq u\) và \(y \leq j \leq v\). Bảng con \((x, y, u, v)\) được gọi là bảng vuông khi và chỉ khi \(u - x = v - y\).

Với mỗi ô \((i,j)\) của ma trận, người ta gán một số nguyên \(a_{i,j}\). Hãy tìm bảng vuông có diện tích lớn nhất có thể, sao cho tổng \(a_{ij}\) của các ô \((i,j)\) không vượt quá \(S\).

Input

• Dòng đầu tiên gồm ba số nguyên dương \(n, m, S\) \((1 \leq n, m \leq 3000, 0 \leq S \leq {10}^{10})\).
• \(n\) dòng tiếp theo, dòng thứ \(i\) \((1 \leq i \leq n)\) chứa \(m\) số nguyên \(a_{i1}, a_{i2}, \ldots, a_{im}\) \((0 \leq a_{ij} \leq {10}^6)\).

Output

• Gồm một số nguyên duy nhất là diện tích lớn nhất có thể của một bảng vuông thỏa mãn điều kiện trên.

Scoring

• Subtask 1 (\(15\%\) số điểm): \(n, m \leq 100\).
• Subtask 2 (\(15\%\) số điểm): \(n, m \leq 500\).
• Subtask 3 (\(25\%\) số điểm): \(n, m \leq 1000\).
• Subtask 4 (\(45\%\) số điểm): \(n, m \leq 3000\).

4 5 9
1 1 1 1 1
1 1 2 1 1
1 1 2 1 1
1 1 1 1 1

4

Chỉ còn vài ngày nữa thôi là đến ngày Phụ Nữ Việt Nam 20/10 rồi, người bố bèn hẹn \(n\) người con của mình tổ chức một bữa tiệc nhỏ ở nhà cho người mẹ.

Ta sẽ đánh số các ngày như sau, hôm nay là ngày \(0\), ngày mai là ngày \(1\), ..., sau ngày \(x\) đến ngày \(x+1\) (với mọi \(x > 0\)).

Các người con được đánh số từ \(1\) đến \(n\). Tại ngày \(0\) tất cả \(n\) người con đều đang bận, người con thứ \(i\) \((1 \leq i \leq n)\) sẽ rảnh tại các ngày được đánh số \(a_i\), \(2a_i\), \(3a_i\), \(\ldots\) Các ngày còn lại người con thứ \(i\) đều bận tất.

Tức là người con thứ \(i\) sẽ chỉ rảnh tại các ngày \(k \times a_i\) \((k > 0)\) là các bội khác \(0\) của \(a_i\).

Người bố hiểu rằng nếu khi tổ chức bữa tiệc tại ngày \(x\) \((x \geq 0)\) nào đó mà chỉ cần có một người con vắng mặt (không đến được vì ngày đó bận) thì người mẹ sẽ không vui. Người bố cần tìm ngày được đánh số \(F\) \((F \geq 0)\) là ngày được đánh số nhỏ nhất và tất cả các người con đều rảnh để tổ chức bữa tiệc.

Yêu cầu: Vì \(F\) có thể rất lớn nên chỉ cần đưa ra \(F \; \% \; ({10}^9 + 7)\).

Input

• Dòng đầu tiên gồm một số nguyên dương \(n\) \((1 \leq n \leq {10}^5)\).
• Dòng thứ hai gồm \(n\) số nguyên \(a_1, a_2, \ldots, a_n\) \((1 \leq a_i \leq {10}^6)\).

Output

• Gồm một số nguyên duy nhất là kết quả cần tìm.

Example

1
10

10

5
2 3 5 7 11

2310

4
2 14 12 10

420

Scoring

• Subtask 1 (\(25\%\) số điểm): \(n \leq 20\).
• Subtask 2 (\(25\%\) số điểm): \(n \leq 200\).
• Subtask 3 (\(25\%\) số điểm): \(n \leq 3000\).
• Subtask 4 (\(25\%\) số điểm): \(n \leq {10}^5\).

Cho một dãy số gồm \(n\) số nguyên \(a_1, a_2, \ldots, a_n\). Với mỗi tập con khác rỗng \(S = (i_1, i_2, \ldots, i_k)\) \((0 < k \leq n, 1 \leq i_1 < i_2 < \ldots < i_k \leq n)\), gọi \(f(S)\) là số nguyên nhỏ nhất mà chia hết cho mọi \(a_{i_j}\) \((1 \leq j \leq k)\), tức là

Yêu cầu: Hãy tính \(R = \sum f(S)\) với tất cả mọi tập con \(S\) khác rỗng. Vì \(R\) có thể rất lớn nên chỉ cần đưa ra số dư của \(R\) khi chia cho \(10^9 + 7\).

Input

• Dòng đầu tiên gồm một số nguyên dương \(T\) \((1 \leq T \leq 10)\) là số bộ dữ liệu.
• \(T\) nhóm dòng sau, mỗi nhóm dòng thể hiện một bộ dữ liệu có dạng sau:
  • Dòng đầu tiên gồm một số nguyên dương \(n\) \((1 \leq n \leq 100)\) --- là số phần tử của dãy.
  • Dòng thứ hai gồm \(n\) số nguyên dương \(a_1, a_2, \ldots, a_n\) \((1 \leq a_i \leq 500)\).

Output

• Gồm \(T\) dòng, mỗi dòng là kết quả của các bộ dữ liệu theo đúng thứ tự trong đầu vào.

Scoring

• Subtask 1 (\(15\%\) số điểm): \(n \leq 20, a_i \leq 20\).
• Subtask 2 (\(20\%\) số điểm): \(n \leq 20\).
• Subtask 3 (\(25\%\) số điểm): Bội chung nhỏ nhất của \(n\) số nguyên dương không vượt quá \(50000\).
• Subtask 4 (\(40\%\) số điểm): Không có ràng buộc gì thêm.

Example

3
2
2 4
10
1 2 3 4 5 6 7 8 9 10
3
20 3 14

10
516031
699

Cho một dãy \(a\) gồm \(n\) số nguyên dương. Số thứ \(i\) của dãy là \(a_i\). Mỗi thao tác ta có thể chọn một số của dãy \(a\) và cộng nó lên \(1\) hoặc trừ nó cho \(1\), sao cho các số của dãy vẫn nguyên dương. Một dãy được gọi là đẹp nếu ước chung lớn nhất của cả dãy khác \(1\).

Yêu cầu: Hãy tìm số thao tác ít nhất để làm cho dãy \(a\) đẹp.

Input

• Dòng đầu tiên gồm một số nguyên dương \(n\) \((1 \leq n \leq 2 \times 10^5)\).
• Dòng thứ hai gồm \(n\) số nguyên dương \(a_1, a_2, \ldots, a_n\) \((1 \leq a_i \leq 10^{12})\).

Output

• Gồm một số nguyên duy nhất là số thao tác ít nhất để làm cho dãy \(a\) đẹp.

Example

3
6 7 6

1

2
18 18

0

Scoring

• Subtask 1 (\(18\%\) số điểm): \(a_i \leq 20\), \(\forall 1 \leq i \leq n\).
• Subtask 2 (\(23\%\) số điểm): \(a_i \leq 10^6\).
• Subtask 3 (\(59\%\) số điểm): Không có ràng buộc gì thêm.