Recently Added DMOJ Problemshttps://dmoj.ca/The latest problems added on the DMOJ: Modern Online Judge websiteenSun, 17 Feb 2019 02:14:27 +0000Valentine's Day '19 S1 - Votinghttps://dmoj.ca/problem/valentines19s1<div><p>At the annual Valentines Day dance, a vote takes place to determine King and Queen Valentine!</p>
<p>The event organizers have decided to use the alternative vote to determine the winner of this contest.</p>
<p>In the alternative vote system, voters can rank their candidates rather than simply picking a single candidate.</p>
<p>Votes are tallied in the following way:</p>
<ol>
<li>Count the voters' first choices.</li>
<li>Eliminate last place candidate by lowest number of votes. If there ...Sun, 17 Feb 2019 02:14:27 +0000https://dmoj.ca/problem/valentines19s1Valentine's Day '19 S2 - Ctudor's Cute Cactihttps://dmoj.ca/problem/valentines19s2<div><p>Ctudor (silent 'C') just bought an \(N\) by \(N\) grid of cacti! He wants to monitor the happiness of each cactus. Cacti only have 2 moods - happy and sad. When Ctudor bought the cacti, all of them were happy. However, \(Q\) events happen:</p>
<ul>
<li><code>1 i j</code>. The cactus at position \((i, j)\) suddenly switches their mood. If it was happy, it is now sad, and vice versa. It is common knowledge that a cactus's mood is easily affected by its surrounding cacti. Thus, when the cac...Sun, 17 Feb 2019 02:11:26 +0000https://dmoj.ca/problem/valentines19s2Valentine's Day '19 S5 - A Top Tree Problemhttps://dmoj.ca/problem/valentines19s5<div><p>Jonathan is making a connected tree of \(N\) nodes, and \(N-1\) bidirectional edges. He wants to give the tree to <REDACTED> for Valentine's Day. However, he wants to make sure the tree is <em>good looking</em>.</p>
<p>Jonathan defines a <em>simple</em> path in the tree as a path where every node is traversed at most once.</p>
<p>To determine whether the tree is <em>good looking</em>, he will give you \(Q\) queries that you must answer for him:</p>
<ul>
<li><code>v k u_1 u_2 ... u_...Sun, 17 Feb 2019 02:03:51 +0000https://dmoj.ca/problem/valentines19s5Valentine's Day '19 S4 - A Greedy Spousehttps://dmoj.ca/problem/valentines19s4<div><p>We all know the famous interval-scheduling problem. You have been given \(N\) tasks, each of which will run between time \(l_i\) and \(r_i\), inclusive, that you must tell your computer to run. You want to schedule the maximum number of tasks, under the condition that only one task can be run at any given point in time.</p>
<p>Your beloved spouse has gone ahead and assigned the tasks greedily. In particular, they will sort the tasks in order of increasing \(l_i\), and then increasing \(r...Sun, 17 Feb 2019 02:03:45 +0000https://dmoj.ca/problem/valentines19s4Valentine's Day '19 S3 - Mathematical Englishhttps://dmoj.ca/problem/valentines19s3<div><p>You are reading a novel in English class! The novel has a total of \(N\) chapters, with each chapter consisting of \(p_i\) pages. Your teacher has broken up your class into \(M\) groups, each with \(g_j\) students, for presentations.</p>
<p>He wants to assign a potentially empty subarray of the chapters to each group for them to present, such that each chapter is assigned to <strong>exactly one</strong> group. Note that <strong>chapters can not be split</strong>.</p>
<p>Your teacher defi...Sun, 17 Feb 2019 02:03:10 +0000https://dmoj.ca/problem/valentines19s3CTU Open Contest 2018 - Escalatorshttps://dmoj.ca/problem/ctuopen2018j<div><p>Binary Casino is a very special skyscraper building consisting of N floors connected by a tricky
network of high speed escalators.
The floor connections are designed in a way that if there is an escalator going from floor \(A\) to
floor \(B\), then there is another escalator going from floor \(B\) to floor \(A\) as well. Also, for any two
floors \(A\) and \(B\), there is exactly one way to go from floor \(A\) to floor \(B\).
Your manager decided to organize a promotion game to attract mo...Thu, 14 Feb 2019 01:19:05 +0000https://dmoj.ca/problem/ctuopen2018jCTU Open Contest 2018 - Moving Furniturehttps://dmoj.ca/problem/ctuopen2018i<div><p>Binary Casino had been open nonstop for a long period of time. It desperately needed renovation
as the substantial damage to its carpet and furniture did not look good. While renovation took
place, four-legged game tables from all game rooms were deposited in a storage room.</p>
<p>Your task is not difficult. You were asked by your boss to move the game tables to the exactly
same place where they were positioned before. Each game table desk is a square and the table
legs are located exac...Thu, 14 Feb 2019 01:13:38 +0000https://dmoj.ca/problem/ctuopen2018iCTU Open Contest 2018 - Split Gamehttps://dmoj.ca/problem/ctuopen2018h<div><p>For a long time, rich clientele of Binary Casino has been requesting a new way to gamble their
money. To fulfill their wishes, the director of Binary Casino decided to introduce a new game
called Split Your Tokens.</p>
<p>This game is played only when a customer is about to exit the casino. Instead of exchanging
tokens won during his visit, he may take up casino’s challenge and bet all of his earned tokens
on winning this game. Should the customer lose, all of his tokens are lost in favo...Thu, 14 Feb 2019 01:05:20 +0000https://dmoj.ca/problem/ctuopen2018hCTU Open Contest 2018 - Horsemeethttps://dmoj.ca/problem/ctuopen2018g<div><p>Traditional games such as chess or checkers with slight modifications, are also played in Binary
Casino. However, not many people play them, as these games are often referred as boring. The
visitors are more attracted to more dynamic games which cause adrenaline rushes. To attract
players to traditional games, your boss wants to introduce a chess-based game called Horsemeet.
The rules of the game are:</p>
<p>The game is played by two players on a \(8 \times 8\) chessboard. One player pla...Thu, 14 Feb 2019 00:57:01 +0000https://dmoj.ca/problem/ctuopen2018gCTU Open Contest 2018 - Lightinghttps://dmoj.ca/problem/ctuopen2018f<div><p>The lighting system in Binary Casino is controlled by a very complex and secure mechanism,
which is connected to a central control console. At the console, the state of each light is stored
as one bit of information (0=the corresponding light is off, 1=light is on), so the complete state
of all lights in the building may be represented by a binary number \(a\).</p>
<p>To avoid manipulation by unauthorized persons, the lighting system has a special method to
control the lights. Should one...Thu, 14 Feb 2019 00:55:37 +0000https://dmoj.ca/problem/ctuopen2018fCTU Open Contest 2018 - Locker Roomhttps://dmoj.ca/problem/ctuopen2018e<div><p>There are several strange rooms in Binary Casino and one of them is a locker room. You have
to enter the locker room several times a day, two times being a minimum (before and after your
shift). There is no key or access code needed to enter the locker room. There is a brand new
security lock system instead.</p>
<p>The lock system presents you with a generated puzzle which you have to solve every time you
want to enter the locker room. This system prevents possible intruders to enter the...Thu, 14 Feb 2019 00:11:46 +0000https://dmoj.ca/problem/ctuopen2018eCTU Open Contest 2018 - Numbers Generatorhttps://dmoj.ca/problem/ctuopen2018d<div><p>Among the most popular games in Binary casino is a game called “The Binary Generator”. It
is played by multiple players and with a single coin. Each player first chooses a sequence of
heads and tails of a given length. After that, players or the casino start flipping the coin and
the winner is the player whose sequence first appears as a contiguous subsequence of the flip
results.</p>
<p>You believe all sequences chosen by players are equally good and so the choice of the sequence
does n...Wed, 13 Feb 2019 23:09:40 +0000https://dmoj.ca/problem/ctuopen2018dCTU Open Contest 2018 - Rulletehttps://dmoj.ca/problem/ctuopen2018c<div><p>Binary Casino has established a new department to attract families with children. One of its
first tasks is to design a game for children which will be not so difficult to play. The result of a
week of hard work is a game called Rullete.
Each player gets a hand of 5 cards. Cards in the hand are ordered as first, second, . . ., fifth.
Each card is described by a rank and a suit. Card’s rank can be one of 2, 3, ..., 10, J, Q, K, A
and its suit can be one of D, H, C, or S (Diamonds, Hearts,...Wed, 13 Feb 2019 22:43:59 +0000https://dmoj.ca/problem/ctuopen2018cCTU Open Contest 2018 - Security Guardshttps://dmoj.ca/problem/ctuopen2018b<div><p>In the course of the last few weeks, Binary Casino has been afflicted by a local crime wave which
is primarily focused on casinos in the neighborhood. Although there are surveillance cameras
installed in Binary Casino, thieves usually manage to sneak out with relative ease as there is
almost nobody patrolling in the casino.</p>
<p>After the theft of all Friday’s earnings, the manager of Binary Casino has lost his patience and
decided to reinforce security of the casino by hiring a vast n...Wed, 13 Feb 2019 22:43:49 +0000https://dmoj.ca/problem/ctuopen2018bCTU Open Contest 2018 - Diehttps://dmoj.ca/problem/ctuopen2018a<div><p>The boss of Binary Casino wants to have control over games played in his casino. This is
especially true in the case of dice games, as from time to time people try to cheat their way to
the victory by manipulating dice even after a throw has already occurred. Therefore, there is a
camera installed to monitor the course of every single dice game. Dice recognition, however, is
not an easy task and sometimes a camera may produce a faulty image which makes the task of
recognition impossible....Wed, 13 Feb 2019 22:23:11 +0000https://dmoj.ca/problem/ctuopen2018aGlobeX Cup '18 S5 - Math Bashhttps://dmoj.ca/problem/globexcup18s5hard<div><p><strong>The constraints for the problem have changed from the in-contest version.</strong></p>
<p>You are taking your calculus exam. In the exam room, there is an \(N \times N\) grid of desks, each with exactly one student taking an exam at that desk.</p>
<p>Your teacher has came up with an interesting way of grading the exams. Let \(p_{i,j}\) represent the initial mark that the student at position \((i,j)\) got on the exam. His <em>actual</em> mark, \(a_{i,j}\), is equal to \(a_{i,j} = ...Tue, 12 Feb 2019 15:06:33 +0000https://dmoj.ca/problem/globexcup18s5hardMock CCC '19 Contest 2 S5 - Tudor Takes Pictures of Goatshttps://dmoj.ca/problem/nccc7s5<div><p>Tudor has decided to upload pictures of his goats to Instagram!</p>
<p>Tudor's goats are currently located at various lattice points in the \(xy\)-plane. To take pictures of his goats,
Tudor will use a drone with a camera mounted on it. Tudor will send the drone to some point \((x, y, z)\) with \(z > 0\) and
then take pictures of the goats from that location.</p>
<p>The camera that Tudor is using is a bit finicky - it can be set to focus on objects that are exactly \(d\) units away,
b...Mon, 11 Feb 2019 05:34:05 +0000https://dmoj.ca/problem/nccc7s5Mock CCC '19 Contest 2 S4 - Tudor Walks Among the Goatshttps://dmoj.ca/problem/nccc7s4<div><p>Tudor is going for a walk!</p>
<p>In this scenario, Tudor has \(N\) goats tied to fence posts at various locations with varying lengths
of ropes. Tudor is going to go walking on an infinite line. If, at any point along the walk,
a goat is able to reach Tudor, even at the maximal range of the rope, then the goat will run at Tudor.
Tudor will then be able to check on the goat to make sure that it's in fine health.</p>
<p>The goats are rather territorial, so Tudor's initial assignments of r...Mon, 11 Feb 2019 05:34:04 +0000https://dmoj.ca/problem/nccc7s4Mock CCC '19 Contest 2 S3 - Tudor Tallies Triangular Totalshttps://dmoj.ca/problem/nccc7s3<div><p>Tudor has decided to build a triangular pen for his goats!</p>
<p>Tudor has identified \(N\) locations on his farm where he can install fence posts.
To construct a pen, Tudor will install fence posts at exactly three locations,
and then build fences between those fence posts.</p>
<p>For obvious reasons, Tudor must select fence posts such that there is strictly
positive area for the goats to roam around inside.</p>
<p>How many different pens can Tudor construct? Two pens are different if ...Mon, 11 Feb 2019 05:23:13 +0000https://dmoj.ca/problem/nccc7s3Mock CCC '19 Contest 2 S2 - Tudor Puts A Goat On A Ropehttps://dmoj.ca/problem/nccc7s2<div><p>Tudor is going on vacation!</p>
<p>While Tudor is on vacation, he decides to take his goat and tie to a fence post with a rope.
Because he doesn't want to infringe too many on the goat's freedom to trample on the earth,
he wants the rope to be as long as possible. However, because he doesn't feel like dealing
with property damage, he doesn't want the goat to be able to run into his house.</p>
<p>Tudor's house is modeled as an axis-aligned rectangle with corners at \((x_1, y_1)\) and \((x...Mon, 11 Feb 2019 05:18:22 +0000https://dmoj.ca/problem/nccc7s2Mock CCC '19 Contest 2 S1 - Tudor's Double Doorshttps://dmoj.ca/problem/nccc7s1<div><p>Tudor, having finally had his fill of tea, now needs to think about keeping his goats safe.</p>
<p>Tudor has obtained a large rectangular door that is \(X\) metres long, \(Y\) metres high,
and 1 metre thick. He intends on using this door to gate access to his goats.</p>
<p>There's only one problem - having just one door is aesthetically unpleasing to Tudor.</p>
<p>Therefore, he intends on taking the door and cutting it in half to make a set of double doors
that he can use to gate access ...Mon, 11 Feb 2019 05:18:14 +0000https://dmoj.ca/problem/nccc7s1IOI '09 P7 - Regionshttps://dmoj.ca/problem/ioi09p7<div><p>The United Nations Regional Development Agency (UNRDA) has a very well defined
organizational structure. It employs a total of \(N\) people, each of them coming from one of \(R\)
geographically distinct regions of the world. The employees are numbered from \(1\) to \(N\) inclusive
in order of seniority, with employee number \(1\), the Chair, being the most senior. The regions are
numbered from \(1\) to \(R\) inclusive in no particular order. Every employee except for the Chair has a
sing...Mon, 04 Feb 2019 14:41:11 +0000https://dmoj.ca/problem/ioi09p7Mock CCC '19 Contest 2 J5 - Tudor Drinks Even More Teahttps://dmoj.ca/problem/nccc7j5<div><p>Tudor hasn't had enough tea yet?</p>
<p>Tudor has prepared two cups of tea this time, each one with a certain number of micrograms
of sugar. Tudor is superstitious and does not like it when the counts of micrograms of
sugar are not relatively prime. The cups of tea must have integer micrograms of sugar.</p>
<p>Recall that two integers are relatively prime if their greatest common divisor is 1.</p>
<p>Given that the first cup of tea must have between \(A\) and \(B\) micrograms of sugar an...Mon, 04 Feb 2019 05:04:31 +0000https://dmoj.ca/problem/nccc7j5Mock CCC '19 Contest 2 J4 - Tudor Buys Some Cheesecakehttps://dmoj.ca/problem/nccc7j4<div><p>Tudor is planning a surprise, and needs to buy a cheesecake!</p>
<p>Having bought the cheesecake, Tudor wants to spell a message with the candles.
Each candle is shaped in the form of one of the 26 letters of the English
alphabet.</p>
<p>Tudor digs around in the DMOJ storage room and finds some candles that he can use.
Given the candles he has and the message he wishes to spell, compute the minimum
number of candles that Tudor needs to purchase in order to spell the message.</p>
<h4>Cons...Mon, 04 Feb 2019 05:03:48 +0000https://dmoj.ca/problem/nccc7j4Mock CCC '19 Contest 2 J3 - Tudor Buys Some Teahttps://dmoj.ca/problem/nccc7j3<div><p>Tudor, having made his own tea for far too long, has decided to go to a nearby tea shop
to buy some tea.</p>
<p>As every respectable tea shop does, this specific tea shop offers a loyalty program.
For every \(K\) cups of tea that Tudor buys at the shop, the shop will give him one free
cup of tea.</p>
<p>Tudor wants to drink at least \(N\) cups of tea. How many cups of tea will he have to buy in order
to achieve this goal?</p>
<h4>Constraints</h4>
<p>\(1 \le N, K \le 10^{18}\) - note that...Mon, 04 Feb 2019 05:02:54 +0000https://dmoj.ca/problem/nccc7j3