A. Alphabet Cake

I solved this problem by first filling the array row by row, and then column by column.

For each row, at first I enumerate from the first element to the last one until I find an element that is not '?', and then break the loop. If such an element that is not '?' does not exist, it means that this row consists of only '?'. Such a row is skipped, however do not worry since it will be implemented later. Now suppose that we have found such an element which is not '?' and denote it as a variable x (char x;). Then, I enumerate from the first element again, and

1) when a '?' is met, just replace it with x;

2) when x is met (note that x must be the first letter that is met, since I immediately break the loop when the first element that is not '?' is found), do nothing (or replace it with x, which achieves the same result);

3) when a letter different from x is met, just update x with this letter, and go to step 1).

After the above operations, for instance, ???A??B??CD? will be changed into AAAAAABBBCDD. However, it can not cover the case where some row consists of only '?', and thus we repeat the above operations again column by column, i.e., the three steps are exactly the same but the enumeration is implemented in a column.

For instance,

???A??B??CD?

????????????

E????F???GHI

will be first changed into

AAAAAABBBCDD

????????????

EEEEEFFFFGHI

then

AAAAAABBBCDD

AAAAAABBBCDD

EEEEEFFFFGHI

B. Ratatouille

Well, this is a tough problem for me. At first, I could not figure out how to solve large input so I wrote a special version for small input. It was about 15 minutes before the end that I finally realized how to deal with N>2...

At first, we should consider under what conditions that two packages corresponding to different ingredients can be used to constitute a kit (or can be paired). For some given two packages, we denote the quantity they contain as Q1 and Q2, while the number of corresponding ingredients are R1 and R2. If we want to use Q1, we must find some integer K1 that satisfies R1*0.9*K1<=Q1<=R1*1.1*K1, and similarly R2*0.9*K2<=Q2<=R2*1.1*K2 if we want to use Q2. Therefore, if both Q1 and Q2 can be used as a kit, there must be at least one common integer K that satisfies K1=K=K2. Moreover, it is not necessary to find out such a precise K since we can find out the intervals that K1 and K2 falls into, respectively, and then check whether the two intervals intersect with each other or not. If they intersect with each other, it means that at least one common integer K=K1=K2 can be found. According to R1*0.9*K1<=Q1<=R1*1.1*K1, we have Q1/(1.1*R1)=<K1<=Q1/(0.9*R1). Note that the "double division" should be avoided since otherwise you might get stuck in "precision problem". We can multiply both denominator and nominator by 10, which gives (10*Q1)/(11*R1)<=K1<=(10*Q1)/(9*R1). Then, as K1 is an integer, we can use "integer division" to obtain the lower bound (inclusive) as (10*Q1)/(11*R1)+((10*Q1)%(11*R1)!=0), and the upper bound (inclusive) as (10*Q1)/(9*R1), where the '/' is "integer division". Therefore, we can check whether the intervals [(10*Q1)/(11*R1)+((10*Q1)%(11*R1)!=0), (10*Q1)/(9*R1)] and [(10*Q2)/(11*R2)+((10*Q2)%(11*R2)!=0), (10*Q2)/(9*R2)] intersect with each other or not.

Then, suppose that there are only two ingredients, and we consider how the corresponding packages can be "paired" to achieve the maximum number of pairs (or kits). We adopt a greedy idea. We adopt an array Q[N][P] (specifically N=2), where Q[i][j] denotes the quantity of the j-th package corresponding to the i-th ingredient. We first sort the packages in an increasing order of their quantities for each ingredient, i.e., Q[i][0]<=Q[i][1]<=...Q[i][P-1]. Then, we enumerate from the first package to the last one for the 0-th ingredient (a simple example will be shown later). For each enumerated package Q[0][j1], we enumerate from the first package to the last one for the 1-th ingredient, and find out the first one Q[1][j2] that can be paired with Q[0][j1]. Then, we break the loop for Q[1][j2] and go back to the loop for Q[0][j1]. However, for this time, when we deal with Q[0][j1+1], we should start from Q[1][j2+1] but not Q[1][0]. The correctness of such greedy idea can be proved but omitted here. Here is a simple example. Suppose that we have

Q[0][0], Q[0][1], Q[0][2], Q[0][3]

Q[1][0], Q[1][1], Q[1][2], Q[1][3]

We first deal with Q[0][0], and try from Q[1][0] to Q[1][3] one by one, and assume that Q[1][1] is the first one which can be "paired" with Q[0][0]. Then, we deal with Q[0][1], and try from Q[1][2] to Q[1][3], and assume that Q[1][3] is "paired" with Q[0][1]. Then, for Q[0][2] and Q[0][3], they cannot be "paired".

Finally, I introduced a "flag" array to denote whether a package has been selected to be "paired" with some other package or not, i.e., flag[N][P] where flag[i][j]=0 means that the j-th package corresponding to the i-th ingredient is not "paired" while flag[i][j]=1 means that it is "paired" with some package corresponding to the (i+1)-th ingredient. With such a "flag", I can deal with N>3 case. For Q[N][P], I enumerate from N-2 to 0, and for each Q[i][j1], I use the above greedy idea to find out which Q[i+1][j2] can be "paired" with Q[i][j1]. The 'can be "paired"' condition is: Q[i+1][j2] intersects with Q[i][j1] (recall the intervals mentioned above) and flag[i+1][j2]==1. Specifically, the row of flag[N-1][ ] is initialized with all "1" values. When Q[i][j1] is "paired", I update flag[i][j1]=1. Here is a simple example:

Q[0][0], Q[0][1], Q[0][2], Q[0][3]

Q[1][0], Q[1][1], Q[1][2], Q[1][3]

Q[2][0], Q[2][1], Q[2][2], Q[2][3]

with flag as

0, 0, 0, 0

0, 0, 0, 0

1, 1, 1, 1

We first deal with the 1-th row and 2-th row. For Q[1][0], we try from Q[2][0] to Q[2][3] and find Q[2][1] "paired" with Q[1][0], then flag is changed into

0, 0, 0, 0

1, 0, 0, 0

1, 1, 1, 1

For Q[1][1], we try from Q[2][2] to Q[2][3] and find no Q[2][] "paired" with Q[1][1], then nothing is doen.

For Q[1][2], we try from Q[2][2] to Q[2][3] and find no Q[2][3] "paired" with Q[1][2], then the flag is changed into

0, 0, 0, 0

1, 0, 1, 0

1, 1, 1, 1

For Q[1][3], it cannot be "paired". Then, we deal with Q[0][0], and try from Q[1][0] to Q[1][3] but note that Q[1][1] and Q[1][3] must be skipped since flag[1][1]=flag[1][3]=0. Assume that Q[0][0] is not "paired", and then we move on to Q[0][1], and try from Q[1][0] to Q[1][3] (Q[1][1] and Q[1][3] are skipped), and suppose that Q[1][2] is "paired", then the flag is changed into

0, 1, 0, 0

1, 0, 1, 0

1, 1, 1, 1

For Q[0][2] to Q[0][3], they cannot be "paired".

The answer is just the number of "1" in the 0-th row of flag, i.e., 0+1+0+0=1. I think this is similar to the idea of dynamic programming. To constitue as many kits as possible, the packages corresponding to the last row (ingredient) Q[N-1][ ] must be "paired" with some other ones. Thus, we start from Q[N-2][ ] and Q[N-1][ ], and try to find out as many "pairs" as possible. Then, we deal with Q[N-3][ ] and Q[N-2][ ], but the "pairs" must be made based on the "pairs" already exist in Q[N-2][ ], which is indicated by flag[N-2][ ]. The last row flag[N-1][ ] is initialized with all "1" since for Q[N-2][ ], any Q[N-1][ ] can be selected without any restriction. This implies that the number of "1" in flag[0][ ] is just the maximum number of kits (pairs). Finally, I deal with N=1 as a special case.