2011-08-17 17:31:55Morris
a094. NOI2003 Day1.1.木棒游戏
a094. NOI2003 Day1.1.木棒游戏
內容 ：
【问题描述】
这是一个很古老的游戏。用木棒在桌上拼出一个不成立的等式，移动且只移
动一根木棒使得等式成立。现在轮到你了。
【任务】
从文件读入一个式子。
如果移动一根木棒可以使等式成立，则输出新的等式，否则输出No。
【说明和限制】
1．式子中只会出现加号和减号（包括负号），并且有且仅有一个等号，不会出现
括号、乘号或除号，也不会有++,--,+-或-+出现。
2．式子中不会出现8个或8个以上的连续数字。
3．你只能移动用来构成数字的木棒，不能移动构成运算符（+ -=）的木棒，所
以加号、减号、等号是不会改变的。移动前后，木棒构成的数字必须严格与
图2中的0~9相符。
4．修改前的等式中的数不会以0 开头，但允许修改后的等式中的数以数字０开
头。
輸入說明
：
从文件中读入一行字符串。该串中包括一个以“#”字符结尾的式
子（ASCII 码35)，式子中没有空格或其他分隔符。输入数据严格符合逻辑。字
符串的长度小于等于1000。
注意：“#”字符后面可能会有一些与题目无关的字符。
子（ASCII 码35)，式子中没有空格或其他分隔符。输入数据严格符合逻辑。字
符串的长度小于等于1000。
注意：“#”字符后面可能会有一些与题目无关的字符。
輸出說明
：
输出结果到文件，输出仅一行。
如果有解，则输出正确的等式，格式与输入的格式相同（以“#”结尾，中
间不能有分隔符，也不要加入多余字符）。
如果无解，则输出“No”（N大写，o 小写）。
如果有解，则输出正确的等式，格式与输入的格式相同（以“#”结尾，中
间不能有分隔符，也不要加入多余字符）。
如果无解，则输出“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,
轉換可以增一根, 減一根, 以及自己本身變換
作法 : 窮舉
窮舉轉換的位置, 判斷是否兩邊相等, 請用 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;
}