# Atcoder Contests 2022

Posted on Dec 25, 2020

## 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.

``````#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​⌋.

``````#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. ``````#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.

``````#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​⌋.

``````#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.
``````#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.

``````#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.

``````#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.

``````#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.

``````#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.

``````#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;
}
``````

## November

### ABC 279

#### A - wwwvvvvvv

You are given a string S consisting of v and w.

Print the number of “bottoms” in the string S (see the figure at Sample Input/Output).

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

typedef long long ll;

void solve()
{
string s;
ll ans(0);
cin >> s;
for(char ch:s)
ans += ch == 'v' ? 1 : 2;
cout << ans << endl;

}

int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
solve();
return 0;
}
``````

#### B - LOOKUP

You are given strings S and T consisting of lowercase English letters. Determine whether T is a (contiguous) substring of S.

A string Y is said to be a (contiguous) substring of X if and only if Y can be obtained by performing the operation below on X zero or more times.

• Do one of the following.
• Delete the first character in X.
• Delete the last character in X.

For instance, tag is a (contiguous) substring of voltage, while ace is not a (contiguous) substring of atcoder.

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

typedef long long ll;

void solve()
{
string s;
ll ans(0);
cin >> s;
for(char ch:s)
ans += ch == 'v' ? 1 : 2;
cout << ans << endl;

}

int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
solve();
return 0;
}
``````