Month: April 2023

Mushroom Filippov cooked himself a meal and while having his lunch, he decided to watch a video on TubeTube. He can not spend more than t� seconds for lunch, so he asks you for help with the selection of video. The TubeTube feed is a list of n� videos, indexed from 11 to n�. The i�-th video lasts ai�� seconds and has an entertainment value bi��. Initially, the feed … Read more

Karina has an array of n� integers a1,a2,a3,…,an�1,�2,�3,…,��. She loves multiplying numbers, so she decided that the beauty of a pair of numbers is their product. And the beauty of an array is the maximum beauty of a pair of adjacent elements in the array. For example, for n=4�=4, a=[3,5,7,4]�=[3,5,7,4], the beauty of the array is maxmax(3⋅53⋅5, 5⋅75⋅7, 7⋅47⋅4) = maxmax(1515, 3535, 2828) = 3535. Karina wants her array to be as beautiful as possible. In order to achieve … Read more

Tema loves cinnabon rolls — buns with cinnabon and chocolate in the shape of a “snail”. Cinnabon rolls come in different sizes and are square when viewed from above. The most delicious part of a roll is the chocolate, which is poured in a thin layer over the cinnabon roll in the form of a … Read more

A permutation is a sequence n� integers, where each integer from 11 to n� appears exactly once. For example, [1][1], [3,5,2,1,4][3,5,2,1,4], [1,3,2][1,3,2] are permutations, while [2,3,2][2,3,2], [4,3,1][4,3,1], [0][0] are not. Given a permutation a�, we construct an array b�, where bi=(a1+a2+ … +ai)modn��=(�1+�2+ … +��)mod�. A permutation of numbers [a1,a2,…,an][�1,�2,…,��] is called a super-permutation if [b1+1,b2+1,…,bn+1][�1+1,�2+1,…,��+1] is also a permutation of length n�. Grisha became interested whether a super-permutation of length n� exists. Help him solve this non-trivial problem. Output any super-permutation of length n�, if it exists. Otherwise, output −1−1. … Read more

You are given a string s�, consisting of lowercase English letters. In one operation, you are allowed to swap any two characters of the string s�. A string s� of length n� is called an anti-palindrome, if s[i]≠s[n−i+1]�[�]≠�[�−�+1] for every i� (1≤i≤n1≤�≤�). For example, the strings “codeforces”, “string” are anti-palindromes, but the strings “abacaba”, “abc”, “test” are not. Determine the minimum number of operations required to make the string s� an anti-palindrome, or output −1−1, if this is … Read more

Two friends, Alisa and Yuki, planted a tree with nn vertices in their garden. A tree is an undirected graph without cycles, loops, or multiple edges. Each edge in this tree has a length of kk. Initially, vertex 11 is the root of the tree. Alisa and Yuki are growing the tree not just for fun, they want to sell … Read more

Magic Triples (Easy Version) time limit per test 4 seconds memory limit per test 256 megabytes This is the easy version of the problem. The only difference is that in this version, ai≤106ai≤106. For a given sequence of nn integers aa, a triple (i,j,k)(i,j,k) is called magic if: 1≤i,j,k≤n1≤i,j,k≤n. ii, jj, kk are pairwise distinct. there exists a positive integer bb such that ai⋅b=ajai⋅b=aj and aj⋅b=akaj⋅b=ak. Kolya received a sequence of … Read more

Magic Triples (Hard Version)time limit per test4 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard outputThis is the hard version of the problem. The only difference is that in this version, ai≤109. For a given sequence of n integers a, a triple (i,j,k) is called magic if: 1≤i,j,k≤n.i, j, k are pairwise distinct.there exists a positive integer … Read more