Problem 1: Tank Battle

Description

Two players engage in a tank battle. Player A has n identical tanks with health a each, and Player B has m identical tanks with health b each. Each round, all surviving tanks fire simultaneously, dealing 1 damage to a target tank. Players use optimal strategies to maximize their victory. The battle continues until one side loses all tanks. Determine how many tanks Player A has remaining when Player B is defeated (output 0 if Player A loses). Multiple test cases are given. ### Input Format

First line: T (number of test cases) For each test case: n m a b (integers) ### Sample Input

5
10 2 15 1
2 1 2 1
2 1 3 1
10 8 4 4
10 8 1145141919 1145141919

Sample Output

3
1
0
5
6

Solution Approach

The optimal strategy for both sides is to focus fire on the weakest enemy tank. Rather than tracking individual tanks, we maintain total health pools for both sides. The solution processes multiple rounds at once by calculating when the weakest tank will be destroyed, significantly improving efficiency over round-by-round simulation. ### Implementation

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

int64 testCases, tanksA, tanksB, healthA, healthB;

void solve() {
    cin >> tanksA >> tanksB >> healthA >> healthB;
    if (tanksB >= tanksA && healthA >= healthB) {
        cout << "0\n";
        return;
    }
    
    int64 totalA = tanksB * healthA;
    int64 totalB = tanksA * healthB;
    
    while (totalA > 0 && totalB > 0) {
        tanksA = (totalB + healthB - 1) / healthB;
        tanksB = (totalA + healthA - 1) / healthA;
        
        int64 rounds = max(1LL, min(
            (totalA % healthA + tanksA - 1) / tanksA,
            (totalB % healthB + tanksB - 1) / tanksB
        ));
        
        totalA -= tanksA * rounds;
        totalB -= tanksB * rounds;
    }
    
    cout << max(0LL, (totalB + healthB - 1) / healthB) << "\n";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> testCases;
    while (testCases--) solve();
    return 0;
}

Problem 2: Matchstick Numbers

Description

Given n matchsticks, construct the smallest possible number using exactly all matchsticks (no leading zeros, except the number 0 ittself). Output the result modulo 998244853. Matchstick costs: 0-9 require [6,2,5,5,4,5,6,3,7,6] matchsticks respectively. ### Input Format

First line: T (test cases) For each test case: n (number of matchsticks) ### Sample Input

2
7
8

Sample Output

8
10

Solution Apporach

To minimize the number, we minimize digit count first. Since 8 uses the most matchsticks (7), we fill all positions with 8. We then adjust the most significant digits based on remaining matchsticks. For efficient modulo calculation, we precompute powers of 10 and repeating patterns. ### Implementation

#include<bits/stdc++.h>
#define int64 long long
#define MAX_SIZE 15005
#define MODULO 998244853
using namespace std;

int64 testCases, matchsticks;
int64 prefixPattern[MAX_SIZE], powerOfTen[MAX_SIZE];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    powerOfTen[0] = 1;
    for (int i = 1; i <= 15000; i++) {
        prefixPattern[i] = (prefixPattern[i-1] * 10 + 1) % MODULO;
        powerOfTen[i] = (powerOfTen[i-1] * 10) % MODULO;
    }
    
    cin >> testCases;
    while (testCases--) {
        cin >> matchsticks;
        
        if (matchsticks < 7) {
            int specialCases[] = {0, 0, 1, 7, 4, 2, 0, 8};
            cout << specialCases[matchsticks] << "\n";
            continue;
        }
        
        int64 digitCount = matchsticks / 7;
        int64 remainder = matchsticks % 7;
        int64 specialPrefix = 0;
        
        if (remainder == 1) {
            digitCount--;
            specialPrefix = 10;
        } else if (remainder == 2) {
            specialPrefix = 1;
        } else if (remainder == 3) {
            if (digitCount > 1) {
                digitCount -= 2;
                specialPrefix = 200;
            } else {
                digitCount--;
                specialPrefix = 22;
            }
        } else if (remainder == 4) {
            digitCount--;
            specialPrefix = 20;
        } else if (remainder == 5) {
            specialPrefix = 2;
        } else if (remainder == 6) {
            specialPrefix = 6;
        }
        
        int64 result = (specialPrefix * powerOfTen[digitCount] % MODULO + 
                       8 * prefixPattern[digitCount] % MODULO) % MODULO;
        cout << result << "\n";
    }
    return 0;
}

Problem 3: Subset Sequence Counting

Description

Given a sequence of non-negative integers, for each position i, count the number of subsequences ending at i where the elements form a chain of subsets when viewed as bitsets. Output results modulo 998244353. ### Input Format

First line: n (sequence length) Next n lines: a₁, a₂, ..., aₙ (sequence elements) ### Sample Input

5
1
2
3
4
5

Sample Output

1
1
3
1
3

Solution Approach

We use dynamic programming with bitmask optimization. For O(n²) solution, we check all previous positions. For optimization, we split 16-bit numbers into high and low 8-bit parts. We maintain a 2D DP table where dp[high][low] stores counts for numbers with specific high/low bit patterns. ### Implementation

#include<bits/stdc++.h>
#define int64 long long
#define MAX_SIZE 100005
#define MODULO 998244353
using namespace std;

int64 sequenceSize, maxValue;
int64 elements[MAX_SIZE], dpCount[MAX_SIZE];
int64 stateDP[300][300];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> sequenceSize;
    
    for (int i = 1; i <= sequenceSize; i++) {
        cin >> elements[i];
        maxValue = max(maxValue, elements[i] >> 8);
    }
    
    for (int i = 1; i <= sequenceSize; i++) {
        dpCount[i] = 1;
        int64 lowBits = elements[i] & 255;
        int64 highBits = elements[i] >> 8;
        
        for (int subset = 0; subset <= lowBits; subset++) {
            if ((subset | lowBits) == lowBits) {
                dpCount[i] = (dpCount[i] + stateDP[highBits][subset]) % MODULO;
            }
        }
        
        cout << dpCount[i] << "\n";
        
        for (int superset = highBits; superset <= maxValue; superset++) {
            if ((superset | highBits) == superset) {
                stateDP[superset][lowBits] = 
                    (stateDP[superset][lowBits] + dpCount[i]) % MODULO;
            }
        }
    }
    return 0;
}

Problem 4: Perfect Permutations

Description

Find the number of permutations of 1..n where for every adjacent pair (including the circular pair of last and first elements), the modulo of the first number by the second is at most 2. Output the result modulo 10^9+7. ### Input Format

Single integer: n ### Sample Input

4

Sample Output

16

Solution Approach

The key observation is that perfect permutations, when viewed circularly, consist of two decreasing sequences joined together, where each sequence ends with 1 or 2. Only 1 and 2 can precede larger numbers due to the modulo constraint. We use DP where dp[i][j] represents building sequences with maximum values i and j for the two decreasing subsequences. ### Implementation

#include<bits/stdc++.h>
#define int64 long long
#define MAX_N 1000005
#define MOD 1000000007
using namespace std;

int64 n, dp[MAX_N], answer;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n;
    dp[1] = 1;
    
    for (int j = 1; j < n; j++) {
        if (j <= 2) {
            for (int i = j + 1; i < n; i++) {
                dp[i] = (dp[i] + dp[j]) % MOD;
            }
        } else {
            for (int offset = -1; offset <= 1; offset++) {
                for (int i = j + offset; i < n; i += j) {
                    if (j < i) {
                        dp[i] = (dp[i] + dp[j]) % MOD;
                    }
                }
            }
        }
    }
    
    for (int i = 1; i < n; i++) {
        answer = (answer + dp[i]) % MOD;
    }
    
    cout << answer * n % MOD;
    return 0;
}