Atcoder Contests 2022
Post
Cancel

# Atcoder Contests 2022

## February

### ABC 239

#### A - Horizon

Assuming that the horizon seen from a place x meters above the ground is x(12800000+x) meters away, find how many meters away the horizon seen from a place H meters above the ground is.

```1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 #include <bits/stdc++.h> using namespace std; typedef long long int ll; void solve() { long double h; cin >> h; long double tmp = h*(12800000 + h); cout << fixed << setprecision(7) << sqrt(tmp) << endl; } int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); solve(); } ```

#### B - Integer Division

Given an integer X between −10^-18 and 10^18 (inclusive), print ⌊10/X​⌋.

```1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 #include <bits/stdc++.h> using namespace std; typedef long long int ll; void solve() { long double n; cin >> n; cout << n / 10 - (n % 10 < 0) << "\n"; } int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); solve(); } ```

#### C - Knight Fork

On an xy-coordinate plane, is there a lattice point whose distances from two lattice points (x1, y1) and (x2, y2) are both √5.

```1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 #include <bits/stdc++.h> using namespace std; typedef long long int ll; bool solve() { long double x1, x2, y1, y2; cin >> x1 >> y1 >> x2 >> y2; long double sum = pow((x1 - x2), 2) + pow((y1 - y2), 2); if (sum == 16 or sum == 20 or sum == 18 or sum == 10 or sum == 4 or sum == 2) return true; return false; } int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); if(solve()) cout << "YES\n"; else cout << "NO\n"; } ```

## March

### ABC 242

#### A - Horizon

In a certain programming contest, T-shirts are awarded to participants according to the following rules.

• All participants who ranked A-th or higher get a T-shirt.
• Additionally, from the participants who ranked between (A+1)-th and B-th (inclusive), C participants chosen uniformly at random get a T-shirt.

There were 1000 participants in this contest, and all of them got different ranks. Iroha-chan, who participated in this contest, ranked X-th. Find the probability that she gets a T-shirt.

```1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 #include <bits/stdc++.h> using namespace std; typedef long long int ll; void solve() { long double a,b,c,x; cin >> a >> b >> c >> x; if(x <= a) cout << fixed << setprecision(7) << 1. << endl; else if(x <= b) cout << fixed << setprecision(7) << c/(b-a) << endl; else cout << fixed << setprecision(7) << 0. << endl; } int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); solve(); } ```

#### B - Integer Division

Given an integer X between −10^-18 and 10^18 (inclusive), print ⌊10/X​⌋.

```1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 #include <bits/stdc++.h> using namespace std; typedef long long int ll; void solve() { string str; cin >> str; sort(str.begin(), str.end()); cout << str << endl; } int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); solve(); } ```

Given an integer N, find the number of integers X that satisfy all of the following conditions, modulo 998244353.

• X is an N-digit positive integer.
• Let X1, X2, …, XN
• 1≤Xi≤9 for all integers 1≤i≤N;
• ∣Xi −Xi+1∣≤1 for all integers 1≤i≤N−1.
• abc242_c
```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 #include <bits/stdc++.h> using namespace std; #define MOD 998244353 typedef long long int ll; void solve() { ll n, ans(0); cin >> n; vector<vector<ll>> dp( n+1 , vector<ll> (10, 0)); for(ll i=0; i<n; i++) { for(ll j=1; j<10; j++) { if (i) { dp[i][j] += dp[i-1][j]; dp[i][j] %= MOD; if (j != 1) dp[i][j] += dp[i-1][j-1]; if (j != 9) dp[i][j] += dp[i-1][j+1]; } else dp[i][j] = 1; dp[i][j] %= MOD; } } for (ll i=1; i<10; i++) { ans += dp[n-1][i]; ans %= MOD; } cout << ans << endl; } int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); solve(); } ```

## April

### ABC 246

#### A - Four Points

There is a rectangle in the xy-plane. Each edge of this rectangle is parallel to the x- or y-axis, and its area is not zero.

Given the coordinates of three of the four vertices of this rectangle, find the coordinates of the other vertex.

```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 #include <bits/stdc++.h> using namespace std; typedef long long int ll; void solve() { int a,b,c,d,e,f; cin >> a >> b>> c >> d >> e >> f; if(a == c) cout << e; else if(a == e) cout << c; else cout << a; cout << " "; if(b == d) cout << f; else if(b == f) cout << d; else cout << b; cout << endl; } int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); solve(); } ```

#### B - Get Closer

From the point (0,0) in a two-dimensional plane, let us move the distance of 1 toward the point (A,B). Find our coordinates after the move.

Here, after moving the distance of d from a point X to a point Y (d≤ length of the segment XY), we are at the point on the segment XY whose distance from X is d. The Constraints guarantee that the distance between the points (0,0) and (A,B) is at least 1.

```1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 #include <bits/stdc++.h> using namespace std; typedef long long int ll; void solve() { double a,b,c,x,y; cin >> a >> b; c = sqrt((a * a) + (b * b)); x = a/c; cout << fixed << setprecision(12) << x << " " << sqrt(1.0 - (x * x)) << endl; } int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); solve(); } ```

There are N items in a shop. For each i=1,2,…,N, the price of the i-th item is Ai yen (the currency of Japan).

Takahashi has K coupons. Each coupon can be used on one item. You can use any number of coupons, possibly zero, on the same item. Using k coupons on an item with a price of a yen allows you to buy it for max{a−kX,0} yen.

Print the minimum amount of money Takahashi needs to buy all the items.

```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 #include <bits/stdc++.h> using namespace std; typedef long long int ll; ll solve() { ll n, k, x, i = 0, d, ans = 0; cin >> n >> k >> x; vector<ll> vec(n); for (; i < n; i++) cin >> vec[i]; for (i = 0; i < n; i++) { d = (vec[i] - (vec[i] % x)) / x; if (d < k) { vec[i] -= d * x; k -= d; } else { vec[i] = vec[i] - k * x < 0 ? 0 : vec[i] - k * x; k = 0; break; } } if (k > 0) { sort(vec.begin(), vec.end(), greater<int>()); i = 0; while (k > 0 && i < n) { vec[i++] = 0; k--; } } return accumulate(vec.begin(), vec.end(), 0); } int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); ll sol = solve(); cout << sol << endl; } ```

## June

### ARC 142

#### B - Unbalanced Squares

For a positive integer x, let f(x) be the answer to the question below.

The following operation on x can be performed zero or more times.

Let x′ be the integer obtained by reversing the decimal notation of x. Then, replace x with x′. If x now has one or more leading zeros, delete them so that it begins with a non-zero digit.

For example, from x=1420, you get x=241 after one operation, x=142 after two operations, and x=241 after three operations.

Find the minimum possible value of x after operations.

Find the number of integers x such that 1≤x≤N and f(x)=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 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 #include <bits/stdc++.h> using namespace std; typedef long long ll; int main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); ll n, k; cin >> n >> k; ll tmp = k; ll rev = 0; while (tmp > 0) { rev *= 10; rev += tmp % 10; tmp = tmp / 10; } ll ans = 0, front = k, rear = rev; if (rev < k) { ans = 0; } else if (rev == k) { while (front <= n) { ans++; front *= 10; } } else { while (front <= n) { ans++; front *= 10; } while (rear <= n) { ans++; rear *= 10; } } cout << ans << endl; return 0; } ```

#### B - Unbalanced Squares

We have an N×N grid. Let (i,j) denote the square at the i-th row from the top and j-th column from the left in this grid. Find one way to write an integer on every square to satisfy the conditions below.

• Each integer between 1 and N*N is written exactly once.
• For every pair of integers i,j(1≤i,j≤N), the square (i,j) satisfies the following.
• Among the squares horizontally, vertically, or diagonally adjacent to (i,j) (there are at most eight of them), let a and b be the number of squares with integers larger than and smaller than that of (i,j), respectively. Then, a != b holds.

Under the Constraints of this problem, it can be proved that such a way to write integers always exists.

```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 #include <bits/stdc++.h> using namespace std; typedef long long ll; int main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); ll i = 1, printed = 0, front = 1, rear, n, mid, lim; cin >> n; lim = n * n; rear = lim; while(i <= lim){ if(printed and printed%n == 0) {cout << endl; printed = 0;} cout << rear << " "; i++; if(i > lim) break; rear--; printed++; if(printed and printed%n == 0) {cout << endl; printed = 0;} cout << front << " "; i++; if(i > lim) break; front++; printed++; } return 0; } ```