---
# System prepended metadata

title: Mo Phắc

---


# **Tham Lam**
**Bài 3: Bus**

```cpp
#include <bits/stdc++.h>

using namespace std;

int n,m,t,k,A[100005],B[100005],d = 0,sum = 0,maxx = INT_MIN;

int main() {
    cin >> n >> m;
    for (int i = 1; i<= n; ++i) {
        cin >> t;
        cin >> k;
        for (int j = 1; j <= k ; ++j) {
            cin >> A[j];
            d++;
            if (A[j] - sum >= 0) B[d] = A[j] - sum;
                else B[d] = 0;
        }
        sum += t;
    }
    sort(B+1,B+d+1);
    cout << sum+B[m];
    // Thằng đầu tiên tốn B[1] thời gian, thằng thứ m tốn B[m] thời gian vì đã sắp xếp 
    // tăng dần nên thời gian ngắn nhất để xếp m thằng vào là B[m]
    return 0;
}
```

# **Tìm Kiếm Nhị Phân**
**Bài 1: Hàng cây – Cưa máy**

```cpp
#include<bits/stdc++.h>
using namespace std;
int n,a[1000001],m,l,r,res=0;
long long sum(int h)
{
    long long res=0;
    for (int i=1;i<=n;i++)
    {
        if (a[i]<=h) return res;
        else res+=(a[i]-h);
    }
    return res;
}
int main()
{
    cin>>n>>m;
    for (int i=1;i<=n;i++) cin>>a[i];
    sort(a+1,a+n+1,greater<int>());
    l=a[n];r=a[1];
    while (l<=r)
    {
        int mid=(l+r)/2;
        if (sum(mid)<m) r=mid-1;
        else
        {
            res=mid;
            l=mid+1;
        }
    }
    cout<<res;
}
```

# **Quy Hoạch Động**
* **Knapsack**

**Bài 3: Chia Kẹo**

- Chưa Truy Vết

```cpp
#include <bits/stdc++.h>

using namespace std;

bool F[100005];
int n,s = 0,A[105];
int main() {
    memset(F,false,sizeof(F));
    F[0] = true;
    cin >> n;
    for (int i = 1; i <= n; ++i ) {
        cin >> A[i];
        s += A[i];
    }
    for (int i = 1; i <= n; ++i)
        for (int j = s; j >= A[i]; --j)
            if (F[j - A[i]])
                F[j] = true;
    for (int i = s/2; i >= 1; i--) if (F[i]) {
        cout << s - (i*2);
        exit(0);
    }
    return 0;
}
```

* **Không Phải Knapsack**

**Bài 3: Bitcoin**

```cpp
#include <bits/stdc++.h>

using namespace std;

double F[105],A[105],x;
int n,t;
bool Fr[105];

int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> t;
    for (int i = 1; i <= t; ++i) {
        cin >> n >> x;
        for (int j = 1; j <= n; ++j) cin >> A[j];
        F[0] = x;
        for (int j = 1; j <= n; ++j) {
            F[j] = F[j-1];
            for (int k = j-1; k >= 1; --k)
                F[j] = max(F[j],F[k]/A[k]*A[j]-F[k]/50);
        }
        cout << setprecision(5) << fixed << F[n] << "\n";
    }
    return 0;
}

```

# **Đồ Thị**
**Bài 5: Ông Bà Già Ngâu**

* Cách 1: Dùng danh sách kề

```cpp
#include <bits/stdc++.h>

using namespace std;

int n,m,s,t,d1[1005],d2[1005],minn = INT_MAX,kq,u,v,w;
vector<pair<int,int>> ke[1005];
bool Fr[1005];

void djs(int s, int d[]) {
    for (int i = 1; i <= n; ++i) {
        d[i] = INT_MAX;
        Fr[i] = true;
    }
    d[s] = 0;
    while (true) {
        int u = 0, minn = INT_MAX;
        for (int i = 1; i <= n; ++i)
            if (Fr[i] && minn > d[i]) {
                u = i;
                minn = d[i];
            }
        Fr[u] = false;
        if (u == 0) break;
        for (pair<int,int> v : ke[u])
            if (Fr[v.second] && v.first + d[u] < d[v.second]) {
                d[v.second] = d[u] + v.first;
        }
    }
}

int main() {
    cin >> n >> m >> s >> t;
    for (int i = 1; i <= m; ++i) {
        cin >> u >> v >> w;
        ke[u].push_back({w,v});
        ke[v].push_back({w,u});
    }
    djs(s,d1);
    djs(t,d2);
    for (int i = 1; i <= n; ++i)
        if (d1[i] == d2[i] && d1[i] < minn) {
            minn = d1[i];
            kq = i;
        }
    if (kq != 0) cout << kq;
        else cout << "CRY";
    return 0;
}
```
* Cách 2: Dùng mảng lưu trọng số

```cpp
#include <bits/stdc++.h>

using namespace std;

int n,m,s,t,d1[10005],d2[10005],minn = INT_MAX,kq,u,v,w,A[1005][1005];
bool Fr[10005];

void djs(int s, int d[]) {
    for (int i = 1; i <= n; ++i) {
        d[i] = INT_MAX;
        Fr[i] = true;
    }
    d[s] = 0;
    while (true) {
        int u = 0, minn = INT_MAX;
        for (int i = 1; i <= n; ++i)
            if (Fr[i] && minn > d[i]) {
                u = i;
                minn = d[i];
            }
        Fr[u] = false;
        if (u == 0) break;
        for (int v = 1; v <= n; ++v)
            if (Fr[v] && u != v && A[u][v] != INT_MAX && A[u][v] + d[u] < d[v])
                d[v] = A[u][v] + d[u];
        }
    }

int main() {
    cin >> n >> m >> s >> t;
    memset(A,INT_MAX,sizeof(A));
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= n; ++j) if (i == j) A[i][j] = 0;
            else A[i][j] = INT_MAX;
    for (int i = 1; i <= m; ++i) {
        cin >> u >> v >> w;
        A[u][v] = A[v][u] = w;
    }
    djs(s,d1);
    djs(t,d2);
    for (int i = 1; i <= n; ++i)
        if (d1[i] == d2[i] && d1[i] < minn) {
            minn = d1[i];
            kq = i;
        }
    if (kq != 0) cout << kq;
        else cout << "CRY";
    return 0;
}
```

**Bài 7: Hệ thống đảo cung cấp xăng**

```cpp
#include <bits/stdc++.h>

using namespace std;

int f,l,n,m,x,y,Q[100000],trace[10000],temp,temp2,d = 1,cnt = 0,A[10000],B[10000],C[10000];
vector<int> ke[10000];
bool visit[10000] = {false};

void truyvet(int v) {
     temp2 = trace[v];
     while (trace[temp2] != -1) {
          cnt ++;
          C[cnt] = temp2;
          //cout << temp2 << endl;
          temp2 = trace[temp2];

     }
     cout << cnt << "\n";
     for (int i = cnt; i>=1; i--) cout << C[i] << " " ;
}

void bfs(int s) {
     f = l = 1;
     Q[l] = s;
     trace[s] = -1;
     visit[s] = true;
     while (f <= l) {
          temp = Q[f];
          f++;
          for (int v : ke[temp]) if (! visit[v]) {
               visit[v] = true;
               trace[v] = temp;
               l++;
               Q[l] = v;
               if (v == y ) {
                    truyvet(v);
                    exit(0);
               }
          }
     }
}

int power(int a) {
     return a*a;
}

int main() {
     cin >> n >> m >> x >> y;
     for (int i = 1; i <= n; ++i) cin >> A[i] >> B[i];
     for (int i = 1; i<= n-1; ++i)
          for (int j = i +1; j<= n; ++j)
               if ((power(A[j]-A[i]) + power(B[j]-B[i])) < power(m)){
                         ke[i].push_back(j);
                         ke[j].push_back(i);
                    }
     bfs(x);
     cout << "-1";
     return 0;
}
```



