kickstart 2020 round A

1

// #1

const fs = require('fs');
const input = fs.readFileSync(0, 'utf8').trim().split('\n');

let currentline = 0;
function readline(){
    return input[currentline++];
}

let T = readline();
for(let i = 1; i <= T; i++){
    let [N, B] = readline().split(' ');
    let arr = readline().split(' ');
    console.log(`Case #${i}: ${solve(B, arr)}`);
}


function solve(B, arr){
    let count = 0;
    let sum = 0;
    
    arr.sort((a,b)=> a-b);

    for(let k = 0; k < arr.length; k++){
        sum+= +arr[k];
        if(sum <= B){
            count++;
        } else {
            return count;
        }
    }
    return count;
}

2

const fs = require('fs');
const input = fs.readFileSync('./3RA.txt', 'utf8').trim().split('\n');

let currentline = 0;
function readline(){
    return input[currentline++];
}

let T = readline();

for(let i = 1; i <= T; i++){
    let stt = readline().split(' ');
    let arr = parseArray(readline().split(' '));
    
    // Brute force solution
    // console.log(`Case #${i}: ${solve(stt, arr)}`);

    let n = parseInt(stt[0].replace('\r', '')), lmt = parseInt(stt[1].replace('\r', ''))

    console.log(`Case #${i}: ${binarySearch(1, 1e9, n, lmt, arr)}`);
}

function binarySearch(lo, hi, n, lmt, arr) {

    while (lo < hi) {
        let mid = parseInt((hi + lo) / 2)

        if (isValid(mid, n, lmt, arr)) {
            hi = mid 
        } else {
            lo = mid + 1
        }
    }

    return parseInt(lo);

}

function isValid(d, n, lmt, arr) {
    let additionalSession = 0

    for (var i = 1; i < n - 1; i++) {
        additionalSession += Math.floor((arr[i + 1] - arr[i] - 1) / d)
    }

    if (additionalSession <= lmt) {
        return true
    } else {
        return false
    }
}

function solve(stt, arr){
    let diff = 0, rDiff = 0, lmt = parseInt(stt[1].replace('\r', ''));
    
    arr = parseArray(arr)

    diff = calcDiff(stt, arr)

    rDiff = diff

    for (var i = 1; i < diff; i++) {
        let tArr = JSON.parse(JSON.stringify(arr)), rt = 1, poss = []
        for (var j = 0; j < tArr.length - 1; j++) {
            if (tArr[j + 1] - tArr[j] > 1) {
                let tn = tArr[j] + i
                while (tn < tArr[j + 1] && rt <= lmt) {
                    poss.push(tn)
                    rt = rt + 1
                    tn = tn + i
                }
            }
        }

        tArr = tArr.concat(poss)
        tArr = tArr.sort((a, b) => a - b)

        let tDiff = calcDiff(stt, tArr)

        if (tDiff < rDiff) {
            rDiff = tDiff
        }

    }

    return rDiff;

}

function calcDiff(stt, arr) {
    let diff = 0
    
    for (var i = 0; i < arr.length - 1; i++) {
        let calc = arr[i + 1] - arr[i]
        if (diff < calc) diff = calc
    }

    return diff
}

function parseArray(arr) {
    let rArr = JSON.parse(JSON.stringify(arr))
    for (var i = 0; i < arr.length; i++) {
        rArr[i] = parseInt(rArr[i].replace('\r', ''))
    }
    
    return rArr
}

3

const fs = require('fs');
const input = fs.readFileSync('./3RA.txt', 'utf8').trim().split('\n');

let currentline = 0;
function readline(){
    return input[currentline++];
}

let T = readline();

for(let i = 1; i <= T; i++){
    let stt = readline().split(' ');
    let arr = parseArray(readline().split(' '));
    
    // Brute force solution
    // console.log(`Case #${i}: ${solve(stt, arr)}`);

    let n = parseInt(stt[0].replace('\r', '')), lmt = parseInt(stt[1].replace('\r', ''))

    console.log(`Case #${i}: ${binarySearch(1, 1e9, n, lmt, arr)}`);
}

function binarySearch(lo, hi, n, lmt, arr) {

    while (lo < hi) {
        let mid = Math.floor((hi + lo) / 2)

        if (isValid(mid, n, lmt, arr)) {
            hi = mid
        } else {
            lo = mid + 1
        }
    }

    return Math.round(lo);

}

function isValid(d, n, lmt, arr) {
    let additionalSession = 0

    for (var i = 0; i + 1 < n; i++) {
        additionalSession += Math.floor((arr[i + 1] - arr[i] - 1) / d)
    }

    if (additionalSession <= lmt) {
        return true
    } else {
        return false
    }
}

function solve(stt, arr){
    let diff = 0, rDiff = 0, lmt = parseInt(stt[1].replace('\r', ''));
    
    arr = parseArray(arr)

    diff = calcDiff(stt, arr)

    rDiff = diff

    for (var i = 1; i < diff; i++) {
        let tArr = JSON.parse(JSON.stringify(arr)), rt = 1, poss = []
        for (var j = 0; j < tArr.length - 1; j++) {
            if (tArr[j + 1] - tArr[j] > 1) {
                let tn = tArr[j] + i
                while (tn < tArr[j + 1] && rt <= lmt) {
                    poss.push(tn)
                    rt = rt + 1
                    tn = tn + i
                }
            }
        }

        tArr = tArr.concat(poss)
        tArr = tArr.sort((a, b) => a - b)

        let tDiff = calcDiff(stt, tArr)

        if (tDiff < rDiff) {
            rDiff = tDiff
        }

    }

    return rDiff;

}

function calcDiff(stt, arr) {
    let diff = 0
    
    for (var i = 0; i < arr.length - 1; i++) {
        let calc = arr[i + 1] - arr[i]
        if (diff < calc) diff = calc
    }

    return diff
}

function parseArray(arr) {
    let rArr = JSON.parse(JSON.stringify(arr))
    for (var i = 0; i < arr.length; i++) {
        rArr[i] = parseInt(rArr[i].replace('\r', ''))
    }
    
    return rArr
}

4

const fs = require('fs');
const { clear } = require('console');
const input = fs.readFileSync('./4RA.txt', 'utf8').trim().split('\n');

let ans = 0

function trieNode(key) { // Object structure
    this.count = 0
    
    this.key = key

    this.parent = null

    this.children = {}

    this.end = false
}

function trie() {
    this.root = new trieNode(null)
}

trie.prototype.insert = function(word) {
    let node = this.root

    for (var i = 0; i < word.length; i++) {

        if (!node.children[word[i]]) {
            node.children[word[i]] = new trieNode(word[i])

            node.children[word[i]].parent = node
        }

        node = node.children[word[i]]

        if (i == word.length - 1) {
            node.end = true
        }
    }

    node.count++
}

let currentline = 0;
function readline() {
    return input[currentline++];
}

let T = readline();

for (let i = 1; i <= T; i++) {
    let stt = readline().split(' ');
    let arr = [];
    let ln = parseInt(stt[0].replace('\r', '')), gb = parseInt(stt[1].replace('\r', ''))

    for (let j = 0; j < stt[0]; j++) {
        arr.push(readline().split(' ')[0].replace('\r', ''));
    }

    let node = new trie()
    ans = 0

    for (var j = 0; j < arr.length; j++) {
        node.insert(arr[j])
    }

    dfs(node.root, gb, 0)

    console.log(`Case #${i}: ${ans}`);
}

function dfs(node, gb, lvl) {

    let apl = ['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M', 'N', 'O', 'P', 'Q', 'R', 'S', 'T', 'U', 'V', 'W', 'X', 'Y', 'Z']

    for (var i = 0; i < apl.length; i++) {

        if (node.children.hasOwnProperty(apl[i])) {
            dfs(node.children[apl[i]], gb, lvl + 1)
            node.count += node.children[apl[i]].count
        }

    }
    
    while (node.count >= gb) {
        node.count -= gb
        ans += lvl
    }
}