112A - Petya and Strings

First change all the letters into lower case ones, and then compare the two strings as the problem requires.

112B - Petya and Square

To cut the whole board into two symmetric parts, the cutting line must pass through the central point. Therefore, the following four squares can not be special cells, i.e., (n, n + 1), (n, n), (n + 1, n), (n + 1, n + 1), where (r, c) denotes the r-th row and the c-th column.

112C - Petya and Inequiations

I did not figure out how to prove this, however it turns out that the following solution can pass all the tests.

At first, note that if can satisfy the requirement, then can satisfy as well. Thus, we set a₁ = a₂ = ...a_n - 1 = 1 and a_n = y - n + 1, which gives the maximum value of . Moreover, if y < n, then the answer is definitely “-1”; otherwise we divide y as mentioned above and check the result is no less than x or not.

112D - Petya and Divisors

For each integer n, it takes complexity to obtain all its divisors. For each divisor, we should check whether it is divisible by any one of the previous y integers. Thus, we can use an array idx[n] to record the maximum index of the given integer that has n as its divisor. When we deal with the current i-th query, we find out each of its divisor x, and check idx[x] to determine whether this divisor satisfies the requirement or not. Next, we update idx[x] = i, since x is divisible by the i-th integer.

Update-1: proof of 112C - Petya and Inequiations

Given a₁ + a₂ + ... + a_n = D where only positive integers are involved and D ≥ n, the maximum value of a₁² + a₂² + ... + a_n² is (n - 1) + (D - (n - 1))² with a₁ = a₂ = ... = a_n - 1 = 1 and a_n = D - (n - 1), i.e., the optimal sequence can have at most one positive integer that is greater than 1.

Proof: We prove this claim by contradiction. Assume that the optimal sequence has more than one positive integer that is greater than 1, and we denote them as x and y, with x > 1 and y > 1. Then, we write s₁ = x² + y² and s₂ = 1² + (y + x - 1)², and one can see that the term s₂ means that we set x = 1 while "moving" a quantity of x - 1 to y. Next, s₂ - s₁ = 1 + (y + x - 1)² - x² - y² = 1 - y² + (y - 1)(y + 2x - 1) = (y - 1)(y + 2x - 1) - (y - 1)(y + 1) = 2(y - 1)(x - 1) > 0. Thus, we have obtained a larger (better) value since s₂ > s₁ and this is contradictory to our assumption, which completes the proof.