The problem is from SPOJ Online Judge [problem description here]
The puzzle asks to you check if the given sequence of integers consists of strictly two parts: the first part descending and the second ascending. If the length of the given integers is 1, it is false. If it is two integers, we can either print true or false, both are correct.
Otherwise, we need to check first if sequence is descending (at least has a descending sub-sequence). And then we check if the sequence is ascending.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 | -- split a string into array function split(s, delimiter) result = {} for match in (s..delimiter):gmatch("(.-)"..delimiter) do table.insert(result, match) end return result end n = tonumber(io.read()) arr = {} for key, var in ipairs(split(io.read(), [[ ]])) do table.insert(arr, tonumber(var)) -- convert to numbers end function Check(s) local len = #s if len <= 2 then return true else local i = 1 while (i < len) and (s[i] > s[i + 1]) do i = i + 1 end if i == 1 then -- not descending return false end i = i + 1 while (i < len) and (s[i] < s[i + 1]) do i = i + 1 end return i == len -- has descending remainder end end if (Check(arr)) then print("Yes") else print("No") end |
-- split a string into array function split(s, delimiter) result = {} for match in (s..delimiter):gmatch("(.-)"..delimiter) do table.insert(result, match) end return result end n = tonumber(io.read()) arr = {} for key, var in ipairs(split(io.read(), [[ ]])) do table.insert(arr, tonumber(var)) -- convert to numbers end function Check(s) local len = #s if len <= 2 then return true else local i = 1 while (i < len) and (s[i] > s[i + 1]) do i = i + 1 end if i == 1 then -- not descending return false end i = i + 1 while (i < len) and (s[i] < s[i + 1]) do i = i + 1 end return i == len -- has descending remainder end end if (Check(arr)) then print("Yes") else print("No") end
We use operator # (sharp) to get the length of a table/array. Also, the sub-strings split should be converted to numbers before comparison i.e. ‘-2′>’-1′ but -2<-1.
The keyword local is similar to the var in Javascript, where it tells the interpreter that the following variable has a limited local scope otherwise, it will be declared as a global variable.
Each statement can be optionally followed by a semicolon, which is similar in Javascript.
The overall algorithm complexity is O(n).
–EOF (The Ultimate Computing & Technology Blog) —
loading...
Last Post: Coding Exercise - LUA Programming - SPOJ Online Judge - 15708. Divisibility
Next Post: Introduction to 8-bit Famicom Clone - Subor - SB2000