【ATcoder】AtCoder Beginner Contest 165

#include <iostream>
#include <cstdio>
using namespace std;
int a, b, k;
int main() {
    cin >> k;
    cin >> a >> b;
    for (int i = a; i <= b; i++) {
        if (i % k == 0) {
            cout << "OK";
            return 0;
        }
    }
    cout << "NG";
    return 0;
}

#include <iostream>
#include <cstdio>
using namespace std;
long long cur = 100;
long long n;
int main() {
    cin >> n;
    for (int i = 1; i <= 10000; i++) {
        cur = cur + cur * 0.01;
        if (cur >= n) {
            cout << i;
            return 0;
        }
    }
    return 0;
}

#include <iostream>
#include <cstdio>
using namespace std;
int n, m, q;
int a[100], b[100], c[100], d[100];
int s[20], ans;
void dfs(int cur, int lst) {
    if (cur > n) {
        int cnt = 0;
        for (int i = 1; i <= q; i++) {
            if (s[b[i]] - s[a[i]] == c[i]) {
                cnt += d[i];
            }
        }
        ans = max(ans, cnt);
        return;
    }
    for (int i = lst; i <= m; i++) {
        s[cur] = i;
        dfs(cur + 1, i);
    }
}
int main() {
    cin >> n >> m >> q;
    for (int i = 1; i <= q; i++) {
        cin >> a[i] >> b[i] >> c[i] >> d[i];
    }
    dfs(1, 1);
    cout << ans;
    return 0;
}

#include <iostream>
#include <cstdio>
using namespace std;
long long a, b, n;
int main() {
    cin >> a >> b >> n;
    long long i = min(b - 1, n);
    cout << (a * i) / b - a * (i / b) << " ";
    return 0;
}

#include <iostream>
#include <cstdio>
using namespace std;
int n, m;
int main() {
    cin >> n >> m;
    for (int i = 1, j = m + 1; i < j; i++, j--) {
        cout << i << " " << j << endl;
    }
    for (int i = m + 2, j = 2 * m + 1; i < j; i++, j--) {
        cout << i << " " << j << endl;
    }
    return 0;
}

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
struct node{
    int pre, to;
}edge[400010];
int head[200010], tot;
int n, a[200010];
int low[200010], cnt;
int ans[200010];
void add(int u, int v) {
    edge[++tot] = node{head[u], v};
    head[u] = tot;
}
void dfs(int x, int fa) {
    ans[x] = cnt;
    for (int i = head[x]; i; i = edge[i].pre) {
        int y = edge[i].to;
        if (y != fa) {
            if (low[cnt] < a[y]) {
                int b = cnt;
                low[++cnt] = a[y];
                dfs(y, x);
                cnt = b;
            } else {
                int p = lower_bound(low + 1, low + cnt + 1, a[y]) - low;
                int v = low[p];
                low[p] = a[y];
                dfs(y, x);
                low[p] = v;
            }
        }
    }
}
int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    for (int i = 1, u, v; i < n; i++) {
        cin >> u >> v;
        add(u, v);
        add(v, u);
    }
    low[++cnt] = a[1];
    ans[1] = cnt;
    dfs(1, 0);
    for (int i = 1; i <= n; i++) {
        cout << ans[i] << "\n";
    }
    return 0;
}