# Lời giải đề thi thử lần 1 môn Tin học PEA
*written by ntan, vson, tminh, haison, mduc*

## NGỌN NÚI
*Written by Minh Đức*

### Tóm tắt đề bài
Cho 2 số nguyên $n$ và $x$, yêu cầu in ra $x$ số nguyên liên tiếp có tổng bằng $n$.

### Subtask 1: Duyệt Trâu (*$x$ $\le$ $n$ $\le$ $10^6$*)

Ý tưởng là duyệt trâu và tính tổng dãy liên tiếp gồm $x$ số bắt đầu từ $i$ với mỗi $i$ từ $1$ đến $n$ cho đến khi tìm được dãy thỏa mãn.

Độ phức tạp của thuật toán $O(n)$.


### Subtask 2: Công thức (*$x \le min(10^6, n), n \le 10^{18}$*)

Ta có tổng $x$ số liên tiếp là \($a + (a + 1) + ... + (a+x-1)=xa+\frac{x(x-1)}{2}$\) với $a$ là số dương.

- Với $x$ lẻ $n = x(a + \frac{x - 1}{2}) \Rightarrow a = \frac{n}{x} - \frac{x - 1}{2}$ suy ra ta chỉ cần $n$ chia hết cho $x$ là chọn được $a$
- Với $x$ chẵn $n=\frac{x}{2}(2a+x-1)\Rightarrow a=\frac{1}{2}(\frac{2n}{x}-(x-1))$ do $x - 1$ lẻ nên $\frac{2n}{x}$ phải lẻ mới chọn được $a$ hay $n$ chia hết cho $\frac{x}{2}$ nhưng không chia hết cho $x$.


Độ phức tạp của thuật toán $O(x)$.

**Source code AC** (đang cập nhật)

## HẠT GẠO
*Written by Nguyễn Văn Sơn (Yumesekai239)*

### Tóm tắt đề bài

Tính tích $1^1.2^2.3^3.....n^n$.

### Subtask 1: Duyệt trâu (*$n$ $\le$ $5.10^3$*)

Việc bạn cần làm chỉ là sử dụng $2$ vòng for lồng nhau để tính $i^i$ $(1 \le i \le n)$ rồi nhân chúng với nhau là xong.

Lưu ý rằng vì kết quả lớn nên để tránh tràn số thì các bạn phải chia lấy dư một cách hợp lý mới có thể đạt điểm tối đa sub này. \(Sử dụng tính chất $(a*b)\%c$ $=$ $(a\%c * b\%c)$$\%c$. \)


Độ phức tạp của thuật toán $O(n^2)$.

### Subtask 2: Phép nhân Ấn Độ (*$n$ $\le$ $5.10^5$*)

Khi gặp một bài toán tính $x^y$ với $y$ quá lớn thì ta thường nghĩ ngay đến thuật toán phép nhân Ấn Độ.

Nói qua về phép nhân Ấn Độ thì đây là một thuật toán sử dụng đệ quy và chặt nhị phân để tính toán. Khi đó với mỗi thao tác tính $i^i$ $(1 \le i \le n)$ thì thay vì có độ phức tạp là $O(i)$ như subtask $1$ mà nó đã được giảm xuống thành $O(log(i))$.

Khi đó giống như subtask 1, ta cũng tính $i^i$ $(1 \le i \le n)$ bằng phép nhân Ấn Độ rồi nhân chúng với nhau.


Độ phức tạp của thuật toán $O(nlogn)$.

### Subtask 3: Quy hoạch động (*$n$ $\le$ $5.10^6$*)

Nếu tinh ý thì bạn có thể ghi các hạng tử của tích cần tìm thành 1 hình tam giác như dưới đây:


Rồi đặt tích các hạng tử trên mỗi hàng là $dp[i]$ $(1 \le i \le n)$. Khi đó, nếu ta tính toàn bộ phần tử mảng dp từ dưới lên thì ta có công thức như sau:
$dp[n]=n$,
$dp[i] = dp[i+1]*i$ $(1 \le i \le n - 1)$.

Lúc này tích của chúng ta cần tìm sẽ bằng tích của toàn bộ phần tử của mảng dp.


Độ phức tạp của thuật toán $O(n)$.

[**Source code AC**](https://ideone.com/kvoFl3)

### Bonus

Các bạn có thể thử sức khi đề bài được nâng giới hạn lên thành $n \le 10^9$ bằng [Baby trick - Giant step trick](https://hackmd.io/@DeMen100ms/DeMenBlog7)

## Tổng S
*Written by Nguyễn Phúc Hải Sơn (son2008)*

### Tóm tắt đề bài

Tìm dãy con liên tiếp dài nhất có tổng $\geq S$.

### Subtask 1: Duyệt Trâu $(n \le 10^3)$

Mình sẽ kiểm tra từng đoạn $[l, r]$ $(0 \le l \le r \le n-1)$ và đoạn đối của nó $[0,l]$ $∪$ $(r,n-1)$.

**Tối ưu**

Thay vì duyệt 2 lần, ta có nhận xét sau để tối ưu:

- Nếu đoạn $[l, r]$ có $n_1$ phần tử thì đoạn còn lại sẽ là $n_2$ $= n - n_1$ phần tử
- Gọi $S(l, r)$ là tổng tất cả các số trong đoạn ($l, r)$ và $S = (0, n-1)$.
- Có $S=S(l,r)+(S(0,l-1)+S(r+1,n-1))$
- Từ đó suy ra $S(0,l-1)+S(r+1,n-1)$ hay tổng đoạn $[0,l] ∪ (r,n-1]$ có giá trị $S-S(l,r)$
- Vậy sau khi tính tổng tất cả các số, ta chỉ duyệt các đoạn $[l,r] (0\le l \le r\le n-1)$, và đoạn còn lại là $(n_2=n-n_1,S-S(l,r))$.

Độ phức tạp của thuật toán $O(n^2)$.

### Subtask 2: 2 con trỏ $(n \le 10^6)$

Với mỗi vị trí $l ∈ [0,n)$:
- Dùng cách như trên để tính $S$
- Nếu $l = r$ thì $S = 0$ mà $a_i\geq1$ nên luôn không thoả mãn, ta sẽ di chuyển $r$
- Ta tăng biến $r$ đến khi nào tổng lớn hơn $k$ thì dừng $r$
- Tối thiểu hoá trị kết quả với độ dài hiện tại (optimize: $ans = 1$ thì break).
- Lưu ý sau mỗi lần chạy, mình di chuyển $l$ thì mình phải xoá giá trị đó khỏi tổng.
- Lưu ý trong trường hợp $r$ ở vị trí cuối, thì sau khi di chuyển, mình phải đưa nó về vị trí đầu.

Độ phức tạp của thuật toán $O(n)$.

[**Source code AC**](https://ideone.com/1s6wUX)

## Cổ phiếu
*Written by Nguyễn Thanh Minh (3m)*

### Subtask 1 Duyệt trâu $(k = 1)$

Ta thấy với $k = 1$ thì bài toán trở thành bài toán tìm dãy con liên tiếp có tổng lớn nhất. Để giải quyết bài toán trên:
- $pre[i]$ : là tổng từ 1 đến i
- $s[i]$ : là tổng liên tiếp bé nhất bắt đầu từ 1 xét đến vị trí thứ i

Kết quả của ta chính là $max(pre[i] - s[i - 1])$.


### Subtask 2 Quy hoạch động $(n \le 1e5, k \le 100)$.

Gọi $dp[j][0/1]$ ta đang chọn được $j$ đoạn và có chọn tiếp đoạn thứ $j$ hay không

Có 2 trường hợp có thể xảy ra:
- Nếu được chọn tiếp dãy thứ $j$ ta có ba khả năng là thêm phần tử $a_{i + 1}$ vào dãy $j$ hoặc dãy $j + 1$ hoặc không sử dụng.
- Nếu không chọn tiếp dãy thứ $i$ thì ta có $2$ khả năng đó là thêm $a_{i + 1}$ vào dãy $j + 1$ hoặc không sử dụng.

Kết quả sẽ là $max(dp[k][1] , dp[k][0])$.


### Bonus subtask 2

*(đang bổ sung)*

[**Source code AC**](https://ideone.com/zQJ9zy)

![]()