UVa817 According to Bartjens

链接:Link 状态:WA

分析

做了两个小时,很可惜最终还是 WA 了。非常奇怪——和网上的 C++ 代码运行结果完全一样,但却 WA 了。不过,在这里我还是记录一下解题的过程。 这道题数据量很小,直接爆搜每个空位,用 *, +, -, #0 来代表符号或不填。

Code

const
operators: array [1..4] of char = ('*', '+', '-', #0); //符号
var
s: string;
_, n: integer;
op: array [0..10] of char;
yes: Boolean;

function toValue(ch: char): integer;
begin
exit(ord(ch) - ord('0'));
end;

procedure calcAndPrint;
var
numtop, opstop: Integer; //数字栈,符号栈
num: array [1..10] of longint;
ops: array [1..10] of char;
i: integer;
begin
i := 1;
numtop := 1;
num[numtop] := toValue(s[1]);
opstop := 0;
while i <= n do
begin
while (i < n) and (op[i] = #0) do
begin
inc(i);
num[numtop] := num[numtop] * 10 + toValue(s[i]);
end;
if (op[i] in ['+', '-']) or (i >= n) then
begin
while (opstop > 0) and (ops[opstop] = '*') do
begin
dec(opstop);
num[numtop - 1] := num[numtop] * num[numtop -1];
dec(numtop);
end;
end;
if i >= n then break;
inc(opstop);
ops[opstop] := op[i];
inc(i);
inc(numtop);
num[numtop] := toValue(s[i]);
end;
i := 1;
while i < numtop do
begin
if ops[i] = '+' then
num[i+1] := num[i] + num[i+1]
else
num[i+1] := num[i] - num[i+1];
inc(i);
end;
if (num[numtop] = 2000) and (opstop > 0) then
begin
yes := True;
write(' ');
for i := 1 to n do
begin
write(s[i]);
if op[i] <> #0 then
write(op[i]);
end;
writeln('=');
end;
end;

procedure dfs(t: integer); //搜索第t个位置
var
i: Integer;
ch: char;
begin
if t = n then
begin
calcAndPrint;
exit;
end;
for i := 1 to 4 do
begin
ch := operators[i];
if (ch = #0) and (s[t] = '0') and ((t = 1) or (t > 1) and (op[t-1] <> #0)) then continue;
op[t] := ch;
dfs(t+1);
end;
end;

var
i: Integer;

begin
assign(input, 'main.in'); reset(input);
assign(output, 'main.out'); rewrite(output);

readln(s);
_ := 0;
while not eof and (s[1] <> '=') do
begin
i := 1;
while not (s[i] in ['0'..'9', '=']) do
begin
inc(i);
end;
delete(s, 1, i-1);
n := pos('=', s) - 1;
inc(_);
writeln('Problem ', _);
yes := False;
fillchar(op, sizeof(op), 0);
dfs(1);
if not yes then
writeln(' IMPOSSIBLE');
readln(s);
end;

close(input); close(output);
end.

作者:hsfzxjy
链接:
许可:CC BY-NC-ND 4.0.
著作权归作者所有。本文不允许被用作商业用途,非商业转载请注明出处。

«UVa11526 H(n)

OOPS!

A comment box should be right here...But it was gone due to network issues :-(If you want to leave comments, make sure you have access to disqus.com.