# Editorial - Minicontest #1 - Team ICPC FPTUDN

## Problem A: [arrayofwish](http://foj.faise.vn:8000/contest/48/problem/arrayofwish)

### Subtask 1 `(k = 2)`

**Ý tưởng**
Khi k=2, ta chỉ cần đếm số cặp $(a,b)$ sao cho $l\le a<b\le r$ và $b$ chia hết cho $a$. Với mỗi $a\in[l,r]$, số b thỏa mãn là:

$$
\#\{b\in[l,r]\mid b\mod a=0,\;b>a\}
= \Bigl\lfloor\frac r a\Bigr\rfloor - \Bigl\lfloor\frac{l-1}a\Bigr\rfloor - 1.
$$

Tổng lên tất cả $a$ cho kết quả trong $O(r-l+1)$, hoàn toàn đủ với $r$ lên đến $2\cdot10^5$.

**Độ phức tạp** $O(r - l + 1)$.

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int l, r, k;
    cin >> l >> r >> k; // k luôn = 2 ở subtask này
    ll ans = 0;
    for(int a = l; a <= r; ++a){
        ll cnt = r/a - ( (l-1)/a );
        ans += cnt - 1;
    }
    cout << ans << "\n";
    return 0;
}

### Subtask 2 `(r ≤ 10⁴, 1 ≤ k ≤ 18)`

**Giải pháp: quy hoạch động đơn giản (theo ước của mỗi số)**

* Ta giữ mảng `dp_prev[x]` = số cách để sinh chuỗi độ dài `len-1` kết thúc tại giá trị `x`.
* Với mỗi bước tăng độ dài lên `len`, tính `dp_cur[x] = ∑_{d | x,\,d≥l} dp_prev[d]`.
* Khởi tạo `dp_prev[x]=1` $∀ x∈[l…r]$ (chuỗi độ dài 1).
* Cuối cùng trả về tổng `∑_{x=l}^r dp_prev[x]` khi đã lặp đến `len=k`.

Độ phức tạp \~O(k·∑\_{x=l}^r√x) ≲ 18·10⁴·100≈1.8·10⁷, hoàn toàn nhanh với r≤10⁴.

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

vector<int> divisors(int n, int l){
    vector<int> ds;
    for(int i=1;i*i<=n;++i){
        if(n%i==0){
            if(i<n && i>=l) ds.push_back(i);
            int j = n/i;
            if(j!=i && j<n && j>=l) ds.push_back(j);
        }
    }
    return ds;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int l, r, k;
    cin >> l >> r >> k;
    int N = r+1;
    vector<ll> dp_prev(N, 0), dp_cur(N, 0);

    for(int x=l; x<=r; ++x) dp_prev[x] = 1;

    for(int len = 2; len <= k; ++len){
        fill(dp_cur.begin()+l, dp_cur.begin()+r+1, 0LL);
        for(int x = l; x <= r; ++x){
            for(int d: divisors(x, l)){
                dp_cur[x] += dp_prev[d];
            }
        }
        dp_prev.swap(dp_cur);
    }

    ll ans = 0;
    for(int x=l; x<=r; ++x) ans += dp_prev[x];
    cout << ans << "\n";
    return 0;
}

### Subtask 3 `(r ≤ 2·10⁵, 1 ≤ k ≤ 18)`

**Giải pháp: đệ quy có nhớ (memoized DFS), tối ưu theo bội**

* Định nghĩa hàm đệ quy

ll dfs(int u, int len);

trả về số chuỗi độ dài `len` bắt đầu tại giá trị `u`.
* Cơ sở: `len==1` ⇒ trả về $1$ .
* Quy hoạch động kèm memo:

memo[len][u] = ∑_{v = multiples of u, v≤r} dfs(v, len-1)

* Gọi lần đầu với mỗi `u` trong $[l…r]$, `len=k`, rồi cộng vào kết quả.

Tổng số trạng thái $≈ (r–l+1)×k$ và tổng công đoạn duyệt bội mỗi trạng thái vẫn là $∑₍u₎⌊r/u⌋ ≈ r ln r$, nên tổng độ phức tạp $O(k·r ln r)$.

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int l, r, k;
vector<vector<ll>> memo;

ll dfs(int u, int len){
    if(len == 1) 
        return 1;
    ll &res = memo[len][u - l];
    if(res != -1) 
        return res;
    res = 0;
    for(int v = u + u; v <= r; v += u){
        res += dfs(v, len - 1);
    }
    return res;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> l >> r >> k;
    memo.assign(k+1, vector<ll>(r - l + 1, -1LL));

    ll ans = 0;
    for(int start = l; start <= r; ++start){
        ans += dfs(start, k);
    }
    cout << ans << "\n";
    return 0;
}

## Problem B: [toanhocmodul](http://foj.faise.vn:8000/problem/mini1_toanhocmodul)

Dưới đây là phiên bản đã được **format lại rõ ràng, sạch sẽ và dễ đọc hơn**, với chú thích và phân đoạn hợp lý:

---

### Subtask 1 + 2: $m \leq 10^6$

Vì $m = a + b$, ta có thể thử tất cả các cặp $(a, b)$ sao cho $a + b = m$ bằng cách duyệt từ $a = 1$ đến $a = m - 1$ (hoặc đến $m/2$ do đối xứng), rồi tính:

$$
f(a, b) = (a \% b) + (b \% a)
$$

Dưới đây là đoạn code để tính min và max:

ll tt(ll a, ll b) {
    return (a % b) + (b % a);
}

ll check(ll m) {
    ll mi = 1e18, mx = -1;
    for (int a = 1; a <= m / 2; a++) {
        int b = m - a;
        mi = min(mi, tt(a, b));
        mx = max(mx, tt(a, b));
    }
    return mi + mx;
}

---

### Subtask 3: $m \leq 10^{18}$

#### Tìm max

Ta không thể duyệt từng cặp (a, b) như trên vì quá nhiều. Ta cần phân tích bài toán:

Gọi $f(a, b) = (a \% b) + (b \% a)$

Giả sử $a < b$
* $a \% b = a$ vì a < b
* $f(a, b) = a + (b \% a)$
* Do $b \% a < a$ nên:
$$
f(a, b) = a + (b \% a) < 2a
$$

#### Nếu $a < b < 2a$

Khi đó:

* $b \% a = b - a$ (do $b < 2a$)
* $f(a, b) = a + (b - a) = b$

→ Vậy trong đoạn $a < b < 2a$, giá trị $f(a, b) = b$

Chuyển điều kiện về theo biến $b$:

* Do $m = a + b \Rightarrow a = m - b$
* Thay vào: $m - b < b < 2(m - b)$
* Nhân 2 lên: $m + b < 3b < 2m$
* → $\frac{m}{3} < b < \frac{2m}{3}$

→ Giá trị lớn nhất có thể đạt là $\left\lfloor \frac{2m - 1}{3} \right\rfloor$

#### Nếu $2a < b$

* $b\%a = b - a*\lfloor \frac{b}{a} \rfloor$
* $f(a,b) = a + (b-a*\lfloor \frac{b}{a} \rfloor) = b-a(\lfloor \frac{b}{a} \rfloor-1)$
* Vì $b>2a$ ta suy ra được $\lfloor \frac{b}{a} \rfloor > 1$
* Suy ra $b-a(\lfloor \frac{b}{a} \rfloor-1) < b$

→ Giá trị lớn nhất có thể đạt được luôn nhỏ hơn trường hợp 1

---

#### Tìm min

#### Nếu m là số lẻ

* Ta có thể thấy $f(1,m-1)$ có giá trị nhỏ nhất là 1

#### Nếu m là số chẳn

* Ta có thể thấy $f(\frac{m}{2},\frac{m}{2})$ có giá trị nhỏ nhất là 0

Suy ra min của $f(a,b)$ sẻ bằng cho $m\%2$

---

#### Tổng kết

* Max: $f(a, b)$ khi $b = \left\lfloor \frac{2m - 1}{3} \right\rfloor$
* Min: $f(a, b)=m\%2$
* Kết quả: tổng của max và min

Lưu ý: trong các trường hợp $m = \{2,4,6\}$ vì phép chia số nguyên $\left\lfloor \frac{2m - 1}{3} \right\rfloor$ trả về một số nhỏ hơn $\frac{2m}{3}$ nên sẻ có trường hợp $a=b$ nên trong những trường hợp này ta có thể sử dụng code cho subtask 1 và 2

---

#include <bits/stdc++.h>
using namespace std;

#define ll long long

ll n;

ll tt(ll a,ll b) {
    return (a%b)+(b%a);
}

ll check(ll n) {
    ll mi=1e18,mx=-1;
    for (int i=1;i<=n/2;i++) {
        mi=min(mi,tt(i,n-i));
        mx=max(mx,tt(i,n-i));
    }
    return mi+mx;
}

void solve()
{
    cin >> n;
    if (n<1e6) cout << check(n);
    else cout << (2 * n - 1) / 3 + n % 2;

}

signed main()
{
    ll tt = 1;
    // cin >> tt;
    while (tt--)
    {
        solve();
    }
}

## Problem C: [udstr](http://foj.faise.vn:8000/contest/48/problem/udstr)

### Subtask 1 (40 điểm): Naive – cập nhật trực tiếp

* **Ràng buộc**: $N,q\le 2\times10^3$.
* **Ý tưởng**: Mỗi truy vấn $(l,r,C)$ ta lặp $i$ từ $l$ đến $r$ và gán $S[i]=C$. Cuối cùng in ra toàn bộ chuỗi.
* **Độ phức tạp**: $O\bigl(\sum_i (r_i-l_i+1)\bigr)=O(N\cdot q)=O(4\times10^6)$, chạy ổn với $2\times10^3$.

#include <bits/stdc++.h>
using namespace std;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, q;
    cin >> N >> q;
    string S(N, '-');  // khởi toàn dấu '-'

    while(q--){
        int l, r;
        char C;
        cin >> l >> r >> C;
        // chuyển sang chỉ số 0-based
        --l; --r;
        for(int i = l; i <= r; ++i){
            S[i] = C;
        }
    }

    cout << S << "\n";
    return 0;
}

### Subtask 2 (60 điểm): Sweep‐line + Multiset

**Ràng buộc**

* $1 \le N \le 10^6$, $1 \le q \le 10^5$
* Không có ràng buộc phụ khác.

**Ý tưởng**

1. **Khái niệm sự kiện (sweep‐line)**

* Với mỗi truy vấn thứ $i$: $(l_i, r_i, C_i)$, ta tạo hai sự kiện:

* Tại vị trí $l_i$, “mở” query $i$ với kí tự $C_i$.
* Tại vị trí $r_i+1$, “đóng” query $i$.
2. **Multiset lưu trạng thái**

* Dùng `multiset<pair<ll,char>> active` để chứa các cặp $(\text{index},\text{char})$ của những query đang mở tại vị trí hiện tại.
* Mỗi khi mở, ta `insert({i, C_i})`; khi đóng, ta `erase(active.find({i, C_i}))`.
* Khởi `active` với $(0,'-')$ để các vùng không có query nào phủ sẽ in dấu ‘-’.
3. **Duyệt từ 1 đến N**

* Tại mỗi vị trí $x$, xử lý tất cả sự kiện liên quan (mở hoặc đóng).
* Lấy phần tử cuối cùng của `active` (cặp có chỉ số query lớn nhất) và in kí tự tương ứng.

**Độ phức tạp**

* Mỗi sự kiện mở/đóng multiset tốn $O(\log q)$. Tổng có $2q$ sự kiện ⇒ $O(q\log q)$.
* Duyệt $N$ vị trí và in ra kí tự ⇒ $O(N)$.
* **Tổng**: $O\bigl((N + q)\log q\bigr)$, đáp ứng tốt với $N\le10^6, q\le10^5$.

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

static const int MAXN = 1000000 + 5;
vector<pair<ll,char>> events[MAXN];
multiset<pair<ll,char>> active;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    ll n, q;
    cin >> n >> q;

    for(ll i = 1, l, r; i <= q; ++i){
        char c;
        cin >> l >> r >> c;
        events[l].emplace_back( i, c);
        events[r+1].emplace_back(-i, c);
    }

    active.insert({0, '-'});

    for(int i = 1; i <= n; ++i){
        for(auto &ev : events[i]){
            ll idx = ev.first;
            char ch = ev.second;
            if(idx > 0) {
                active.insert({idx, ch});
            } else {
                active.erase(active.find({-idx, ch}));
            }
        }
        cout << prev(active.end())->second;
    }
    cout << "\n";
    return 0;
}

## Problem D: [cutwood](http://foj.faise.vn:8000/problem/mini1_woodcut)

### Subtask 1:

Ta có thể thực hiện theo 2 công đoạn
1. Cắt tất cả các khúc gỗ thành những đoạn có độ dài là m và đoạn dư, ta có thể đếm số lượng đoạn bằng công thức $a[i]\%m$.
2. Sau khi cắt ta sẻ có được n đoạn gỗ có độ dài từ 0 đến m-1.
* Chúng ta có thể duyện qua n đoạn và tìm ra đoạn có độ dài nhỏ nhất để tính vào phần dư sau đó xóa đoạn đó khỏi mảng.
* Thực hiện cho đến khi tổng dư đạt đến giới hạn hoặc đã lấy hệt các khúc gỗ.

### Subtask 2:

* Ta có thể thấy được ở công đoạn 2 ta tốn khá nhiều thời gian cho việc tìm đoạn nhỏ nhất.
* vì vậy ta có thế sắp xếp các đoạn trước khi tìm và lấy từ nhỏ đến lớn cho đến khi hoàn thành yêu cầu.

#include<bits/stdc++.h>
#define fi first
#define se second
#define ii pair<ll,ll>

typedef long long ll;

using namespace std;

const ll MOD = 1e9+7;
const ll N = 1e6+999;
const ll NN = 1e5+9;

ll n,m,k,kq=0,a[N];

void solve()
{
    cin >> n >> m >> k;
    for (int i=0;i<n;i++) {
        cin >> a[i];
        kq+=a[i]/m;
        a[i]=a[i]%m;
    }
    sort(a,a+n);
    for (int i=0;i<n;i++) {
        k-=a[i]%m;
        if (k<0) break;
        kq+=(a[i]+m-1)/m;
    }
    cout << kq;
}

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    ll t=1;
    //cin>>t;
    while (t--)
    {
        solve();
    }
    return 0;
}