当前位置: 首页 > 工具软件 > romannumerals > 使用案例 >

UVa 185 - Roman Numerals

东郭淇
2023-12-01

题目链接:http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=109&page=show_problem&problem=121

题目描述:(待编辑)

分析:(待编辑)

  1 #include <cstdio>
  2 #include <cstring>
  3 
  4 const int MAXN = 12;
  5 
  6 char num1[MAXN], num2[MAXN], sum[MAXN], str[100];
  7 int len1, len2, len3;
  8 int char_to_num[30];
  9 int Flag;
 10 bool visnum[30];
 11 int visch[30];
 12 int lenth;
 13 bool vis[9876543];
 14 
 15 void init()
 16 {
 17     memset(char_to_num, 0, sizeof(char_to_num) );
 18     char_to_num[ 'I' - 'A' ] = 1;
 19     char_to_num[ 'X' - 'A' ] = 10;
 20     char_to_num[ 'C' - 'A' ] = 100;
 21     char_to_num[ 'M' - 'A' ] = 1000;
 22     char_to_num[ 'V' - 'A' ] = 5;
 23     char_to_num[ 'L' - 'A' ] = 50;
 24     char_to_num[ 'D' - 'A' ] = 500;
 25     return;
 26 }
 27 
 28 void InputDeal()
 29 {
 30     int i = 0, j = 0;
 31     while ( str[i] && str[i] != '+' )
 32         num1[j++] = str[i++];
 33     num1[j] = '\0';
 34     len1 = j;
 35 
 36     j = 0;
 37     ++i;
 38     while ( str[i] && str[i] != '=' )
 39         num2[ j++ ] = str[ i++ ];
 40     num2[j] = '\0';
 41     len2 = j;
 42 
 43     j = 0;
 44     ++i;
 45     while ( str[i] )
 46         sum[j++] = str[i++];
 47     sum[j] = '\0';
 48     len3 = j;
 49     /*
 50         puts(num1);
 51         puts(num2);
 52         puts(sum);
 53     */
 54     return;
 55 }
 56 
 57 int GetNum( char *ss )
 58 {
 59     int len = strlen(ss);
 60     int number = char_to_num[ ss[len - 1] - 'A' ];
 61     for ( int i = len - 2; i >= 0; --i )
 62     {
 63         int next = char_to_num[ ss[i + 1] - 'A' ];
 64         int cur = char_to_num[ ss[i] - 'A' ];
 65         if ( cur < next ) number -= cur;
 66         else number += cur;
 67     }
 68     return number;
 69 }
 70 
 71 bool checkRoma()
 72 {
 73     int n1 = GetNum( num1 );
 74     int n2 = GetNum( num2 );
 75     int Sum = GetNum( sum );
 76 //    printf("%d %d %d\n", n1, n2, Sum );
 77     return ( ( n1 + n2 ) == Sum );
 78 }
 79 
 80 bool Judge()
 81 {
 82     if ( ( len3 > 1 && !visch[ sum[0] - 'A' ] )
 83        || ( len1 > 1 && !visch[ num1[0] - 'A' ] )
 84        || ( len2 > 1 && !visch[ num2[0] - 'A' ] ) ) return false;
 85     int n1 = 0;
 86     int n2 = 0;
 87     int Sum = 0;
 88 
 89     int i = 0;
 90     while ( num1[i] ) n1 = n1 * 10 + visch[ num1[i++] - 'A'];
 91     i = 0;
 92     while ( num2[i] ) n2 = n2 * 10 + visch[ num2[i++] - 'A'];
 93     i = 0;
 94     while ( sum[i] ) Sum =  Sum * 10 + visch[ sum[i++] - 'A'];
 95 
 96 //    if ( n1 + n2 == Sum )
 97 //    printf( "%d %d %d\n", n1, n2, Sum );
 98 
 99     return n1 + n2 == Sum;
100 }
101 
102 int GetNNN()
103 {
104     int nn = 0;
105     if ( visch['I' - 'A' ] >= 0 )
106         nn += visch['I' - 'A' ];
107     if ( visch['X' - 'A' ] >= 0 )
108         nn += visch['X' - 'A' ] * 10;
109     if ( visch['C' - 'A' ] >= 0 )
110         nn += visch['C' - 'A' ] * 100;
111     if ( visch['M' - 'A' ] >= 0 )
112         nn += visch['M' - 'A' ] * 1000;
113     if ( visch['V' - 'A' ] >= 0 )
114         nn += visch['V' - 'A' ] * 10000;
115     if ( visch['L' - 'A' ] >= 0 )
116         nn += visch['L' - 'A' ] * 100000;
117     if ( visch['D' - 'A' ] >= 0 )
118         nn += visch['D' - 'A' ] * 1000000;
119 
120     return nn;
121 }
122 
123 void DFS( int cur, char *ss )
124 {
125     if ( Flag >= 2 ) return;
126     if ( cur >= lenth )
127     {
128         int nnn = GetNNN();
129     //    printf("%d\n", nnn);
130         if ( !vis[nnn] )
131         {
132             vis[nnn] = true;
133             if ( Judge() ) ++Flag;
134         }
135         return;
136     }
137 
138     for ( int i = 0; i < 10; ++i )
139         if ( !visnum[i] )
140         {
141             visnum[i] = true;
142 
143             if ( visch[ ss[cur] - 'A' ] == -1 )
144             {
145                 visch[ ss[cur] - 'A' ] = i;
146                 DFS( cur + 1, ss );
147                 visch[ ss[cur] - 'A' ] = -1;
148             }
149             else DFS( cur + 1, ss );
150 
151             visnum[i] = false;
152 
153         }
154     return;
155 }
156 
157 int main()
158 {
159     init();
160  //   freopen( "s.out", "w", stdout );
161     while ( scanf( "%s", str ), str[0] != '#' )
162     {
163         memset( vis, false, sizeof(vis) );
164 
165         InputDeal();
166         if ( checkRoma() ) printf("Correct ");
167         else printf("Incorrect ");
168 
169         memset( visnum, false, sizeof(visnum) );
170         memset( visch, -1, sizeof(visch) );
171 
172         Flag = 0;
173 
174         strcpy( str, num1 );
175         strcat( str, num2 );
176         strcat( str, sum );
177 
178         lenth = strlen(str);
179         DFS( 0, str );
180 
181         switch(Flag)
182         {
183         case 0:
184             puts("impossible");
185             break;
186 
187         case 1:
188             puts("valid");
189             break;
190 
191         default:
192             puts("ambiguous");
193         }
194     }
195     return 0;
196 }

 

转载于:https://www.cnblogs.com/GBRgbr/archive/2012/11/08/2761705.html

 类似资料:

相关阅读

相关文章

相关问答