Codeforces Round #490 (Div. 3)

  • 2018-07-11
  • 30
  • 0

A. Mishka and Contest

题目:

Mishka started participating in a programming contest. There are n​ problems in the contest. Mishka’s problem-solving skill is equal to k​.hka arranges all problems from the contest into a list. Because of his weird principles, Mishka only solves problems from one of the ends of the list. Every time, he chooses which end (left or right) he will solve the next problem from. Thus, each problem Mishka solves is either the leftmost or the rightmost problem in the list.

Mishka cannot solve a problem with difficulty greater than k. When Mishka solves the problem, it disappears from the list, so the length of the list decreases by 1. Mishka stops when he is unable to solve any problem from any end of the list.

How many problems can Mishka solve?

## Input:

The first line of input contains two integers n and k (1 \le n, k \le 100) — the number of problems in the contest and Mishka’s problem-solving skill.The second line of input contains n integers a_1, a_2, \dots, a_n (1 \le a_i \le 100), where a_i is the difficulty of the i-th problem. The problems are given in order from the leftmost to the rightmost in the list.

Output:

Print one integer — the maximum number of problems Mishka can solve.

Sample Input:

8 4
4 2 3 1 5 1 6 4

Sample Output:

5

Sample Input:

5 2
3 1 2 1 3

Sample Output:

0

Sample Input:

5 100
12 34 55 43 21

Sample Output:

5

题目链接

在数列中从左右两侧取走不大于k的数,求能取走多少个数。

分别在数组中标记最左侧不大于k的数和最右侧不大于k的数,求出两边数的个数即可。

AC代码:

B. Reversing Encryption

题目:

A string s of length n can be encrypted by the following algorithm:

  • iterate over all divisors of n in decreasing order (i.e. from n to 1),
  • for each divisor d, reverse the substring s[1 \dots d] (i.e. the substring which starts at position 1 and ends at position d).

For example, the above algorithm applied to the string s="codeforces" leads to the following changes: "codeforces \to "secrofedoc" \to "orcesfedoc" \to "rocesfedoc" \to "rocesfedoc" (obviously, the last reverse operation doesn’t change the string because d=1).You are given the encrypted string t. Your task is to decrypt this string, i.e., to find a string s such that the above algorithm results in string t. It can be proven that this string s always exists and is unique.

Input:

The first line of input consists of a single integer n (1 \le n \le 100) — the length of the string t. The second line of input consists of the string t. The length of t is n, and it consists only of lowercase Latin letters.

Output:

Print a string s such that the above algorithm results in t.

Sample Input:

10
rocesfedoc

Sample Output:

codeforces

Sample Input:

16
plmaetwoxesisiht

Sample Output:

thisisexampletwo

Sample Input:

1
z

Sample Output:

z

题目链接

一个字符串长度为n,按照d从n开始由n的因数依次递减到1,每次字符串从第一个字母开始翻转第1~d个字母,现给出翻转后字符串,求原始字符串。

暴力遍历i = 1~n,若i是n的因数则翻翻转字符串1~i。

AC代码:

C. Alphabetic Removals

题目:

You are given a string s consisting of n lowercase Latin letters. Polycarp wants to remove exactly k characters (k \le n) from the string s. Polycarp uses the following algorithm k times:

  • if there is at least one letter ‘a’, remove the leftmost occurrence and stop the algorithm, otherwise go to next item;
  • if there is at least one letter ‘b’, remove the leftmost occurrence and stop the algorithm, otherwise go to next item;
  • remove the leftmost occurrence of the letter ‘z’ and stop the algorithm.

This algorithm removes a single letter from the string. Polycarp performs this algorithm exactly k times, thus removing exactly k characters.

Help Polycarp find the resulting string.

Input:

The first line of input contains two integers n and k (1 \le k \le n \le 4 \cdot 10^5) — the length of the string and the number of letters Polycarp will remove.

The second line contains the string s consisting of n lowercase Latin letters.

Output:

Print the string that will be obtained from s after Polycarp removes exactly k letters using the above algorithm k times.

If the resulting string is empty, print nothing. It is allowed to print nothing or an empty line (line break).

Sample Input:

15 3
cccaabababaccbc

Sample Output:

cccbbabaccbc

Sample Input:

15 9
cccaabababaccbc

Sample Output:

cccccc

Sample Input:

1 1
u

Sample Output:

题目链接

一个n个小写字母的字符串,按照字典序去掉k个字母。

统计每个字母的数量,依次输出字符串字母时判断输出即可。

AC代码:

D. Equalize the Remainders

题目:

You are given an array consisting of n integers a_1, a_2, \dots, a_n, and a positive integer m. It is guaranteed that m is a divisor of n.

In a single move, you can choose any position i between 1 and n and increase a_i by 1.

Let’s calculate c_r (0 \le r \le m-1) — the number of elements having remainder r when divided by m. In other words, for each remainder, let’s find the number of corresponding elements in a with that remainder.

Your task is to change the array in such a way that c_0 = c_1 = \dots = c_{m-1} = \frac{n}{m}.

Find the minimum number of moves to satisfy the above requirement.

Input:

The first line of input contains two integers n and m (1 \le n \le 2 \cdot 10^5, 1 \le m \le n). It is guaranteed that m is a divisor of n.

The second line of input contains n integers a_1, a_2, \dots, a_n (0 \le a_i \le 10^9), the elements of the array.

Output:

In the first line, print a single integer — the minimum number of moves required to satisfy the following condition: for each remainder from 0 to m – 1, the number of elements of the array having this remainder equals \frac{n}{m}.

In the second line, print any array satisfying the condition and can be obtained from the given array with the minimum number of moves. The values of the elements of the resulting array must not exceed 10^{18}.

Sample Input:

6 3
3 2 0 6 10 12

Sample Output:

3
3 2 0 7 10 14

Sample Input:

4 2
0 1 2 3

Sample Output:

0
0 1 2 3

题目链接

给定一个n个数的数列a,和一个数字m,数列中每个数对m取模得到一个有n个数的新数列c,对数列a进行操作,每次操作可以选择数列中的一个数+1,最终使得c数列中1~m-1每个数字都为\frac{n}{m}个。

这道题自己写一直超时过不了,最后无奈看了Tutorial,学习了一下写法。

先把每个余数下标都加入到余数二位数组中,然后使用循环变量i对1~m-1循环两次,每个循环中若余数为i的数多于\frac{n}{m},先抽出多余部分加入到一个动态数组中,若余数为i的数少于\frac{n}{m},则从动态数组种抽出少的数量加入到余数为i的数中,在操作中改变相应原始数列的值。

AC代码:

E. Reachability from the Capital

题目:

There are n cities and m roads in Berland. Each road connects a pair of cities. The roads in Berland are one-way.

What is the minimum number of new roads that need to be built to make all the cities reachable from the capital?

New roads will also be one-way.

Input:

The first line of input consists of three integers n, m and s (1 \le n \le 5000, 0 \le m \le 5000, 1 \le s \le n) — the number of cities, the number of roads and the index of the capital. Cities are indexed from 1 to n.

The following m lines contain roads: road i is given as a pair of cities u_i, v_i (1 \le u_i, v_i \le n, u_i \ne v_i). For each pair of cities (u, v), there can be at most one road from u to v. Roads in opposite directions between a pair of cities are allowed (i.e. from u to v and from v to u).

Output:

Print one integer — the minimum number of extra roads needed to make all the cities reachable from city s. If all the cities are already reachable from s, print 0.

Sample Input:

9 9 1
1 2
1 3
2 3
1 5
5 6
6 1
1 8
9 8
7 1

Sample Output:

3

Sample Input:

5 4 5
1 2
2 3
3 4
4 1

Sample Output:

1

题目链接

一个有向图,要求添加最少的边数使的从s点出发可以到达任意一点。

先dfs把无法到达的点搜索出来,然后再遍历无法到达的点dfs搜索出使s连接此点后可增加连接的点数,按照点数降序排序,依次遍历添加边并更新图。

AC代码:

F. Cards and Joy

题目:

There are n players sitting at the card table. Each player has a favorite number. The favorite number of the j-th player is f_j.

There are k \cdot n cards on the table. Each card contains a single integer: the i-th card contains number c_i. Also, you are given a sequence h_1, h_2, \dots, h_k. Its meaning will be explained below.

The players have to distribute all the cards in such a way that each of them will hold exactly k cards. After all the cards are distributed, each player counts the number of cards he has that contains his favorite number. The joy level of a player equals h_t if the player holds t cards containing his favorite number. If a player gets no cards with his favorite number (i.e., t=0), his joy level is 0.

Print the maximum possible total joy levels of the players after the cards are distributed. Note that the sequence h_1, \dots, h_k is the same for all the players.

Input:

The first line of input contains two integers n and k (1 \le n \le 500, 1 \le k \le 10) — the number of players and the number of cards each player will get.

The second line contains k \cdot n integers c_1, c_2, \dots, c_{k \cdot n} (1 \le c_i \le 10^5) — the numbers written on the cards.

The third line contains n integers f_1, f_2, \dots, f_n (1 \le f_j \le 10^5) — the favorite numbers of the players.

The fourth line contains k integers h_1, h_2, \dots, h_k (1 \le h_t \le 10^5), where h_t is the joy level of a player if he gets exactly t cards with his favorite number written on them. It is guaranteed that the condition h_{t – 1} \lt; h_t holds for each t \in [2..k].

Output:

Print one integer — the maximum possible total joy levels of the players among all possible card distributions.

Sample Input:

4 3
1 3 2 8 5 5 8 2 2 8 5 2
1 2 2 5
2 6 7

Sample Output:

21

Sample Input:

3 3
9 9 9 9 9 9 9 9 9
1 2 3
1 2 3

Sample Output:

0

题目链接

一共n个人,n×k个数,每个人都有一个最喜欢的数,将n×k个数平均分别给n个人,每个人有k个数,给定h[i]数组表示一个人拿到i个最喜欢数字的喜悦值,求所有人喜悦值之和的最大值。

对于一个数来说,喜悦值之和的结果只和喜欢这个数的人数和这个数字的个数相关。

dp[x][y]表示有x个喜欢数字相同的人,分配共y张此数字的卡片的最大值

状态转移方程:

AC代码:

评论

还没有任何评论,你来说两句吧