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.
#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();
}
C - 1111gal password
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();
}
C - 1111gal password
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;
}