CSES - Datatähti 2023 alku - Results
Submission details
Task:Kertoma
Sender:Esinko
Submission time:2022-11-01 11:47:11 +0200
Language:Node.js
Status:READY
Result:0
Feedback
groupverdictscore
#10
#20
#30
Test results
testverdicttimegroup
#10.12 s1, 2, 3details
#2ACCEPTED0.12 s1, 2, 3details
#3ACCEPTED0.12 s1, 2, 3details
#4ACCEPTED0.12 s1, 2, 3details
#50.12 s1, 2, 3details
#60.13 s1, 2, 3details
#70.12 s2, 3details
#80.12 s2, 3details
#90.12 s2, 3details
#100.12 s2, 3details
#110.12 s3details
#120.12 s3details
#130.14 s3details
#140.15 s3details
#150.16 s3details
#160.16 s3details

Code

// Päättele luku x
// Kun saat tietoa kertomasta
 
const { createInterface } = require("readline")
const interface = createInterface({
    input: process.stdin,
    terminal: false
})
 
function findDigits(factorial) {
    let count = 0
    for (let i = 2; i <= factorial; i++) count += Math.log10(i)
    return Math.floor(count) + 1
}
function factorial(number) {
    let returnValue = 1
    for (let i = 2; i <= number; i++) returnValue *= i
    return returnValue  
}
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 = 100000
const fallbackThreshold = 1
 
interface.once("line", (line) => {
    const expectedCounts = line.split(" ")
        .map((val) => parseInt(val))
    
    // 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 = [1, manualTarget]
    let lastTarget = []
    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 + (currentTarget[1] < 1000 ? 2 : 0)) break
        const newTarget = Math.round((currentTarget[1] + currentTarget[0]) / 2)
        const testFactorialLength = findDigits(newTarget)
        
        if (testFactorialLength > expectedLength) currentTarget[1] = newTarget
        else currentTarget[0] = newTarget

        if (lastTarget === newTarget) break
        lastTarget = newTarget

    }
    if (currentTarget[0] !== currentTarget[1]) {
        let lastValue = factorial(currentTarget[0] - 1)
        let i = currentTarget[0] - 1
        while (i !== currentTarget[1]) {
            ++i
            lastValue *= i
            const calculatedCounts = getCounts(lastValue.toString())
            if (expectedCounts.join("") === calculatedCounts.join("")) {
                console.log(i.toString())
                break
            }
        }
    } else {
        console.log(currentTarget[0])
    }
    process.exit()
})

Test details

Test 1

Group: 1, 2, 3

Verdict:

input
0 0 1 0 0 0 0 0 0 0

correct output
2

user output
(empty)

Test 2

Group: 1, 2, 3

Verdict: ACCEPTED

input
0 0 0 0 0 0 1 0 0 0

correct output
3

user output
3

Test 3

Group: 1, 2, 3

Verdict: ACCEPTED

input
0 0 1 0 1 0 0 0 0 0

correct output
4

user output
4

Test 4

Group: 1, 2, 3

Verdict: ACCEPTED

input
2 0 1 1 0 0 1 0 2 0

correct output
10

user output
10

Test 5

Group: 1, 2, 3

Verdict:

input
9 3 1 1 2 2 3 1 6 1

correct output
27

user output
(empty)

Test 6

Group: 1, 2, 3

Verdict:

input
10 4 3 4 3 2 2 4 3 7

correct output
36

user output
(empty)

Test 7

Group: 2, 3

Verdict:

input
71 53 36 30 25 29 42 24 34 29

correct output
199

user output
(empty)

Test 8

Group: 2, 3

Verdict:

input
71 33 46 38 27 45 36 21 35 35

correct output
205

user output
(empty)

Test 9

Group: 2, 3

Verdict:

input
93 38 35 26 43 54 38 25 41 34

correct output
222

user output
(empty)

Test 10

Group: 2, 3

Verdict:

input
100 33 33 45 36 43 38 54 56 36

correct output
242

user output
(empty)

Test 11

Group: 3

Verdict:

input
3419 1797 1845 1849 1879 1791 ...

correct output
5959

user output
(empty)

Test 12

Group: 3

Verdict:

input
4776 2695 2709 2781 2616 2753 ...

correct output
8391

user output
(empty)

Test 13

Group: 3

Verdict:

input
20097 12282 12229 12214 12406 ...

correct output
32001

user output
(empty)

Test 14

Group: 3

Verdict:

input
47934 29918 29878 29713 29984 ...

correct output
71718

user output
(empty)

Test 15

Group: 3

Verdict:

input
84691 54156 54277 54533 54296 ...

correct output
123123

user output
100000

Test 16

Group: 3

Verdict:

input
99098 63339 63878 64182 63904 ...

correct output
142663

user output
100000