817 - According to Bartjens

All about problems in Volume 8. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

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

817 - According to Bartjens

Post by junbin »

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

Adrian Kuegel
Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany

Post by Adrian Kuegel »

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

Post by junbin »

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

Post by junbin »

-- 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

Adrian Kuegel
Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany

Post by Adrian Kuegel »

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

Post by yusuf »

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

Adrian Kuegel
Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany

Post by Adrian Kuegel »

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

Post by yusuf »

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,

Post Reply

Return to “Volume 8 (800-899)”