Programming exercise on 14 August

A.Zero Sum Game

The sum of the $N$ people’s score is always $0$. Denoting by $A_N$ the score of person $N$, we have $A_1+A_2+ \cdots +A_{N−1}+A_N=0$, so $A_N=−(A_1+ A_2+ \cdots +A_{N−1})$.

It is sufficient to receive the scores of the $(N−1)$ people, find the sum, multiply it by $−1$, and print the result.

N = int(input())
A = list(map(int, input().split()))
print(-sum(A))

B

First, we count the occurrences of each character in $S$. Prepare a length-$26$ array $cnt$; for $i=1,2,\cdots,26$, let $cnt[i]$= (the number of occurrences of the $i$-th character of the alphabet in $S$).

Next, for each integer $i$ greater than or equal to $1$, we inspect the number of occurrences of $i$ in $cnt$. Prepare a length-$100$ array $cnt2$; for $i=1,2,\cdots,100$, let $cnt2[i]$= (the number of occurrences of $i$ in $cnt$).

After filling these arrays, $cnt2[i]$ equals the number of distinct characters that occur exactly $i$ times in $S$. Hence, one can answer the original problem by checking if all values of $cnt2$ are $0$ or $2$.

Sample code (Python)

S = input()
cnt = [0] * 26
for c in S:
    cnt[ord(c) - ord("a")] += 1
cnt2 = [0] * 101
for c in cnt:
    if c > 0:
        cnt2[c] += 1
print("Yes" if all(c in (0, 2) for c in cnt2) else "No")

C

Let $S_i$ denote the $i$-th character of $S$, and $T_j$ the $j$-th character of $T$.

First of all, capitalize all characters of $S$.

If $T$ does not end with X, one can determine if $T$ is a substring of $S$.

If $T$ ends with X, one can determine if the first two characters of $T$ is a substring of $S$.

Finally, we describe how to determine if a string $T$ is a substring of $S$. This can be achieved by corresponding each character of $T$ to a character of $S$, greedily from the left, and checking if it succeeds to the end of $T$. More formally, it can be determined by the following greedy algorithm:

1. Initialize $k\leftarrow1$.
2. For each $j=1,2,\cdots,|T|$, do the following:
   1. If there is no $i$ such that $S_i=T_j$ and $k \le i \le |S|$, return No and terminate.
   2. If there is a conforming $i$, let $i′$ be the smallest one. Set$k \leftarrow i′+1$
3. Return Yes and terminate.

Sample code (Python)

s = input() + 'x'
t = input()

p = 0
indexes = []
for c in t.lower():
    a = s.find(c, p)
    p = a + 1
    indexes.append(a)

i, j, k = indexes

ans = 'Yes' if (i < j < k) else 'No'

print(ans)