Recently Added DMOJ Problemshttps://dmoj.ca/The latest problems added on the DMOJ: Modern Online Judge websiteenWed, 15 Nov 2017 19:11:43 +0000DMOPC '17 Contest 2 P6 - Lazy Dayshttps://dmoj.ca/problem/dmopc17c2p6<div><p>Bob is kicking back and relaxing today! He plans to continually watch TV for \(N\) hours. His TV has two channels each of which has a new show every hour. Every show has a rating from \(0\) to \(10^6\). Arrays \(A\) and \(B\) will represent the ratings of the shows of the first and second channel respectively. Bob wants to watch the shows so that he maximizes the minimum of the ratings of the shows he watches. Additionally, he is lazy, so he doesn't like reaching for his remote. Help Bob...Wed, 15 Nov 2017 19:11:43 +0000https://dmoj.ca/problem/dmopc17c2p6DMOPC '17 Contest 2 P5 - Gamehttps://dmoj.ca/problem/dmopc17c2p5<div><p>You are playing a game with your friend. There is a pile with \(N\) stones and a chosen number \(K\). You and your friend alternate turns to remove some number of stones. Call \(s_i\) the number of stones removed on the \(i^{\text{th}}\) turn. \(s_1=1\), that is, the first player must remove exactly \(1\) stone. After that, on the \(i^{\text{th}}\) turn, the current player is allowed to remove any number of stones between \(1\) and \(s_{i-1}+K\). The player who removes the last stone win...Wed, 15 Nov 2017 19:11:22 +0000https://dmoj.ca/problem/dmopc17c2p5DMOPC '17 Contest 2 P3 - Bad Bunnieshttps://dmoj.ca/problem/dmopc17c2p3<div><p>Carrots fear one thing, and one thing alone: bad bunnies.</p>
<p>A lost carrot has found themselves in a unweighted graph with \(N\) nodes inside bad bunny territory. The carrot knows a little graph theory and recognizes that this graph is a tree! Currently, they are at node \(X\) and needs to get to node \(Y\) to escape. However, there are \(R\) rabbits, the \(i^{\text{th}}\) of which is on node \(R_i\) of the graph. Help this carrot figure out the closest they will ever have to be to a...Wed, 15 Nov 2017 19:10:20 +0000https://dmoj.ca/problem/dmopc17c2p3DMOPC '17 Contest 2 P4 - Mimi and Dictionaryhttps://dmoj.ca/problem/dmopc17c2p4<div><p>Mimi is playing with a dictionary when she gets a great idea! Throw random words together, give them a definition, and then make a problem about it!</p>
<p>For this problem, Mimi has decided to define a <strong>proper prefix palindrome</strong> of string \(S\) as a proper prefix of \(S\) which is also a palindrome. Given a string \(S\), find the length of the longest proper prefix palindrome which appears at least twice.</p>
<h4>Constraints</h4>
<p>Let \(|S|\) denote the length of string...Wed, 15 Nov 2017 18:56:54 +0000https://dmoj.ca/problem/dmopc17c2p4DMOPC '17 Contest 2 P2 - Balancehttps://dmoj.ca/problem/dmopc17c2p2<div><blockquote><p>You were the Chosen One! You were supposed to destroy the Sith, not join them. You were supposed to bring balance to the Force, not leave it in darkness.</p>
</blockquote>
<p>The Force, represented by the characters <code>(</code> and <code>)</code> is now unbalanced! The Force is <em>balanced</em> if it is one of the following:</p>
<ul>
<li><code>()</code></li>
<li><code>AB</code>, where \(A\) and \(B\) are balanced</li>
<li><code>(A)</code>, where \(A\) is balanced</li>
</u...Wed, 15 Nov 2017 18:37:50 +0000https://dmoj.ca/problem/dmopc17c2p2DMOPC '17 Contest 2 P1 - 0-1 Knapsackhttps://dmoj.ca/problem/dmopc17c2p1<div><p>A classical problem in Computer Science is the 0-1 Knapsack problem. In this problem, you are given \(N\) items with the \(i\)th item takes up a capacity of \(c_i\) and has a value of \(v_i\), and a knapsack with capacity \(C\), and try to maximize sum of the value of the items in the knapsack while not exceeding the capacity of the knapsack.</p>
<p>Unfortunately, your knapsack has just broke (again). Since you can't fix it, you decide to get a new knapsack. Upon doing so, you shall atte...Wed, 15 Nov 2017 18:37:29 +0000https://dmoj.ca/problem/dmopc17c2p1DMOPC '17 Contest 2 P0 - Secretshttps://dmoj.ca/problem/dmopc17c2p0<div><p>Two secret agents are exchanging messages over a computer, however, they notice that there is a shady being nearby. Given the coordinates of the two secret agents \((x_1, y_1)\) and \((x_2, y_2)\), and the shady being, \((x_s, y_s)\), is the shady being within \(D\) units of an agent?</p>
<h4>Constraints</h4>
<p>\(-100 \le x_1, y_1, x_2, y_2, x_s, y_s \le 100\)<br>
\(1 \le D \le 100\)</p>
<h4>Input Specification</h4>
<p>The first line will consist of two space separated integers, \(x_1\)...Wed, 15 Nov 2017 18:36:23 +0000https://dmoj.ca/problem/dmopc17c2p0CCO '08 P6 - Landinghttps://dmoj.ca/problem/cco08p6<div><h5>Canadian Computing Olympiad: 2008 Day 2, Problem 3</h5>
<p>Keep watching the skies! Alien spacecraft are due to land any day now to share all of
their advanced programming secrets with us.</p>
<p>In preparation for this day, you’ve been tasked with preparing a landing pad for our
visitors in a given field. Unfortunately, due to environmental considerations, you will not be
permitted to remove any of the trees which currently exist on the field. These trees are of
immense scientific inte...Mon, 06 Nov 2017 02:46:49 +0000https://dmoj.ca/problem/cco08p6CCO '08 P4 - Herdinghttps://dmoj.ca/problem/cco08p4<div><h5>Canadian Computing Olympiad: 2008 Day 2, Problem 1</h5>
<p>Oh no! A number of stray cats have been let loose in the city, and as the City Cat
Catcher, you have been assigned the vital task of retrieving all of the cats. This is an ideal
opportunity to test your latest invention, a cat trap which is guaranteed to retrieve every
cat which walks into a square-shaped subsection of the city.
Fortunately, you have the assistance of one of the world’s foremost cat psychologists, who
has the am...Mon, 06 Nov 2017 02:13:47 +0000https://dmoj.ca/problem/cco08p4TLE '17 Contest 2 P6 - Save Jody!https://dmoj.ca/problem/tle17c2p6<div><div style="float:right; width:300px; padding: 10px 10px">
<img src="https://camo.dmuser.ml/f2bff8d65e8da30379076cc3bc51978dc0bc6ad6/68747470733a2f2f692e696d6775722e636f6d2f775a38343939352e6a7067" style="display: block; margin: 0 auto; width:100%;">
<div style="text-align:center;font-style:italic;margin-top:0.5em">Can Fax escape in time?</div></div><p>Fax McClad, Croneria's most heroic bounty hunter has learned that Space Pirates have captured his friend Jody and locked her up in a power pl...Sun, 29 Oct 2017 18:51:48 +0000https://dmoj.ca/problem/tle17c2p6TLE '17 Contest 2 P5 - Crew Selection Testhttps://dmoj.ca/problem/tle17c2p5<div><div style="float:right; width:300px; padding: 10px 10px">
<img src="https://camo.dmuser.ml/18bb9731cf4bc1510434bbf2418d607535974705/68747470733a2f2f692e696d6775722e636f6d2f4f49346e6a71562e706e67" style="display: block; margin: 0 auto; width:100%;">
<div style="text-align:center;font-style:italic;margin-top:0.5em">Fax and the Great Fax.</div></div><p>Fax McClad, Croneria's most independent bounty hunter, has decided to form a crew of \(P\) people to operate his spacecraft carrier, the Great...Sun, 29 Oct 2017 18:51:39 +0000https://dmoj.ca/problem/tle17c2p5TLE '17 Contest 2 P4 - ECOOhttps://dmoj.ca/problem/tle17c2p4<div><div style="float:right; width:250px; padding: 10px 10px">
<img src="https://camo.dmuser.ml/f50598390cf0f0f12dea2f91496ffc73877742ce/68747470733a2f2f692e696d6775722e636f6d2f696d5a6b444d642e706e67" style="display: block; margin: 0 auto; width:100%;">
<div style="text-align:center;font-style:italic;margin-top:0.5em">It's hard to see the scoreboard...</div></div><p>Your team has already finished the ECOO Provincials, but you aren't sure if you are winning or not!</p>
<p>A team's score on the E...Sat, 28 Oct 2017 21:24:01 +0000https://dmoj.ca/problem/tle17c2p4TLE '17 Contest 2 P3 - Willson and Migrationhttps://dmoj.ca/problem/tle17c2p3<div><div style="float:right; width:300px; padding: 10px 10px">
<img src="https://camo.dmuser.ml/7b244732c8b32c04c97c4c92ec33bcdf0e1dac2c/68747470733a2f2f692e696d6775722e636f6d2f643334316739712e6a7067" style="display: block; margin: 0 auto; width:100%;">
<div style="text-align:center;font-style:italic;margin-top:0.5em">Willson and his family migrating.</div></div><p>Willson the Canada Goose is like any other Canada goose - he migrates south for winter. As anyone knows, geese like to travel with ...Sat, 28 Oct 2017 21:07:14 +0000https://dmoj.ca/problem/tle17c2p3TLE '17 Contest 2 P2 - Unlucky Numbershttps://dmoj.ca/problem/tle17c2p2<div><div style="float:right; width:250px; padding: 10px 10px">
<img src="https://camo.dmuser.ml/dddb9440dc52d860882638485a4442d8375580ad/68747470733a2f2f692e696d6775722e636f6d2f43564d30556f542e706e67" style="display: block; margin: 0 auto; width:100%;">
<div style="text-align:center;font-style:italic;margin-top:0.5em">The bright red buildings and skies of the University of Fireloo.</div></div><p>The University of Fireloo is about to build a new on-campus residence named <strong>University of Fi...Sat, 28 Oct 2017 21:06:33 +0000https://dmoj.ca/problem/tle17c2p2TLE '17 Contest 2 P1 - Cadadrhttps://dmoj.ca/problem/tle17c2p1<div><div style="float:right; width:200px; padding: 10px 10px">
<img src="https://camo.dmuser.ml/620cde0aea44002e74ebd74d532bdbf0fe7dc29b/68747470733a2f2f692e696d6775722e636f6d2f457436625832592e706e67" style="display: block; margin: 0 auto; width:100%;">
<div style="text-align:center;font-style:italic;margin-top:0.5em">Sample ending logic of a program in Bracket.</div></div><p>Some computer science courses at the University of Fireloo teach a programming language called Bracket.</p>
<p>Two of th...Sat, 28 Oct 2017 21:06:18 +0000https://dmoj.ca/problem/tle17c2p1CCO '08 P5 - Candyhttps://dmoj.ca/problem/cco08p5<div><h5>Canadian Computing Olympiad: 2008 Day 2, Problem 2</h5>
<p>You and a friend have a big bag of candy. You want to keep slim and trim, and so you would like to equalize the candy which you are sharing with your friend in terms of calorie count. That is, your task is to divide the candies into two groups such that the number of calories in each group is as close together as possible.</p>
<h4>Input Specification</h4>
<p>The first line of input contains the number of different kinds of can...Sat, 21 Oct 2017 21:04:02 +0000https://dmoj.ca/problem/cco08p5Inaho IIhttps://dmoj.ca/problem/inaho2<div><p>Inaho is a scientist. He discovered the fourth dimension recently. In fact, he also discovered the fifth, the sixth, the seventh, the eighth, the ninth, and the tenth dimension! Today, as he was travelling on the infinite plane of uniform density, he fell into an \(N\)-dimensional hole. "How did that even happen?", he asks in disbelief, but he quickly realized that finding his way out is perhaps more important. However, as a measly 3-D being, he cannot understand the complexities of \(N\...Sun, 15 Oct 2017 05:49:25 +0000https://dmoj.ca/problem/inaho2DMOPC '17 Contest 1 P6 - Land of the Carrot Treeshttps://dmoj.ca/problem/dmopc17c1p6<div><p>A long time ago, in the not-so-distant LCT (land of the carrot trees), where carrots grow on trees, lived a magical carrot. In this magical land, there were \(N\) cities numbered \(1, 2, \ldots N\), connected with \(N-1\) roads, with no cycles. Over the course of \(Q\) days, some interesting things happened to the roads:</p>
<ul>
<li><code>A x y z</code>: A new road of durability \(z\) is built between cities \(x\) and \(y\)</li>
<li><code>R x y</code>: The road between cities \(x\) and ...Wed, 11 Oct 2017 21:18:49 +0000https://dmoj.ca/problem/dmopc17c1p6DMOPC '17 Contest 1 P5 - Intimidating Arrayshttps://dmoj.ca/problem/dmopc17c1p5<div><p>Call an element of an array \(A\) a <em>peak of \(A\)</em> if it is larger than all elements before it in \(A\). The <em>intimidation value</em> of an array is the number of peaks of \(A\).</p>
<p>For example, the intimidation value of \(1, 2, 3, 4, 5\) is \(5\) and the intimidation value of \(5, 4, 3, 2, 1\) is \(1\) (only \(5\) is intimidating).</p>
<p>You are given a permutation of \(1, 2, \ldots, N\) and are asked to answer \(Q\) queries. These queries are of the form <code>l r</code...Wed, 11 Oct 2017 21:18:35 +0000https://dmoj.ca/problem/dmopc17c1p5DMOPC '17 Contest 1 P4 - Questshttps://dmoj.ca/problem/dmopc17c1p4<div><p>In a distant kingdom, there lived a certain <span title="NEET">knight</span>. What did this <span title="NEET">knight</span> do? Play video games of course!</p>
<p>In his most recent video game, there are \(N\) NPCs, each of whom offers a distinct repeatable quest. It takes the <span title="NEET">knight</span> \(h_i\) hours to reach the \(i^{\text{th}}\) NPC and and he gains \(g_i\) gold along the way. Once he reaches an NPC, he can perform its quest as many times as he likes. Doing the ...Wed, 11 Oct 2017 21:18:17 +0000https://dmoj.ca/problem/dmopc17c1p4DMOPC '17 Contest 1 P3 - Hitchhiking Funhttps://dmoj.ca/problem/dmopc17c1p3<div><p>Bob is hitchhiking from city to city. There are \(N\) cities numbered from \(1\) to \(N\) and \(M\) bidirectional roads. He starts at city \(1\) and wants to get to city \(N\). He has researched each road, and designated each one as either <strong>safe</strong> or <strong>dangerous</strong> for hitchhikers. Assuming that Bob will always be able to find a ride, find the minimum number of dangerous roads Bob must travel along to get to city \(N\). Bob also wants to know the minimum number ...Wed, 11 Oct 2017 21:17:51 +0000https://dmoj.ca/problem/dmopc17c1p3DMOPC '17 Contest 1 P2 - Sharing Crayonshttps://dmoj.ca/problem/dmopc17c1p2<div><p>Mimi is helping out at a daycare! There are \(M\) children and \(N\) boxes of crayons in a row, the \(i^\text{th}\) of which has \(c_i\) crayons. Mimi will choose a single contiguous section of crayon boxes to give to the children. In order to be fair, she also wants the total number of crayons in the subarray she chooses to be divisible by \(M\) so that it can be split equally. How many ways can she do this?</p>
<h4>Constraints</h4>
<p>For all subtasks, \(1 \le c_i \le 10^9\).</p>
<h5>S...Wed, 11 Oct 2017 17:00:11 +0000https://dmoj.ca/problem/dmopc17c1p2DMOPC '17 Contest 1 P1 - Fujō Nekohttps://dmoj.ca/problem/dmopc17c1p1<div><p><!--needs more neko-->
Saki is walking around the school fields when she notices that <em>something</em> might be stalking her. As such, she stops at \(Q\) locations on the field, with the \(i^\text{th}\) being \((x_i,y_i)\) and takes a look directly in all 4 cardinal directions (north, south, east, and west) to see if she can locate these mysterious being<strong>s</strong>. Saki's vision is quite good, so even if the being is far away, as long as she's looking in the right direction, sh...Wed, 11 Oct 2017 16:50:24 +0000https://dmoj.ca/problem/dmopc17c1p1Computer Sciencehttps://dmoj.ca/problem/waterloof2017c<div><h5>2017 Fall Waterloo Local ACM Contest, Problem C</h5>
<p>Vera has \(N\) integers \(a_1, \dots , a_N\). A <em>margin</em> is a non-negative integer \(L\) such that it is possible to choose \(N\) integers \(x_1, \dots , x_N\) such that for all \(i\), \(1 \le i \le N\), the interval \([x_i, x_i + L]\) contains at least \(K\) of Vera's integers and also contains \(a_i\).</p>
<p>Compute the minimum possible margin.</p>
<h4>Input</h4>
<p>Line \(1\) contains integers \(N\) and \(K\) \((1 \le K ...Mon, 09 Oct 2017 20:45:00 +0000https://dmoj.ca/problem/waterloof2017cIOI '13 P2 - Art Classhttps://dmoj.ca/problem/ioi13p2<html><head>
<style>
.img-arr tr td img {
height: 125px;
}</style></head><body><p>You have an Art History exam approaching, but you have been paying more attention to informatics at school than to your art classes! You will need to write a program to take the exam for you.</p>
<p>The exam will consist of several paintings. Each painting is an example of one of four distinctive styles, numbered \(1, 2, 3\) and \(4\).</p>
<p>Style \(1\) contains neoplastic modern art. For example:</p>
<table cla...Mon, 09 Oct 2017 02:41:57 +0000https://dmoj.ca/problem/ioi13p2