## Link đề
https://open.kattis.com/problems/monk
## Tóm đề
Tại một thời điểm xác định trong ngày, nhà sư đi lên đỉnh núi, giữa quãng đường có dừng lại để nghỉ ngơi nhiều lần (mỗi lần dừng lại tốc độ sẽ thay đổi). Sau khi lên tới đỉnh, tại cùng một thời điểm xác định trong ngày, nhà sư lại đi từ đỉnh núi xuống và vẫn dừng lại nghỉ ngơi nhiều lần (dĩ nhiên tốc độ trung bình khi xuống núi sẽ nhanh hơn khi lên núi). Xác định thời điểm sớm nhất sao cho khi đó quãng đường nhà sư đi được khi lên núi và xuống núi là bằng nhau.

Coi **thời điểm xác định trong ngày** là **thời điểm 0**.

## Solution

Gọi $curA$ và $curD$ lần lượt là độ cao hiện tại khi lên núi và xuống núi tại thời điểm $t$ nào đó. Việc ta cần làm là tìm $t$ sao cho $curA = curD$.

Bài này tuy có giới hạn khá nhỏ nhưng vì $t$ thuộc tập số thực nên không thể vét cạn được thay vào đó có thể dễ dàng nhận thấy $t$ và **độ cao** có thể viết thành một hàm **nhất biến** vì vậy ta có thể sử dụng kĩ thuật **chặt nhị phân trên số thực**. Ở đây có hai hướng có thể chặt nhị phân, cách thứ nhất là cnp theo **độ cao**, hai là cnp theo $t$, lời giải này sẽ chỉ đề cập đến cách thứ hai.

Tiếp theo, ta cần xác định điều kiện để hàm cnp dừng lại. Bạn có thể chạy for với 150 tới 200 lần hoặc lấy điều kiện sai số $\epsilon$ khoảng $10^{-6}$ vẫn có thể đảm bảo hàm cnp của bạn ra kết quả đúng. Hoặc bạn có thể tính theo cách sau nếu time limit quá chặt hoặc bạn muốn một số chính xác: theo tính chất của cnp, cnp $X$ lần thì giá trị bạn muốn chặt sẽ giảm $2^X$ lần. Giả sử giá trị ban đầu bạn cần chặt là $N$ và bạn muốn độ chính xác lên tới $\epsilon$ = $10^{-6}$. Từ đây, bạn sẽ có phương trình $N/2^X = \epsilon$. Bạn chỉ cần giải $X$ sẽ ra số lần chặt nhị phân chính xác bạn cần với độ chính xác như mong muốn.

Việc ta cần quan tâm tiếp theo là tăng/giảm $t$ như thế nào. Ta cần đảm bảo độ cao khi xuống núi phải luôn luôn cao hơn hoặc bằng độ cao khi lên núi vì nếu không đảm bảo điều kiện này, $t$ sẽ vô nghiệm vì nó là hàm nhất biến. Do đó khi $curA \geq curD$ ta sẽ giảm $t$ để đảm bảo điều kiện đó và ngược lại ta sẽ tăng $t$. Đáp số sẽ là $t$ của lần chặt nhị phân cuối cùng.

Ở code mẫu khi cập nhật $lo$ và $hi$ chỉ cập nhật theo $mi$ chứ không $-1$ hay $+1$ vì nó là số thực, nếu cập nhật như thế sẽ bỏ qua rất nhiều trường hợp.

## Code mẫu

#include <bits/stdc++.h>

using namespace std;

const int MAXN = 5005;

pair<int,int> a[MAXN],d[MAXN];

signed main() {
        int n,m; cin >> n >> m;
        double h = 0, t = 0;
        for (int i = 0; i < n; i++) {
            cin >> a[i].first >> a[i].second;
            h += a[i].first; t += a[i].second;
        }
        for (int i = 0; i < m; i++) cin >> d[i].first >> d[i].second;
        double lo = 0, hi = t;
        for (int j = 1; j <= 100; j++) {
            double mi = (lo+hi)/2;
            double curTime = mi;
            double curA = 0;
            for (int i = 0; i < n; i++) {
                if (a[i].second < curTime) {
                    curA += a[i].first;
                    curTime -= a[i].second;
                } else {
                    curA += (a[i].first*curTime/a[i].second);
                    break;
                }

            }
            curTime = mi;
            double curD = h;
            for (int i = 0; i < m && curD > 0; i++) {
                if (d[i].second < curTime) {
                    curD -= d[i].first;
                    curTime -= d[i].second;
                } else {
                    curD -= (d[i].first*curTime/d[i].second);
                    break;
                }

            }
            if (curA >= curD) hi = mi;
            else lo = mi;
        }
        cout << setprecision(5) << fixed << hi;
        return 0;
}

$$\sum_{S \subseteq A} \gcd(S) = \sum_{d = 1}^n d \cdot \phi(m_d)$$