A cow's language, known as Cowphabet, consists of the 26 lowercase letters. However, the order in which a cow recites these letters is a permutation of the standard alphabet sequence. Bessie repeats this song, and Farmer John notes down a string of letters he remembers hearing. The task is to determine the minimum number of complete Cowphabet recitations needed for Farmer John to have heard the observed sequence, given that he might miss some letter during each recitation.

The input provides the 26-letter Cowphabet on the first line and the observed string (length between 1 and 1000) on the second line.

Output the minimum number of complete recitations.

Example

abcdefghijklmnopqrstuvwxyz
mood

Output: 3

Approach For the observed string, iterate through its characters. Each time the current character is not positioned after the previous character in the provided Cowphabet order, it indicates the start of a new recitation. Initialize the count to 1.

Implementation

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

int main() {
    string alphabet, heard;
    cin >> alphabet >> heard;
    int repetitions = 1;
    for (int i = 1; i < heard.length(); ++i) {
        int prevPos = alphabet.find(heard[i-1]);
        int currPos = alphabet.find(heard[i]);
        if (currPos <= prevPos) {
            ++repetitions;
        }
    }
    cout << repetitions << endl;
    return 0;
}

Maximizing Alternating Parity Groups for Cow Photos

Farmer John aims to partition N cows (2 ≤ N ≤ 1000) into the maximum number of contiguous groups. The sum of breed IDs in the first group must be even, the second odd, and so on, alternating. Breed IDs are integers between 1 and 100.

Input: N on the first line, followed by N breed IDs.

Output the maximum possible number of groups.

Examples

7
1 3 5 7 9 11 13

Output: 3

7
11 2 17 13 1 15 3

Output: 5

Strategy Count the number of cows with even (ev) and odd (od) breed IDs.

• If ev > od: Maximum groups = 2 * od + 1.
• If ev == od: Maximum groups = N (i.e., ev + od).
• If od > ev: First, pair each even with an odd: groups = 2 * ev. Remaining odds: rem = od - ev. The contribution from remaining odds follows a pattern based on rem % 3:
  • If rem % 3 == 0: add 2 * (rem / 3).
  • If rem % 3 == 1: add 2 * (rem / 3) - 1.
  • If rem % 3 == 2: add 2 * (rem / 3) + 1.

Solution

#include <iostream>
using namespace std;

int main() {
    int n, val, ev = 0, od = 0;
    cin >> n;
    for (int i = 0; i < n; ++i) {
        cin >> val;
        if (val % 2 == 0) ++ev;
        else ++od;
    }
    int result = 0;
    if (ev > od) {
        result = 2 * od + 1;
    } else if (ev == od) {
        result = ev + od;
    } else { // od > ev
        result = 2 * ev;
        int rem = od - ev;
        int q = rem / 3;
        int r = rem % 3;
        if (r == 0) result += 2 * q;
        else if (r == 1) result += 2 * q - 1;
        else result += 2 * q + 1;
    }
    cout << result << endl;
    return 0;
}

Counting Valid Cow-to-Stall Assignments Under Height Constraints

There are N cows (1 ≤ N ≤ 20) with heights cowH[] and N stalls with height limits limit[]. Each cow must be assigned to a distinct stall such that the cow's height does not exceed the stall's limit. Compute the number of valid assignments.

Input: N, followed by the list of cow heights and the list of stall limits.

Output the total number of valid permutations. Use a 64-bit integer type.

Example

4
1 2 3 4
2 4 3 4

Output: 8

Method Sort cows in descending order of height. For the i-th tallest cow (1-indexed), count how many stalls have a limit atleast its height. The first cow can choose from all such stalls. Each subsequent cow must avoid stalls already taken by taller cows. Therefore, for the i-th cow, the number of available stalls is (count_of_valid_stalls - (i - 1)). Multiply these counts for all cows.

Implementation

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

int main() {
    int n;
    cin >> n;
    long long cowH[n], limit[n];
    for (int i = 0; i < n; ++i) cin >> cowH[i];
    for (int i = 0; i < n; ++i) cin >> limit[i];
    sort(cowH, cowH + n, greater<long long>());
    long long total = 1;
    for (int i = 0; i < n; ++i) {
        int valid = 0;
        for (int j = 0; j < n; ++j) {
            if (limit[j] >= cowH[i]) ++valid;
        }
        total *= (valid - i);
    }
    cout << total << endl;
    return 0;
}