投資錢景>買台積電就對了女大生禁不起誘惑!按了..正妹的東京自助旅行買太多也不行!7500...
2012-12-08 12:29:43 人氣(146) | 回應(0) | 推薦(0) | 收藏(0) 上一篇 | 下一篇

[UVA][字串分析] 1200 - A DP Problem

0
收藏
0
推薦

In this problem, you are to solve a very easy linear equation with only one variable x with no parentheses! An example of such equations is like the following:

2x - 4 + 5x + 300 = 98x

An expression in its general form, will contain a `=' character with two expressions on its sides. Each expression is made up of one or more terms combined by `+' or `-' operators. No unary plus or minus operators are allowed in the expressions. Each term is either a single integer, or an integer followed by the lower-case character x or the single character x which is equivalent to 1x.


You are to write a program to find the value of x that satisfies the equation. Note that it is possible for the equation to have no solution or have infinitely many. Your program must detect these cases too.

Input 

The first number in the input line, t ( 1$ le$t$ le$10) is the number of test cases, followed by t lines of length at most 255 each containing an equation. There is no blank character in the equations and the variable is always represented by the lower-case character `x'. The coefficients are integers in the range (0..1000) inclusive.

Output 

The output contains one line per test case containing the solution of the equation. If s is the solution to the equation, the output line should contain $ lfloor$s$ rfloor$ (the ``floor" of s, i.e., the largest integer number less than or equal to s). The output should be `IMPOSSIBLE' or `IDENTITY' if the equation has no solution or has infinite solutions, respectively. Note that the output is case-sensitive.

Sample Input 

2 
2x-4+5x+300=98x
x+2=2+x

Sample Output 

3
IDENTITY


#include <stdio.h>
#include <math.h>
void parse(char *s, int& A, int& B) {
A = 0, B = 0;
int i, g = 0, f = 0, neg = 1;
for(i = 0; s[i]; i++) {
if(s[i] == 'x') {
if(g)
A += neg*f;
else
A += neg;
g = 0, f = 0, neg = 1;
} else {
if(s[i] == '-') {
if(g)
B += neg*f;
g = 0, f = 0;
neg = -1;
} else if(s[i] == '+') {
if(g)
B += neg*f;
g = 0, f = 0;
neg = 1;
} else
f = f*10 + s[i]-'0', g = 1;
}
}
if(g)
B += neg*f;
}
int main() {
int t, i;
scanf("%d", &t);
char s1[502], *s2;
while(t--) {
scanf("%s", s1);
for(i = 0; s1[i]; i++) {
if(s1[i] == '=') {
s2 = s1+i+1;
s1[i] = '\0';
break;
}
}
int la, lb, ra, rb;
parse(s1, la, lb);
parse(s2, ra, rb);
if(la == ra && lb == rb)
puts("IDENTITY");
else if(la == ra && lb != rb)
puts("IMPOSSIBLE");
else
printf("%d\n", (int)floor((double)(rb-lb)/(la-ra)));
}
return 0;
}

 

1200A DP Problem
台長:Morris
人氣(146) | 回應(0)| 推薦 (0)| 收藏 (0)| 轉寄
全站分類: 不分類 | 個人分類: UVA |
此分類下一篇:[UVA][高斯消去][線性系統] 10109 - Solving Systems of Linear ...
此分類上一篇:[UVA][博奕] 10368 - Euclid's Game

我要回應
是 (若未登入"個人新聞台帳號"則看不到回覆唷!)
* 請輸入識別碼:
請輸入以下數字 (ex:123)

(有*為必填)
詳全文