Kertoma

// Päättele luku x
// Kun saat tietoa kertomasta

// const { performance } = require("perf_hooks")

const { createInterface } = require("readline")
const interface = createInterface({
    input: process.stdin,
    terminal: false
})

function factorial(number) {
    let returnValue = 1n
    for (let i = 2; i <= number; i++) returnValue *= BigInt(i)
    return returnValue
}

// Implements Stirling approximation
// Total black magic!
function factorialApproximation(number) {
    number += 1
    //return Math.ceil(Math.sqrt(2 * Math.PI / number) * ((number / Math.E).toFixed(0)) ** number)
    return BigInt(Math.ceil(Math.sqrt(2 * Math.PI / number).toFixed(0) + 1)) * (BigInt((number / Math.E).toFixed(0)) ** BigInt(number))
}

function getCounts(string) {
    let counts = new Array(10).fill(0)
    for (const char of string.split("")) {
        if (isNaN(parseInt(char))) continue
        counts[parseInt(char)] += 1
    }
    return counts
}

const manualTarget = 100000n
const fallbackThreshold = 2n

interface.once("line", (line) => {
    const expectedCounts = line.split(" ")
        .map((val) => parseInt(val))

    // const start = performance.now()
    
    // Find the expected length of the factorial and find a factorial within a range of lengths with a given precision
    const expectedLength = expectedCounts.reduce((a, b) => a + b)
    let currentTarget = [1n, manualTarget]
    while(true) {
        // If the min factorial's length is more than the mean of the min-max factorial, add the mean as the min
        // and the other way around for if it's larger
        if (currentTarget[1] - currentTarget[0] < fallbackThreshold) break
        const newTarget = currentTarget[0] + (currentTarget[1] - currentTarget[0]) / 2n
        const testFactorial = factorialApproximation(parseInt(newTarget.toString()))
        if (testFactorial.toString().length > expectedLength) currentTarget[1] = newTarget
        else currentTarget[0] = newTarget
    }
    // console.log("Achieved precision of", (currentTarget[1] - currentTarget[0]).toString(), "at", (performance.now() - start) / 1000, "s")

    // Now we know the number is one of at max 10 factorials, calculate them all until we find a match
    let lastValue = factorial(currentTarget[0] - 1n)
    let i = currentTarget[0] - 1n
    while (i !== manualTarget) {
        ++i
        lastValue *= i
        const calculatedCounts = getCounts(lastValue.toString())
        if (expectedCounts.join("") === calculatedCounts.join("")) {
            console.log(i.toString())
            break
        }
    }
    process.exit()
})

Test 1

Group: 1, 2, 3

Verdict: TIME LIMIT EXCEEDED

Test 2

Group: 1, 2, 3

Verdict: TIME LIMIT EXCEEDED

Test 3

Group: 1, 2, 3

Verdict: TIME LIMIT EXCEEDED

Test 4

Group: 1, 2, 3

Verdict: TIME LIMIT EXCEEDED

Test 5

Group: 1, 2, 3

Verdict: TIME LIMIT EXCEEDED

Test 6

Group: 1, 2, 3

Verdict: TIME LIMIT EXCEEDED

Test 7

Group: 2, 3

Verdict: TIME LIMIT EXCEEDED

Test 8

Group: 2, 3

Verdict: TIME LIMIT EXCEEDED

Test 9

Group: 2, 3

Verdict: TIME LIMIT EXCEEDED

Test 10

Group: 2, 3

Verdict: TIME LIMIT EXCEEDED

Test 11

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 12

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 13

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 14

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 15

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 16

Group: 3

Verdict: TIME LIMIT EXCEEDED