Codeforces 96A Football Solution in C (Counting Consecutive Runs)

Football (96A) is about finding a long run of identical characters in a string. Tracking the length of the current run is a pattern you will reuse in many problems, from compressing strings to finding the longest streak in an array.

The problem in short

A string of 0s and 1s (length up to 100) describes where the players stand on a field: 0 for one team and 1 for the other. The situation is dangerous if at least 7 players of the same team stand next to each other. Print YES if it is dangerous, otherwise NO.

Full statement: Codeforces 96A – Football.

Approach: track the current run

Walk through the string from left to right while keeping a counter run, which is the length of the block of equal characters ending at the current position.

• Start with run = 1 for the first character.
• If the current character equals the previous one, increase run. If run reaches 7, we can stop and print YES.
• Otherwise a new block starts, so reset run to 1.

If we reach the end without the counter hitting 7, print NO.

Examples

001001

The longest blocks are “00”, so run never passes 2 → NO.

1000000001

After the first 1, the 0s build up a run of 8, which hits 7 along the way → YES.

Solution in C

#include <stdio.h>

int main(void) {
    char s[105];
    scanf("%s", s);

    int run = 1;
    for (int i = 1; s[i] != '\0'; i++) {
        if (s[i] == s[i - 1]) {
            run++;
            if (run >= 7) {
                printf("YES\n");
                return 0;
            }
        } else {
            run = 1;
        }
    }

    printf("NO\n");
    return 0;
}

An even shorter alternative

Since the condition is “7 equal characters in a row”, you could also check whether the string contains "0000000" or "1111111" using strstr. That is a perfectly good solution here. The run counter is still worth knowing because it generalizes: it works for any threshold, any alphabet and any array, without building a search pattern.

Complexity

One pass: O(n) time and O(1) extra memory.

Common mistakes

• Starting run at 0 instead of 1, which makes every run look one shorter.
• Checking for exactly 7 (run == 7 only at the end of a block) and missing longer runs. Checking as soon as run reaches 7 avoids this.

Practice next

266A Stones on the Table uses the same “compare with the previous character” idea.

Codeforces 282A Bit++ Solution in C (Explained)

Bit++ (282A) describes a tiny programming language with one variable and two operations. Simulating it is straightforward. The nice part is noticing that you do not need to compare whole strings at all: one character tells you everything.

The problem in short

The language has a single variable x, which starts at 0, and two operations: ++ adds 1 and -- subtracts 1. Each statement is exactly three characters: the operation and the variable, in either order, so it is one of X++, ++X, X-- or --X. Given n statements (1 ≤ n ≤ 150), print the final value of x.

Full statement: Codeforces 282A – Bit++.

Key observation

Look at the four possible statements with their characters numbered from 0:

X++   ++X   X--   --X
 ^     ^     ^     ^
index 1 is always '+' or '-'

Whatever the order, the middle character (index 1) is always part of the operation. So the whole statement can be decided by checking stmt[1]: if it is '+', increment, otherwise decrement.

The original version of this post compared each statement against all four strings using strcmp. That is correct too, but it is longer and gives you four chances to make a typo.

Example

2
X++
--X

The first statement has '+' in the middle, so x becomes 1. The second has '-', so x goes back to 0.

Solution in C

#include <stdio.h>

int main(void) {
    int n, x = 0;
    char stmt[4];
    scanf("%d", &n);

    while (n--) {
        scanf("%s", stmt);
        /* The middle character is always '+' or '-',
           whether the statement is X++, ++X, X-- or --X. */
        if (stmt[1] == '+')
            x++;
        else
            x--;
    }

    printf("%d\n", x);
    return 0;
}

The buffer is 4 characters: 3 for the statement plus 1 for the terminating '\0'. Making it size 3 is a classic buffer overflow.

Complexity

O(n) time, O(1) extra memory.

What to take away

Before writing a comparison for every possible input, look for a position or property that all cases share. It makes code shorter and harder to get wrong. You will see the same trick in 339A Helpful Maths, where digits always sit at even positions in the input.

Codeforces 158A Next Round Solution in C (Explained)

Next Round (158A) is a short implementation problem that tests whether you read a statement precisely. There are two conditions for advancing, and most wrong answers come from handling only one of them.

The problem in short

n contestants took part in a contest (1 ≤ k ≤ n ≤ 50). Their scores are given in non-increasing order. A contestant advances to the next round if their score is at least the score of whoever finished in k-th place, and their score is positive. Count how many contestants advance.

Full statement: Codeforces 158A – Next Round.

Approach

Since the array is sorted from highest to lowest, the k-th place score is simply a[k - 1] (arrays in C start at index 0). Call it the threshold. Then count every score s with s ≥ threshold and s > 0.

The “at least” part matters because of ties. If several people share the k-th place score, all of them advance, so the answer can be larger than k.

Walking through the samples

8 5
10 9 8 7 7 7 5 5

The 5th score is 7, so the threshold is 7. The scores 10, 9, 8, 7, 7, 7 are all ≥ 7 and positive. That is 6 contestants, one more than k, because three people are tied at 7.

4 2
0 0 0 0

The threshold is 0, and every score is ≥ 0, but nobody has a positive score. The answer is 0. This is the sample that catches solutions which forget the second condition.

Solution in C

#include <stdio.h>

int main(void) {
    int n, k;
    int a[55];
    scanf("%d %d", &n, &k);
    for (int i = 0; i < n; i++)
        scanf("%d", &a[i]);

    int threshold = a[k - 1];   /* score of the k-th place finisher */
    int count = 0;

    for (int i = 0; i < n; i++) {
        if (a[i] >= threshold && a[i] > 0)
            count++;
    }

    printf("%d\n", count);
    return 0;
}

Complexity

One pass over the scores: O(n) time and O(n) memory. Since the list is sorted, you could also stop at the first score that fails, but with n ≤ 50 the simple loop is clearer.

Common mistakes

• Printing k directly, which ignores ties and zero scores.
• Using a[k] instead of a[k - 1] as the threshold (off by one).
• Checking > instead of ≥, which drops everyone tied with the k-th place.

Note: an earlier version of this post accidentally showed the code for 71A. It has been replaced with the correct solution above.

Practice next

For more careful condition checking, try 96A Football and 4A Watermelon.