Recently Added DMOJ Problemshttps://dmoj.ca/The latest problems added on the DMOJ: Modern Online Judge websiteenMon, 14 Oct 2019 17:19:52 +0000Bohemian Rhaksodyhttps://dmoj.ca/problem/bohemianrhaksody<div><p><em>MolaMola</em> is a world-famous rock band composed of three members: Guitarist Sangsoo <em>cki86201</em> Park famous for his amazing performance with Link-cut tree, drummer Sunggwan <em>dotorya</em> Park who plays 5 problems in 10 minutes without single WA, and the vocalist Bumsoo <em>zlzmsrhak</em> Park who is responsible for the impressive outlook of the band. The movie about their story, <em>Bohemian Rhaksody</em>, became a blockbuster in Korea, and they are preparing for their pe...Mon, 14 Oct 2019 17:19:52 +0000https://dmoj.ca/problem/bohemianrhaksodyIcebergshttps://dmoj.ca/problem/icebergs<div><p>As the navigator of the newly christened RMS Titanic II, you've been commissioned to plot the ship's course through the ocean, represented by an \(R\) by \(C\) grid. Keeping with the tradition of the biggest and best, the Titanic II is a large ship, with length \(L\) and width \(W\) \((1 \le L \le R, 1 \le W \le C)\). Not wanting awful newspaper headlines again, you decide that this time, you will do your best to avoid icebergs, which are represented by the character <code>#</code>. The ...Sat, 12 Oct 2019 01:26:03 +0000https://dmoj.ca/problem/icebergsBOI 2013 P5 - Tracks in the Snowhttps://dmoj.ca/problem/boi2013p5<div><p>There is a rectangular meadow in a forest, having been covered with a blanket of fresh snow in the
morning (left in the figure below).</p>
<p>Rabbits and foxes, who live in the forest, are crossing the meadow and leave their tracks in the snow.
They always enter in the upper left corner and leave the meadow from the lower right corner. In
between they can move back and forth, playing in the snow, even crossing their own tracks. At any
time there is at most one animal on the meadow. No an...Thu, 26 Sep 2019 23:36:42 +0000https://dmoj.ca/problem/boi2013p5BOI 2013 P2 - Palindrome-Free Numbershttps://dmoj.ca/problem/boi2013p2<div><p>A string is a palindrome if it remains the same when it is read backwards. A number is palindromefree if it does not contain a palindrome with a length greater than \(1\) as a substring. For example, the
number \(16276\) is palindrome-free whereas the number \(17276\) is not because it contains the palindrome
\(727\).</p>
<p>Your task is to calculate the total number of palindrome-free numbers in a given range.</p>
<h4>Input</h4>
<p>The input contains two integers, \(a\) and \(b\).</p>
<...Tue, 24 Sep 2019 21:19:26 +0000https://dmoj.ca/problem/boi2013p2APIO '17 P1 - Land of the Rainbow Goldhttps://dmoj.ca/problem/apio17p1<div><p>A long long time ago, in the Dreamtime, Australia was a flat grid of \(R\) rows and \(C\) columns and each grid cell was <em>land</em>. The rows were numbered \(1\) to \(R\) from North to South, and the columns were numbered \(1\) to \(C\) from West to East. The cell in row \(r\) and column \(c\) was denoted as \((r,c)\). One day, the great rainbow serpent rose from the earth at \((s_r,s_c)\), and moved across Australia, creating rivers wherever it slid. The serpent made \(M\) consecutiv...Tue, 24 Sep 2019 19:41:06 +0000https://dmoj.ca/problem/apio17p1BOI 2013 P6 - Vimhttps://dmoj.ca/problem/boi2013p6<div><p>Ernest Vincent Wright was an American author, known for writing a novel (Gadsby) without using
the letter <code>e</code>. Victor is a big fan of Ernest and tries to imitate him in writing a novel, but is looking
for a real challenge. He uses only the first ten characters of the alphabet (namely <code>abcdefghij</code>).
Ironically, the <code>e</code> key on his computer breaks halfway through the novel, and for consistency, he
decides to delete all the <code>e</code>s he has already writ...Tue, 24 Sep 2019 16:31:16 +0000https://dmoj.ca/problem/boi2013p6APIO '08 P3 - DNAhttps://dmoj.ca/problem/apio08p3<div><p>One interesting use of computer is to analyze biological data such as DNA sequences. Biologically,
a strand of DNA is a chain of nucleotides Adenine, Cytosine, Guanine, and Thymine. The four
nucleotides are represented by characters <code>A</code>, <code>C</code>, <code>G</code>, and <code>T</code>, respectively. Thus, a strand of DNA can be
represented by a string of these four characters. We call such a string a DNA <em>sequence</em>.</p>
<p>It is possible that the biologists cannot de...Sun, 22 Sep 2019 21:49:33 +0000https://dmoj.ca/problem/apio08p3COCI '18 Contest 2 #5 Sunčanjehttps://dmoj.ca/problem/coci18c2p5<div><p>Little Slavko dreamed of an unusual dream. One sunny morning, \(N\) white rectangles climbed one by
one on the rectangular roof of Slavko's house. They were preparing for an exotic trip to Hawaii -
sunbathing. Each rectangle chose a place on the roof and lay in such a way that its sides were
parallel to the edges of the roof. It is possible that some rectangles overlapped parts of other
rectangles that have previously lain down on Slavko's roof. For each rectangle its length \(A_i\), hei...Sun, 22 Sep 2019 03:27:31 +0000https://dmoj.ca/problem/coci18c2p5IOI '19 P6 - Sky Walkinghttps://dmoj.ca/problem/ioi19p6<div><p>Kenan drew a plan of the buildings and skywalks along one side of the main avenue of
Baku. There are \(n\) buildings numbered from \(0\) to \(n-1\) and \(m\) skywalks numbered from
\(0\) to \(m-1\). The plan is drawn on a two-dimensional plane, where the buildings and
skywalks are vertical and horizontal segments respectively.</p>
<p>The bottom of building \(i\) \((0 \le i \le n-1)\) is located at point \((x[i],0)\) and the building has
height \(h[i]\). Hence, it is a segment connecting ...Sun, 22 Sep 2019 01:44:35 +0000https://dmoj.ca/problem/ioi19p6BOI 2006 P2 - Coin Collectorhttps://dmoj.ca/problem/boi2006p2<div><p>In a certain country, there are \(N\) denominations of coins in circulation, including the
\(1\)-cent coin. Additionally, there’s a bill whose value of \(K\) cents is known to exceed
any of the coins. There's a coin collector who wants to collect a specimen of each
denomination of coins. He already has a few coins at home, but currently he only
carries one \(K\)-cent bill in his wallet. He’s in a shop where there are items sold at all
prices less than \(K\) cents (\(1\) cent, \(2\) cents...Sat, 21 Sep 2019 21:32:38 +0000https://dmoj.ca/problem/boi2006p2BOI 2006 P1 - Bitwise Expressionshttps://dmoj.ca/problem/boi2006p1<div><p>In signal processing, one is sometimes interested in the maximum value of a certain
expression, containing bitwise AND and OR operators, when the variables are
integers in certain ranges. You are to write a program that takes such an expression
and the range of each variable as input and determines the maximum value that the
expression can take.</p>
<p>For simplicity, the expression is of a specific form, namely a number of
subexpressions in parentheses separated by the bitwise AND opera...Sat, 21 Sep 2019 21:10:33 +0000https://dmoj.ca/problem/boi2006p1Castle Invasionhttps://dmoj.ca/problem/casinv<div><p>Bob is planning an attack on a suspicious castle owned by the evil villain Joe! The castle can be thought of as an \(N\) by \(N\) grid of towers, with each tower having an integer height. To scout for this attack, Bob sent his only drone that can instantly transmit pictures to take photos of the castle. However, the drone only managed to take 2 photos before critically running out of battery and tumbling into the forest. One photo was taken of the front side of the castle, while the othe...Thu, 19 Sep 2019 00:44:40 +0000https://dmoj.ca/problem/casinvOverflowhttps://dmoj.ca/problem/olep1<div><p>Joe is an economical man and he has found a new scheme to save some money! Joe wants to save money on his water bill, so he decides to collect rainwater. Joe has a row of \(N\) water containers, all initially empty and each with a maximum capacity of \(v_i\) liters of water. The containers are connected in such a way that when container \(i\) overflows, the excess liquid flows to container \(i+1\). When container \(N\) overflows, the extra water magically disappears. Joe wishes to gather...Tue, 17 Sep 2019 22:40:40 +0000https://dmoj.ca/problem/olep1Back To School '19: FFT Funhttps://dmoj.ca/problem/bts19p7<div><p>Winnie has a small list \(v\) of integers consisting of \(2\) primes, \(X\) and \(Y\). Winnie wants to make the list larger, so Winnie will take two indices \(i\) and \(j\ (1 \le i \lt j \le |v|)\) in the list and add \(v_i \times v_j\) to the end of the list. She does this operation \(N\) times. After the first time, she cannot choose two indices that have been multiplied together before. That is, the pair \((i, j)\) must not have been used before. In addition, she will always take the ...Tue, 10 Sep 2019 19:44:09 +0000https://dmoj.ca/problem/bts19p7Back To School '19: Beautiful_Times' Fruit Scamhttps://dmoj.ca/problem/bts19p8<div><p>You are going to the farmers market to buy and sell fruit. There are \(N\) farmers markets that each buy and sell \(2\) types of fruit: Apples, and Bananas. Initially, each market will buy and sell each type of fruit at a fixed price decided by its farmer, who will keep these prices forever. Since the farmers are not sure about the prices of the other markets, <strong>they will pick a price uniformly at random for each type of fruit</strong>. Note that apples, and bananas may have differ...Tue, 10 Sep 2019 19:43:57 +0000https://dmoj.ca/problem/bts19p8Back To School '19: Unstable Bookshttps://dmoj.ca/problem/bts19p6<div><p>Andy is getting bored in English class, and so he decides to pull out his laptop and start playing his favourite game!</p>
<p>In this game, Andy controls a stationary robot that stands in the center of a line of \(N\) books. Each book has a unique integer height between \(1\) and \(N\) (that is, the heights of the books form a permutation of the integers from \(1\) to \(N\)). The robot has \(2\) arms that can only extend outward perpendicular to the robot's body to any length. These arms...Tue, 10 Sep 2019 19:43:42 +0000https://dmoj.ca/problem/bts19p6Back To School '19: Heist Nighthttps://dmoj.ca/problem/bts19p5<div><p>The famous thief Matthew is robbing a jewellery store and has his hands on \(N\) jewels numbered from \(1\) to \(N\). These jewels have all been attached together into one heavy clump of \(N\) jewels with \(N - 1\) titanium wires to prevent anyone from stealing them all at once.</p>
<p>Fortunately, the thief has a specialized device that lets him separate exactly one jewel from the rest by cutting the connected wires. Through this process, the thief will split the heavy clump of jewels i...Tue, 10 Sep 2019 19:42:43 +0000https://dmoj.ca/problem/bts19p5Back To School '19: A Circular Gamehttps://dmoj.ca/problem/bts19p4<div><p>At Zeyu's school, a certain circle game has been getting all the craze lately.</p>
<p>The game consists of \(N\) identical circular spinners, each containing \(M\) equally-sized sectors labelled in order from \(1\) to \(M\).
A small arrow at the top of the spinner points to one of the \(M\) sectors to represent the sector it is currently on.</p>
<p>In this game, two players race each other to set all \(N\) spinners to point to the same number.
They do so by picking a spinner and change t...Tue, 10 Sep 2019 19:42:32 +0000https://dmoj.ca/problem/bts19p4Back To School '19: Chemistryhttps://dmoj.ca/problem/bts19p3<div><p>Dereck is in chemistry class!</p>
<p>For Dereck's first lab in chemistry, he is told to create a solution. Little does he know, he is actually creating hydrogen cyanide, a deadly (colourless) poison! Unfortunately for him, after creating the solution, he wasn't keeping track of which beaker it was in, and the beaker got mixed with the \(N-1\) other beakers containing distilled water (which is harmless). Now, he must find which beaker contains the poison so that he can properly dispose of...Tue, 10 Sep 2019 19:42:20 +0000https://dmoj.ca/problem/bts19p3Back To School '19: Parkourhttps://dmoj.ca/problem/bts19p2<div><p>Wesley is running late to school!</p>
<p>The neighbourhood is modelled as a coordinate plane, and Wesley's house is currently sitting at \((0, 0)\).
The school is a rectangle of dimensions \(H\) metres horizontally and \(V\) metres vertically. Its bottom left corner is situated at \((X, Y)\), but there are entrances located at any point of the school. Formally, there are entrances located at all points \((x_i, y_i)\) such that \(X \le x_i \lt X+H\) <strong>and</strong> \(Y \le y_i \lt Y+...Tue, 10 Sep 2019 19:42:15 +0000https://dmoj.ca/problem/bts19p2Back To School '19: H🅰️r🅰️mbehttps://dmoj.ca/problem/bts19p1<div><p>Emily is writing an English essay. She wants to make her essay sound more attractive, so she decides to replace some words with other words. However, she has already hit her character limit on her essay <strong>exactly</strong>, so the word she will replace with must be less than or equal to the length of the word that she replaces. Because Emily is a [wannabe] perfectionist, she wants her essay to be as close to the character limit as possible by <em>choosing a word that is as close to ...Tue, 10 Sep 2019 19:40:43 +0000https://dmoj.ca/problem/bts19p1DMOPC '19 Contest 1 P3 - Simple Mathhttps://dmoj.ca/problem/dmopc19c1p3<div><p>In math class, Bob is currently studying systems of linear equations. Being bored of his teacher's lectures, he decides to make a problem for himself. In his problem, he is trying to solve for the \(N\) variables, \(x_1,x_2,\ldots,x_N\). He then writes \(M\) equations, the \(i\)-th of which being the equation \(x_{a_i}+x_{b_i}=c_i\) where \(a_i\neq b_i\). Believing that simply finding a solution to this problem would be too easy, he instead wants to find how many solutions of \((x_1,x_2,...Fri, 06 Sep 2019 18:52:22 +0000https://dmoj.ca/problem/dmopc19c1p3DMOPC '19 Contest 1 P5 - Broken Stringhttps://dmoj.ca/problem/dmopc19c1p5<div><p>During class, Bob's teacher wanted to try an interesting activity. He began by writing down a string of length \(N+K-1\) containing only lower-case English letters, where \(N\) is the number of students. Afterwards, he writes down each of the \(N\) substrings of length \(K\), and gives one to each student. Bob and the rest of the class now need to find out what the original string could have been, or if the teacher has made a mistake.</p>
<h4>Constraints</h4>
<p>In all subtasks,<br>
\(1 ...Fri, 06 Sep 2019 18:47:13 +0000https://dmoj.ca/problem/dmopc19c1p5DMOPC '19 Contest 1 P2 - Good Writinghttps://dmoj.ca/problem/dmopc19c1p2<div><p>A teacher once said: "Good writing is good writing is good writing."<br>
Hence, the teacher defines \(f_0 =\) "Good writing is good writing is good writing."<br>
To make the quote more interesting the teacher defines \(f_n =\) "Good writing is good " +\(f_{n-1}\)+ " writing is good " \(+ f_{n-1} +\) " is good writing." for all \(n \ge 1\)</p>
<p>For example, \(f_1\) is</p>
<pre><code>Good writing is good Good writing is good writing is good writing. writing is good Good writing is good ...Thu, 05 Sep 2019 23:59:33 +0000https://dmoj.ca/problem/dmopc19c1p2DMOPC '19 Contest 1 P6 - Bob and Binary Stringshttps://dmoj.ca/problem/dmopc19c1p6<div><p>Bob is playing with binary strings. He defines two strings \(S\) and \(T\) to be similar if at least one of the following conditions holds:</p>
<ol>
<li>\(S\) = \(T\)</li>
<li>The lengths of both \(S\) and \(T\) must be divisible by \(2\). Let \(S_1\) denote the first half of \(S\), and \(S_2\) denote the second half. Similarly, define \(T_1\) and \(T_2\) as the first and second halves of \(T\). Then \(S\) and \(T\) are similar if either:<ul>
<li>\(S_1\) is similar to \(T_1\) and \(S_2\)...Thu, 05 Sep 2019 22:15:06 +0000https://dmoj.ca/problem/dmopc19c1p6