12414: Calculating Yuan Fen

For this UVA problem, I created a Microsoft Excel simulation to find out if there are any patterns I can see. In the file, the two yellow boxes can be changed by the user. The first yellow box can be changed to the desired ST value, while the second yellow box can be edited to the desired test case, which corresponds to the name abbreviations of the couple. For instance, the first yellow box can be changed to 2277, and the second yellow box can be changed to QWERTY. By doing so, one would be able to see that the numbers converge to 100.

I tried looking for a pattern in the Microsoft Excel simulation but could not seem to find one. I checked the web for clues and I read a blog that mentioned that there is no trick needed for this problem. A straightforward brute-force approach would do. So, I tried implementing a brute-force approach, which fortunately got accepted with a run time of 0.220. I thought I would breach the 2.000-second time limit.

In this implementation, for every test case, I first converted each letter to its corresponding number representation by subtracting the ascii number equivalent of 'A' from the ascii number equivalent of the letter in the test case, and adding ST (lines 033-035). For instance, for an ST value of 81, the letter J would be represented as 90, because the ascii number equivalent of J is 74, while that of A is 65. So, 74-65+81 gives 90.

After converting all letters in the test case to their corresponding number representations that are stored in an integer array, nrep[], I split each number into its individual digits, by a modulo-divide loop (lines 040-044). For instance, to obtain the digits of the number 90, first get the remainder of 90 when it is divided by 10. This would give 0, which is the first digit of 90. Then divide 90 by 10, and this leaves us with 9. The remainder of 9 when it is divided by 10 gives us 9, which is the second digit of 90. Now, we divide 9 by 10, and this gives us the integer, 0, which is our signal to stop the loop. Since, we obtain the digits from the least significant digit, we have to store these digits in reverse into the main array, narr[] (lines 046-048).

Once the main integer array, narr[], is built, we reduce the length of this array by 1 by getting the modulo of the sum of each consecutive integer pair in the array, as described in the problem. We continue reducing the length of the array by 1, and we only stop the reducing loop (lines 051-055) when the length of the array has been reduced to 3. At this length, a check (lines 057-060) is performed to see if a 100 is obtained in the first 3 elements of the array. If a 100 is obtained, the ST loop is broken, and the value of ST which yielded the 100 yuan-fen result is printed. Otherwise, if the ST loop is naturally terminated and not broken mid-way, then a sad-face is printed (lines 066-068).

The first part of the code (lines 009-030) is for parsing words, which in this case, are the test cases, which correspond to the abbreviations of the names of the lovers being assessed for yuan-fen compatibility. I believe there are more convenient ways to parse, but as long as the code works, then maybe it would suffice. Perhaps, my parsing algorithm may have slowed down the performance of my code.

Here is my C/C++ code for your comments, hopefully, for improvements:

001 #include <stdio.h>
002 
003 int main() {
004   char line[100], ctmp[100];
005   
006   int i, j, k, q, r, s, t;
007   int nrep[10], st, narr[50], itmp[5];
008 
009   while (fgets(line, 100, stdin)) {
010     for (i = 0; 1; i += 1) {
011       if (line[i] == '\n' || line[i] == 0) {
012         break;
013       }
014     
015       if (line[i] == ' ' || line[i] == '\t') {
016         continue;
017       }
018 
019       for (j = 0; 1 ; i += 1, j += 1) {
020         if (    line[i] == ' '
021              || line[i] == '\t' 
022              || line[i] == '\n'
023              || line[i] == 0
024         ) {
025           break;
026         }
027       
028         ctmp[j] = line[i];
029       }
030       ctmp[j] = 0;
031       
032       for (st = 1, t = 0; st <= 10000; st += 1) {        
033         for (k = 0; k < j; k += 1) {
034           nrep[k] = ctmp[k] - 'A' + st;
035         }
036         
037         for (k = 0, s = 0; k < j; k += 1) {
038           q = nrep[k];
039           
040           for (r = 0; q > 0; r += 1) {
041             itmp[r] = q % 10;
042             
043             q /= 10;          
044           }
045           
046           for (r -= 1; r >= 0; r -= 1, s += 1) {
047             narr[s] = itmp[r];
048           }        
049         }    
050     
051         for (s -= 1; s > 2; s -= 1) {
052           for (k = 0; k < s; k += 1) {
053             narr[k] = (narr[k] + narr[k+1]) % 10;
054           }
055         }
056         
057         if (narr[0] == 1 && narr[1] == 0 && narr[2] == 0) {
058           t = 1;
059           break;
060         }
061       }
062       
063       if (t) {
064         printf("%d\n", st);
065       }
066       else {
067         printf(":(\n");
068       }
069     }
070   }
071   
072   return 0;
073 }