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 }

## No comments:

## Post a Comment