# AtCoder Beginner Contest 186 题解

# Problem A - Brick (opens new window)

n, w = map(int, input().split())
print(n // w)

1
2

# Problem B - Blocks on Grid (opens new window)

def read_int():
return int(input())

return map(int, input().split(' '))

lo = 100
s = 0
for i in range(h):
lo = min(lo, min(row))
s += sum(row)
print(s - lo * h * w)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

# Problem C - Unlucky 7 (opens new window)

n = int(input())
ans = 0
for i in range(1, n + 1):
if '7' in str(i) or '7' in oct(i):
continue
ans += 1
print(ans)

1
2
3
4
5
6
7

# Problem D - Sum of difference (opens new window)

\begin{aligned} \sum_{i=1}^{N-1}\sum_{j=i+1}^N|A_i-A_j|&=\frac{1}{2}\sum_{i=1}^{N-1}\sum_{j=i+1}^N2|A_i-A_j|\\ &=\frac{1}{2}\sum_{i=1}^{N-1}\sum_{j=i+1}^N|A_i-A_j|+|A_j-A_i|\\ &=\frac{1}{2}\sum_{i=1}^{N}\sum_{j=1}^N|A_i-A_j| \end{aligned}

n = int(input())
a = list(map(int, input().split()))
a.sort()
r = sum(a)
ans = 0
l = 0
for i in range(n):
r -= a[i]
ans += r - (n - 1 - i) * a[i] + i * a[i] - l
l += a[i]
print(ans // 2)

1
2
3
4
5
6
7
8
9
10
11

# Problem E - Throne (opens new window)

$X$为移动次数，$Y$为移动圈数，则有：

$XK+S=YN$

$YN-XK=S$

$Y'N+X'K=gcd(N,K)$

$Y''N+X''K=S$

def exgcd(a, b):
s = 0
olds = 1
t = 1
oldt = 0
r = b
oldr = a
while r:
q = oldr // r
oldr, r = r, oldr-q*r
olds, s = s, olds-q*s
oldt, t = t, oldt-q*t
return oldr, olds, oldt

t = int(input())
for _ in range(t):
n, s, k = map(int, input().split())
g, a, b = exgcd(n, k)
if s % g != 0:
print(-1)
else:
a *= s // g
b *= s // g
lcm = n * k // g
print(((a * n - s) % lcm + lcm) % lcm // k)

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

# Problem F - Rook on Grid (opens new window)

#include <algorithm>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <iostream>
#include <vector>

using namespace __gnu_pbds;
using namespace std;
typedef long long ll;
typedef tree<int, null_type, less_equal<>, rb_tree_tag,
tree_order_statistics_node_update>
indexed_set;

int main() {
int h, w, m;
cin >> h >> w >> m;
vector<int> x(m), y(m);
vector<int> hlimit(h + 1, w), wlimit(w + 1, h);
for (int i = 0; i < m; ++i) {
cin >> x[i] >> y[i];
hlimit[x[i]] = min(hlimit[x[i]], y[i] - 1);
wlimit[y[i]] = min(wlimit[y[i]], x[i] - 1);
}
ll ans = 0;
for (int i = 1; i <= hlimit[1]; ++i)
ans += wlimit[i];
vector<pair<int, int>> v;
for (int i = 2; i <= wlimit[1]; ++i)
v.emplace_back(hlimit[i], i);
sort(v.begin(), v.end());
indexed_set s;
int r = 0;
for (auto [hl, i] : v) {
while (r < hl && r < hlimit[1])
s.insert(wlimit[++r]);
int dup = s.size() - s.order_of_key(i - 1);
ans += hlimit[i] - dup;
}
cout << ans << endl;
}
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