## 11622 - Le Compte est Bon

Moderator: Board moderators

Robert Gerbicz
Experienced poster
Posts: 196
Joined: Wed May 02, 2007 10:12 pm
Location: Hungary, Pest county, Halasztelek
Contact:

### 11622 - Le Compte est Bon

How on the Earth so large the answer for n=8000 ? That means that about 77% percentage of a random 6-tuplet generate 8000. My first code used the http://en.wikipedia.org/wiki/Order_of_operations, and the answer was less than 1 million. And I don't understand this sentence: "(always working with integer and positive numbers)", for example 1-2+10 would be an invalid solution for n=9??!

Using left to right evaulation and c/c++ rounding for integer division I've gotten 5540057 solutions.
Not using the standard c/c++ rounding (so for exapmle -2/3=-1 ), I got 5540237 solutions.
I tried using exact calculation by rationals, that gives 5511601 solutions

On the competion there was one AC, and 4 other (CE,TLE,WA).

Some random solutions using left-to-right order (first the tuplet then the solution for n=8000).

Code: Select all

``````[7, 8, 6, 9, 1, 100]
"1+9*100*8"
[6, 4, 75, 3, 100, 9]
"9+75-4*100"
[4, 50, 100, 100, 4, 6]
"6+4*100*100*4/50"
[3, 4, 10, 10, 3, 50]
"3*10+10*50*4"
``````

baodog
Experienced poster
Posts: 202
Joined: Wed Jul 04, 2007 6:53 am

### Re: 11622 - Le Compte est Bon

I do get 5838170, but it would hit tle for me (without precalculation and nasty uncoding in base 100 to make the 40k source limit, which seems not what's intended!!!). At any time the partial cumulative result cannot become negative, and no fractions are allowed. Conisder posting your code, if you still can't get 5838170.

Robert Gerbicz
Experienced poster
Posts: 196
Joined: Wed May 02, 2007 10:12 pm
Location: Hungary, Pest county, Halasztelek
Contact:

### Re: 11622 - Le Compte est Bon

Thanks! Now solved by precomputation.

Forget the above examples. We should use the order of operations, we can use as many parentheses as we want, all partial calculations should be integer, but my program used negative integers also! This means that for example:

Code: Select all

``````valid: 3+100*2=203
valid: (5-7)*(2+3)+100=90
valid: (2+3)*(7+100+3)=550
valid: 5*100/2+6=256
valid: (2+10)*(5+1)/(3*3)=8
invalid: (2+3/7)*7=17 because the partial result 2+3/7 is not integer
``````

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 11622 - Le Compte est Bon

I also solved it using precomputation and encoding to get it under 40k. It took less than 2 hours to run on my machine.
From all 14^6 tuples, I take every permutation of every combination of size 1 through 6 and apply each of the 4 operations between each two numbers in every possible order. Subtraction is only allowed if the result is positive, division is only allowed if there is no remainder.
Check input and AC output for thousands of problems on uDebug!