Tests

Class Test 1

1. `230B` - T-primes

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

bool is_prime(long long x)
{
    if (x < 2)
        return false;

    for (long long i = 2; i * i <= x; i++)
        if (x % i == 0)
            return false;

    return true;
}

void solve()
{
    long long n;
    cin >> n;

    long long root = sqrt(n);

    if (root * root == n && is_prime(root))
        cout << "YES" << '\n';
    else
        cout << "NO" << '\n';
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t;
    cin >> t;

    while (t--)
        solve();

    return 0;
}

2. `2218A` - The 67th Integer Problem

CF link: 2218A - The 67th Integer Problem

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

void solve()
{
    int x;
    cin >> x;

    if (x < 67)
        cout << x + 1 << '\n';
    else
        cout << x << '\n';
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t;
    cin >> t;

    while (t--)
        solve();

    return 0;
}

3. `2218E` - The 67th XOR Problem

CF link: 2218E - The 67th XOR Problem

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

void solve()
{
    int n;
    cin >> n;

    int ans = 0;

    vector<int> arr(n);
    for (int &x : arr)
        cin >> x;

    for (int i = 0; i < n; i++)
        for (int j = i + 1; j < n; j++)
            ans = max(ans, arr[i] ^ arr[j]);

    cout << ans << '\n';
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t;
    cin >> t;

    while (t--)
        solve();

    return 0;
}

4. Change minimum characters in binary string so that it becomes perfectly alternating

Question:

Perfect alternating binary string can be:

010101...
101010...

Find minimum number of character changes needed.

Answer:

Count mismatches against both target patterns. Take minimum.

int minChanges(string s) {
    int c1 = 0, c2 = 0;
    for (int i = 0; i < s.size(); i++) {
        if (s[i] != (i % 2 ? '1' : '0')) c1++;
        if (s[i] != (i % 2 ? '0' : '1')) c2++;
    }
    return min(c1, c2);
}

5. Find maximum possible sum from array after removing at most one element

Question:

Find maximum possible array sum if you may remove at most one element.

Answer:

Compute total sum. Remove most negative element if one exists.

long long maxSum(vector<int>& a) {
    long long sum = 0;
    int mn = INT_MAX;

    for (int x : a) {
        sum += x;
        mn = min(mn, x);
    }

    if (mn < 0) sum -= mn;
    return sum;
}

6. Count number of segments of consecutive equal characters of given string

Question:

Given string, count segments of consecutive equal characters.

Answer:

Start with 1 segment if string non-empty. Each character change starts new segment.

int countSegments(string s) {
    if (s.empty()) return 0;

    int cnt = 1;
    for (int i = 1; i < s.size(); i++) {
        if (s[i] != s[i - 1]) cnt++;
    }
    return cnt;
}

Example:

aaabbcca
Segments:
aaa | bb | cc | a
Answer = 4

7. Count number of subarrays where sum is `0`

Question:

Count all subarrays with sum 0.

Answer:

Use prefix sum frequency map.

long long countZeroSum(vector<int>& a) {
    unordered_map<long long, long long> mp;
    mp[0] = 1;

    long long pref = 0, ans = 0;

    for (int x : a) {
        pref += x;
        ans += mp[pref];
        mp[pref]++;
    }

    return ans;
}

Example:

a = {1, -1, 2, -2}

Zero-sum subarrays:
[1,-1]
[2,-2]
[1,-1,2,-2]

Answer = 3

8. TODO list using array

Question:

Alex wants to develop TODO list task manager but he only has concept of array. Operations:

Add TaskDelete TaskShow Task

If empty, print no task.

Input:

7
1 shop
1 study
1 sleep
3
2 sleep
1 exercise
3

Output:

shop study sleep
shop study exercise

Input:

3
1 taskA
2 taskA
3

Output:

no task

Answer:

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

vector<string> arr;

void show_task()
{
    for (auto s : arr)
        cout << s << " ";
    cout << '\n';
}

void solve()
{
    int n;
    cin >> n;

    string s;

    if (n == 1)
    {
        cin >> s;
        arr.push_back(s);
    }
    else if (n == 2)
    {
        cin >> s;
        auto it = find(arr.begin(), arr.end(), s);
        arr.erase(it);
    }
    else if (n == 3)
    {
        if (arr.empty())
            cout << "no task" << '\n';
        else
            show_task();
    }
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t;
    cin >> t;

    while (t--)
        solve();

    return 0;
}

9. `977A` - Wrong Subtraction

CF link: 977A - Wrong Subtraction

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

void solve()
{
    long long n;
    int k;

    cin >> n >> k;

    while (k--)
    {
        if (n % 10 == 0)
            n /= 10;
        else
            n--;
    }

    cout << n << '\n';
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    solve();

    return 0;
}

10. `734A` - Anton and Danik

CF link: 734A - Anton and Danik

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

void solve()
{
    int n;
    string s;
    cin >> n >> s;

    int count_a = 0, count_d = 0;

    for (char c : s)
    {
        if (c == 'A')
            count_a++;
        else if (c == 'D')
            count_d++;
    }

    if (count_a > count_d)
        cout << "Anton" << '\n';
    else if (count_d > count_a)
        cout << "Danik" << '\n';
    else
        cout << "Friendship" << '\n';
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    solve();

    return 0;
}

11. `236D` - Let's Play Osu!

CF link: 236D - Let's Play Osu!

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

void solve()
{
    int n;
    cin >> n;

    double ans = 0;
    double cur = 0;

    while (n--)
    {
        double p;
        cin >> p;

        ans += p * (2 * cur + 1);
        cur = p * (cur + 1);
    }

    cout << fixed << setprecision(15) << ans << '\n';
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    solve();

    return 0;
}

12. `158B` - Taxi

CF link: 158B - Taxi

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

void solve()
{
          int n;
          cin >> n;

          vector<int> a(n);
          for (int &x : a)
                    cin >> x;

          sort(a.begin(), a.end());

          int l = 0, r = n - 1, cnt = 0;

          while (l <= r)
          {
                    int s = 4 - a[r];
                    r--;

                    while (l <= r && a[l] <= s)
                    {
                              s -= a[l];
                              l++;
                    }

                    cnt++;
          }

          cout << cnt;
}

int main()
{
          ios::sync_with_stdio(false);
          cin.tie(nullptr);

          solve();

          return 0;
}

On this page