Recently Added DMOJ Problemshttps://dmoj.ca/The latest problems added on the DMOJ: Modern Online Judge websiteenWed, 26 Jun 2019 01:41:59 +0000CEOI '18 P5 - Toyshttps://dmoj.ca/problem/ceoi18p5<div><p>Johnny collects toys. His collection may contain many toys of many different types: cars, trucks, diggers and
many more. He may own more than one piece of the same toy, e.g. four trucks, in which case all the pieces are
indistinguishable for him.</p>
<p>Emma asked Johnny how many toys he has. Not wanting to reveal the secret, he answered with a riddle (it
is typical for him): <em>If I chose a different set of my toys for each day, I could play for \(n\) days</em>. In other words,
for eve...Wed, 26 Jun 2019 01:41:59 +0000https://dmoj.ca/problem/ceoi18p5CEOI '18 P4 - Fibonacci Representationshttps://dmoj.ca/problem/ceoi18p4<div><p>Let us define the sequence of Fibonacci numbers as:
\[ F_1 = 1 \]
\[ F_2 = 2 \]</p>
<p>\[ F_n = F_{n−1} + F_{n−2 } \space \text{for} \space n ≥ 3 \]</p>
<p>The first few elements of the sequence are \(1, 2, 3, 5, 8, 13, 21, \dots\)</p>
<p>For a positive integer \(p\), let \(X(p)\) denote the number of different ways of expressing \(p\) as a sum of <strong>different</strong>
Fibonacci numbers. Two ways are considered different if there is a Fibonacci number that exists in exactly one
of t...Tue, 25 Jun 2019 23:30:39 +0000https://dmoj.ca/problem/ceoi18p4CEOI '18 P3 - Lotteryhttps://dmoj.ca/problem/ceoi18p3<div><p>For a long long time you have been a big fan of Bytelotto. For around the same time, the members of your
family have been telling you that all such games are a waste of money. You are sure that it is because of their
lack of skill! You have a brilliant plan and everyone will see you winning the game soon.</p>
<p>There are many types of games. You are interested in one of them: Bitlotto. The choice was simple, as it
is the easiest offered type of game: on each day exactly one number is dr...Tue, 25 Jun 2019 20:11:09 +0000https://dmoj.ca/problem/ceoi18p3CEOI '18 P2 - Global Warminghttps://dmoj.ca/problem/ceoi18p2<div><p>Global warming is an important issue and Johnny knows about it. He decided to make an analysis of historical
temperatures and find a subsequence of days (not necessarily consecutive) where the temperature was strictly
increasing. It will convince the non-believers!</p>
<p>Johnny has found historical data from \(n\) consecutive days. The temperature on the \(i^{th}\) day was \(t_i\).</p>
<p>Formally, we are interested in finding the length of the longest increasing subsequence \((LIS)\) o...Tue, 25 Jun 2019 04:46:31 +0000https://dmoj.ca/problem/ceoi18p2CEOI '18 P1 - Cloud Computinghttps://dmoj.ca/problem/ceoi18p1<div><p>Johnny is founding Bytecomp, a company that offers computing power in the cloud. Companies with this
profile usually have many fast computers on which customers’ computations can be made.</p>
<p>Johnny still has not bought any machines. He went to a computer shop and received a list of all \(n\) available
computers. Every computer is specified by the number of (processor) cores \(c_i\), the clock rate \(f_i\), and the price \(v_i\).
Such a computer contains \(c_i\) separate cores that do...Tue, 25 Jun 2019 04:35:57 +0000https://dmoj.ca/problem/ceoi18p1APIO '14 P3 - Beads and Wireshttps://dmoj.ca/problem/apio14p3<div><p>A popular child game at the time of Leonardo was called Beads-and-wires. Not surprisingly, it was played
with beads and wires. The wires are red or blue. The beads are numbered from \(1\) to \(n\). The game starts
with a single bead. From this moment on, new beads can be added using wires as follows.</p>
<ul>
<li>Append \((w, v)\): a new bead \(w\) is attached to an existing bead \(v\) through a piece of red wire.</li>
<li>Insert \((w, u, v)\): a new bead \(w\) is inserted by substitutin...Mon, 24 Jun 2019 03:06:17 +0000https://dmoj.ca/problem/apio14p3Allen's Segmentshttps://dmoj.ca/problem/cheapsegments<div><p><strong>Credit to [user:AQT] for tweaking the problem to be harder.</strong></p>
<p>[user:verygoodallen] is having trouble with his latin homework. Since he wants to study for his summatives, he has translated the problem and entrusted you with this task instead.</p>
<p>He has given you \(N\) segments, each of which covers a certain range \(L_i\) to \(R_i\) and has a value \(V_i\). Each segment will either completely fall within another one or not. In other words, there cannot be any two...Mon, 24 Jun 2019 00:24:14 +0000https://dmoj.ca/problem/cheapsegmentsK-Dimensional Gridshttps://dmoj.ca/problem/kdgrid<div><p>Neo was bored of always living in three-dimensional space. In order to cope with his boredom, he learned how to lucid dream, where he was be able to recreate his own world with \(K\)-dimensions and conveniently place himself in any corner of his world. His world can be imagined as a \(K\)-dimensional grid where each dimension is located on a unique plane with a grid size of length \(l_i\). The drawback of Neo's dream world is that when he wakes up, he forgets most of the properties he us...Mon, 24 Jun 2019 00:24:06 +0000https://dmoj.ca/problem/kdgridAPIO '18 P2 - Circle Selectionhttps://dmoj.ca/problem/apio18p2<div><p>Given \(n\) circles \(c_1, c_2, \dots , c_n\) on a flat Cartesian plane. We attempt to do the following:</p>
<ol>
<li><p>Find the circle \(c_i\) with the largest radius. If there are multiple candidates all having the same
(largest) radius, choose the one with the smallest index. (i.e. minimize \(i\)).</p>
</li>
<li><p>Remove \(c_i\) and all the circles intersecting with \(c_i\). Two circles intersect if there exists a point included
by both circles. A point is included by a circle if it...Sun, 23 Jun 2019 02:41:11 +0000https://dmoj.ca/problem/apio18p2CCO '09 P6 - A Weighty Problemhttps://dmoj.ca/problem/cco09p6<div><h5>Canadian Computing Olympiad: 2009 Day 2, Problem 3</h5>
<p>You like to make purchases using coins, but you have a problem: you have so much
change that it is too heavy in your pocket. You have devised a plan to reduce the weight of
your change, and you need to write a program to help you execute it.</p>
<p>Here is your plan. The next purchase you make costs \(C\) \((1 \le C \le 100\,000)\) cents, and
you know how the store will pay back change if you pay extra. You want to select some o...Fri, 21 Jun 2019 02:16:20 +0000https://dmoj.ca/problem/cco09p6CCO '09 P3 - Beware the Geoduckshttps://dmoj.ca/problem/cco09p3<div><h5>Canadian Computing Olympiad: 2009 Day 1, Problem 3</h5>
<p>After perfecting the art of converting water to working C++ code, Stan Velikiy is once
again facing his arch-nemesis, Mario the Wabbit. At the moment, Stan is chasing Mario on
a circuit and you, as the amused observer, are being asked to predict the outcome.</p>
<p>The circuit can be thought as of series of nodes connected by wires of specified length.
Stan and Mario each start at one of the nodes and travel along the nodes in a...Thu, 20 Jun 2019 19:34:31 +0000https://dmoj.ca/problem/cco09p3CCO '09 P2 - Dinnerhttps://dmoj.ca/problem/cco09p2<div><h5>Canadian Computing Olympiad: 2009 Day 1, Problem 2</h5>
<p>On the way to dinner, the CCC competitors are lining up for their delicious curly fries. The \(N\) \((1 \le N \le 100)\) competitors have lined up single-file to enter the cafeteria.</p>
<p>Doctor V, who runs the CCC, realized at the last minute that programmers simply hate standing in line next to programmers who use a different language. Thankfully, only two languages are allowed at the CCC: Gnold and Helpfile. Furthermore, th...Thu, 20 Jun 2019 02:36:22 +0000https://dmoj.ca/problem/cco09p2CCO '09 P1 - Invasion of the Boxeshttps://dmoj.ca/problem/cco09p1<div><h5>Canadian Computing Olympiad: 2009 Day 1, Problem 1</h5>
<p>Oh no! You are under attack by a swarm of boxes. The \(N\) \((0 \le N \le 1\,000)\) boxes are all
rectangular with sides perpendicular to the axes. To help you defend against these menacing
boxes, you have a giant laser at your disposal.</p>
<p>The laser is located at the origin and shoots a single beam in some fixed specified direction.
The beam, upon encountering a box, will destroy and reflect off of that box.</p>
<p>Beams ar...Thu, 20 Jun 2019 02:19:54 +0000https://dmoj.ca/problem/cco09p1CCO '09 P5 - Paradehttps://dmoj.ca/problem/cco09p5<div><h5>Canadian Computing Olympiad: 2009 Day 2, Problem 2</h5>
<p>May 9 is VE day, when the annual victory parade is held through Red Square. Inspired by
the award ceremony of the 2009 ACM World Finals, you have decided to recreate the original
VE day parade digitally. Since you have skillfully obtained all the necessary hardware, the
most difficult part remaining is to track the configuration of a single formation.</p>
<p>A formation can be viewed as a 4-by-4 array, with the people initially ...Thu, 20 Jun 2019 00:13:16 +0000https://dmoj.ca/problem/cco09p5COCI '06 Regional #3 Fireflyhttps://dmoj.ca/problem/crci06p3<div><p>A Japanese firefly has flown into a cave full of obstacles: stalagmites (rising from the floor) and
stalactites (hanging from the ceiling). The cave is \(N\) units long (where \(N\) is even) and \(H\) units high. The
first obstacle is a stalagmite after which stalactites and stalagmites alternate.</p>
<p>Here is an example cave \(14\) units long and \(5\) units high (the image corresponds to the second example):</p>
<center><img src="https://camo.algome.me/a8838ee9c9df928ac2eefe94d1ffcf7...Mon, 17 Jun 2019 01:37:45 +0000https://dmoj.ca/problem/crci06p3COCI '06 Regional #2 Tetrishttps://dmoj.ca/problem/crci06p2<div><p>Tetris is a popular computer game played in a field consisting of \(C\) columns and an unlimited number
of rows. In one move, one of the following seven pieces is dropped into the field:</p>
<center><img src="https://camo.algome.me/f031d9c0496f27e7aab5a25d69944a1d241b88b6/68747470733a2f2f7763697065672e636f6d2f70726f626c656d2f696d616765732f636f636930363770322f636f636930363770322e312e706e67" alt=""></center><p>When dropping the piece, the player is free to rotate the piece 90, 180 or 270 d...Mon, 17 Jun 2019 01:37:28 +0000https://dmoj.ca/problem/crci06p2COCI '06 Regional #4 Circlehttps://dmoj.ca/problem/crci06p4<div><p>One nice summer day while Mirko was drinking lemonade in his room...</p>
<blockquote><p>"Big brother!", yells Stanko.</p>
<p>"I wonder sometimes which of the two of us is the big one. What is it?", Mirko asked.</p>
<p>"Listen carefully! In the backyard I have \(N\) pebbles arranged in a circle. Some of the pebbles are black,
some are white. I will do the following: between any two neighbouring pebbles of the <strong>same colour</strong> I
will insert a <strong>black pebble</strong>, and ...Sun, 16 Jun 2019 22:48:21 +0000https://dmoj.ca/problem/crci06p4COCI '06 Regional #1 Bardhttps://dmoj.ca/problem/crci06p1<div><p>Every evening villagers in a small village gather around a big fire and sing songs.</p>
<p>A prominent member of the community is the bard. Every evening, if the bard is present, he sings a
brand <strong>new song</strong> that no villager has heard before, and <strong>no other song</strong> is sung that night. In the event
that the bard is not present, other villagers sing without him and exchange <strong>all songs that they know.</strong></p>
<p>Given the list of villagers present for \...Sun, 16 Jun 2019 22:47:33 +0000https://dmoj.ca/problem/crci06p1An Easy Problemhttps://dmoj.ca/problem/tc19summeri<div><p>You wish to create an array \(f(x)\) with the following properties:</p>
<ol>
<li>The array has \(N\) elements.</li>
<li>Each element in the array is between \(0\) and \(N-1\).</li>
</ol>
<p>We define \(f^k(x)\) as follows:</p>
<p>\[f^k(x) = \begin{cases} f(x) & \text{if $k = 1$} \\ f(f^{k-1}(x)) & \text{if $k > 1$}\end{cases}\]</p>
<p>for all \(x\) between \(0\) and \(N-1\), \(f^k(x) = 0\) for some \(k\)</p>
<p>Given an integer \(N\), what is the number of arrays that satisfy ...Wed, 12 Jun 2019 03:56:30 +0000https://dmoj.ca/problem/tc19summeriTime Traveller Imaxbluehttps://dmoj.ca/problem/tc19summerh<div><p>//Lore</p>
<p>AQT: Hey Imax, I've been thinking about something ...</p>
<p>IMAX: Hmmmm?</p>
<p>AQT: You ever thought about going back in time? Fixing some of your old mistakes?</p>
<p>IMAX: Well ... I've always thought that its good to let fate take its course .... except for that one time..... that time ruined my life.</p>
<p>AQT: Wanna tell me about it?</p>
<p>IMAX: Lets fix it instead.</p>
<p>This problem takes place in space - time. Space-time consists of two parts - Space and Time. ...Wed, 12 Jun 2019 03:56:27 +0000https://dmoj.ca/problem/tc19summerhRacehttps://dmoj.ca/problem/tc19summerf<div><p>A point in Minecraft can be represented a 3-D coordinate. Currently, Chebyshev The Creeper, Euclidean The Enderman and Manhattan The Magma Cube are having a race. Each of them want to know how long it will take them to go from the coordinates \((A, B, C)\) to the coordinates \((X, Y, Z)\).</p>
<p>Every second, Chebyshev The Creeper can change his x-coordinate by <strong>at most</strong> one, y-coordinate by <strong>at most</strong> one and z-coordinate by <strong>at most</strong> one.</p...Wed, 12 Jun 2019 03:56:24 +0000https://dmoj.ca/problem/tc19summerfSolar Powerhttps://dmoj.ca/problem/tc19summere<div><p>Joe, ever-efficient, has now turned to another form of green energy: solar power. Joe owns one solar panel which he will use to produce electricity each day.
Each day consists of \(N\) minutes, over each of which the Sun changes position from sunrise at position \(1\) to sunset at position \(N\). The energy collected by the solar panel depends on the distance between its own position and the Sun’s position. Formally, if the solar panel is at a position \(i\) and the Sun is at a position...Wed, 12 Jun 2019 03:56:21 +0000https://dmoj.ca/problem/tc19summereNappinghttps://dmoj.ca/problem/tc19summerd<div><p>Joe loves sleeping. He loves it so much that he’ll take naps whenever and wherever possible. He is currently on a car ride with his parents, which will be \(N\) minutes long. During the trip, there will be \(M\) events at distinct times \(t_1, t_2, \ldots, t_M\) that will wake Joe up if he is sleeping during those times. Joe plans to take up to \(K\) naps during these \(N\) minutes, and since he loves uniformity, he wants them all to be of the same length. Joe wishes to know the maximum ...Wed, 12 Jun 2019 03:56:17 +0000https://dmoj.ca/problem/tc19summerdStringhttps://dmoj.ca/problem/tc19summerc<div><p>Given a string \(S\), concatenate it to itself \(N\) times, and call the result \(S'\). Given a string \(T\), you want to find the maximum number \(M\) such that \(T\) concatenated to itself \(M\) times is a subsequence of \(S'\). String \(S\) consists of lowercase English letters and wildcard character <code>&</code>, which can be any lowercase English letter, and string \(T\) consists of only lowercase English letters.</p>
<h4>Constraints</h4>
<p>\(|S|\), \(|T| \leq 7\,500\)<br>
\(...Wed, 12 Jun 2019 03:56:07 +0000https://dmoj.ca/problem/tc19summercCamerashttps://dmoj.ca/problem/tc19summerb<div><p>You have won the labour lottery and are now an apartment manager at 100 KRUSHVICE st. There, your job is to ensure that the \(N\) tenants are satisfied, and more important, following the government directives.</p>
<p>In order to do the latter, you plan to install \(K\)<sub>\(i\)</sub> cameras in tenant \(i\)'s room. Camera \(j\) in the \(i\)-th person's room has a probability of \(P\)<sub>\(i,j\)</sub> of discovering that person doing something illegal. (Note that discovering a person tw...Wed, 12 Jun 2019 03:55:57 +0000https://dmoj.ca/problem/tc19summerb