Recently Added PCS Online Judge Problemshttps://pcs.org.au/The latest problems added on the PCS Online Judge websiteen-auWed, 14 Sep 2022 15:35:17 +0000Programming Competition Partyhttps://pcs.org.au/problem/pcp<p>With Guild elections around the corner, PCS has decided last minute to form its very own Guild party - <strong>Programming Competition Party (PCP)</strong>. They have decided to focus on just a single policy because quality is always better than quantity. PCP promises to optimise the layout of the UWA campus so the minimal total length of path is needed to connect every single building on campus. Although this may actually increase the distance students walk to get to their classes, PCP belie...Wed, 14 Sep 2022 15:35:17 +0000https://pcs.org.au/problem/pcpMagician's hathttps://pcs.org.au/problem/magicianshat<p>Our magician Harry decided to give a stage performance. To perform his famous magic trick, he needs to stick his hand inside the hat and take two rabbits out, magically turn them into one rabbit and then put it back inside the hat. He continues to do this until he is left with only one rabbit. Every transformation that Harry does uses up his energy, the bigger the rabbits are, the more energy Harry needs to use in order to perform his magic trick. Given the number of the rabbits inside the ha...Mon, 04 Apr 2022 04:00:00 +0000https://pcs.org.au/problem/magicianshatEdge List to Adj Mathttps://pcs.org.au/problem/simplegraphrepr<p>For far too long, the war between two raging factions, the Edgians and Adjunds ravished the great plains at the bottom of the sea (plus plus).
Fortunately, both factions communicate using heiro-graphs - each graph corresopnds to what we would call a word and to us looks like a directed but unweighted graph.</p>
<p>Unfortunately, Edgians represents heiro-graphs using edge-lists (an edge is specified by two vertices \(u,v\))
but Adjunds use adjacency matrices.</p>
<p>As head-translator for the ...Fri, 30 Jul 2021 07:27:17 +0000https://pcs.org.au/problem/simplegraphreprShortest-Pathshttps://pcs.org.au/problem/simpleshortestpath<p>No hidden tricks here, read in an adjacency matrix for a positively-weighted and directed graph (no self-edges). Output the shortest distance from \(0\) to each other vertex.
Graphs are labelled from \(0\) to \(V\).</p>
<h4>Input Specification</h4>
<p>The first line contains a single integer \(V\), the number of vertices in the graph.</p>
<p>The next \(V\) lines will contain \(V\) space-separated integers specifying an adjacency matrix.</p>
<p>For any element \(v_{i,j}\), a \(0\) indicates no...Tue, 20 Jul 2021 04:16:40 +0000https://pcs.org.au/problem/simpleshortestpathDepth-First-Searchhttps://pcs.org.au/problem/simpledfs<p>No hidden tricks here, read in an adjacency matrix for an unweighted but directed graph (no self-edges). Output the <em>iterative DFS</em> traversal order.
Graphs are labelled from \(0\) to \(V\).</p>
<h4>Input Specification</h4>
<p>The first line contains a single integer \(V\), the number of vertices in the graph.</p>
<p>The next \(V\) lines will contain \(V\) space-separated integers specifying an adjacency matrix.</p>
<p>For any element \(v_{i,j}\), a \(0\) indicates no edge from \(u\) to...Tue, 20 Jul 2021 03:30:05 +0000https://pcs.org.au/problem/simpledfsBreadth-First-Searchhttps://pcs.org.au/problem/simplebfs<p>No hidden tricks here, read in an adjacency matrix for an unweighted but directed graph (no self-edges). Output the BFS traversal order starting from vertex \(0\) in numerically increasing node labels.
Graphs are labelled from \(0\) to \(V\).</p>
<h4>Input Specification</h4>
<p>The first line contains a single integer \(V\), the number of vertices in the graph.</p>
<p>The next \(V\) lines will contain \(V\) space-separated integers specifying an adjacency matrix.</p>
<p>For any element \(v_{i...Tue, 20 Jul 2021 03:08:09 +0000https://pcs.org.au/problem/simplebfsChess Board Renderinghttps://pcs.org.au/problem/chessboard<p>Alexei was a child chess prodigy who has become distracted in their teen years by the dreaded computer.
Without access to the Internet, however, Alexei wants to play chess with the computer, the first step is to render boards to his screen.</p>
<p>Given the description of \(N\) chess pieces on a standard chessboard including their type and location, print out a basic visualisation of the chessboard.
There is no need to consider whether the described chess board is accurate, nor is there any n...Fri, 16 Jul 2021 03:00:00 +0000https://pcs.org.au/problem/chessboardWhere is *?https://pcs.org.au/problem/whereisstar<p>Nic, after filing away all of his nicely sorted numbers has lost all his asterixis (asterixes?)... anyway</p>
<p>Given \(N\) lines of characters, one such character will be an asterisk, print out what column (zero-indexed) the asterisk appears on.</p>
<h4>Input Specification</h4>
<p>The first line will contain a single integer \(N\), the number of lines to process.</p>
<p>The next \(N\) lines will consist of up to <code>m</code> characters. Each line is comprised of dashes <code>-</code> and ...Thu, 15 Jul 2021 08:12:50 +0000https://pcs.org.au/problem/whereisstarMatrix Additionhttps://pcs.org.au/problem/matrixaddition<p>Nic, having sorted all his numbers wants to pack them away nicely in a matrix.
Given two square matrices \(A\) and \(B\) of side-length \(N\), add them together to produce a new _compacted_ matrix \(C\), also of side-length \(N\).</p>
<p>Any element in \(C\) can be expressed with the following formula:</p>
<p>\(c_{i,j} = a_{i,j} + b_{i,j}\)</p>
<h4>Input Specification</h4>
<p>The first line will contain a single integer \(N\), the side-length of \(A, B\) and \(C\).</p>
<p>The next \(N\) lines...Wed, 14 Jul 2021 02:28:05 +0000https://pcs.org.au/problem/matrixadditionSimple-ish Sorthttps://pcs.org.au/problem/simplensort<p>Silly Nic, while putting his collection of neatly sorted numbers back on his shelf, he's jumbled several groups of numbers out of order.
Can you help Nic sort all \(N\) of his number collections, each into ascending order?</p>
<h4>Input Specification</h4>
<p>The first line contains a single integer \(N\) - the number of _arrays_ Nic needs sorting.</p>
<p>The next \(N\) lines will contain \(k\) space-separated integers where each number \(a_k\) sits between \(-100\) and \(100\) inclusive.</p>
...Tue, 13 Jul 2021 06:19:46 +0000https://pcs.org.au/problem/simplensortSimple Sorthttps://pcs.org.au/problem/simplesorting<p>Oh No! Nic has gotten his numbers all jumbled, can you help him put them back in ascending order?</p>
<h4>Input Specification</h4>
<p>Two lines. The first line contains a single integer \(N\), the number of integers Nic needs to sort.</p>
<p>The second line contains \(N\) space-separated integers, Nic's numbers (\(a_i | 1 \leq i \leq N\)).</p>
<h4>Output Specification</h4>
<p>The same integers provided as input in sorted order and space-separated.</p>
<h4>Bounds</h4>
<p>For all test cases:</p...Mon, 12 Jul 2021 05:53:36 +0000https://pcs.org.au/problem/simplesortingFlavour Saverhttps://pcs.org.au/problem/flavoursaver<p>It's 3:59 pm which means it's closing time at the local Frozen Yogurt store and that means there are bargains to be found. This frozen yogurt vendor has a particular policy that any yogurt order that finishes a particular topping is free! Yes, free!</p>
<p>You and your <em>associates</em>, skint but sweaty they may be, are looking to minimise the collective money you spend which means maximizing the number of toppings your orders finish. But, you still have standards and preferences which mea...Wed, 23 Sep 2020 04:22:47 +0000https://pcs.org.au/problem/flavoursaverRedwood Mailhttps://pcs.org.au/problem/redwood<p>Max has been sending a LOT of letters recently. So much so that he's run out of paper! Max, being again, a marvellous algorithmic influencer orders stationary from the online shopping giant Redwood.</p>
<p>The boffins at Redwood are looking to improve their shipping margins and Max's orders are so voluminous they consider the case of shipping some quantity of paper \(P\) from their shipping outlet to Max through a variety of postal routes, each with their own capacity and cost per unit paper....Tue, 22 Sep 2020 04:42:18 +0000https://pcs.org.au/problem/redwoodFan Mailhttps://pcs.org.au/problem/fanmail<p>Max Flow is a very popular influencer in the competitive programming world and as such gets sent a large volume of fan mail. In particular, Max's <em>number one</em> fan sends a practically infinite number of letters all. the. time. As a very dedicated public figure, Max responds to each and every letter but the postal service has limits on how many letters can be transported at a given time.</p>
<p>Given the possible postage routes and their letter-capacities as a directed graph, the locatio...Mon, 21 Sep 2020 07:30:38 +0000https://pcs.org.au/problem/fanmailTwin Lunchhttps://pcs.org.au/problem/twinlunch<p>Imagine you have a twin sibling. Imagine a typical morning before school in your family. Your parents have already left (to go do whatever adults do during the day) and have rudely forgotten to leave any food for lunch. They have, however, left some coins to buy lunch with. To be specific, \(n\) coins of arbitrary value \(a_1, a_2, ... ,a_n\). Your parents have not split the coins, however.</p>
<p>Since you have woken up before your (clearly inferior) twin you have decided to split the lunch ...Wed, 09 Sep 2020 04:31:48 +0000https://pcs.org.au/problem/twinlunchCow Datinghttps://pcs.org.au/problem/cowdating<p>Disappointed in the lacklustre dating websites and apps currently available to cows (OkCowpid, eHarmoony, Plenty of Barns, EliteCattle), Farmer Adams decides to launch a new site based on a fancy matching algorithm matching cows and bulls according to their mootual interests.</p>
<p>Bessie, a cow, searching for a partner to the Guild Ball has decided to try out the site. After making an account, the algorithm has provided a list of \(N\) possible matches \((1 \leq N \leq 10^6)\). Going throug...Tue, 08 Sep 2020 07:08:11 +0000https://pcs.org.au/problem/cowdatingEdit Distancehttps://pcs.org.au/problem/editdist<p>Ryan, an anthropomorphic cat, has taken a liking to strings. Given two strings of great interest, Ryan can insert, remove or replace characters in either string. Ryan also like order and conformity and would like the first string to be converted to the second string. Write a program to tell Ryan how many operations are needed to do this.</p>
<h4>Input Specification</h4>
<p>Two lines, each containing a string of English characters [a-Z]. The length of each string will be less than $10000$</p>
...Tue, 01 Sep 2020 01:26:36 +0000https://pcs.org.au/problem/editdistMowing More Lawnshttps://pcs.org.au/problem/mowingmorelawns<p>You are still <em>awful</em> at gardening, and between you, your grass and the weeds, you are losing. Each cell in your \(n \times n\) grid-garden either contains grass (denoted as <code>0</code>) or weeds (denoted as <code>1</code>).</p>
<p>You have robotised your borrowed lawn-mower but the weeds have become so very overgrown that the lawn-mower cannot get through them. Since you are lazy however, you don't care, in fact, you kind of like the extra greenery.</p>
<p>You initially place the r...Mon, 31 Aug 2020 10:40:10 +0000https://pcs.org.au/problem/mowingmorelawnsDavid's Exquisite Subsequencehttps://pcs.org.au/problem/davidssubseq<p>David's enterprising sloth has created an array of its own. David thinks it is a most exquisite array and wants to enter it into "Git's Next Most Increasing Array" - an exciting reality TV show where contestants enter their arrays. The winning array has the longest increasing subsequence.</p>
<p>Before entering his Sloth's (Jeff's) array, he wants to know what it's longest increasing subsequence is.</p>
<h4>Input Specification</h4>
<p>The first line contains an integer \(n\) \((1 \leq n \leq ...Mon, 31 Aug 2020 08:16:20 +0000https://pcs.org.au/problem/davidssubseqDavid's Magic Band Networkhttps://pcs.org.au/problem/davidsnetwork<p>David is not only an avid collector of arrays and sloths but is also a keen musician and as such is the chief administrator of the National Band Network or NBN. The NBN connects band members together with bi-directional links where connections bear a cost \(c_{ij}\) to maintain. Given a description of the current NBN, write David a program that tells him the minimum total cost of all connections needed to keep any previously connected members connected.</p>
<h4>Input Specification</h4>
<p>The...Tue, 25 Aug 2020 06:30:31 +0000https://pcs.org.au/problem/davidsnetworkBreakfast Searchhttps://pcs.org.au/problem/breakfastsearch<p>Benson is a <em>very hungry boy</em> and is in desperate <em>need</em> of \(k\) breakfasts. His house is also peculiar as doorways between rooms are one-way so on his quest to break his fast Benson wants to find out if he can move through his house of \(n\) rooms and \(e\) doorways from room \(u\) to room \(v\) moving through at most \(d\) doorways (he is also very lazy) for \(k\) \((u,v)\) pairs.</p>
<p>Given a description of one-way doorways between rooms in his house, \(k\) pairs of start/...Mon, 24 Aug 2020 09:41:32 +0000https://pcs.org.au/problem/breakfastsearchRoman Translationhttps://pcs.org.au/problem/romantranslator<p>Romeo and Tulio are two Roman thugs that through the power of plot-devices and time-travel have found their way to CS 1.24. On their way to programming greatness, they are having a spat about how to write numbers in this new-fangled Arabic numerals everyone seems to be using nowadays.</p>
<p>Specifically, they have \(n\) numbers they want to translate from our well understood base-10 Arabic numerals to roman numerals. Can you help them write a program to do so?</p>
<p>Romeo and Tulio weren't ...Thu, 20 Aug 2020 09:04:05 +0000https://pcs.org.au/problem/romantranslatorDavid's Magic Slothhttps://pcs.org.au/problem/davidsloth<p>Sloths live, nay, <em>thrive</em> in trees. Obviously David has a pet sloth that he lets play on his unweighted trees while solving programming problems. Sloths are typically very slow creatures but David's sloth (Jeff for those invested) has the ability to teleport around the tree at will (but only on the tree, Jeff is still lazy at heart).</p>
<p>What is the furthest possible distance David's magic sloth can travel in a given tree?</p>
<p>Background: A tree is a graph with \(n\) nodes, \(n-...Wed, 19 Aug 2020 09:19:40 +0000https://pcs.org.au/problem/davidslothMowing Lawnshttps://pcs.org.au/problem/mowinglawns<p>You are <em>awful</em> at gardening. Your garden is full of grass and weeds exclusively. Your garden is an \(n \times m\) grid. Each garden cell contains either grass (<code>G</code>) or weeds (<code>W</code>).</p>
<p>You have borrowed a lawn-mower and wish to yeet the weeds. Initially, you stand in the top-left corner of your garden facing right. At each time-step, you either move one cell in the direction you face (left or right) or move one cell down and change direction (moving down is th...Tue, 18 Aug 2020 10:15:35 +0000https://pcs.org.au/problem/mowinglawnsSpreadsheet Locationshttps://pcs.org.au/problem/spreadsheet<p>In popular spreadsheet applications (such as Apple's Numbers) cells are identified in one of two systems.</p>
<p>In the first system, the first 26 columns are denoted as 'A' to 'Z', column 27 is denoted as 'AA', 28 as 'AB' etc. Rows are marked with integers beginning from 1. The cell name is the concatenation of column and row specifiers. E.g. A1 is column 1, row 1, AC24 is column 29, row 24.</p>
<p>In the second system, rows are specified first as RX and columns are specified as CY, where X ...Sat, 15 Aug 2020 04:48:09 +0000https://pcs.org.au/problem/spreadsheet