Recently Added MOI Arena Problemshttps://arena.moi/The latest problems added on the MOI Arena: MOI Online Judge websiteen-caSun, 09 May 2021 09:19:32 +0000Walk in the parkhttps://arena.moi/problem/magoi21walkinthepark<p>During the pandemic, the most exciting outdoor activity one can do is walk around the local park, alone. All this alone-time inspired you to wonder about the following problem.</p>
<p>The park has \(n\) interesting locations numbered from \(1\) to \(n\). You can move between any two locations only if there is a trail between them. The structure of the park is a <strong>connected undirected graph</strong>. The number of steps needed to move from location \(i\) to an adjacent location \(j\) is ...Sun, 09 May 2021 09:19:32 +0000https://arena.moi/problem/magoi21walkintheparkBookingshttps://arena.moi/problem/magoi21bookings<p><em>This problem is interactive.</em></p>
<p>Covid is finally over and you can now go to gym ! To avoid crowding and thus prevent another wave of covid, the administration decided to set up a booking system.</p>
<p>The gym will be open for \(M\) units of time each day. To use any machine a member should make a reservation. A reservation \(i\) has a start time \(s_i\) and a duration \(d_i\) (\(0 \leq s_i < s_i + d_i \leq M\)). Reservations may arbitrarily overlap with one another, and are n...Sun, 09 May 2021 09:19:32 +0000https://arena.moi/problem/magoi21bookingsAzza and palindromeshttps://arena.moi/problem/magoi21azzaandpalind<p>A palindrome is any sequence of characters which reads the same backward as forward. Azza, Aya, Ala are all palindromes.</p>
<p>Azza likes very much inventing algorithmic puzzles to solve them in her free time. She created the following problem recently :</p>
<p>Let's call a partition of a string \(s\) a set of disjoint substrings of \(s\) \(a_i\) that when joined together form \(s\). \(s = \sum a_i \) for \( i \in [1,n]\). We'll call each string \(a_i\) a fragment and \(n\) the size of the p...Sun, 09 May 2021 09:19:32 +0000https://arena.moi/problem/magoi21azzaandpalindFile d'attentehttps://arena.moi/problem/magj21filedattente<p>\(N\) personnes font la queue devant une salle pour assister à une conférence. Ils ont chacun un identifiant qui correspond à un entier entre 1 et \(10^5\).</p>
<p>Deux personnes peuvent faire connaissance s'ils ont le même identifiant et si l'écart entre leurs positions dans la queue ne dépasse pas \(K\) \((1 \leq K < N)\).</p>
<p>Nous aimerions connaître l'identifiant le plus petit des personnes qui peuvent faire connaissance dans la queue. si aucun identifiant ne remplit les conditions,...Sun, 09 May 2021 04:16:15 +0000https://arena.moi/problem/magj21filedattenteBMXhttps://arena.moi/problem/magj21bmx<p>Le BMX freestyle est une discipline (passionnante) du BMX qui peut être paratiquée dans les rues, parcs ou sur piste. Le pricipe est de réaliser avec un vélo BMX des acrobaties qu'on appelle des figures. Daniel Dhers est l'un des meilleurs riders BMX, il a emporté les plus grandes compétitions du bmx freestyle.</p>
<p>Aujourd'hui Daniel Dhers participe au FISE, la plus grande compétition de sport
freestyle. Il est le dernier rider à jouer. On se donne l'objectif de savoir si Daniel pourra gag...Sun, 09 May 2021 04:16:15 +0000https://arena.moi/problem/magj21bmxLes multiples de 7https://arena.moi/problem/magj21lesmultiplesde<p>Karim et Sarah sont en train de jouer. Ils ont une sequence d'entiers positifs, et ils veulent trouver la sequence la plus longue de nombres consécutifs dont la somme est un multiple de 7.</p>
<h4>Input Specification</h4>
<p>La première ligne d'entrée contient N (1<= N <= 50,000), le nombre d'entiers.</p>
<p>Les N lignes suivantes contiennent chacune un entier entre 0 et 1,000,000.</p>
<h4>Output Specification</h4>
<p>La sortie est un seul entier représentant la longueur maximale possi...Sun, 09 May 2021 04:16:15 +0000https://arena.moi/problem/magj21lesmultiplesdeWelcome to MOI 2021!https://arena.moi/problem/moi21qualwelcometomo<p>The Moroccan Olympiad in Informatics is a great way to develop important problem-solving skills. Students who take part in the competition quickly become good at dealing with problems that involve thorough logical reasoning, algorithmic thinking, efficiency, and optimization.</p>
<p>With this in mind, MOI contestants are therefore sometimes invited to compete in other programming contests in teams of up to three students. Your task is to help make these teams.</p>
<p>Given the number of MOI c...Fri, 25 Dec 2020 21:45:39 +0000https://arena.moi/problem/moi21qualwelcometomoEasy splittinghttps://arena.moi/problem/1yeasysplitting<p>For future Arena rounds we're discussing the possibility to add solutions hacking to contests : each contestant will be assigned to exactly one room where they can see solutions of every other contestant in that room, the sum of ratings of contestants in a room cannot exceed \(M\).</p>
<p>We want you to write the algorithm that distributes contestants to rooms : You will given a list of \(n\) positive integers \(a_1,...,a_n\) denoting the ratings of contestants, arranged in a circle (\(a_n\) ...Sat, 12 Dec 2020 17:21:12 +0000https://arena.moi/problem/1yeasysplittingXor Sorthttps://arena.moi/problem/1yxorsort<p>It's been one year since the first arena contest! In a year we hosted many rated contests and we look forward to hosting more frequent contests in the future.</p>
<p>After each rated contest, participants' ratings change. Your tasks is to write a new rating algorithm.</p>
<p>You will be given an array \(a\) of \(n\) integers, where \(a_i\) represents the rating of the \(ith\) contestant, from the bottom of the standing (contestant \(1\) was the last one). Your objective is to make this array ...Sat, 12 Dec 2020 17:21:12 +0000https://arena.moi/problem/1yxorsortContest strategyhttps://arena.moi/problem/1ysalesman<p>"One more contest to retire", this was your motivation to take part in one last contest and live happily ever after in the MOI land.</p>
<p>You're given \(n\) contests in a row to participate in, the \(i\) contest has \(a_i\) problems and when solving one problem in that contest you gain \(b_i\) points. You want to make the <strong>maximum</strong> number of points but <strong>you can't participate in 4 successive contests</strong>.</p>
<p>In other words, if you participated in the \(i\), \(i...Sat, 12 Dec 2020 17:21:12 +0000https://arena.moi/problem/1ysalesmanOmar and Circleshttps://arena.moi/problem/1yomarandcircles<p>Omar really liked circles and was very disappointed when he learned that even after one year, there was no problem on Arena about circles so he decided to make his own: he starts by choosing a point \(P\) with coordinates \((a, b)\). He then draws a circle centered at \((0, 0)\) such that \(P\) is on the circle, let's denote the radius of this circle as \(R\). He then draws a second circle centered at \(P\) with a given radius \(C\) (\(C < 2R\)), these two circles intersect in 2 points, he...Sat, 12 Dec 2020 17:21:12 +0000https://arena.moi/problem/1yomarandcirclesLost arrayhttps://arena.moi/problem/round9lostarray<p>In this problem an array \(A\) of \(N\) integers (possibly negative) is hidden from you. We will give you instead an array \(S\) such that \(S_i = \sum_{j = 0}^{k-1} A_{i+j}\). We want you to output the difference between the largest and smallest elements of \(A\).</p>
<p>Because there is a lot of possible answers, we want you to output the one minimizing that difference.</p>
<h4>Input Specification</h4>
<p>The first line of the input file contains one integer \( 1 \leq T \leq 30 \): the numb...Sun, 04 Oct 2020 12:29:51 +0000https://arena.moi/problem/round9lostarrayCall centerhttps://arena.moi/problem/round9callcenter<p>\(M\) people are working in a call center. Each minute, exactly one customer will call for assistance, this is denoted by an array \(A\) of \(N\) elements : customer \(x\) will need assistance each minute \(i\) such as \(A_i = x\).</p>
<p>An employee can give assistance to one customer at a time. Assistance will last for an amount of time strictly less than one minute, after that he can either put the customer on hold and give assistance to another one or keep the line open waiting for anothe...Sun, 04 Oct 2020 12:29:51 +0000https://arena.moi/problem/round9callcenterWood factoryhttps://arena.moi/problem/round9carpentry<p>There are multiple rows of trees in a forest, each row has \(N\) trees numbered from 1 to \(N\), with tree number \(i\) of height \(h_i\).</p>
<p>Each day a wood factory cuts trees from a new row. They chose two trees \(l\) and \(r\) (\(l \leq r\)) from that row and cut all trees \(i\), \(l \leq i \leq r\).</p>
<p>The factory needs trees of different heights each day. They want to know what is the minimum number of trees they will need to cut in order to have at least \(q_i\) trees of each he...Sun, 04 Oct 2020 12:29:50 +0000https://arena.moi/problem/round9carpentryIOI 2017 - Wiringhttps://arena.moi/problem/ioi17wiring<h3>Wiring</h3>
<p>Maryam is an electrical engineer.
She is designing wiring on a communication tower.
On the tower there are some connection points, placed at distinct heights.
A wire can be used to connect any two connection points.
Each connection point can be connected to an arbitrary number of wires.
There are two types of connection points: red and blue.</p>
<p>For the purpose of this problem the tower should be viewed as a line and the connection points
as blue and red points that are at ...Mon, 14 Sep 2020 12:35:39 +0000https://arena.moi/problem/ioi17wiringIOI 2017 - Trainhttps://arena.moi/problem/ioi17train<h3>Toy Train</h3>
<p>Arezou and her brother Borzou are twins.
They have received an amazing toy train set for their birthday, and they used it to build a railway system with \(n\) stations and \(m\) <em>one-way</em> tracks.
The stations are numbered from \(0\) to \(n-1\).
Each track starts at one station and ends at the same or a different station.
There is at least one track starting at each station.</p>
<p>Some stations are <em>charging stations</em>.
Whenever the train arrives at a charging ...Mon, 14 Sep 2020 12:20:32 +0000https://arena.moi/problem/ioi17trainIOI 2017 - Bookshttps://arena.moi/problem/ioi17books<h3>Ancient Books</h3>
<p>The city of Tehran is home to the National Library of Iran.
The main treasure of this library is located in a long hall with a row of \(n\) tables, labeled \(0\) through \(n-1\) from left to right.
On each table there is one ancient handwritten book being displayed.
These books are ordered based on their ages, which makes it hard for the visitors to search for books by title.
So, the library manager has decided to sort the books in alphabetical order of their titles.</p...Mon, 14 Sep 2020 12:16:25 +0000https://arena.moi/problem/ioi17booksTraffic jamshttps://arena.moi/problem/paoitrafficjams<p>You live in a country with \(n\) cities and \(m\) bidirectional roads connecting these cities. The cities are numbered from \(1\) to \(n.\) You are planning to commute by car from
some city \(s\) \((1 \leq s \leq n)\) to some city \(d\) \((1 \leq d \leq n)\).</p>
<p>Some of the roads are called strategic as they are impossible to avoid when going from some city to another. All the paths between both cities necessarily use this road.</p>
<p>During your trip, you want to avoid traffic jams as ...Sat, 29 Aug 2020 04:00:27 +0000https://arena.moi/problem/paoitrafficjamsNinja Race 2https://arena.moi/problem/paoininjarace<p>This year's Ninja Olympiad is taking place in the great forest. There are millions of trees in this forest, \(N\) of them are perfectly aligned and equidistant, they can be seen as \(N\) equidistant line-segments in the 2D plane, parallel to the \(Y\) axis.</p>
<p>Line segment \(i\) have one endpoint at \(Y = 0\) and the other one at \(Y = h_i\). The distance between a successive pair of segments is \(1\).</p>
<p>A ninja will depart from tree \(a_i\) and must reach the tree \(b_i (b_i > a...Sat, 29 Aug 2020 04:00:27 +0000https://arena.moi/problem/paoininjaraceRocket Shipyardhttps://arena.moi/problem/paoirocketshipyard<p>Inspired by the recent progress made in cheap spaceflight, you decide to start up a rocketry company and launch your rockets from the East Coast of Africa, a prime launch site (as it is on the equator and close to the ocean to avoid flying over inhibited areas).</p>
<p>To start your company, you hire \(N\) engineers and task them with \(M\) different tasks to build your rocket. Sadly, the engineers you hired are not good at communicating with each other and easily get overwhelmed with work. W...Sat, 29 Aug 2020 04:00:26 +0000https://arena.moi/problem/paoirocketshipyardNoir et Blanchttps://arena.moi/problem/junior20noiretblanc<p>C'est l'heure du déjeuner pour Sami. Son ami Amine, lui a préparé un jeu difficile à jouer en mangeant.</p>
<p>Amine a un appareil avec n touches consécutives, pour chaque clic sur une touche, il y a deux résultats: soit la touche devient noire ou blanche.</p>
<p>Une partie de jeu peut être considérée comme une séquence de n touches colorées.</p>
<p>pour le jeu, Sami peut effectuer au plus K opérations (éventuellement zéro) sur l'appareil.</p>
<p>Une opération consiste à choisir un intervalle...Sat, 22 Aug 2020 07:14:05 +0000https://arena.moi/problem/junior20noiretblancTournoi de Xiangqihttps://arena.moi/problem/junior20tournoidexia<p>Quand Ya Xi rentre en Chine, la première chose qu'elle fait quand elle rencontre ses copines est d'organiser une partie de Xiangqi (jeu aux échecs chinois).</p>
<p>Le jeu se joue sur un tableau carré de dimensions \(n \times n\), dont les cases sont numérotées de \(1\) à \(n^{2}\). Le premier joueur pose \(k\) pions cylindriques superposés sur une case, le deuxième pose \(2 \times k^{2}\) pions superposés sur une autre case, le troisième \(3 \times k^{3}\) et ainsi de suite jusqu'à ce que to...Sat, 22 Aug 2020 07:14:05 +0000https://arena.moi/problem/junior20tournoidexiaHotelhttps://arena.moi/problem/moi20hotel<p>You are the manager of MOI Hotel.</p>
<p>MOI Hotel is a special hotel that consists of \(N\) rooms numbered from \(1\) to \(N\), guests of this hotel make bookings of contiguous segments of rooms.</p>
<p>You have a list of \(M\) groups of guests such that each group \(i\) wants to book a contiguous segment of rooms starting from room \(L_i\) to room \(R_i\). Depending on the size of the rooms and service quality that a group is requesting, they will pay an amount \(C_i\).</p>
<p>As manager o...Fri, 21 Aug 2020 23:15:00 +0000https://arena.moi/problem/moi20hotelBuilding a roller coasterhttps://arena.moi/problem/moi20buildingaroller<p>MOI entertainment INC. is a global leader in theme parks construction. They want to build the largest roller coaster in the world.</p>
<p>The roller coaster circuit consists of \(N\) vertical columns that support the railways, these columns rise up perpendicular to the floor and have different heights. Each one of the \(N-1\) railway tracks is supported by exactly two columns, two tracks may share at most one column.</p>
<p>For this problem we consider columns and tracks to be infinitely thin...Fri, 21 Aug 2020 23:15:00 +0000https://arena.moi/problem/moi20buildingarollerRunwayhttps://arena.moi/problem/moi20runway<p>You are an air traffic controller at MOI Airport, you are in charge of delivering takeoff and landing clearances to airplanes.</p>
<p>The runway can be seen as an infinitely thin line segment of length L. Airplanes can take-off and land from either sides of the runway (That is, they can start from either \(x = 0\) or \(x = L\)).</p>
<p>Holidays start tomorrow, and you are expecting a lot of traffic. You received \(N\) flights plans, each one corresponds to an aircraft that will use the runway...Fri, 21 Aug 2020 23:14:59 +0000https://arena.moi/problem/moi20runway