Preparation for the National Competition in Informatics

Hints — solution idea

1. Reading the table

We store the table in a character matrix char grid[3][3]. The digits are written without spaces, but cin >> ch reads one character at a time, so reading works without any extra splitting. If we read the digits into an int, the whole line (e.g. 123) would be read as one number.

2. Diagonals

In row i, the main diagonal digit is grid[i][i], and the anti-diagonal digit is grid[i][2 - i].

3. Building the numbers

We build each number digit by digit, from top to bottom: number = number * 10 + digit. The digit is obtained from the character by subtracting the character zero: ch - '0'.

4. Product

Finally we print the product of the two three-digit numbers. The largest possible product is 999 · 999 = 998001, which fits in an int.

C++ solution

#include <iostream>
using namespace std;

int main() {
    char grid[3][3];

    // The digits are written without spaces, but cin >> char reads one character at a time
    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < 3; j++) {
            cin >> grid[i][j];
        }
    }

    int mainDiag = 0;    // number formed from the main diagonal digits
    int antiDiag = 0;    // number formed from the anti-diagonal digits

    for (int i = 0; i < 3; i++) {
        // the main diagonal digit in row i is in column i
        mainDiag = mainDiag * 10 + (grid[i][i] - '0');
        // the anti-diagonal digit in row i is in column 2 - i
        antiDiag = antiDiag * 10 + (grid[i][2 - i] - '0');
    }

    cout << mainDiag * antiDiag << endl;
    return 0;
}

Hints — solution idea

1. Reading

We read the integer. The sum of squares is set to 0 before the loop starts.

2. Extracting digits

Loop while (number > 0): the rightmost digit is number % 10, and number / 10 removes that digit. The procedure is repeated until the rest of the number becomes 0.

3. Checking parity

A digit is odd if digit % 2 != 0.

4. Sum

For each odd digit we add its square digit * digit to the sum.

C++ solution

#include <iostream>
using namespace std;

int main() {
    int number;
    cin >> number;

    int sum = 0;                   // sum of squares of odd digits, 0 at the start
    while (number > 0) {
        int digit = number % 10;   // the rightmost digit
        number = number / 10;      // removes the rightmost digit

        if (digit % 2 != 0) {      // is the digit odd
            sum += digit * digit;
        }
    }

    cout << sum << endl;
    return 0;
}

Hints — solution idea

1. Function for the number of divisors

We write a function countDivisors(n). It loops through the numbers from 1 to n and counts those that divide n (condition n % i == 0).

2. Main loop

After reading the first term, we repeat the step N − 1 times (the first term is already known): the new term is term + countDivisors(term).

3. Output

After the loop we print the last computed term.

4. Checking the example

For a1 = 2: 2 has divisors 1 and 2 (2 + 2 = 4), 4 has divisors 1, 2, 4 (4 + 3 = 7), 7 has divisors 1 and 7 (7 + 2 = 9).

C++ solution

#include <iostream>
using namespace std;

// Number of divisors of a natural number n
int countDivisors(int n) {
    int cnt = 0;
    for (int i = 1; i <= n; i++) {
        if (n % i == 0) {          // i is a divisor of n
            cnt++;
        }
    }
    return cnt;
}

int main() {
    int a1, n;
    cin >> a1 >> n;

    int term = a1;                 // current term of the sequence
    for (int i = 1; i < n; i++) {  // n - 1 steps are needed to reach the n-th term
        term = term + countDivisors(term);
    }

    cout << term << endl;
    return 0;
}

Hints — solution idea

1. First occurrence

The first occurrence of n is in the middle of row n. There are (n − 1)² terms before that row, so the position is (n − 1)² + n. For k = 1 that is the answer.

2. Other occurrences

After row n, every row has two occurrences: the first (left) one at position (M − 1)² + n, and the second (right) one at position (M − 1)² + 2M − n, where M is the row number.

3. Which row

For k ≥ 2 let j = k − 1 be the number of occurrences after the first one. Occurrences j = 1, 2 are in row n + 1, occurrences j = 3, 4 in row n + 2 and so on, so the row is M = n + (j + 1) / 2. If j is odd, we need the left occurrence; if it is even, the right one.

4. Simulation or formula

Solution 1 goes row by row and “uses up” occurrences (two in each row), while solution 2 computes the row and the position directly with a formula, without a loop.

5. Data type

The position can be of order (1.5·106)² ≈ 2.25·1012, which does not fit in an int. That is why we use long long.

Solution 1: row by row (simulation)

#include <iostream>
using namespace std;

int main() {
    long long n, k;
    cin >> n >> k;

    // Row M has 2M - 1 terms, so there are (M-1)^2 terms in total before row M.
    // The number n appears for the first time in row n (only once, in the middle),
    // and in every following row M > n it appears twice:
    // at place n (from the left) and at place 2M - n.
    long long row = n;                 // the row in which we look for the occurrence
    long long remaining = k - 1;       // occurrences after the first one (in row n)

    while (remaining > 0) {
        row++;                         // move to the next row, which has 2 occurrences
        if (remaining >= 2) {
            remaining -= 2;            // skip both occurrences in this row
        } else {
            break;                     // the required occurrence is the first one in this row
        }
    }

    long long before = (row - 1) * (row - 1); // number of terms before this row
    long long position;

    if (row == n) {
        position = before + n;               // the only occurrence, in the middle of row n
    } else if (remaining == 1) {
        position = before + n;               // left occurrence in the row
    } else {
        position = before + 2 * row - n;     // right occurrence in the row
    }

    cout << position << endl;
    return 0;
}

Solution 2: formula

#include <iostream>
using namespace std;

int main() {
    long long n, k;
    cin >> n >> k;

    long long position;
    if (k == 1) {
        // first occurrence: middle of row n
        position = (n - 1) * (n - 1) + n;
    } else {
        long long j = k - 1;               // how many occurrences after the first one
        long long row = n + (j + 1) / 2;   // two occurrences in every row after the n-th
        long long before = (row - 1) * (row - 1);
        if (j % 2 == 1) {
            position = before + n;         // odd j: left occurrence in the row
        } else {
            position = before + 2 * row - n; // even j: right occurrence in the row
        }
    }

    cout << position << endl;
    return 0;
}

Hints — solution idea

Method I: brute force

We write a function that returns the number of divisors of the given number: a loop changes the divisor d from 1 to the number itself and counts those for which the number is divisible by d. In the main part, a loop goes from a to b and counts the numbers for which the function returns an odd value. This is slow even for small limits (for b = 1015 it would take years).

Method II: optimized

Divisors come in pairs (d, x / d). A pair always contains two different numbers, except when d = x / d, i.e. when x is a perfect square. So only perfect squares have an odd number of divisors. Instead of counting divisors, we write a function that checks whether a number is a perfect square. We still go through all numbers from a to b.

Method III: fully optimized

We do not check all numbers from a to b; instead we find the smallest and the largest integer whose square lies in the interval. Then we count the integers between them. The loop has about √b ≈ 3·107 steps, which is acceptable.

Method IV: formula

There are ⌊√x⌋ perfect squares in [1, x], so there are ⌊√b⌋ − ⌊√(a − 1)⌋ of them in [a, b]. This is computed in constant time.

Be careful with square roots

The sqrt function works with real numbers and for large values it can return a result that is 1 smaller or larger than the exact one. That is why we check the obtained integer k and correct it until k² ≤ x < (k + 1)² holds. For numbers up to 10¹⁵ the products fit in long long.

Method I (brute force)

#include <iostream>
using namespace std;

// Number of divisors of x (brute force)
long long countDivisors(long long x) {
    long long cnt = 0;
    for (long long d = 1; d <= x; d++) {
        if (x % d == 0) cnt++;
    }
    return cnt;
}

int main() {
    long long a, b;
    cin >> a >> b;

    long long counter = 0;
    for (long long x = a; x <= b; x++) {
        if (countDivisors(x) % 2 == 1) {     // odd number of divisors
            counter++;
        }
    }

    cout << counter << endl;
    return 0;
}

Method II (perfect square check)

#include <iostream>
#include <cmath>
using namespace std;

// Only perfect squares have an odd number of divisors
bool isPerfectSquare(long long x) {
    long long k = (long long)sqrtl((long double)x);
    // fix a possible rounding error
    while (k * k > x) k--;
    while ((k + 1) * (k + 1) <= x) k++;
    return k * k == x;
}

int main() {
    long long a, b;
    cin >> a >> b;

    long long counter = 0;
    for (long long x = a; x <= b; x++) {
        if (isPerfectSquare(x)) counter++;
    }

    cout << counter << endl;
    return 0;
}

Method III (squares only)

#include <iostream>
#include <cmath>
using namespace std;

// The largest integer k such that k * k <= x
long long intSqrt(long long x) {
    long long k = (long long)sqrtl((long double)x);
    while (k * k > x) k--;
    while ((k + 1) * (k + 1) <= x) k++;
    return k;
}

int main() {
    long long a, b;
    cin >> a >> b;

    // the smallest k with k * k >= a
    long long firstK = intSqrt(a);
    if (firstK * firstK < a) firstK++;

    // the largest k with k * k <= b
    long long lastK = intSqrt(b);

    // we check only the squares from firstK * firstK to lastK * lastK
    long long counter = 0;
    for (long long k = firstK; k <= lastK; k++) {
        counter++;                     // k * k is in the interval [a, b]
    }

    cout << counter << endl;
    return 0;
}

Method IV (formula)

#include <iostream>
#include <cmath>
using namespace std;

long long intSqrt(long long x) {
    if (x <= 0) return 0;
    long long k = (long long)sqrtl((long double)x);
    while (k * k > x) k--;
    while ((k + 1) * (k + 1) <= x) k++;
    return k;
}

int main() {
    long long a, b;
    cin >> a >> b;

    // There are intSqrt(b) squares in [1, b] and intSqrt(a - 1) squares in [1, a - 1]
    cout << intSqrt(b) - intSqrt(a - 1) << endl;
    return 0;
}

Hints — solution idea

Method I: nested loops

The outer loop goes through the N deals, and the inner one reads the k cards. We compare each card with the previous card of the same deal. If the current card is smaller than the previous one, the deal is wrong. It is important to read all remaining cards of that deal even after a mistake is found, so that the input is read correctly.

Method II: vectors

We read the cards of one deal into a vector. We make a copy of the vector and sort only the copy. If the copy differs from the original, the original was not sorted, so Baja made a mistake.

Counting

In both methods we increase the counter of wrong deals by 1 every time a deal is not arranged in non-decreasing order.

Method I (nested loops)

#include <iostream>
using namespace std;

int main() {
    int n, k;
    cin >> n >> k;

    int wrongDeals = 0;
    for (int deal = 0; deal < n; deal++) {
        int previous;
        cin >> previous;               // the first card of the deal
        bool ok = true;

        for (int i = 1; i < k; i++) {
            int current;
            cin >> current;            // read all cards, even after a mistake
            if (current < previous) {  // not non-decreasing
                ok = false;
            }
            previous = current;
        }

        if (!ok) wrongDeals++;
    }

    cout << wrongDeals << endl;
    return 0;
}

Method II (vectors)

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    int n, k;
    cin >> n >> k;

    int wrongDeals = 0;
    for (int deal = 0; deal < n; deal++) {
        vector<int> cards(k);
        for (int i = 0; i < k; i++) cin >> cards[i];

        vector<int> sortedCards = cards;             // copy of the original sequence
        sort(sortedCards.begin(), sortedCards.end()); // sort only the copy

        if (sortedCards != cards) {                  // different => Baja made a mistake
            wrongDeals++;
        }
    }

    cout << wrongDeals << endl;
    return 0;
}

Hints — solution idea

1. Reading

We read n and the points (in decreasing order), then m and the threshold for each question.

2. What we are looking for

Since the points are sorted from the largest to the smallest, the advancing contestants form the beginning of the array. The required number is the index of the first position where the number of points is smaller than the threshold (or n if there is no such position).

3. Linear search

For each question we start from the beginning of the array and count contestants while points[i] >= threshold. In the worst case that is n · m = 2.5·109 steps.

4. Binary search

Because the array is sorted, we can halve it in every step: if the middle element is ≥ threshold, all elements to its left also advance, so we look for the boundary to the right; otherwise to the left. Each question then takes O(log n).

Solution 1: linear search

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<int> points(n);            // points are sorted from the largest to the smallest
    for (int i = 0; i < n; i++) cin >> points[i];

    int m;
    cin >> m;
    for (int q = 0; q < m; q++) {
        int threshold;
        cin >> threshold;

        // linear search: count contestants with points >= threshold
        int number = 0;
        while (number < n && points[number] >= threshold) {
            number++;
        }
        cout << number << "\n";
    }
    return 0;
}

Solution 2: binary search

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<int> points(n);            // decreasing order
    for (int i = 0; i < n; i++) cin >> points[i];

    int m;
    cin >> m;
    for (int q = 0; q < m; q++) {
        int threshold;
        cin >> threshold;

        // binary search for the first position where points[position] < threshold
        int lo = 0, hi = n;           // the required index is in [lo, hi]
        while (lo < hi) {
            int mid = (lo + hi) / 2;
            if (points[mid] >= threshold) {
                lo = mid + 1;         // everything left of mid advances too, search further to the right
            } else {
                hi = mid;             // mid is already below the threshold
            }
        }
        cout << lo << "\n";           // lo is also the number of advancing contestants
    }
    return 0;
}

Hints — solution idea

1. Reading

We read n and in a loop read the height (int) and the gender (char) n times.

2. Two maximums

We keep the greatest height of the boys and, separately, the greatest height of the girls. For each student, depending on the gender, we update the corresponding maximum.

3. Comparison

At the end we compare the two maximums and print the required message: the gender mark of the taller student and the difference, or the = sign.

C++ solution

#include <iostream>
using namespace std;

int main() {
    int n;
    cin >> n;

    int tallestBoy = 0, tallestGirl = 0;
    for (int i = 0; i < n; i++) {
        int height;
        char gender;
        cin >> height >> gender;

        if (gender == 'm') {
            if (height > tallestBoy) tallestBoy = height;
        } else if (gender == 'z') {
            if (height > tallestGirl) tallestGirl = height;
        }
    }

    if (tallestBoy > tallestGirl) {
        cout << "m " << tallestBoy - tallestGirl << endl;
    } else if (tallestGirl > tallestBoy) {
        cout << "z " << tallestGirl - tallestBoy << endl;
    } else {
        cout << "=" << endl;
    }
    return 0;
}

Hints — solution idea

1. Total number of pages

We read the chapters into an array and at the same time add up the total number of pages total.

2. Difference for one split

If the first part (chapters 0 to i) has leftPages pages, the second part has total − leftPages. The difference is |total − 2·leftPages|.

3. Best split

For each i from 0 to n − 2 (there is no split after the last chapter) we increase leftPages and compute the difference. We remember the smallest difference and the chapter where it was obtained.

4. Equal differences

We change the chapter only when the difference is strictly smaller than the smallest one so far. That way, in case of a tie the earlier chapter stays, as the task requires.

C++ solution

#include <iostream>
#include <vector>
#include <cstdlib>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<int> pages(n);
    int total = 0;
    for (int i = 0; i < n; i++) {
        cin >> pages[i];
        total += pages[i];
    }

    int leftPages = 0;             // number of pages in chapters 0..i
    int minDiff = total + 1;
    int bestChapter = 0;

    // the split is made after chapter i, so the last possible split is after n - 2
    for (int i = 0; i < n - 1; i++) {
        leftPages += pages[i];
        int rightPages = total - leftPages;
        int diff = abs(rightPages - leftPages);

        // strictly smaller difference: in case of a tie the earlier one stays (shorter first part)
        if (diff < minDiff) {
            minDiff = diff;
            bestChapter = i;
        }
    }

    cout << bestChapter << endl;
    return 0;
}

Hints — solution idea

Idea

The digits are strictly increasing from left to right when every digit is strictly smaller than the digit to its right. Equivalently, looking from right to left, the digits are strictly decreasing.

Solution 1: digits from the right

We extract the digits starting from the last one (x % 10), and x /= 10 removes it. We remember the previous (right) digit; at the start it is 10, which is greater than any digit. If the current digit is greater than or equal to the previous one, the digits are not increasing and we stop the loop. This way there is no need to count the digits.

Solution 2: string

We read the number as a string. Neighbouring characters are compared with the <= operator: digit characters are ordered the same way as the digits, so the comparison is correct.

Solution 1: digits from the right

#include <iostream>
using namespace std;

int main() {
    int n;
    cin >> n;

    for (int i = 0; i < n; i++) {
        int number;
        cin >> number;

        // We go from the least significant digit (from right to left). The digits are strictly increasing
        // from the left if they are strictly decreasing from the right.
        int x = number;
        int previous = 10;         // greater than any digit
        bool increasing = true;

        while (x > 0) {
            int digit = x % 10;
            if (digit >= previous) {    // the left digit is not smaller than the right one
                increasing = false;
                break;
            }
            previous = digit;
            x /= 10;
        }

        if (increasing) {
            cout << number << "\n";
        }
    }
    return 0;
}

Solution 2: number as a string

#include <iostream>
#include <string>
using namespace std;

int main() {
    int n;
    cin >> n;

    for (int i = 0; i < n; i++) {
        string number;
        cin >> number;              // read the number as a string of digits

        bool increasing = true;
        for (size_t j = 1; j < number.size(); j++) {
            if (number[j] <= number[j - 1]) { // digits are compared as characters
                increasing = false;
                break;
            }
        }

        if (increasing) {
            cout << number << "\n";
        }
    }
    return 0;
}

Hints — solution idea

Solution 1: two loops

We sort the heights in increasing order. For each height v[i] we go through the following heights v[j]. If the difference equals r, we increase the number of pairs; if it is greater than r, we stop the inner loop because all following differences will be even greater. For test cases with many equal heights this can be slow.

Solution 2: binary search

We sort the heights. For each height v[i] we look for how many elements are equal to v[i] + r. Since the array is sorted, these elements form one continuous block, and the function equal_range finds its beginning and end with binary search. We add the number of elements in the block to the result. This also counts repeated heights correctly.

Solution 3: counting

Heights are limited to 100000, so we can count how many students have each height in the array number[h]. For each height h, the number of pairs (h, h + r) is number[h] · number[h + r]. We add up the result over all heights. No sorting is needed.

Data type

The number of pairs can be greater than 10⁹ (e.g. if half of the students have one height and the other half a height greater by r), so the counter should be a long long.

Solution 1: two loops

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    int r, n;
    cin >> r >> n;
    vector<int> v(n);
    for (int i = 0; i < n; i++) cin >> v[i];

    sort(v.begin(), v.end());        // heights in increasing order

    long long pairs = 0;
    for (int i = 0; i < n - 1; i++) {
        for (int j = i + 1; j < n; j++) {
            int diff = v[j] - v[i];
            if (diff == r) {
                pairs++;
            } else if (diff > r) {
                break;               // all further differences are even greater
            }
        }
    }

    cout << pairs << endl;
    return 0;
}

Solution 2: binary search

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    int r, n;
    cin >> r >> n;
    vector<int> v(n);
    for (int i = 0; i < n; i++) cin >> v[i];

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

    long long pairs = 0;
    for (int i = 0; i < n; i++) {
        // using binary search we find all elements equal to v[i] + r
        // (they are always to the right of i, because r >= 1)
        auto range = equal_range(v.begin(), v.end(), v[i] + r);
        pairs += range.second - range.first;    // how many of them there are
    }

    cout << pairs << endl;
    return 0;
}

Solution 3: counting by heights

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int r, n;
    cin >> r >> n;

    const int LIMIT = 100000;                // the greatest possible height
    vector<long long> number(LIMIT + 1, 0);  // number[h] = how many students have height h
    for (int i = 0; i < n; i++) {
        int h;
        cin >> h;
        number[h]++;
    }

    // For each height h, there are number[h] * number[h + r] pairs (h, h + r)
    long long pairs = 0;
    for (int h = 1; h + r <= LIMIT; h++) {
        pairs += number[h] * number[h + r];
    }

    cout << pairs << endl;
    return 0;
}

Hints — solution idea

1. Sorting

We sort the prices in decreasing order, so that we process them from the most expensive to the cheapest. In C++ this is done with sort and the comparison function greater<int>().

2. Traversal

For each item we check whether its price is less than or equal to the remaining money. If it is, we subtract it from the remainder.

3. Output

After going through all items we print the remainder.

C++ solution

#include <iostream>
#include <vector>
#include <algorithm>
#include <functional>
using namespace std;

int main() {
    int money, n;
    cin >> money >> n;
    vector<int> prices(n);
    for (int i = 0; i < n; i++) cin >> prices[i];

    // from the most expensive to the cheapest
    sort(prices.begin(), prices.end(), greater<int>());

    int remaining = money;
    for (int i = 0; i < n; i++) {
        if (prices[i] <= remaining) {  // if there is enough money, the item is bought
            remaining -= prices[i];
        }
    }

    cout << remaining << endl;
    return 0;
}

Hints — solution idea

1. Recursive function

The function build(i) fills position i, while positions 0..i − 1 are already filled.

2. Base case

When i == n, all elements are set: we print the sequence and return.

3. Branching

First we write 0 and call build(i + 1). Then, if i == 0 or the previous element is 0, we write 1 and call build(i + 1) again.

4. Order

Because we always try zero first and then one, the sequences are printed in increasing (lexicographic) order.

C++ solution

#include <iostream>
using namespace std;

int n;
int seq[10];

// Print the formed binary sequence
void printSeq() {
    for (int i = 0; i < n; i++) {
        cout << seq[i];
    }
    cout << "\n";
}

// Fills position i; positions 0..i-1 are already filled
void build(int i) {
    if (i == n) {                    // the sequence is complete
        printSeq();
        return;
    }

    seq[i] = 0;                      // a zero can always be written
    build(i + 1);

    // a one is allowed only if the previous element is not a one
    if (i == 0 || seq[i - 1] == 0) {
        seq[i] = 1;
        build(i + 1);
    }
}

int main() {
    cin >> n;
    build(0);
    return 0;
}

Hints — solution idea

Solution 1: all segments

We fix the start i, then in a loop increase the end j and add change[j] to the running sum. Every time the sum equals z, we increase the counter. This passes the smaller tests.

Solution 2: prefix sums

Let P[j] be the sum of the first j changes (P[0] = 0). The sum of the segment from day i + 1 to day j is P[j] − P[i]. The segment has sum z when P[i] = P[j] − z.

Counting

As we go through the days, we maintain a map seen that stores, for each prefix sum value, how many times it has appeared so far. For each j we add seen[P[j] − z] to the result, and then record P[j] as well. At the start seen[0] = 1 (the empty prefix).

Data type

The number of segments can be about 1.25·10⁹, which exceeds the limit of the int type, so the counter must be a long long.

Solution 1: all segments

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int z, n;
    cin >> z >> n;
    vector<int> change(n);
    for (int i = 0; i < n; i++) cin >> change[i];

    long long counter = 0;
    for (int i = 0; i < n; i++) {        // start of the period
        int sum = 0;
        for (int j = i; j < n; j++) {    // end of the period
            sum += change[j];
            if (sum == z) counter++;
        }
    }

    cout << counter << endl;
    return 0;
}

Solution 2: prefix sums and a map

#include <iostream>
#include <map>
using namespace std;

int main() {
    int z, n;
    cin >> z >> n;

    // prefix[j] = sum of the first j changes. Period (i, j] has the sum prefix[j] - prefix[i].
    // So for each prefix we count how many earlier prefixes have the value (prefix - z).
    map<int, int> seen;
    seen[0] = 1;                    // empty prefix (before the first day)

    int prefix = 0;
    long long counter = 0;
    for (int i = 0; i < n; i++) {
        int change;
        cin >> change;
        prefix += change;

        auto it = seen.find(prefix - z);
        if (it != seen.end()) {
            counter += it->second;
        }
        seen[prefix]++;
    }

    cout << counter << endl;
    return 0;
}

Hints — solution idea

Solution 1: all numbers

In a loop from a to b we check the condition i % c == 0 and count. For b up to 10¹⁵ that is far too many steps.

Solution 2: steps of c

The first multiple of c that is ≥ a is (a + c − 1) / c * c. From it we go in steps of c up to b and count. For a small divisor c (e.g. 2) there are still too many steps.

Solution 3: formula

Among the numbers from 1 to x there are x / c multiples of c (integer division). So the number of multiples in [a, b] is b / c − (a − 1) / c. It is computed in constant time.

Data type

The numbers reach 10¹⁵, so a 64-bit type is needed, e.g. unsigned long long or long long.

Reading from a file (while testing)

While practising, you can read the examples from a file instead of standard input if you add freopen("deljivi.01.in", "r", stdin); at the beginning of main (and #include <cstdio>). Remove this line before submitting the solution.

Solution 1: all numbers

#include <iostream>
using namespace std;

int main() {
    unsigned long long a, b, c;
    cin >> a >> b >> c;

    unsigned long long counter = 0;
    for (unsigned long long i = a; i <= b; i++) {   // check every number
        if (i % c == 0) {
            counter++;
        }
    }

    cout << counter << endl;
    return 0;
}

Solution 2: steps of c

#include <iostream>
using namespace std;

int main() {
    unsigned long long a, b, c;
    cin >> a >> b >> c;

    // the first multiple of c that is not smaller than a
    unsigned long long i = (a + c - 1) / c * c;

    unsigned long long counter = 0;
    while (i <= b) {
        counter++;
        i += c;                      // the next multiple is greater by c
    }

    cout << counter << endl;
    return 0;
}

Solution 3: formula

#include <iostream>
using namespace std;

int main() {
    unsigned long long a, b, c;
    cin >> a >> b >> c;

    // There are x / c multiples of c in [1, x] (integer division).
    // In [a, b] there are: (those in [1, b]) - (those in [1, a - 1]).
    unsigned long long result = b / c - (a - 1) / c;

    cout << result << endl;
    return 0;
}

Hints — solution idea

1. Input

We read the weights of the four bags and the carrying capacities of the two travellers.

2. Recursion

The function solve(i, cap1, cap2, bags1, bags2) processes the bag with index i. The parameters cap1 and cap2 are the remaining capacities of the travellers, and bags1 and bags2 the numbers of bags they already carry (at most 2).

3. Three possibilities

For bag i we consider: (1) nobody carries it (its weight is added to the “not carried” part); (2) the first traveller carries it – if he has a free hand and enough capacity; (3) the second traveller carries it, under the same conditions. The function returns the smallest total load that is left uncarried.

4. End of recursion

When all four bags are processed (i == 4), there is no more uncarried load, so we return 0.

5. Number of possibilities

There are at most 34 = 81 ways to distribute the bags, so such a complete search (trying all possibilities) is very fast.

C++ solution

#include <iostream>
#include <algorithm>
using namespace std;

int weight[4];      // weights of the bags

// Minimum weight of the bags that will not be carried, if bags 0..i-1 are already distributed.
// cap1, cap2 - remaining capacity of the travellers, bags1, bags2 - number of bags they already carry
int solve(int i, int cap1, int cap2, int bags1, int bags2) {
    if (i == 4) {
        return 0;                    // all bags are processed
    }

    // 1) nobody carries bag i (help from others is needed)
    int best = weight[i] + solve(i + 1, cap1, cap2, bags1, bags2);

    // 2) the first traveller carries the bag (if he has a free hand and enough capacity)
    if (bags1 < 2 && weight[i] <= cap1) {
        best = min(best, solve(i + 1, cap1 - weight[i], cap2, bags1 + 1, bags2));
    }

    // 3) the second traveller carries the bag
    if (bags2 < 2 && weight[i] <= cap2) {
        best = min(best, solve(i + 1, cap1, cap2 - weight[i], bags1, bags2 + 1));
    }

    return best;
}

int main() {
    for (int i = 0; i < 4; i++) cin >> weight[i];
    int p1, p2;
    cin >> p1 >> p2;

    cout << solve(0, p1, p2, 0, 0) << endl;
    return 0;
}

Hints — solution idea

1. What oscillation is

A run oscillates if the direction of change keeps switching: up, then down, then up... Equal neighbouring elements break the oscillation (there is neither an increase nor a decrease).

2. Direction of change

For every two neighbouring measurements we determine the direction: +1 if the speed increases, −1 if it decreases, 0 if it stays the same.

3. Length of the current run

We keep the length current of the current oscillating run and the direction of the last change. If the new direction is 0, the length goes back to 1. If the new direction is opposite to the previous one, the length grows by 1. In all other cases (same direction, or there was no change before) the run starts from the previous element, so the length is 2.

4. Longest run

We keep the greatest length longest. If longest ≥ k, we print yes, otherwise no; in the second line we print longest.

5. Speed

There can be up to a million numbers, so we turn on faster input: ios::sync_with_stdio(false); cin.tie(nullptr);. There is no need to store the whole array – the previous value is enough.

C++ solution

#include <iostream>
using namespace std;

int main() {
    ios::sync_with_stdio(false);     // fast input, because there are up to a million numbers
    cin.tie(nullptr);

    int n, k;
    cin >> n >> k;

    double previous;
    cin >> previous;

    int current = 1;                 // length of the current oscillating run
    int longest = 1;
    int dir = 0;                     // direction of the last change: +1 up, -1 down, 0 none

    for (int i = 1; i < n; i++) {
        double x;
        cin >> x;

        int newDir;                  // direction of the change previous -> x
        if (x > previous) newDir = 1;
        else if (x < previous) newDir = -1;
        else newDir = 0;

        if (newDir == 0) {
            current = 1;             // equal neighbours break the oscillation
        } else if (dir != 0 && newDir == -dir) {
            current++;               // the direction changed: the oscillation continues
        } else {
            current = 2;             // new start: previous and x form a run of length 2
        }
        dir = newDir;
        previous = x;

        if (current > longest) longest = current;
    }

    cout << (longest >= k ? "yes" : "no") << "\n" << longest << "\n";
    return 0;
}

Hints — solution idea

1. Sneaker data

Prices are less than 50000, so we can group the sneakers by price: for each price c we keep a vector of the names of the sneakers that cost exactly c (vector<vector<string>>).

2. Sorting the names

The names in each group are sorted lexicographically.

3. The most expensive affordable price

For every possible budget x we compute in advance bestPrice[x] – the greatest price ≤ x for which there is at least one model (or −1 if there is none). This is done in a single pass: if there are sneakers with price x, the value is x; otherwise it is the value for x − 1.

4. Queries

For each customer, one array access gives us the price: if it is −1, we print none; otherwise we print all names from that price group.

5. Alternative

The sneakers can also be sorted by price, and then for each budget binary search finds the most expensive model that is not more expensive than the budget. Counting by prices is simpler because the prices are small.

6. Speed

There are up to a million queries, so we turn on fast input and output and avoid endl (we use "\n").

C++ solution

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    ios::sync_with_stdio(false);     // fast input and output because of the large number of queries
    cin.tie(nullptr);

    const int LIMIT = 50000;         // prices are less than 50000
    vector<vector<string>> byPrice(LIMIT); // byPrice[c] = names of the sneakers with price c

    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        string name;
        int price;
        cin >> name >> price;
        byPrice[price].push_back(name);
    }
    for (int c = 0; c < LIMIT; c++) {
        sort(byPrice[c].begin(), byPrice[c].end()); // lexicographic order within the same price
    }

    // bestPrice[x] = the greatest price <= x for which there is at least one model (or -1)
    vector<int> bestPrice(LIMIT, -1);
    for (int x = 0; x < LIMIT; x++) {
        if (!byPrice[x].empty()) bestPrice[x] = x;
        else if (x > 0) bestPrice[x] = bestPrice[x - 1];
    }

    int k;
    cin >> k;
    for (int q = 0; q < k; q++) {
        int budget;
        cin >> budget;
        if (budget >= LIMIT) budget = LIMIT - 1;

        int price = bestPrice[budget];
        if (price == -1) {
            cout << "none\n";
        } else {
            for (const string &name : byPrice[price]) {
                cout << name << " " << price << "\n";
            }
        }
    }
    return 0;
}

Hints — solution idea

1. Words are independent

Each word is rotated by one letter on every key press, independently of the others. The whole sentence returns to its initial state when all words return to their initial states at the same time.

2. One word

A word of length L returns to its initial state after L presses, but maybe earlier if it is periodic. For example, the word abcabc has length 6, but after 3 rotations the same word is obtained, so its number of presses is 3. The number of presses is the smallest period of the word if it divides the length of the word; otherwise it is the length of the word.

3. Smallest period

We compute the smallest period with the prefix function (KMP algorithm): if pi is the length of the longest proper prefix that is also a suffix of the word, the period is L − pi. If L is not divisible by the period, the word is not periodic and the number of presses is L. For short words (up to 100 letters) simply checking all divisors of the length is enough.

4. All together

If word 1 needs p1 presses, word 2 needs p2 and so on, the sentence is in its initial state when the number of presses is divisible by all pi, and the smallest such number is their LCM (least common multiple). We compute the LCM using the GCD (Euclid's algorithm): LCM(a, b) = a / GCD(a, b) * b.

5. Data type

The result can be up to 10¹⁸, so we use long long. We divide before multiplying to avoid overflow.

C++ solution

#include <iostream>
#include <string>
#include <sstream>
#include <vector>
using namespace std;

long long gcdOf(long long a, long long b) {
    while (b != 0) {
        long long rem = a % b;
        a = b;
        b = rem;
    }
    return a;
}

// The smallest number of moves of the first letter to the end after which the word returns to its initial state.
// It is the smallest period of the word if it divides the length of the word; otherwise it is the whole length.
int wordPeriod(const string &r) {
    int len = r.size();
    vector<int> pi(len, 0);                  // prefix function (KMP)
    for (int i = 1; i < len; i++) {
        int j = pi[i - 1];
        while (j > 0 && r[i] != r[j]) j = pi[j - 1];
        if (r[i] == r[j]) j++;
        pi[i] = j;
    }
    int p = len - pi[len - 1];               // smallest period
    if (len % p == 0) return p;
    return len;
}

int main() {
    string line;
    getline(cin, line);
    istringstream input(line);

    long long result = 1;                    // LCM of the periods of all words
    string word;
    while (input >> word) {
        long long p = wordPeriod(word);
        result = result / gcdOf(result, p) * p;
    }

    cout << result << endl;
    return 0;
}

Hints — solution idea

1. Two loops

The outer loop goes through the n sequences, and the inner one through the k elements of one sequence.

2. Condition for one element

Element x at position j is correct if x and j have the same parity, i.e. x % 2 == j % 2. Indeed: an even position (j % 2 == 0) must contain an even number (x % 2 == 0), and an odd position an odd number.

3. Reading to the end of the line

Even when we find that a sequence is not correct, the remaining elements of that sequence must be read, so that the next sequence is read correctly. That is why we use a boolean variable valid instead of breaking the loop.

4. Output

After the inner loop we print yes or no.

C++ solution

#include <iostream>
using namespace std;

int main() {
    int n, k;
    cin >> n >> k;

    for (int i = 0; i < n; i++) {          // n sequences
        bool valid = true;
        for (int j = 0; j < k; j++) {      // k elements of a sequence
            int x;
            cin >> x;                      // read all elements, even after a mistake
            // even positions must contain even numbers, odd positions odd numbers:
            // the remainder of division by 2 must equal the remainder of the position
            if (x % 2 != j % 2) {
                valid = false;
            }
        }
        cout << (valid ? "yes" : "no") << "\n";
    }
    return 0;
}

Hints — solution idea

1. Two maps

We keep two dictionaries: toSerbian (English word → Serbian word) and toEnglish (Serbian word → English word). For every pair we read, we store both directions.

2. Queries

If the target language is en, the word is Serbian, so we look it up in the map toEnglish. If the target language is sr, the word is English, so we look it up in the map toSerbian.

3. Unknown word

We search with the find function. If the word is not in the map, we print ?. We do not use the [] operator for searching, because for an unknown word it would add a new (empty) element.

4. Speed

We use unordered_map (constant access time on average) or an ordinary map (logarithmic) – both are fast enough for 50000 words and queries.

C++ solution

#include <iostream>
#include <string>
#include <unordered_map>
using namespace std;

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

    int n;
    cin >> n;
    unordered_map<string, string> toSerbian;    // English word -> Serbian word
    unordered_map<string, string> toEnglish;    // Serbian word -> English word

    for (int i = 0; i < n; i++) {
        string english, serbian;
        cin >> english >> serbian;              // in the example the English word comes first, then the Serbian one
        toSerbian[english] = serbian;
        toEnglish[serbian] = english;
    }

    int m;
    cin >> m;
    for (int i = 0; i < m; i++) {
        string lang, word;
        cin >> lang >> word;                    // lang is the language we translate into

        if (lang == "en") {
            auto it = toEnglish.find(word);     // word is Serbian
            cout << (it == toEnglish.end() ? "?" : it->second) << "\n";
        } else {
            auto it = toSerbian.find(word);     // word is English
            cout << (it == toSerbian.end() ? "?" : it->second) << "\n";
        }
    }
    return 0;
}