# Bài làm các đề thi thành phố vòng 1

## Link đề thi
[đề thi thành phố vòng 1](http://www.chuyentin.pro/search/label/%C4%90%E1%BB%81%20thi%20hoc%20sinh%20gi%E1%BB%8Fi%20tin%20h%E1%BB%8Dc%20l%E1%BB%9Bp%2012%20th%C3%A0nh%20ph%E1%BB%91%20H%C3%A0%20N%E1%BB%99i)

## 2018

### Bài 1

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

const int MN = 1e6 + 7;
long long n;
bool unpr[MN];
int pr[MN], lim;

void sieve() {
    unpr[0] = true; unpr[1] = true;
    pr[lim] = 1;
    for (int i = 2; i*i < MN; i++) {
        if (unpr[i]) continue;
        pr[++lim] = i;
        for (int j = i*i; j < MN; j += i) unpr[j] = true;
    }
}

void process() {
    cin >> n;
    long long ans = -1;
    for (int i = 1; i <= lim; i++) {
        if (pr[i]*pr[i+1]*pr[i+2] > n) break;
        ans = pr[i]*pr[i+1]*pr[i+2];
    }
    cout << ans << "\n";
}

int main() {
    freopen("BAI1.INP", "r", stdin); 
    freopen("BAI1.OUT", "ư", stdout); 
    int t;
    cin >> t;
    sieve();
    while (t--) process();
    return 0;
}

### Bài 2

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

const int MN = 1e5 + 5;
int n;
int a[MN], p[MN];
long long ans;

int main() {
    freopen("BAI2.INP", "r", stdin); 
    freopen("BAI2.OUT", "ư", stdout); 
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 1; i <= n; i++) cin >> p[i];
    int save = p[1], flag = 0;
    for (int i = 1; i <= n; i++) {
        if (p[i] < save) {
            ans += flag * save;
            save = p[i]; flag = 0;
        }
        flag += a[i];
    }
    ans += flag * save;
    cout << ans;
    return 0;
}

### Bài 3

> Chưa làm

### Bài 4

> Chưa làm

## 2019

### Bài 1

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

long long n, ans;

int main() {
    freopen("BAI1.INP", "r", stdin); 
    freopen("BAI1.OUT", "w", stdout); 
    cin >> n;
    n *= 2;
    for (long i = 1; i <= sqrt(n); i++) {
        if (n % i == 0) {
            long long t = (n/i)-i+1;
            if (t % 2 == 0) ans++;
        }
    }
    cout << ans;
    return 0;
}

### Bài 2

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

int a, b, k;
long long n;

int main() {
    freopen("BAI2.INP", "r", stdin);
    freopen("BAI2.OUT", "w", stdout);
    cin >> a >> b >> k;
    k -= 10;
    long long t = 100;
    while (1) {
        long long ok = a*t+b;
        if (ok % k == 0) {
            n = ok/k;
            break;
        }
        t *= 10;
    }
    cout << n;
    return 0;
}

### Bài 3

> Chưa làm

### Bài 4

> Chưa làm

## 2020

### Bài 1

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

#define ll long long

ll l, r;

ll sum(ll s, ll e) {
    return (e+s)*(e-s+1)/2;
}

ll bs(ll s, ll e) {
    ll mid = (s+e)/2;
    ll sum1 = sum(l, mid), sum2 = sum(mid+1, r);
    if (s >= e) {
        return mid;
    }
    if (sum1 == sum2) return mid;
        else if (sum1 < sum2) s = mid+1;
        else e = mid;
    return bs(s, e);
}

int main() {
    freopen("BAI1.INP", "r", stdin);
    freopen("BAI1.OUT", "w", stdout);
    cin >> l >> r;
    ll m = (l+r)/2;
    ll ans = m; 
    for (ll i = m; i < r; i++) {
        if (sum(l,i) >= sum(i+1,r)) {
            if (sum(i,r)-sum(l,i-1) >= sum(l,i)-sum(i+1,r)) ans = i;
                else ans = i-1;
            break;
        }
    }
    cout << ans;
    return 0;
}

### Bài 2

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

string s;
bool ok;
long long sum;

int main() {
    freopen("BAI2.INP", "r", stdin);
    freopen("BAI2.OUT", "w", stdout);
    cin >> s;
    for (auto c : s) {
        int t = c - '0';
        if (t == 0) ok = true;
        sum += t;
    }
    if (ok && (sum % 3 == 0)) {
        sort(s.begin(), s.end(), greater<>());
        cout << s;
    } else cout << -1;
    return 0;
}

### Bài 3

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

const int MN = 1e5 + 5;
int n, m;
int node[MN*4];
int ans;

void update(int l, int r, int id, int u, int v) {
    if (l > v || r < u) return;
    if (u <= l && r <= v) {
        node[id]++;
        return;
    }
    int mid = (l+r)/2;
    update(l, mid, id*2, u, v);
    update(mid+1, r, id*2+1, u, v);
}

void lazy(int l, int r, int id) {
    if (l >= r) {
        ans = max(ans, node[id]);
        return;
    }
    node[id*2] += node[id];
    node[id*2+1] += node[id];
    node[id] = 0;
    int mid = (l+r)/2;
    lazy(l, mid, id*2);
    lazy(mid+1, r, id*2+1);
}

int source(int l, int r, int id) {
    if (l >= r) {
        if (node[id] == ans) return 1;
        return 0;
    }
    int mid = (l+r)/2;
    return source(l, mid, id*2) + source(mid+1, r, id*2+1);
}

int main() {
    freopen("BAI3.INP", "r", stdin);
    freopen("BAI3.OUT", "w", stdout);
    cin >> n >> m;
    int l, r;
    while (m--) {
        cin >> l >> r;
        if (l <= r) update(1, n, 1, l, r);
        else {
            update(1, n, 1, 1, r);
            update(1, n, 1, l, n);
        }
    }
    lazy(1, n, 1);
    cout << ans << " " << source(1, n, 1);
    return 0;
}

### Bài 4

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

const int MN = 1005;
int n, m;
int a[MN][MN];
int vs[MN][MN];
int x, y, z, t;
int dir[4][2] = { {1,0}, {0,1}, {-1,0}, {0,-1} };

int bfs() {
    queue<pair<int,int>> q;
    vs[x][y] = 1;
    q.push({x,y});

    while (q.size()) {
        int u = q.front().first;
        int v = q.front().second;
        q.pop();

        if (!vs[u][v]) continue;

        for (int i = 0; i < 4; i++) {
            int uu = u + dir[i][0];
            int vv = v + dir[i][1];

            if (vs[uu][vv] || a[uu][vv] == 0) continue;
            vs[uu][vv] = vs[u][v] + 1;
            if (uu == z && vv == t) return vs[uu][vv];
            q.push({uu,vv});
        }
    }
    return 0;
}

int main() {
    freopen("BAI4.INP", "r", stdin);
    freopen("BAI4.OUT", "w", stdout);
    cin >> n >> m;
    cin >> x >> y >> z >> t;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cin >> a[i][j];
        }
    }
    cout << bfs()-1;
    return 0;
}

## 2021

### Bài 1

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

int a = 1;

int main() {
    freopen("TBS.INP", "r", stdin);
    freopen("TBS.OUT", "w", stdout);
    double j;
    for (int i = 0; i < 4; i++) {
        cin >> j;
        if (j == 0) a = 0;
            else if (j < 0) a *= -1;
    }
    cout << a;
    return 0;
}

### Bài 2

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

int a = 1;
long long n;

int main() {
    freopen("DKT.INP", "r", stdin);
    freopen("DKT.OUT", "w", stdout);
    cin >> n;
    long long ans = n*(n+1)/2;
    ans %= 26;
    char c = ans + 'A';
    cout << c;
    return 0;
}

### Bài 3

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

#define ll long long

const int MN = 1e5 + 5;
int n, k;
map<ll,ll> m;
vector<ll> v;
ll ans;

int main() {
    freopen("DC.INP", "r", stdin);
    freopen("DC.OUT", "w", stdout);
    cin >> n >> k;
    ll a, b;
    for (int i = 1; i <= n; i++) {
        cin >> a >> b;
        ++b;
        m[a] += 1; m[b] -= 1;
        v.push_back(a); v.push_back(b);
    }
    sort(v.begin(), v.end());
    ll t = 0, save = 0;
    for (auto c : v) {
        if (m[c] == 0) continue;
        t += m[c]; m[c] = 0;
        if (t == k) save = c;
            else {
                if (save != 0) ans += c - save;
                save = 0;
            }
    }
    cout << ans;
    return 0;
}

### Bài 4

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

const int MN = 1e5 + 5;
int n, m, k;
int vs[MN], r[MN];
vector<int> g[MN], bv;
int mx, mn = MN;
int ans;

void tree() {
    queue<int> q;
    vs[1] = -1; r[1] = 1;
    q.push(1);

    while (q.size()) {
        int u = q.front();
        q.pop();

        for (auto v : g[u]) {
            if (vs[v] != 0) continue;
            vs[v] = u; r[v] = r[u]+1;
            q.push(v);
        }
    }
}

int trace(int u, int v) {
    if (r[u] < r[v]) swap(u,v);
    int k = 0;
    while (r[u] > r[v]) {
        u = vs[u];
        k++;
    }
    while (u != v) {
        u = vs[u];
        v = vs[v];
        k += 2;
    }
    return k;
}

int main() {
    freopen("BV.INP", "r", stdin);
    freopen("BV.OUT", "w", stdout);
    cin >> n >> m >> k;
    for (int i = 1, u, v; i < n; i++) {
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    for (int i = 1, j; i <= m; i++) {
        cin >> j;
        bv.push_back(j);
    }
    tree();
    for (int i = 1; i <= n; i++) {
        bool ok = true;
        for (auto v : bv) {
            if (trace(i,v) > k) {
                ok = false;
                break;
            }
        }
        if (ok) ans++;
    }
    cout << ans;
    return 0;
}

### Bài 5

> Chưa làm

## 2022

### Bài 1

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

const int MN = 1e6 + 6;
long long a, b;
bool unpr[MN];
long long ans;

void sieve() {
    unpr[0] = 1; unpr[1] = 1;
    for (int i = 2; i*i < MN; i++) {
        if (unpr[i]) continue;
        for (int j = i*i; j < MN; j += i) unpr[j] = 1;
    }
}

int main() {
    freopen("CP.INP", "r", stdin);
    freopen("CP.OUT", "w", stdout);
    cin >> a >> b;
    sieve();
    for (long long i = ceil(sqrt(a)); i <= sqrt(b); i++) {
        if (!unpr[i]) ans++;
    }
    cout << ans;
    return 0;
}

### Bài 2

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

long long n, x;
long long ans;

int main() {
    freopen("BS.INP", "r", stdin);
    freopen("BS.OUT", "w", stdout);
    cin >> n >> x;
    for (int i = 1, j; i <= sqrt(x); i++) {
        if (x%i) continue;
        j = x/i;
        if (j > n || i > n) continue;
        ans += 2;
        if (j == i) ans--;
    }
    cout << ans;
    return 0;
}

### Bài 3

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

const int MN = 505;
const int MX = 1e5 + 5;
long lim;
int n;
int a[MN];
bool dp[MN][MX];

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        lim += a[i];
    }
    dp[0][0] = true;
    for (int i = 1; i <= n; i++) {
        for (long j = 0; j <= lim; j++) {
            dp[i][j] = dp[i-1][j];
            if (j >= a[i]) dp[i][j] = dp[i-1][j] || dp[i-1][j-a[i]];
        }
    }
    for (long i = lim; i > 0; i--) {
        int t = i/2;
        if (i % 2 == 0 && dp[n][i] && dp[n][t]) {
            cout << t;
            break;
        }
    }
    return 0;
}

### Bài 4

> Chưa làm

### Bài 5

> Chưa làm

:::info
Đức Huy
:::