11622 - Le Compte est Bon

All about problems in Volume 116. 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
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

Post by Robert Gerbicz » Sat May 23, 2009 6:22 pm

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

Post by baodog » Sat May 23, 2009 7:35 pm

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

Post by Robert Gerbicz » Sat May 23, 2009 9:02 pm

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

Post by brianfry713 » Thu Aug 29, 2013 4:05 am

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!

Post Reply

Return to “Volume 116 (11600-11699)”