Recently Added DMOJ Problemshttps://dmoj.ca/The latest problems added on the DMOJ: Modern Online Judge websiteenWed, 11 Dec 2019 01:54:58 +0000APIO '08 P2 - Roadshttps://dmoj.ca/problem/apio08p2<div><p>The Kingdom of New Asia contains \(N\) villages connected by \(M\) roads. Some roads are made of
cobblestones, and others are made of concrete. Keeping roads free-of-charge needs a lot of money, and
it seems impossible for the Kingdom to maintain every road. A new road maintaining plan is needed.</p>
<p>The King has decided that the Kingdom will keep as few free roads as possible, but every two
distinct villages must be connected by <em>one and only one</em> path of free roads. Also, alt...Wed, 11 Dec 2019 01:54:58 +0000https://dmoj.ca/problem/apio08p2DMOPC '19 Contest 3 P6 - TSThttps://dmoj.ca/problem/dmopc19c3p6<div><p>Bob is tinkering with self-driving cars! He realizes that for the cars to drive efficiently, they should not use roads that human drivers are using. Bobland consists of \(N\) cities and \(M\) bidirectional edges. Bob proposes that they find a Triple Spanning Tree within the road system of Bobland to fix this problem. A TST consists of three sets of edges \(E_1\), \(E_2\), and \(E_3\) such that \(E_1 \cap E_2 = \varnothing\), \(E_2 \cap E_3 = \varnothing\) and \(E_3 \cap E_1 = \varnothing...Sun, 08 Dec 2019 00:46:23 +0000https://dmoj.ca/problem/dmopc19c3p6DMOPC '19 Contest 3 P5 - Festivalhttps://dmoj.ca/problem/dmopc19c3p5<div><p>To prepare for his village's annual festival, Rexzae plans on putting on a display of fireworks. According to the village's spiritual beliefs, each firework is associated with a particular number, which they call its "colour". Currently, he has already set up \(N\) of these fireworks, the \(i\)th of which has "colour" \(c_i\). In the following \(Q\) minutes, one of three events may occur. On the \(j\)th minute, Rexzae may add a new firework that has colour \(d_j\), he may decide to adjus...Sun, 08 Dec 2019 00:46:11 +0000https://dmoj.ca/problem/dmopc19c3p5DMOPC '19 Contest 3 P4 - Same Colour Leaveshttps://dmoj.ca/problem/dmopc19c3p4<div><p>Reina is interested in colourful trees. In particular, she currently has her eyes on a tree with \(N\) nodes, each coloured either red or blue. By definition, this tree has \(N-1\) edges, the \(i\)th of which connecting nodes \(u_i\) and \(v_i\). Looking at this tree, Reina wonders, "how many <strong>connected</strong> vertex-induced subgraphs of this tree form trees where all its leaves are the same colour?" Being unable to solve this problem, she has come to you for help. Since the ans...Sun, 08 Dec 2019 00:46:01 +0000https://dmoj.ca/problem/dmopc19c3p4DMOPC '19 Contest 3 P3 - Majorityhttps://dmoj.ca/problem/dmopc19c3p3<div><p>In preparation for an upcoming election, Najya has polled \(N\) of her friends on whether they decide on voting for candidate \(1\) or candidate \(2\). In her poll, she learned that the \(i\)th friend is a supporter of candidate \(v_i\). Being a supporter of candidate \(1\), she wants to know how many ways she can remove any number of people (possibly none) from the beginning and then remove any number of people (possibly none) end of her list such that a <strong>majority</strong> of he...Sun, 08 Dec 2019 00:45:51 +0000https://dmoj.ca/problem/dmopc19c3p3DMOPC '19 Contest 3 P2 - Generating Nameshttps://dmoj.ca/problem/dmopc19c3p2<div><p>Veshy is trying to come up with a username for his new alt-account! Unfortunately, he is currently in a creative lull, so he has turned to permutating strings of lowercase letters of length \(N\) to find a username. This was still not creative enough for Veshy, so he is currently trying to increase the number of potential candidate usernames by having \(K\) wildcard characters (<code>*</code>) in his starting string before permutating. Since you are Veshy's absolute best friend, help him...Sun, 08 Dec 2019 00:45:36 +0000https://dmoj.ca/problem/dmopc19c3p2DMOPC '19 Contest 3 P1 - Mode Findinghttps://dmoj.ca/problem/dmopc19c3p1<div><p>You are given \(N\) numbers, \(a_1, a_2, \ldots , a_N\). Output all the modes of this list on a single line from least to greatest. The mode of a list is/are the value(s) that appear(s) the most times relative to the other values in the list. It is guaranteed that at least one mode exists.</p>
<h4>Constraints</h4>
<p>In all tests,<br>
\(1 \le N \le 10^6\)<br>
\(-10^5 \le a_i \le 10^5\)</p>
<h4>Input Specifications</h4>
<p>The first line contains one number, \(N\).<br>
The second line con...Sun, 08 Dec 2019 00:45:22 +0000https://dmoj.ca/problem/dmopc19c3p1DMOPC '19 Contest 3 P0 - What is it?https://dmoj.ca/problem/dmopc19c3p0<div><p>Veshy needs help in math class. He has \(N\) sequences of 10 spaced terms in order of \(a_1, a_2, a_3, ..., a_{10}\). For each sequence he wants to know if it is arithmetic, geometric, or neither. Output the the answer to the \(i^{th}\) sequence on the \(i^{th}\) line. Terms are guaranteed to be integers.</p>
<p>Note:<br>
A arithmetic sequence is a sequence such that it can be written in the form: \(a, a+d, a+2d, a+3d, ... \) where \(a\) and \(d\) are constants.<br>
A geometric sequence ...Sun, 08 Dec 2019 00:44:52 +0000https://dmoj.ca/problem/dmopc19c3p0Wesley++https://dmoj.ca/problem/wesleyplusplus<div><p>Wesley's template has everything, except for good support for interactive problems and fast arbitrary precision integer arithmetic. For now.</p>
<p>Wesley is playing a game against Lesley. They are both standing in front of a pile of \(N\) pebbles and will alternate turns. On a person's turn, they may take \(2^X\)
pebbles from the pile for some nonnegative integer \(X\). The person who takes the last pebble from the pile wins. Wesley gets to choose whether he goes first or second.
Help W...Thu, 05 Dec 2019 04:22:19 +0000https://dmoj.ca/problem/wesleyplusplusCOCI '19 Contest 2 #5 Zvijezdahttps://dmoj.ca/problem/coci19c2p5<div><p>Mirko and Slavko are spending their free time playing with polygons and watching a new season of <em>The
Biggest Loser</em>. Mirko recently drew a convex polygon with an even number of vertices \(N\). Slavko then
considered each pair of oposite sides (two sides are opposite if there are \(\frac{N}
{2} − 1\) sides between them), drew
straight lines that lie on those sides and colored them along with the part of the plane that lies between
them and contains the polygon. Finally, Mirko foun...Tue, 03 Dec 2019 00:20:05 +0000https://dmoj.ca/problem/coci19c2p5COCI '18 Contest 6 #4 Simfonijahttps://dmoj.ca/problem/coci18c6p4<div><p>Almost no one believed in the virtuous abilities of the composer Marin. Specifically, not until the day
he composed his 9th symphony.</p>
<p>The symphony can be represented as a series of frequencies that are integer numbers. In order for
Marin to prove his talent and demonstrate that this symphony is not just one of many, he decided to
compare it with the ancient symphony "Little Night Fiesta" of the best musician in history, Stjepan. In
the stars it is written that the lengths of these...Thu, 28 Nov 2019 01:50:37 +0000https://dmoj.ca/problem/coci18c6p4COCI '18 Contest 6 #3 Sličicehttps://dmoj.ca/problem/coci18c6p3<div><p>Nikola is a passionate collector of albums with images of football players. He and his friends compete
with each other in a game they invented based on the albums whose images are currently being
collected. The images in that album are divided into \(N\) teams, each of which has exactly \(M\) football
players. The main rule of the game is that the total number of points a person wins for \(i^{th}\)
team is \(B_x\), where \(x\) is the total number of unique pictures of football players of...Thu, 28 Nov 2019 01:43:17 +0000https://dmoj.ca/problem/coci18c6p3Board Gameshttps://dmoj.ca/problem/boardgames<div><p>Soupy boy is playing a game! He is currently on the \(N^{th}\) square, and wants to get to the \(M^{th}\) square <strong>exactly</strong>. However, moves in this game are a bit different than your average board game.</p>
<p>Starting from the current square, he can do one of \(4\) things.</p>
<ul>
<li>Go to the \((3 \times N)^{th}\) square.</li>
<li>Go to the \((N-1)^{th}\) square.</li>
<li>Go to the \((N-3)^{th}\) square.</li>
<li>Go to the \((\dfrac{N}{2})^{th}\) square if the current s...Tue, 05 Nov 2019 01:15:31 +0000https://dmoj.ca/problem/boardgamesMagic Mazehttps://dmoj.ca/problem/magicmaze<div><p>Naofumi is exploring a magical maze! The maze is a 2D array with \(N \times N\) pillars. The height of each pillar is generated using two arrays \(R\) and \(C\), each of size \(N\). Specifically, the height of the pillar at row \(i\) and column \(j\), pillar \((i, j)\), would be \(R_i \times C_j\). A path in this maze is defined as a sequence of pillars where every successive pillar is below or to the right of the previous pillar (i.e. only moving down or to the right). A valid path is d...Mon, 04 Nov 2019 03:44:05 +0000https://dmoj.ca/problem/magicmazeRectangle Countinghttps://dmoj.ca/problem/rectanglecounting<div><p>In the sport of rectangle counting, participants are given a set of \(N\) rectangles and race to count the number of intersecting pairs. In order to check the answer, judges are called in to verify that the number of pairs counted by each contestant is correct.</p>
<p>The other day, Angie was invited to judge one of the competitions and now has to produce the correct answer for today's set of \(N\) rectangles. Her schedule is very busy so she doesn't have the time to do all the calcula...Mon, 04 Nov 2019 02:46:35 +0000https://dmoj.ca/problem/rectanglecountingAngie and Functionshttps://dmoj.ca/problem/angieandfunctions<div><p>Angie is studying functions!</p>
<p>For her homework, she was asked to figure out the coefficients \(c_1, c_2, ..., c_N, c_{N+1}\) in the following function:</p>
<blockquote><p>\(f(x)=c_1x^N+c_2x^{N-1}+...+c_Nx+c_{N+1}\) (All the coefficients are integers)</p>
</blockquote>
<p>To assist her on this question, her math teacher has allowed her to ask queries in the following form:</p>
<blockquote><p>Given an integer \(x\), what is \(f(x)\)?</p>
</blockquote>
<p>However, as he doesn't want t...Mon, 04 Nov 2019 02:46:20 +0000https://dmoj.ca/problem/angieandfunctionsBig Depositshttps://dmoj.ca/problem/bdep<div><p>Kazuma is depositing money! Every year, Kazuma puts \(N\) coins into his bank account. At the end of each year, Kazuma's investments will grow by \(P\) percent, rounded down to the nearest coin. After \(Y\) years, he would like to have at least \(T\) coins in his bank account so that he can buy some presents for a special someone. Since Kazuma is an efficient individual, he would like to know the minimum number of coins he has to put into his bank account every year so that he will have ...Sun, 03 Nov 2019 19:34:12 +0000https://dmoj.ca/problem/bdepWesley's Anger Contest 2 Problem 6 - Haunted Houseshttps://dmoj.ca/problem/wac2p6<div><p>Halloween has finally arrived and the ghosts on your street have decided to volunteer at your local haunted houses. Each of the \(N\) ghosts (numbered from \(1\) to \(N\)) will volunteer at <strong>exactly one of the \(5\) haunted houses</strong> and perform their prepared routine. The \(i^{th}\) ghost will perform \(k_i\) <strong>unique</strong> moves in their routine, with the \(k_i\) moves each being one of \(4\) types of moves:</p>
<ul>
<li>spook</li>
<li>hide</li>
<li>creep</li>
<li...Sun, 03 Nov 2019 04:00:00 +0000https://dmoj.ca/problem/wac2p6Wesley's Anger Contest 2 Problem 5 - Oober Treatshttps://dmoj.ca/problem/wac2p5<div><p>After years of deliberation, you have finally decided to get a job for the fast growing startup called Oober Treats! Oober Treats has decided that rather than having children running around streets on Halloween, the candy will instead be delivered right to their door!</p>
<p>On Halloween night, you will drive a delivery truck that has \(F\) units of fuel, and will have \(N\) different candy delivery routes to choose from. Each route takes \(f_i\) units of fuel and allows you to earn cash...Sun, 03 Nov 2019 04:00:00 +0000https://dmoj.ca/problem/wac2p5Wesley's Anger Contest 2 Problem 4 - The Ninth Triangle of the Underworldhttps://dmoj.ca/problem/wac2p4<div><p>At your neighbourhood Halloween party, appropriately named <code>The Ninth Triangle of the Underworld</code>, you've decided to play a fun game! Two witch hats are placed on conveyor belts moving in opposite directions. For simplicity, we can imagine the witch hats as triangles, with their bases on the same line parallel to the \(x\)-axis, and that the witch hats will continue moving in opposite directions for eternity.</p>
<p><img src="https://dmoj.algome.me/media/martor/f3b6c055-13fb-4...Sun, 03 Nov 2019 04:00:00 +0000https://dmoj.ca/problem/wac2p4Wesley's Anger Contest 2 Problem 3 - Pumpkin Countinghttps://dmoj.ca/problem/wac2p3<div><p><strong>For this question, Python users are recommended to use PYPY over CPython.</strong></p>
<p>To celebrate Halloween, you have decided to hold an art contest! A drawing is a grid of pixels with \(N\) rows and \(2N\) columns, composed of only <code>#</code> and <code>.</code> characters. <code>#</code> can be thought of as a black pixel, and <code>.</code> can be thought of as a white pixel. <strong>It is guaranteed that the drawing will be framed with a single layer of black pixels.<...Sun, 03 Nov 2019 04:00:00 +0000https://dmoj.ca/problem/wac2p3Wesley's Anger Contest 2 Problem 2 - Costume Shoppinghttps://dmoj.ca/problem/wac2p2<div><p>With Halloween coming up in \(N\) days, you realized that you need to buy costumes! Specifically, you want to buy \(M\) different costumes <strong>before Halloween</strong> so that you have multiple options to choose from on Halloween. Thankfully there is a store nearby that allows you to <strong>buy at most one costume a day</strong>, however the price of the costume keeps changing. Initially, the costumes will cost \($1\,000\,000\), however over the course of \(N\) days, they will chan...Sun, 03 Nov 2019 04:00:00 +0000https://dmoj.ca/problem/wac2p2Wesley's Anger Contest 2 Problem 1 - OCT 31 = DEC 25?https://dmoj.ca/problem/wac2p1<div><p>Halloween is coming up soon! Unfortunately you forgot what day of the week it is on. Thankfully, [user:Pookmeister] has remembered the day of the week that Christmas is on, and knowing that OCT 31 = DEC 25, believes this information is more than enough to help you out.</p>
<p>Given the day of the week the Christmas is on, determine the day that Halloween is on.</p>
<p>Recall that Halloween is on October 31 and Christmas is on December 25 based on the <a href="https://en.wikipedia.org/wik...Sun, 03 Nov 2019 04:00:00 +0000https://dmoj.ca/problem/wac2p1Brazilian IOI TST '19 Day 1 - Secret Santahttps://dmoj.ca/problem/braziloi19p2<div><p>The company where Arthur works organizes a secret Santa every year, and unfortunately, he is responsible for organizing the game this year. In this game, every person has to send a gift to someone previously chosen at random, and in the day of the gifts exchange, when person \(A\) sends a gift to person \(B\), \(B\) is the next person to send a gift (in case \(B\) hasn't sent it yet). When the next person to send a gift isn't defined (at the start of the game, for example), this person i...Thu, 24 Oct 2019 22:44:35 +0000https://dmoj.ca/problem/braziloi19p2Fast Factorial Calculator 3https://dmoj.ca/problem/factorial3<div><p>ho94949 is in a good mood today. He discovered a secret method to compute large factorials very quickly. Can you beat him?</p>
<h4>Input Specification</h4>
<p>The first and only line of integer contains two positive integers, \(N\) and \(P\).</p>
<p>You may assume \(1 \le N < P \le 10^{10}\), and that \(P\) is prime.</p>
<h4>Output Specification</h4>
<p>Print \(N! \pmod{P}\).</p>
<h4>Sample Input</h4>
<pre><code>9999999966 9999999967</code></pre>
<h4>Sample Output</h4>
<pre><code>99...Tue, 22 Oct 2019 21:53:56 +0000https://dmoj.ca/problem/factorial3