lua-users home
lua-l archive

[Date Prev][Date Next][Thread Prev][Thread Next] [Date Index] [Thread Index]


possibly not. It scales badly on large a and m....


Am 04.01.2017 um 18:59 schrieb Oliver Kroth:
Hi Egor,

you may possibly stay within the tmieout with this algorithm:
(this isonly a test snippet, it uses fixed a and m)

local p={ 2,3,5,7,11,13,17,19 }
local m=2
local a=4

-- vektor of exponents
local i={}
local sum=0

-- k is the exponent to count through
-- u is the available occurrences
local function find( k, u )
    if k==0 then
        -- made a full counting step
        -- compute the divisor from the  prime factors
        local f=1
        for j,e in ipairs( i ) do
            f = f * p[j] ^ e
        -- multiply by frequency and add
        sum = sum + f*u
        while sum > 1000000007 do sum = sum - 1000000007 end
        i[k-1] = 0
        for x=0,a+k do
            i[k] = x
            find( k-1, u * (a+k+1-x) )

find(m, 1)

Am 04.01.2017 um 13:10 schrieb Egor Skriptunoff:

I have made an attempt to use Lua as language for solving problems
in a programming contest.
I came across a situation where I can solve a problem using Pascal,
but not using Lua (4 test cases of 10 were failed due to timeout).

This is the problem I'm talking about:
The contest is over, so it is OK to discuss the solutions.