-
-
Save koswarabilly/c47cded6d1955e22044c88ddeba0edb3 to your computer and use it in GitHub Desktop.
kickstart 2020 round A
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| // #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; | |
| } |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| 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 | |
| } |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| 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 | |
| } |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| 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 | |
| } | |
| } |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment