Thi thử TS10 LQĐ

Nhân dịp sinh nhật, bé Bo được mẹ tặng một số nguyên dương \(n\) \((n \leq 10^9)\). Với bản tính hiếu kì, bé Bo thắc mắc giá trị \(P(n)\) là bao nhiêu, trong đó \(P(n) = \lfloor \frac{n}{1} \rfloor + \lfloor \frac{n}{2} \rfloor + ... + \lfloor \frac{n}{n} \rfloor\).

\(\lfloor \frac{a}{b} \rfloor\) là phần nguyên khi tính \(\frac{a}{b}\). Ví dụ \(\frac{13}{5} = 2.6\) thì \(\lfloor \frac{13}{5} \rfloor = 2\).

Yêu cầu: In ra giá trị \(P(n)\).

Input

• Gồm \(1\) dòng duy nhất chứa số nguyên dương \(n\).

Output

• Gồm \(1\) dòng duy nhất là giá trị \(P(n)\).

Scoring

• Subtask \(1\) (\(60\%\) số điểm): \(n \leq 10^6\).
• Subtask \(2\) (\(40\%\) số điểm): \(n \leq 10^9\).

Example

5

10

Bé An được mẹ tặng cho một xâu \(s\) gồm \(n\) kí tự số \((n \leq 10^7).\) Bé An quyết định tạo ra xâu \(t\) bằng cách chọn \(k\) kí tự đầu tiên của xâu \(s\), sau đó liệt kê ra tất cả các lần xuất hiện của \(t\) trong \(s\).

Xâu \(t\) với độ dài \(k\) được gọi là xuất hiện ở vị trí \(i\) trong xâu \(s\) nếu \(s[i]s[i + 1]...s[i + k - 1] = t\).

Các xâu trong bài được đánh chỉ số bắt đầu từ \(1\) từ trái sang phải.

Yêu cầu: Tìm \(k\) lớn nhất sao cho xâu \(t\) xuất hiện ít nhất \(2\) lần không chồng lên nhau trong xâu \(s\). In ra \(k\) và vị trí xuất hiện của \(t\) trong \(s\) nhỏ nhất khác \(1\). Trong trường hợp \(k = 0\) in ra \(0\) \(1\).

Input

• Gồm \(1\) dòng duy nhất chứa xâu \(s\).

Output

• Gồm \(2\) số là độ dài lớn nhất của xâu \(t\) và vị trí xuất hiện nhỏ nhất khác \(1\) trong \(s\).

Scoring

• Subtask \(1\) (\(30\%\) số điểm): \(n \leq 10^3\).
• Subtask \(2\) (\(30\%\) số điểm): \(n \leq 10^4\).
• Subtask \(3\) (\(40\%\) số điểm): \(n \leq 10^7\).

Example

12312312312

5 7

Hôm nay, do thời tiết nắng đẹp, mẹ bé Bo dẫn bé cùng đi hái nấm ở trong rừng. Khu rừng có thể được miêu tả bằng một mảng \(2\) chiều \(a\) gồm \(n\) hàng, \(n\) cột \((2 \leq n \leq 1000)\), các hàng và cột được đánh số từ \(1\). Tại vị trí ở hàng thứ \(i\), cột thứ \(j\) có một số nguyên \(a_{ij}\) là số lượng cây nấm tại vị trí đó, vì một số bẫy được đặt trong rừng nên khi đi vào đó bé Bo sẽ bị mất nấm nên số lượng nấm có thể âm \((-1000 \leq a_{ij} \leq 1000)\). Bé Bo xuất phát ở ô \((1, 1)\) và tìm đường đi đến ô \((n, n)\). Ở mỗi bước di chuyển, nếu bé bo đang ở ô \((x, y)\) (hàng \(x\) cột \(y\)) thì có thể đi tới ô \((x + 1, y)\) hoặc \((x, y + 1)\), miễn là không đi ra khỏi khu rừng. Tuy nhiên, do có nhiều thời gian rảnh, bé Bo có thể không quá \(k\) \((k \leq 200)\) lần đi theo hướng ngược lại (tức là đi tới ô \((x - 1, y)\) và \((x, y - 1)\)). Một ô có thể được đi đến nhiều lần (đúng với cả ô \((n, n)\)), và mỗi lần đến bé Bo đều nhận được \(a_{ij}\) cây nấm.

Yêu cầu: In ra số lượng nấm lớn nhất (kết quả có thể âm) mà bé Bo hái được nếu di chuyển tối ưu.

Input

• Dòng đầu tiên chứa \(2\) số \(n, k\) \((2 \leq n \leq 1000, 0 \leq k \leq 100)\)
• \(n\) dòng sau, mỗi dòng gồm \(n\) số mô tả khu rừng.

Output

• Số lượng nấm lớn nhất mà bé Bo hái được nếu di chuyển tối ưu.

Scoring

• Subtask \(1\) (\(20\%\) số điểm): \(k = 0\).
• Subtask \(2\) (\(20\%\) số điểm): \(2 \leq n \leq 5, 1 \leq k \leq 5\).
• Subtask \(3\) (\(20\%\) số điểm): \(2 \leq n \leq 200, 1 \leq k \leq 100\).
• Subtask \(4\) (\(60\%\) số điểm): \(2 \leq n \leq 1000, 1 \leq k \leq 100\)

Example

3 1
1 1 0
1 1 0
1 1 1

7

4 4
1 1 1 0
1 0 1 0
1 1 1 0
0 0 1 1

15

Nhân dịp sắp thi tuyển sinh, mẹ tặng bạn Bo dãy số nguyên không âm gồm \(n\) phần tử \(a_1, a_2, ..., a_n\) thỏa \(1 \leq n \leq 10^5\) và \(0 \leq a_i \leq 10^8\) với mọi \(i\). Gọi dãy số \(b_1, b_2, ..., b_n\) là dãy số sau khi sắp xếp các phần tử trong dãy \(a\) một cách tùy ý. Độ yêu thích của bạn Bo đối với dãy số \(b\) là \(P(b) = 1 * b_1 + 2 * b_2 + ... + n * b_n\). Để chiều con, mẹ bạn Bo quyết định sắp xếp dãy \(a\) sao cho độ yêu thích của bạn Bo là lớn nhất.

Mặc khác, để làm khó con, mẹ bạn Bo quyết định cho Bo \(q\) \((q \leq 10^5)\) truy vấn, mỗi truy vấn gồm \(2\) số nguyên \(i, j\) \((1 \leq i \leq n; 0 \leq j \leq 10^8)\). Với mỗi truy vấn, mẹ bạn Bo tạo ra dãy \(c = a\) và gán \(c_i = j\). Sau đó, mẹ yêu cầu bạn Bo sắp xếp lại dãy \(c\) sao cho độ yêu thích của bạn là lớn nhất.

Yêu cầu: Sau mỗi truy vấn, hãy giúp bạn Bo in ra độ yêu thích lớn nhất theo yêu cầu của mẹ.

Input

• Dòng đầu gồm \(2\) số nguyên dương \(n, q\) \((n, q \leq 10^5)\).
• Dòng tiếp theo gồm \(n\) số nguyên không âm \(a_1, a_2, ..., a_n\) \((0 \leq a_i \leq 10^8)\).
• \(q\) dòng tiếp theo, mỗi dòng gồm \(2\) số \(i, j\).

Output

• Gồm \(q\) dòng, trong đó dòng thứ \(i\) là kết quả khi thực hiện truy vấn thứ \(i\).

Scoring

• Subtask \(1\) (\(20\%\) số điểm): \(n, q \leq 10\).
• Subtask \(2\) (\(35\%\) số điểm): \(n, q \leq 10^3\).
• Subtask \(3\) (\(45\%\) số điểm): \(n, q \leq 10^5\).

Example

5 3
1 10 4 2 6
2 1
2 8
4 5

55
81
98