Recently Added PCS Online Judge Problemshttps://pcs.org.au/The latest problems added on the PCS Online Judge websiteen-auMon, 16 Mar 2020 01:40:25 +0000Query In A Queryhttps://pcs.org.au/problem/queryinaquery<h3>Query In A Query</h3>
<p>Alden some permutation \(a\) of the numbers \(1\) to \(n\). He's very familiar with some properties of this permutation, to the extent that simple range queries are a trivial problem to him. However, he ponders the idea of a range query containing a similar query. Alden thinks to himself, if he defined a function \(g\) such that \(g(l, r)\) gives the index of the maximum in \(a\) in the range \(l\) to \(r\), and then defines another function \(f\) such that \(f(l, r...Mon, 16 Mar 2020 01:40:25 +0000https://pcs.org.au/problem/queryinaqueryParticular Particleshttps://pcs.org.au/problem/particularparticles<h3>Particular Particles</h3>
<p>Lauren is conducting an experiment to test an apparatus. She expects the black box to perform in the following way. Given \(n\) particles of \(k\) types, the box will act on the particles at each step such that \(k-1\) particles are selected, all of differing types. These particles are then transformed into the remaining type of particle. Lauren wants to know in how many combinations of particles are possible for her to observe. As this answer can be very large i...Tue, 03 Mar 2020 16:39:20 +0000https://pcs.org.au/problem/particularparticlesA squared plus B squaredhttps://pcs.org.au/problem/asquaredplusbsquared<h3>A squared plus B squared</h3>
<p>Albert is an enthusiastic mathematician. He states that he knows all pythagorean triples that use the numbers from 1 to 1000. Naturally you feel obligated to one up Albert and wish to create a program that given any non-negative integer \(c\) you can find two non-negative integers \(a\) and \(b\) such that \(a^2 + b^2 = c\) if two such integers exist</p>
<h4>Input Specification</h4>
<p>The first line contains one integer \(c\)</p>
<h4>Output Specification</h4...Tue, 03 Mar 2020 15:44:59 +0000https://pcs.org.au/problem/asquaredplusbsquaredArray Rotationhttps://pcs.org.au/problem/arrayrotation<h3>Array Rotation</h3>
<p>Nick is just starting out his CS course at UWA. His first project involves
going through a list of \(n\) numbers with the index corresponding to a clockwise rotation on a circle. Nick finds that if he at first rotates this mapping by \(k\) indices clockwise, his project is much more efficient. Help nick determine what this list would look like</p>
<h4>Input Specification</h4>
<p>The first line contains two integers \(n\) and \(k\)
the next line will contain \(n\) spac...Tue, 03 Mar 2020 14:25:01 +0000https://pcs.org.au/problem/arrayrotationCrazy Typisthttps://pcs.org.au/problem/crazytypist<h3>Crazy Typist</h3>
<p>David is an avid typist. Unfortunately with how fast he moves his fingers he can often type duplicate characters by mistake. Given a string \(s\) of length \(n\) find the string david meant to type. It is safe to assume that any duplicate character is a mistake</p>
<h4>Input Specification</h4>
<p>The first line contains one integer \(n\)<br>
The next line will contain a string of \(n\) characters</p>
<h4>Output Specification</h4>
<p>Output the correct string on a single ...Tue, 03 Mar 2020 07:53:38 +0000https://pcs.org.au/problem/crazytypistMultipleshttps://pcs.org.au/problem/multiples<p>Imagine you are still a lowly high-school student (apologies to the lowly high-school students competing). You are bored in maths class (purely hypothetically). To amuse yourself, you are playing a game. The games works as follows. You want to find the largest non-negative multiple of a positive integer \(X\) such that the number of digits (in base 10) is exactly \(D\). Several of your friends have started playing. So you can shame them and their families, you have decided to write a program ...Mon, 13 Aug 2018 02:46:19 +0000https://pcs.org.au/problem/multiplesUneven Sandhttps://pcs.org.au/problem/unevensand<p>Having just landed in the desert Kira remembers that his Strike Gundam is not yet programmed for sand environments. He needs to determine the right amount of pressure \(N\) that the Strike needs to exert on the sand so that it will neither sink nor float. In other words, he needs the pressure to be an exact number. He knows that the maximum pressure that needs to be exerted is \(2×10^9\) and the minimum pressure is \(1\). He wants to find this number \(N\) in at most 31 guesses.</p>
<h4>Inter...Sun, 01 Jul 2018 05:09:23 +0000https://pcs.org.au/problem/unevensandColouring Treeshttps://pcs.org.au/problem/coltrees<p>Nick has found a very odd looking tree. It seems to have 3 different coloured nodes, cyan (<code>C</code>), yellow (<code>Y</code>) and red (<code>R</code>), where each node is connected to any number of other nodes. Unfortunately, Nick cannot see all the nodes of the tree, as some of them are hidden from view, so he wants to know the number of ways that the hidden nodes could be coloured and the tree remain "coloured".</p>
<p>The tree is considered coloured if no two connected nodes are the ...Sat, 31 Mar 2018 11:25:49 +0000https://pcs.org.au/problem/coltreesBear Chesshttps://pcs.org.au/problem/bearchess<p>Yogi "Gozz" Bear, being smarter than the average bear, is attempting to develop his own unique take on chess. Although, still being a bear, he only has access to a checkerboard pic-a-nic blanket with \(R\) rows, and \(C\) columns, and his pristine collection of stolen rooks (castles).</p>
<p>Gozz wishes to find the ideal starting position for his game, such that he can place as many rooks as possible onto the checkerboard blanket without allowing any two pieces to attack each other directly.<...Sat, 31 Mar 2018 10:13:24 +0000https://pcs.org.au/problem/bearchessPurple Lightshttps://pcs.org.au/problem/purplelights<p>Historically, the colour purple has been associated with royalty, magic, eggplants and a rather suspicious dinosaur whose name rhymes with 'arnie'. Mark, in anticipation of fulfilling his dream of ruling the galaxy for the next millennium is throwing the most purple party possible to reflect his royal-magic.</p>
<p>Mark in his haste to throw the galaxy's best gathering hastily ordered 'purple-range' lights. When they arrived, they turned out to be rather peculiar bulbs indeed. Instead of bein...Fri, 30 Mar 2018 22:43:28 +0000https://pcs.org.au/problem/purplelightsPlanet Gozzhttps://pcs.org.au/problem/planetgozz<p>Planet Gozz calls for aid! They are under attack from the minions of the evil MAX! Gozz has sent out messages to other planets using an FTL email system so all planets receive the message at the same time, but due to some wacky timespace hijinks the receipt time may be years after the send time, or even years before. None of the planets that receive the message have FTL travel, but they do have access to wormholes that allow instantaneous travel through time and space.</p>
<p>A wormhole \(w\)...Fri, 30 Mar 2018 22:32:04 +0000https://pcs.org.au/problem/planetgozzRemoval Sortinghttps://pcs.org.au/problem/removalsorting<p>You have a zero-indexed array, \(A\), containing positive integers, and a permutation of the indexes for that array, \(D\). You plan to go through \(D\) in order, and mark the corresponding element in \(A\) as deleted. Note that you won't then move elements of \(A\) down after deletion, so elements keep their original indexes throughout this process. For example, consider \(A = \{ 2, 1, 8, 3 \}\) and \(D = \{ 1, 3, 0, 2 \}\).</p>
<p>We start with,</p>
<p><code>2, 1, 8, 3</code></p>
<p>Then in...Fri, 23 Mar 2018 09:52:21 +0000https://pcs.org.au/problem/removalsortingWeapons of mass distractionhttps://pcs.org.au/problem/weaponsofmassdist<p>Gozz has decided that simply ruling PCS and UCC isn't enough, he wants to rule the entire planet! He has discovered the location of a bomb making facility that he plans to infiltrate to steal their technology to create an unstoppable army of bomb-dropping drones!</p>
<p>The plan to get in is relatively simple. The facility makes bombs in batches and drops them in specific locations around a room. The bombs are circular and have a center and a radius, and if they touch each-other, then they wi...Thu, 22 Mar 2018 14:14:54 +0000https://pcs.org.au/problem/weaponsofmassdistSquare Gamehttps://pcs.org.au/problem/squaregame<p>Connie and Max are both quite bored after a day of boorish behavior and have decided to play a board game. The game is played on a checkerboard with \(R\) rows and \(C\) columns. The game is played by placing squares (these could be \(1\times1\), or \(2\times2\), and so on) of any size on the board. At the beginning of the game, certain grid locations are marked as <em>out-of-bounds</em> and cannot have any square placed over them. The players take turns placing squares. Squares must be place...Wed, 21 Mar 2018 21:40:37 +0000https://pcs.org.au/problem/squaregameMinutemenhttps://pcs.org.au/problem/minutemen<p>Gozz is now president of UCC and has set himself the task of returning the club to glory.
In this quest he must review UCC scripture in search of a great Oracle.
Unfortunately you have been confused for a member (that cares) and have been set the task of finding the Oracle.
Gozz has given you a copy of the minutes dating back years and an array of clever words that an Oracle would totally use.
He suggested you search the minutes for the longest clever words used and report back.</p>
<p>A wor...Wed, 21 Mar 2018 21:09:57 +0000https://pcs.org.au/problem/minutemenMurder for a jar of red rumhttps://pcs.org.au/problem/murderforajar<p>In an upside down and back to front world of president Trump, Fake News and the Kardashians it may be prudent to begin communicating in phrases that make as much sense backward as the do forward.
To that end your aim in this challenge is to determine whether a given phrase will survive in the new world.</p>
<p>Welcome to Palindromes.</p>
<p>A <a href="https://en.wikipedia.org/wiki/Palindrome]" rel="nofollow">Palindrome</a> is a word, phrase, number or other sequence of symbols or elements tha...Wed, 21 Mar 2018 20:55:53 +0000https://pcs.org.au/problem/murderforajarGozz's Paymenthttps://pcs.org.au/problem/gozzpayment<p>Gozz needs to pay exactly \(X\) dollars to Max on a bet (Gozz bet that NP = P). Gozz only has \(a\) $5 coins, and \(b\) $7 coins. Can he pay Max exactly \(X\) dollars?</p>
<h4>Input Specification</h4>
<p>The first line contains an integer \(T\), the number of test cases to follow. The next \(T\) lines each contain three space-separated integers, \(X\), \(a\), and \(b\) respectively (\(1 \leq a,b,X \leq 100\)).</p>
<h4>Output Specification</h4>
<p>For each each test case, output either <code>Y...Wed, 21 Mar 2018 20:39:46 +0000https://pcs.org.au/problem/gozzpaymentSwapping Numbershttps://pcs.org.au/problem/swapnums<p>This question is intended to be a basic introduction to how to submit a problem in a contest using the PCS contest server. In this question, you will need to write a program that takes two integers as input, we will call them \(x\) and \(y\) respectively. Your program will then need to output them in reverse order, that is, output \(y\) followed by \(x\). The exact details of this can be found in the Input and Output Specifications.</p>
<p>(Note, if maths notation shows up weirdly for you, li...Wed, 21 Mar 2018 05:46:40 +0000https://pcs.org.au/problem/swapnumsPhone Chargershttps://pcs.org.au/problem/phonechargers<p>You have exactly \(3\) phones and \(3\) chargers. You wish to charge all the phones as fast as possible. To do this, you must assign every phone to a charger such that the total wait time is minimized. Each charger can be used to charge at most \(1\) phone, so you cannot move phones between chargers, or assign \(2\) phones to a charger.</p>
<h4>Input Specification</h4>
<p>The first line contains a single integer \(T\) (\(1\leq T \leq 10\)), the number of test cases to follow. Each test cases ...Sat, 24 Feb 2018 10:05:29 +0000https://pcs.org.au/problem/phonechargersTetrishttps://pcs.org.au/problem/tetris<p>You are friends with a genius inventor, and she needs your help with her latest invention. She has built a real life Tetris machine, which also doubles as an obstacle course / climbing wall. However, for safety reasons, she needs to know exactly how many blocks there are in any given column, at any stage in the game.</p>
<p>This ain't your grandma's game of Tetris. Instead of four-block clusters falling from the sky, there are rectangular slabs of blocks falling from the sky. These slabs have...Sat, 24 Feb 2018 09:59:37 +0000https://pcs.org.au/problem/tetrisBeautiful Skylineshttps://pcs.org.au/problem/beautifulskylines<p>You are an architect designing a city, and you have decided that you are going to make it
beautiful, or more specifically, that it is going to have a beautiful skyline. A skyline consists of \(N\)
consecutive, unit width buildings, each with a height between \(0\) and \(H\) inclusive. It is considered beautiful if the
height of two directly adjacent buildings differs by no more than \(K\).
In order to design your beautiful city, you first want to know how many different beautiful
skylines are...Thu, 22 Feb 2018 07:17:35 +0000https://pcs.org.au/problem/beautifulskylinesGozz's Prankhttps://pcs.org.au/problem/gozzprank<p>Gozz has decided to play an outrageous prank on poor old Nick. Gozz has given Nick an array, \(A\), that he claims is 'sorted'. But actually, Gozz started with some number of non-decreasing arrays, and then interleaved them to create \(A\). This means that \(A\) may not actually be sorted! Can you write a program to help Nick determine the minimum number of non-decreasing arrays Gozz could have started with? Nick needs the program so he can intimidate Gozz with his deduction skills. As we all...Sun, 18 Feb 2018 04:34:38 +0000https://pcs.org.au/problem/gozzprankTo Bee or Not To Bee?https://pcs.org.au/problem/tobeeornottobee<p>A flower garden is having all of it's visitors chased away by particularly unfriendly bees. In order
to combat this problem in the most unfriendly way possible, the gardeners have chosen to set up
a series of laser cannons to keep the bees away. The lasers can shoot in each of the cardinal
directions for infinite distances or until it hits one of the many statues in the garden. A laser placed in a statue will hit that statue, and travel nowhere. The flower garden can be seen as an \(N\) by \(...Sun, 24 Dec 2017 09:49:27 +0000https://pcs.org.au/problem/tobeeornottobeeA Poem Problemhttps://pcs.org.au/problem/apoemproblem<p>The year is 2025, 4 years since the ruler of Earth, the benevolent MAX, came into power and outlawed all forms of pointless self-expression. Since the fall of the decadent, sinful old-world, you have kept your head down and worked your way into the office of the supreme leader of the world. Years of effort has come to this opportunity. Your dastardly plot will doubtlessly get you killed, or worse, if you are ever discovered, but you consider this a small price to pay. Your aim is to send your...Sat, 23 Dec 2017 17:24:37 +0000https://pcs.org.au/problem/apoemproblemHaunted Househttps://pcs.org.au/problem/hauntedhouse<p>Gozz is still trying to build the best haunted house in town. He has a new plan to optimise the spookiness. He already has \(N\) rooms, but hasn't yet built the hallways between the rooms. All the hallways Gozz can build are undirected, and so can be traversed in either direction. Each hallway goes from some room to a different room--there are no hallways that lead from a room to itself. Every hallway has an associated comfort value, which is how comfortable people feel traversing that hallwa...Fri, 22 Dec 2017 12:04:17 +0000https://pcs.org.au/problem/hauntedhouse