## 817 - According to Bartjens

Moderator: Board moderators

junbin
Experienced poster
Posts: 174
Joined: Mon Dec 08, 2003 10:41 am

### 817 - According to Bartjens

I'm trying to solve q817 According to Bartjens without luck..

My algorithm uses brute force to generate all posibilities and then prints the ones that give 2000 as the answer.. but the judge gives WA.

Can someone with AC please verify my output? Thank you!

input:

Code: Select all

``````398418986=
29961250=
268369264=
128833027=
72492121=
569334384=
24593075=
527215732=
957667301=
20633440=
8400519=
82820233=
042872620=
196314291=
298647=
476496525=
44995560=
227677387=
3722=
230428=
7935064=
34916=
110495=
923325=
5035=
06666263=
95105309=
7715=
586629=
526472=
80818=
98458=
3295=
53217=
7176044=
23829=
0652=
92481212=
091177321=
005784828=
``````

my output:

Code: Select all

``````Problem 1
3+9+84+1898+6=
Problem 2
2*996+1+2+5+0=
2*996+1+2+5-0=
Problem 3
2*6+836+9*2*64=
2-6-8+3*692-64=
2-68*3-6+92*6*4=
2-68+3*692-6-4=
26*83-6*9-26*4=
Problem 4
1+2+8*83*3+0-2+7=
1+2+8*83*3-0-2+7=
1-2+8*83*3+0+2+7=
1-2+8*83*3-0+2+7=
Problem 5
72-4+92*1*21=
Problem 6
569+33*43+8+4=
Problem 7
245*9-30*7+5=
Problem 8
527+215*7-32=
Problem 9
9+5*7*6*6+730+1=
9-5-7-6+67*30-1=
Problem 10
2*0+6*334-4+0=
2*0+6*334-4-0=
Problem 11
8+400*5+1-9=
Problem 12
8-28+2023-3=
Problem 13
0-4+28*72-6*2+0=
0-4+28*72-6*2-0=
Problem 14
1963+14*2+9*1=
Problem 15
2*986+4*7=
Problem 16
4+7*6*49-65-2+5=
4+7+64+965*2-5=
476-4*9+6*52*5=
Problem 17
4*499+5+5-6+0=
4*499+5+5-6-0=
Problem 18
2*27*6*7-7-3*87=
2+276*7+7+3+8*7=
2+276*7-7*3+87=
Problem 19
IMPOSSIBLE
Problem 20
IMPOSSIBLE
Problem 21
IMPOSSIBLE
Problem 22
IMPOSSIBLE
Problem 23
IMPOSSIBLE
Problem 24
IMPOSSIBLE
Problem 25
IMPOSSIBLE
Problem 26
IMPOSSIBLE
Problem 27
IMPOSSIBLE
Problem 28
IMPOSSIBLE
Problem 29
IMPOSSIBLE
Problem 30
IMPOSSIBLE
Problem 31
IMPOSSIBLE
Problem 32
IMPOSSIBLE
Problem 33
IMPOSSIBLE
Problem 34
IMPOSSIBLE
Problem 35
IMPOSSIBLE
Problem 36
IMPOSSIBLE
Problem 37
IMPOSSIBLE
Problem 38
IMPOSSIBLE
Problem 39
IMPOSSIBLE
Problem 40
IMPOSSIBLE
``````

Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany
There is exactly one special case. Read the problem statement again, think what the special case could be, and you will get Accepted

junbin
Experienced poster
Posts: 174
Joined: Mon Dec 08, 2003 10:41 am
The only special cases I can think of are:

He is sure that whenever he wrote down a number (other than 0), it would not start with a zero. So 2*10*0100= could not have been one of his problems.

He also knows he never wrote the number zero as anything but 0. So he would not have a problem like 2*1000+000=.

The last test case is followed by a line containing only the equal sign. This line should not be processed.

ie:

1/2) 2000000

3) =______

where ______ are spaces

but I sent a program in that would give a floating point error if there is another line of data after the line with = as the first character.. and I got WA.. so there's no case 3.

Case 1 and 2, my program handles fine:

Code: Select all

``````2000000=
Problem 1
2000+0*0*0=
2000+0*0+0=
2000+0*0-0=
2000+0+0*0=
2000+0+0+0=
2000+0+0-0=
2000+0-0*0=
2000+0-0+0=
2000+0-0-0=
2000-0*0*0=
2000-0*0+0=
2000-0*0-0=
2000-0+0*0=
2000-0+0+0=
2000-0+0-0=
2000-0-0*0=
2000-0-0+0=
2000-0-0-0=
``````

and since all operations are binary, there cannot be a case where:

Code: Select all

``````24004400
Problem 1
-2400+4400
``````

so.. I did I find the special case... or am I missing the nail completely?

junbin
Experienced poster
Posts: 174
Joined: Mon Dec 08, 2003 10:41 am
-- edit --

ignore the below post.. 2000= should be impossible. :p silly one or more statemnets...

anyway, I managed to get AC.. thanks to Adrian for pointing out. :p

-- end edit --

I just reread the question for the 100th time and I figured that a line with only = cannot exist (since there must be 1 to 9 numbers).

So the only special case I can think of is:

2000=

which should just give

2000=

and my program does that.. but is still wa. :p

Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany
Well, the only difficulty in this problem is to find this special case. I myself don't like special cases very much, but for this problem I had to insert this case, because I think that the World Finals input probably also had the 2000= case included.

yusuf
New poster
Posts: 2
Joined: Mon May 17, 2004 4:36 am
Any hints on the special case?

Not more than 9 digits - check

at least 1 digit - check (if there was no digit it would be the end, right?)

Opertoras properly placed - no leading zeros + only unary ops + times before other ops

What am I missing?

Cheers,

Yusuf

Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany
ignore the below post.. 2000= should be impossible. :p silly one or more statemnets...
...because I think that the World Finals input probably also had the 2000= case included
Isn't this enough hint?
And the problem description says:
insert one or more of the operators +, - and * in such a way ...

yusuf
New poster
Posts: 2
Joined: Mon May 17, 2004 4:36 am
My program already handles 2000= as impossible, but still gets a WA.

The output is the same as what junbin posted above, so must be still missing a test case...

Cheers,