Talk is Cheap, Show Me the Code!

0%

AtCoder 186

Posted on In

A - Brick
At most how many bricks can be loaded?

brick.cppview raw
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <iostream>
#include <string>
#include <cstring>
#include <vector>
#include <algorithm>
#include <cmath>
#include <queue>
#include <set>
using namespace std;


int main(){
    int n, w;
    cin>>n>>w;
    cout<<n/w<<endl;
    return 0;
}

B - Blocks on Grid
Print the minimum number of blocks that must be removed.

blocks-on-grid.cppview raw
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include <iostream>
#include <string>
#include <cstring>
#include <vector>
#include <algorithm>
#include <cmath>
#include <queue>
#include <set>
using namespace std;

const int N = 110, INF = 0x3f3f3f3f;
int a[N][N];
int main() {
    int n, m;
    cin>>n>>m;
    int k = INF;
    for(int i=0;i<n;i++)
        for(int j=0;j<m;j++) {
            scanf("%d", &a[i][j]);
            k = min(k, a[i][j]);
        }
    int res = 0;
    for(int i=0;i<n;i++)
        for(int j=0;j<m;j++)
            res += a[i][j] - k;
    cout<<res<<endl;
    return 0;
}

C - Unlucky 7
Number of digits in octal and decimal format from 1 to N.

unlucky-7.cppview raw
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include <iostream>
#include <string>
#include <cstring>
#include <vector>
#include <algorithm>
#include <cmath>
#include <queue>
#include <set>
using namespace std;

bool to_oct(int x){
    string s;
    while(x) {
        s = to_string(x % 8) + s;
        x /= 8;
    }
    for(int j=0;j<s.size();j++)
        if(s[j]=='7') return true;
    return false;
}

bool to_dec(int x){
    string s = to_string(x);
    for(int j=0;j<s.size();j++)
        if(s[j]=='7') return true;
    return false;
}

int main(){
    int n;
    cin>>n;
    int s = 0;
    for(int i=1;i<=n;i++){
        if(to_dec(i) || to_oct(i)) s++;
    }
    cout<<n-s<<endl;
    return 0;
}

D - Sum of difference
Calculate |A_i - A_j| for all pairs of i, j in O(NlogN) time.

sum-of-diff.cppview raw
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include <iostream>
#include <string>
#include <cstring>
#include <vector>
#include <algorithm>
#include <cmath>
#include <queue>
#include <set>
using namespace std;

const int N = 200010;
int a[N];

typedef long long LL;

int main(){
    int n;
    cin>>n;
    LL s = 0;
    for(int i=1;i<=n;i++){
        scanf("%d", &a[i]);
        s += a[i];
    }
    sort(a+1, a+n+1);
    LL res = 0;
    for(int i=1;i<=n;i++){
        s -= a[i];
        res += s  - (LL)(n-i) * a[i];
    }
    cout<<res<<endl;
    return 0;

}

E - Throne
N chairs arranged in a circle, S is the initial offset.
Move K chairs away each time. Minimum move to go back the first location?

throne.cppview raw
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include <iostream>

using namespace std;

typedef long long ll;

int exgcd(int a, int b, ll &x, ll &y){
    if(!b){
        x = 1, y = 0;
        return a;
    }
    int d= exgcd(b, a % b, y, x);
    y -= a/b  * (ll)x;
    return d;
}

int main() {
    int t;
    cin>>t;

    while (t--) {
        ll n,s,k;
        cin>>n>>s>>k;
        ll x, y;
        s = n-s;
        int g=exgcd(k, n, x, y);
        if (s%g!=0) {
            cout<<"-1\n";
            continue;
        }

        x = (ll)x * (s/g);
        x = (x%(n/g) + n/g) % (n/g);
        cout<<x<<endl;
    }

    return 0;
}

F - Rook on Grid
Given a 2-d grid and some obstacles. Print the number of cells that can be reached with the following two moves.

  1. Move down followed by move right;
  2. Move right followed by move down;

Idea: First add all the cells that can be reached with approach 1. Second add remaining cells that can only be reached with approach 2.
Use sweep line + bit tree to get O(NlogN) complexity.
For each line, consider the first obstacle. Cells left of this obstacle can use approach 1.
For cells right of this obstacle, it may be reached with approach 2.
tr[i] is the number of rows from 1~ith row, that has an obstacle on the left of the current enumerating column.

rook-on-grid.cppview raw
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
#include <iostream>
#include <vector>
using namespace std;

const int N = 2e5 + 10;
int r[N], c[N];
typedef long long LL;

int tr[N];
int h, w;

int lowbit(int x){
    return x & -x;
}

void add(int x, int v){
    for(int i=x;i<=h;i+=lowbit(i)) {
        tr[i] += v;
    }
}

int sum(int x){
    int res =0;
    for(int i=x;i;i-=lowbit(i)){
        res += tr[i];
    }
    return res;
}

int main(){
    int m;
    cin>>h>>w>>m;
    for(int i=1;i<=h;i++) r[i] = w+1;
    for(int j=1;j<=w;j++) c[j] = h+1;
    while(m--){
        int x,y;
        scanf("%d%d", &x, &y);
        r[x] = min(r[x], y);
        c[y] = min(c[y], x);
    }
    LL res = 0;
    bool flag = 0;
    for(int i=1;i<=h;i++) {
        if(flag) {r[i] = 1; continue;}
        if(r[i]==1) {flag = 1; continue;}
        res += r[i] - 1;
    }
    vector<int> v[w+2];
    for(int i=1;i<=h;i++) v[r[i]].push_back(i);

    for(int j=1;j<=w;j++){
        if(c[j]==1) break; //important
        res += sum(c[j] -1);
        for(int i: v[j]) add(i, 1);
    }
    printf("%lld\n", res);
    return 0;
}