a094. NOI2003 Day1.1.木棒游戏＠Morris' Blog

2011-08-17 17:31:55| 人氣769| 回應0 | 上一篇 | 下一篇

a094. NOI2003 Day1.1.木棒游戏

推薦 0 收藏 0 轉貼0 訂閱站台

a094. NOI2003 Day1.1.木棒游戏

內容：

【问题描述】
这是一个很古老的游戏。用木棒在桌上拼出一个不成立的等式，移动且只移
动一根木棒使得等式成立。现在轮到你了。

【任务】
从文件读入一个式子。
如果移动一根木棒可以使等式成立，则输出新的等式，否则输出No。

【说明和限制】
1．式子中只会出现加号和减号（包括负号），并且有且仅有一个等号，不会出现
括号、乘号或除号，也不会有++,--,+-或-+出现。
2．式子中不会出现8个或8个以上的连续数字。
3．你只能移动用来构成数字的木棒，不能移动构成运算符（+ -=）的木棒，所
以加号、减号、等号是不会改变的。移动前后，木棒构成的数字必须严格与
图2中的0~9相符。
4．修改前的等式中的数不会以0 开头，但允许修改后的等式中的数以数字０开
头。

輸入說明：

从文件中读入一行字符串。该串中包括一个以“#”字符结尾的式
子（ASCII 码35)，式子中没有空格或其他分隔符。输入数据严格符合逻辑。字
符串的长度小于等于1000。
注意：“#”字符后面可能会有一些与题目无关的字符。

輸出說明：

输出结果到文件，输出仅一行。
如果有解，则输出正确的等式，格式与输入的格式相同（以“#”结尾，中
间不能有分隔符，也不要加入多余字符）。
如果无解，则输出“No”（N大写，o 小写）。

範例輸入：

1+1=3#

1+1=3+5#

11+77=34#

範例輸出：

1+1=2#

No

17+17=34#

提示：

出處：

NOI2003 Day1 第一题 (管理：liouzhou_101)

作法 : 窮舉
窮舉轉換的位置, 判斷是否兩邊相等, 請用 O(1) 左右的辦法,
重新計算, 會吃 TLE,
轉換可以增一根, 減一根, 以及自己本身變換

/**********************************************************************************/
/* Problem: a094 "NOI2003 Day1.1.木棒游戏" from NOI2003 Day1 第一题       */
/* Language: C                                                                   */
/* Result: AC (8ms, 170KB) on ZeroJudge                                          */
/* Author: morris1028 at 2011-08-17 17:24:51                                     */
/**********************************************************************************/

#include<stdio.h>
#include<stdlib.h>
int ch1[10][3] = {/*add1*/
       {8,-1},{7,-1},{-1},{9,-1},{-1},
       {6,9,-1},{8,-1},{-1},{-1},{8,-1}
   };
int ch2[10][4] = {/*minus*/
       {-1},{-1},{-1},{-1},{-1},
       {-1},{5,-1},{1,-1},{0,6,9,-1},{3,5,-1}
   };
int ch3[10][3] = {/*no*/
       {6,9,-1},{-1},{3,-1},{2,5,-1},{-1},
       {3,-1},{0,9,-1},{-1},{-1},{0,6,-1}
   };
int flag, left, right;
char s[1001];
void Calu1() {
   int a, neg = 1, tmp = 0;
   left = right = 0;
   for(a = 0; s[a] && s[a] != '='; a++) {
       if(s[a] >= '0' && s[a] <= '9')
           tmp = tmp*10 + s[a] - '0';
       else {
           left += tmp * neg;
           if(s[a] == '+')   neg = 1;
           else neg = -1;
           tmp = 0;
       }
   }
   left += tmp * neg, tmp = 0, neg = 1;
   for(a ++; s[a] && s[a] != '#'; a++) {
       if(s[a] >= '0' && s[a] <= '9')
           tmp = tmp*10 + s[a] - '0';
       else {
           right += tmp * neg;
           if(s[a] == '+')   neg = 1;
           else neg = -1;
           tmp = 0;
       }
   }
   right += tmp * neg;
}
void Calu2(int x, int s1, int y, int s2, int t1, int t2) {
   int a, v = 1, tl = left, tr = right;
   int neg = 1;
   if(x == y) return;
   for(a = x+1; s[a]; a++)
       if(s[a] >= '0' && s[a] <= '9')   v *= 10;
       else   break;
   for(a = x-1; a >= 0; a--)
       if(s[a] == '-') neg = -1;
       else if(s[a] == '+')neg = 1;
       else break;
   if(s1 == 0)   tl -= (t1-(s[x]-'0'))*v*neg;
   else   tr -= (t1-(s[x]-'0'))*v*neg;
   if(y != -1) {
       for(a = y+1, v = 1, neg = 1; s[a]; a++)
           if(s[a] >= '0' && s[a] <= '9')   v *= 10;
           else   break;
       for(a = y-1; a >= 0; a--)
           if(s[a] == '-') neg = -1;
           else if(s[a] == '+')neg = 1;
       else break;
       if(s2 == 0)   tl -= (t2-(s[y]-'0'))*v*neg;
       else tr-= (t2-(s[y]-'0'))*v*neg;
   }
   if(tl == tr) {
       flag = 1;
       for(a = 0; s[a] && s[a] != '#'; a++)
           printf("%c", s[a]);
       puts("#");
   }
}
main() {
   int a, b, c, d;
   while(scanf("%s", s) == 1) {
       flag = 0;
       for(a = 0; s[a]; a++)
           if(s[a] == '#') flag = 1;
       if(flag == 0) continue;
       else flag = 0;
       Calu1();
       int set1 = 0, set2 = 0;
       for(a = 0; s[a] && flag == 0 && s[a] != '#'; a++)
           if(s[a] >= '0' && s[a] <= '9') {
               int t1 = s[a]-'0';
               for(b = 0; ch3[t1][b] != -1; b++) {
                   s[a] = ch3[t1][b]+'0';
                   Calu2(a, set1, -1, set2, t1, -1);
                   if(flag)   break;
               }
               for(b = 0; ch1[t1][b] != -1 && flag == 0; b++) {
                   s[a] = ch1[t1][b]+'0', set2 = 0;
                   for(c = 0; s[c] && s[c] != '#' && flag == 0; c++) {
                       if(s[c] >= '0' && s[c] <= '9') {
                           int t2 = s[c]-'0';
                           for(d = 0; ch2[t2][d] != -1 && flag == 0; d++) {
                               s[c] = ch2[t2][d]+'0';
                               Calu2(a, set1, c, set2, t1, t2);
                               if(flag)   break;
                           }
                           s[c] = t2+'0';
                       } else {
                           if(s[c] == '=') set2 = 1;
                       }
                   }
               }
               for(b = 0; ch2[t1][b] != -1 && flag == 0; b++) {
                   s[a] = ch2[t1][b]+'0', set2 = 0;
                   for(c = 0; s[c] && s[c] != '#' && flag == 0; c++) {
                       if(s[c] >= '0' && s[c] <= '9') {
                           int t2 = s[c]-'0';
                           for(d = 0; ch1[t1][d] != -1 && flag == 0; d++) {
                               s[c] = ch1[t1][d]+'0';
                               Calu2(a, set1, c, set2, t1, t2);
                               if(flag)   break;
                           }
                           s[c] = t2+'0';
                       } else {
                           if(s[c] == '=')   set2 = 1;
                       }
                   }
               }
               s[a] = t1+'0';
           } else {
               if(s[a] == '=')   set1 = 1;
           }

        if(!flag)    puts("No");
    }
    return 0;
}

我要檢舉

#a094#NOI2003#Day1.1#木棒游戏

台長： Morris

您可能對以下文章有興趣

[ZJ][模擬、旋轉] b125. 積木的拼疊問題（Bricks）

[ZJ][數學解] a534. IOI2008 Day2.1.花園問題

[ZJ][拓樸] d917. 5. 貼磁磚

[ZJ][樹形dp] a265. 紅黑樹

人氣(769) | 回應(0)| 推薦 (0)| 收藏 (0)| 轉寄
全站分類: 不分類 | 個人分類: 資訊競賽 |
此分類下一篇:d232. 97北縣賽-3-資料統計問題
此分類上一篇:d855. NOIP2001 2.数的划分

回應(0)