Recently Added DMOJ Problemshttps://dmoj.ca/The latest problems added on the DMOJ: Modern Online Judge websiteenFri, 16 Aug 2019 17:06:58 +0000IOI '19 P3 - Rectangleshttps://dmoj.ca/problem/ioi19p3<div><p>In the early 19th century, the ruler Hoseyngulu Khan Sardar ordered a palace to be
built on a plateau overseeing a beautiful river. The plateau is modeled as an \(n \times m\) grid
of square cells. The rows of the grid are numbered \(0\) through \(n-1\), and the columns
are numbered \(0\) through \(m-1\). We refer to the cell in row \(i\) and column \(j\) \((0 \le i \le n-1, 0 \le j \le m-1
)\) as cell \((i,j)\). Each cell \((i,j)\) has a specific height, denoted
by \(a[i][j]\).</p>
<p>H...Fri, 16 Aug 2019 17:06:58 +0000https://dmoj.ca/problem/ioi19p3IOI '19 P2 - Split the Attractionshttps://dmoj.ca/problem/ioi19p2<div><p>There are \(n\) attractions in Baku, numbered from \(0\) to \(n-1\). There are also \(m\) two-way
roads, numbered from \(0\) to \(m-1\). Each road connects two different attractions. It is
possible to travel between any pair of attractions through the roads.</p>
<p>Fatima is planning to visit all of the attractions in three days. She already decided that
she wants to visit \(a\) attractions on the first day, \(b\) attractions on the second day, and
\(c\) attractions on the third day. The...Fri, 16 Aug 2019 16:50:13 +0000https://dmoj.ca/problem/ioi19p2IOI '19 P1 - Arranging Shoeshttps://dmoj.ca/problem/ioi19p1<div><p>Adnan owns the biggest shoe store in Baku. A box containing \(n\) pairs of shoes has just
arrived at the store. Each pair consists of two shoes of the same size: a left and a right
one. Adnan has put all of the \(2n\) shoes in a row consisting of \(2n\) <strong>positions</strong> numbered \(0\)
through \(2n-1\) from left to right.</p>
<p>Adnan wants to rearrange the shoes into a <strong>valid arrangement</strong>. An arrangement is
valid if and only if for every \(i\) \((0 \le i \le n-1)...Fri, 16 Aug 2019 14:06:53 +0000https://dmoj.ca/problem/ioi19p1CEOI '16 P2 - Kangaroohttps://dmoj.ca/problem/ceoi16p2<div><p>A garden is composed of a row of \(N\) cells numbered from \(1\) to \(N\). Initially, all cells contain plants. A
kangaroo arrived in the garden in cell numbered \(c_s\). Then he jumps from cell to cell, eating the plants as
he goes. He will always finish in cell numbered \(c_f\), after visiting each of the \(N\) cells exactly once,
including \(c_s\) and \(c_f\). Obviously, the kangaroo will make \(N-1\) jumps.</p>
<p>The kangaroo doesn't want to be caught, so after each jump he changes ...Wed, 14 Aug 2019 03:19:27 +0000https://dmoj.ca/problem/ceoi16p2APIO '11 P3 - Guess My Word!https://dmoj.ca/problem/apio11p3<div><p><strong>The official test data is incorrect and has been recreated. If there are any issues with the data, please contact [user:Pookmeister] on slack.</strong></p>
<p>"Guess My Word" (or shortly GMW) is a two-player game, which is being played widely among young Iranian students! Naming two players A and B, initially A, the first player, picks a word from a corpus known to both players and keeps it in mind. Then, on a piece of paper visible to B, he draws as many little horizontal line s...Sun, 11 Aug 2019 02:05:05 +0000https://dmoj.ca/problem/apio11p3APIO '17 P2 - Travelling Merchanthttps://dmoj.ca/problem/apio17p2<div><p>After many days' journey through the great Australian outback, you have finally arrived at the great
city of Cobar with nothing but a small backpack. Enamoured by the wonder and beauty of its markets,
you decide to become a merchant and make Cobar your new home. Cobar has \(N\) markets, numbered
from \(1\) to \(N\), connected by \(M\) <strong>one-way</strong> footpaths, each taking a particular number of minutes to walk
along.</p>
<p>The markets of Cobar trade in \(K\) different items, n...Sun, 11 Aug 2019 00:30:59 +0000https://dmoj.ca/problem/apio17p2COCI '09 Contest 2 #2 Rimskihttps://dmoj.ca/problem/coci09c2p2<div><p>Using roman numerals the numbers \(1, 2, 3, 4, 5, 6, 7, 8, 9\) are written as <code>I</code>, <code>II</code>,
<code>III</code>, <code>IV</code>, <code>V</code>, <code>VI</code>, <code>VII</code>, <code>VIII</code>, <code>IX</code>. Numbers \(10, 20, 30, 40, 50, 60, 70, 80, 90\) are
written as <code>X</code>, <code>XX</code>, <code>XXX</code>, <code>XL</code>, <code>L</code>, <code>LX</code>, <code>LXX</code>, <code>LXXX</code>, <code>XC</code>.</p>
<p>Any number smaller than \(100\) can...Fri, 09 Aug 2019 01:58:40 +0000https://dmoj.ca/problem/coci09c2p2COCI '09 Contest 2 #1 Faktorhttps://dmoj.ca/problem/coci09c2p1<div><p>Impact factor of a scientific journal is a measure reflecting the average number
of citations to articles published in science journals. For this task we are using a
simplified formula for calculating the impact factor:</p>
<center>\(\Large \frac{\text{Total sum of all citations articles published in the journal received}}{\text{Total number of articles published}}\)</center><p><strong>Rounding is always preformed up.</strong> For example the impact factor of the
"Journal for ore researc...Fri, 09 Aug 2019 01:51:39 +0000https://dmoj.ca/problem/coci09c2p1COCI '09 Contest 1 #6 Aladinhttps://dmoj.ca/problem/coci09c1p6<div><p>Aladin was walking down the path one day when he found the strangest thing.
\(N\) empty boxes right next to a weird alien machine. After a bit of fumbling
around he got the machine to do something. The machine now accepts 4
integers \(L, R, A\) and \(B\). After that hitting the big red glowing button labeled "NE
DIRAJ" causes the machine to go crazy and follow the next routine:</p>
<ul>
<li>Set the number of stones in the box labeled \(L\) to \(A\) modulo \(B\).</li>
<li>It procedes to f...Fri, 09 Aug 2019 00:29:43 +0000https://dmoj.ca/problem/coci09c1p6COCI '18 Contest 3 #5 Praktičnihttps://dmoj.ca/problem/coci18c3p5<div><p>While writing an exam, Ivan had problems with the following task:</p>
<blockquote><p><em>"In the input there is an integer number \(N\). Find the \(N^{th}\) digit of the number \(0.135791113151719...\)"</em></p>
</blockquote>
<p>In order to succeed in the next attempt to pass the exam and so saving himself from repeating the
academic year, he decided to practice by being the main character in tasks such as the following:</p>
<p>An undirected graph of \(N\) nodes and \(M\) edges is given....Sat, 03 Aug 2019 20:54:09 +0000https://dmoj.ca/problem/coci18c3p5COCI '18 Contest 4 #5 Akviznahttps://dmoj.ca/problem/coci18c4p5<div><p><em>1 vs. 100</em> is a quiz that we could follow on TVs a few years ago. For the purposes of this task, we will
slightly simplify the quiz rules.</p>
<p>The contestant answers questions and has to throw out \(100\) people who compete against him.
Everyone responds to the same question in each round and those who answer the question wrong
are thrown out. The amount of money that a competitor who manages to throw out all \(100\) opponents
gets is equal to the sum of money won per round. I...Sat, 03 Aug 2019 20:47:26 +0000https://dmoj.ca/problem/coci18c4p5COCI '18 Contest 5 #5 Transporthttps://dmoj.ca/problem/coci18c5p5<div><p>The traffic network in one country consists of \(N\) cities (marked by numbers from \(1\) to \(N\)) and \(N-1\)
roads connecting them in a way that all cities are connected. For each road, its length in kilometers is
known, and in each city there is a gas station with a certain amount of fuel.</p>
<p>Due to the fuel shortages that hit the country a few years ago, the leading transport agency has
decided to conduct a survey on the ability to transport goods between cities. Trucks transpor...Sat, 03 Aug 2019 20:45:23 +0000https://dmoj.ca/problem/coci18c5p5COCI '18 Contest 5 #4 Parametriziranhttps://dmoj.ca/problem/coci18c5p4<div><p>A string of characters consisting of lowercase letters of the English alphabet and question marks is
called a parameterized word (e.g., <code>a??cd</code>, <code>bcd</code>, <code>??</code>). Two parameterized words are considered similar
if the question mark symbols in both words can be replaced by arbitrary lowercase letters of the
english alphabet so that the resulting strings are the same. For example, parameterized words <code>a???</code>
and <code>?b?a</code> are similar because by...Sat, 03 Aug 2019 20:39:21 +0000https://dmoj.ca/problem/coci18c5p4COCI '18 Contest 5 #3 Ispithttps://dmoj.ca/problem/coci18c5p3<div><p>After 26 years of studying, little Mirko took his potentially last exam. He confidently took his seat,
sharpened his pencil and waited calmly for the professor's permission to start writing – after all, that
was his favorite subject, <em>Data Structures and Algorithms</em>. But, as in any good story, this one also has
<em>that but</em>... Namely, when he got his exam, Mirko could not even comprehend what was written in it.</p>
<p>He only saw a meaningless matrix of letters with \(N\) row...Sat, 03 Aug 2019 20:21:07 +0000https://dmoj.ca/problem/coci18c5p3COCI '18 Contest 5 #2 Jarvishttps://dmoj.ca/problem/coci18c5p2<div><p>Ivan sent \(N\) drone warriors to the final battle against Tony Stark, also known as Iron Man. Each drone
has a defined frequency, expressed as an integer number, on which it receives commands from Ivan
during the fight. Jarvis, the artificial intelligence developed by Toni, has to determine which
frequencies those are and thereby take control over as many drones as possible.</p>
<p>Jarvis knows the original factory values of the frequency for each drone, but the frequencies required
for...Sat, 03 Aug 2019 20:13:26 +0000https://dmoj.ca/problem/coci18c5p2COCI '18 Contest 4 #2 Wandhttps://dmoj.ca/problem/coci18c4p2<div><p>Kile really liked Nikola's task with wizards and a wand (see task <em><a href="https://dmoj.ca/problem/coci18c4p1">Elder</a></em>) so he decided to make his
own version. He imagined that instead of the 26 wizards there are \(N\) of them labeled with integers
from \(1\) to \(N\) and that \(M\) duels must be held among the wizards. It is possible that a duel between the
same pair of wizards will be held multiple times.</p>
<p>As in Nikola's task, if before the match the wand belonged to th...Sat, 03 Aug 2019 19:54:40 +0000https://dmoj.ca/problem/coci18c4p2COCI '18 Contest 4 #1 Elderhttps://dmoj.ca/problem/coci18c4p1<div><p>After having watched all eight Harry Potter movies in a week, Nikola finally realized how the famous
Elder Wand changes the wizard it obeys. If wizard \(A\), whom the wand is currently obeying, is
defeated by wizard \(B\) in a duel, then the wand will start obeying the wizard \(B\).</p>
<p>Nikola is now wondering what would happen if 26 wizards labeled with upper case letters of the
English alphabet from <code>A</code> to <code>Z</code> began fighting in duels for the fondness of the Eld...Sat, 03 Aug 2019 19:23:46 +0000https://dmoj.ca/problem/coci18c4p1COCI '18 Contest 3 #4 NLOhttps://dmoj.ca/problem/coci18c3p4<div><p>The locals of the village Žabnik have been struggling for many years with unidentified flying objects
(UFOs) that create circles in grain fields. The damage is particularly noticeable during summer hay
mowing.</p>
<p>Let us imagine a rectangular grain field of \(N\) rows and \(M\) columns - the upper left field is designated
by coordinates \((1, 1)\), while the lower right field is designated by coordinates \((N, M)\). In each field
there is a certain amount of grass. Initially, amount o...Thu, 01 Aug 2019 18:56:35 +0000https://dmoj.ca/problem/coci18c3p4COCI '18 Contest 3 #2 Pismohttps://dmoj.ca/problem/coci18c3p2<div><p>In a small village besides Đakovo lives Kasap. While agriculture is his branch, love and destiny, in his
free time Kasap solves tasks in competitive programming and is doing very well. Particularly
interesting are the tasks involving data structures.</p>
<p>On a sunny summer day, Kasap's friend Mirko sent him a letter we carry forward entirely:</p>
<blockquote><p><em>"My dear Kasap,</em></p>
<p><em>I hope you tolerate well these hot summer days. I'm writing this letter because I have a p...Wed, 31 Jul 2019 02:05:38 +0000https://dmoj.ca/problem/coci18c3p2COCI '18 Contest 3 #1 Magnushttps://dmoj.ca/problem/coci18c3p1<div><p>Magnus lost a game of chess to Kile so he found comfort in competitive programming. Very soon, he
heard of the iconic COCI competition and decided to try his luck there.</p>
<p>He wrote a mail to Kile: <em>"Dear Kile, please, prepare me for COCI. Magnus".</em></p>
<p>Kile replied: <em>"You want to participate in COCI? All right, here's your warm-up task. A series of four
consecutive letters of some word that make up the subword <code>HONI</code> (Croatian acronym for COCI) is
called the ...Wed, 31 Jul 2019 00:51:00 +0000https://dmoj.ca/problem/coci18c3p1COCI '18 Contest 2 #4 Majahttps://dmoj.ca/problem/coci18c2p4<div><p>Maja the Bee pollinates flowers in a magical meadow. The meadow can be represented as a matrix of \(N\) rows and \(M\) columns. In \(i^{th}\) row and \(j^{th}\) column there are \(C_{i,j}\) unpollinated flowers.</p>
<p>Maja will start her journey from her hive, which is located in the field in the \(A^{th}\) row and \(B^{th}\) column. In several steps, she will visit some fields of the meadow and then return back to her hive. From each field, Maja can move to one of its adjacent cells in...Tue, 30 Jul 2019 19:28:47 +0000https://dmoj.ca/problem/coci18c2p4COCI '18 Contest 2 #3 Deblohttps://dmoj.ca/problem/coci18c2p3<div><p>About thirty years ago, young Krešo participated for the first time in the national informatics
competition. Similar to today, the opening of the competition consisted of a series of speakers who
tried to demonstrate the importance of this event to the contestants through motivational messages.
The audience, with enthusiasm, began applauding every couple of seconds, but Krešo was irritated
by one sentence. Namely, one of the speakers claimed he was more appreciative of the logical
operat...Tue, 30 Jul 2019 19:28:23 +0000https://dmoj.ca/problem/coci18c2p3COCI '18 Contest 2 #2 Kockahttps://dmoj.ca/problem/coci18c2p2<div><p>I’m again in the cube!</p>
<p>I’m again in the cube!</p>
<p>While watching the kids’ playground in the early morning hours, the author of this task caught sight of
an interesting object: a cube made out of metal bars, composed of many unit-sized cubes made out
of metal bars.</p>
<p>While observing the cube, an interesting problem came to his mind. Here follows the two-dimensional
version of the problem, since nobody likes problems involving 3D objects:</p>
<p>You’re given \(N × N\) matri...Tue, 30 Jul 2019 19:27:39 +0000https://dmoj.ca/problem/coci18c2p2Bane of Arthropodshttps://dmoj.ca/problem/spider<div><p>Leon has created a cute little robot spider pet! //\((::\)w\(::)\)\\
<br>
Instead of generating an intricate pattern for its web, it simply interweaves \(R\) rows with \(C\) columns of silk.
It starts with an empty web; a full web consists of \(R + C\) strands of silk forming a grid-like pattern.
<br>
Please help implement some of its functions, and you might be rewarded (with points)!</p>
<p><strong>F1</strong>: <em>Robo-Spider</em> generates silk somehow (don't ask me, I'm just the pro...Wed, 24 Jul 2019 13:21:42 +0000https://dmoj.ca/problem/spiderAnother Contest 5 Problem 5 - Another Cheese Problemhttps://dmoj.ca/problem/acc5p5<div><p>After a long day of being a goat farmer, Tudor finally returns to an old hobby of his - baking cheese.</p>
<p>Tudor's recipe requires \(N\) operations to be performed. The operations happen to form a directed tree,
where operation \(a_i\) may depend on some other operations to be performed first. Operation 1
is guaranteed to be the last operation to perform and there will be no cyclic dependencies.</p>
<p>Each operation will generate some intermediate result in the process of baking chee...Mon, 22 Jul 2019 06:40:51 +0000https://dmoj.ca/problem/acc5p5