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

loading image

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();
}

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.
  • 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();
}

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.

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;
}
This post is licensed under CC BY 4.0 by the author.

Linked List | 450 DSA | Love Babbar

Binary Tree | 450 DSA | Love Babbar