Codeforces Round #501 (Div. 3)

  • 2018-08-02
  • 15
  • 0

A. Points in Segments

题目:

You are given a set of n segments on the axis Ox, each segment has integer endpoints between 1 and m inclusive. Segments may intersect, overlap or even coincide with each other. Each segment is characterized by two integers l_i and r_i (1 \le l_i \le r_i \le m) — coordinates of the left and of the right endpoints.
Consider all integer points between 1 and m inclusive. Your task is to print all such points that don’t belong to any segment. The point x belongs to the segment [l; r] if and only if l \le x \le r.

Input:

The first line of the input contains two integers n and m (1 \le n, m \le 100) — the number of segments and the upper bound for coordinates.
The next n lines contain two integers each l_i and r_i (1 \le l_i \le r_i \le m) — the endpoints of the i-th segment. Segments may intersect, overlap or even coincide with each other. Note, it is possible that l_i=r_i, i.e. a segment can degenerate to a point.

Output

In the first line print one integer k — the number of points that don’t belong to any segment.
In the second line print exactly k integers in any order — the points that don’t belong to any segment. All points you print should be distinct.
If there are no such points at all, print a single integer 0 in the first line and either leave the second line empty or do not print it at all.

Sample Input:

3 5
2 2
1 2
5 5

Sample Output:

2
3 4

Sample Input:

1 7
1 7

Sample Output:

0

题目链接

给出几组区间,求不在区间内的所有点。

直接用一个数组标记记录即可。

最开始读题以为要输出所有区间,一直WA…

AC代码:

B. Obtaining the String

题目:

You are given two strings s and t. Both strings have length n and consist of lowercase Latin letters. The characters in the strings are numbered from 1 to n.
You can successively perform the following move any number of times (possibly, zero):
swap any two adjacent (neighboring) characters of s (i.e. for any i = {1, 2, \dots, n – 1} you can swap s_i and s_{i + 1}). You can’t apply a move to the string t. The moves are applied to the string s one after another.
Your task is to obtain the string t from the string s. Find any way to do it with at most 10^4 such moves.
You do not have to minimize the number of moves, just find any sequence of moves of length 10^4 or less to transform s into t.

Input:

The first line of the input contains one integer n (1 \le n \le 50) — the length of strings s and t.
The second line of the input contains the string s consisting of n lowercase Latin letters.
The third line of the input contains the string t consisting of n lowercase Latin letters.

Output

If it is impossible to obtain the string t using moves, print “-1”.
Otherwise in the first line print one integer k — the number of moves to transform s to t. Note that k must be an integer number between 0 and 10^4 inclusive.
In the second line print k integers c_j (1 \le c_j < n), where c_j means that on the j-th move you swap characters s_{c_j} and s_{c_j + 1}.
If you do not need to apply any moves, print a single integer 0 in the first line and either leave the second line empty or do not print it at all.

Sample Input:

6
abcdef
abdfec

Sample Output:

4
3 5 4 5

Sample Input:

4
abcd
accd

Sample Output:

-1

题目链接

求第一个字符串相邻字符如何交换可以与第二个字符串相同。

先判断两个字符串内每个字符个数是否都相同,再在第二个字符串中从后往前找两个字符串中不同的字符进行交换。

AC代码:

C. Songs Compression

题目:

Ivan has n songs on his phone. The size of the i-th song is a_i bytes. Ivan also has a flash drive which can hold at most m bytes in total. Initially, his flash drive is empty.
Ivan wants to copy all n songs to the flash drive. He can compress the songs. If he compresses the i-th song, the size of the i-th song reduces from a_i to b_i bytes (b_i < a_i).
Ivan can compress any subset of the songs (possibly empty) and copy all the songs to his flash drive if the sum of their sizes is at most m. He can compress any subset of the songs (not necessarily contiguous).
Ivan wants to find the minimum number of songs he needs to compress in such a way that all his songs fit on the drive (i.e. the sum of their sizes is less than or equal to m).
If it is impossible to copy all the songs (even if Ivan compresses all the songs), print “-1”. Otherwise print the minimum number of songs Ivan needs to compress.

Input:

The first line of the input contains two integers n and m (1 \le n \le 10^5, 1 \le m \le 10^9) — the number of the songs on Ivan’s phone and the capacity of Ivan’s flash drive.
The next n lines contain two integers each: the i-th line contains two integers a_i and b_i (1 \le a_i, b_i \le 10^9, a_i > b_i) — the initial size of the i-th song and the size of the i-th song after compression.

Output

If it is impossible to compress a subset of the songs in such a way that all songs fit on the flash drive, print “-1”. Otherwise print the minimum number of the songs to compress.

Sample Input:

4 21
10 8
7 4
3 1
5 4

Sample Output:

2

Sample Input:

4 16
10 8
7 4
3 1
5 4

Sample Output:

-1

题目链接

每首歌有a大小,压缩后是b大小,求最少压缩几首歌可以达到要求。

按照压缩变化大小(a-b)降序排序,优先压缩变化大的歌曲,直到达到要求。

AC代码:

D. Walking Between Houses

题目:

There are n houses in a row. They are numbered from 1 to n in order from left to right. Initially you are in the house 1.
You have to perform k moves to other house. In one move you go from your current house to some other house. You can’t stay where you are (i.e., in each move the new house differs from the current house). If you go from the house x to the house y, the total distance you walked increases by |x-y| units of distance, where |a| is the absolute value of a. It is possible to visit the same house multiple times (but you can’t visit the same house in sequence).
Your goal is to walk exactly s units of distance in total.
If it is impossible, print “NO”. Otherwise print “YES” and any of the ways to do that. Remember that you should do exactly k moves.

Input:

The first line of the input contains three integers n, k, s (2 \le n \le 10^9, 1 \le k \le 2 \cdot 10^5, 1 \le s \le 10^{18}) — the number of houses, the number of moves and the total distance you want to walk.

Output

If you cannot perform k moves with total walking distance equal to s, print “NO”.
Otherwise print “YES” on the first line and then print exactly k integers h_i (1 \le h_i \le n) on the second line, where h_i is the house you visit on the i-th move.
For each j from 1 to k-1 the following condition should be satisfied: h_j \ne h_{j + 1}. Also h_1 \ne 1 should be satisfied.

Sample Input:

10 2 15

Sample Output:

YES
10 4

Sample Input:

10 9 45

Sample Output:

YES
10 1 10 1 2 1 2 1 6

Sample Input:

10 9 81

Sample Output:

YES
10 1 10 1 10 1 10 1 10

Sample Input:

10 9 82

Sample Output:

NO

题目链接

有1~n栋房子,起始位置是1,输出进过k次移动正好移动s距离的移动过程。

最大可以移动n-1距离,从n-1遍历到1,优先移动远距离,最后用1进行剩下的移动即可。

AC代码:

E1. Stars Drawing (Easy Edition)

题目:

A star is a figure of the following type: an asterisk character ‘*’ in the center of the figure and four rays (to the left, right, top, bottom) of the same positive length. The size of a star is the length of its rays. The size of a star must be a positive number (i.e. rays of length 0 are not allowed).
Let’s consider empty cells are denoted by ‘.’, then the following figures are stars:

The leftmost figure is a star of size 1, the middle figure is a star of size 2 and the rightmost figure is a star of size 3. You are given a rectangular grid of size n \times m consisting only of asterisks ‘*’ and periods (dots) ‘.’. Rows are numbered from 1 to n, columns are numbered from 1 to m. Your task is to draw this grid using any number of stars or find out that it is impossible. Stars can intersect, overlap or even coincide with each other. The number of stars in the output can’t exceed n \cdot m. Each star should be completely inside the grid. You can use stars of same and arbitrary sizes.

In this problem, you do not need to minimize the number of stars. Just find any way to draw the given grid with at most n \cdot m stars.

Input:

The first line of the input contains two integers n and m (3 \le n, m \le 100) — the sizes of the given grid.
The next n lines contains m characters each, the i-th line describes the i-th row of the grid. It is guaranteed that grid consists of characters ‘*’ and ‘.’ only.

Output

If it is impossible to draw the given grid using stars only, print “-1”.
Otherwise in the first line print one integer k (0 \le k \le n \cdot m) — the number of stars needed to draw the given grid. The next k lines should contain three integers each — x_j, y_j and s_j, where x_j is the row index of the central star character, y_j is the column index of the central star character and s_j is the size of the star. Each star should be completely inside the grid.

Sample Input:

6 8
….

..*****.

….

……..

Sample Output:

3
3 4 1
3 5 2
3 5 1

Sample Input:

5 5
.*…
****.
.****
..**.
…..

Sample Output:

3
2 2 1
3 3 1
3 4 1

Sample Input:

5 5
.
***..
.

.*…
…..

Sample Output:

-1

Sample Input:

3 3
.
.*.
.

Sample Output:

-1

题目链接

E1和E2两道题目只是数据范围稍有不同,做法一样。

给出一个由’*’和’.’组成的矩阵,有多少种由’*’组成的’十’型图案,若这些图案可以覆盖全部’*’字符,则输出每个’十’的中心’*’坐标和长度,若不能全部覆盖输出’-1’。

枚举每一个’*’为’十’的中心,判断标记即可。

AC代码:

E2. Stars Drawing (Hard Edition)

题目:

A star is a figure of the following type: an asterisk character ‘*’ in the center of the figure and four rays (to the left, right, top, bottom) of the same positive length. The size of a star is the length of its rays. The size of a star must be a positive number (i.e. rays of length 0 are not allowed).
Let’s consider empty cells are denoted by ‘.’, then the following figures are stars:

The leftmost figure is a star of size 1, the middle figure is a star of size 2 and the rightmost figure is a star of size 3. You are given a rectangular grid of size n \times m consisting only of asterisks ‘*’ and periods (dots) ‘.’. Rows are numbered from 1 to n, columns are numbered from 1 to m. Your task is to draw this grid using any number of stars or find out that it is impossible. Stars can intersect, overlap or even coincide with each other. The number of stars in the output can’t exceed n \cdot m. Each star should be completely inside the grid. You can use stars of same and arbitrary sizes.

In this problem, you do not need to minimize the number of stars. Just find any way to draw the given grid with at most n \cdot m stars.

Input:

The first line of the input contains two integers n and m (3 \le n, m \le 1000) — the sizes of the given grid.
The next n lines contains m characters each, the i-th line describes the i-th row of the grid. It is guaranteed that grid consists of characters ‘*’ and ‘.’ only.

Output

If it is impossible to draw the given grid using stars only, print “-1”.
Otherwise in the first line print one integer k (0 \le k \le n \cdot m) — the number of stars needed to draw the given grid. The next k lines should contain three integers each — x_j, y_j and s_j, where x_j is the row index of the central star character, y_j is the column index of the central star character and s_j is the size of the star. Each star should be completely inside the grid.

Sample Input:

6 8
….

..*****.

….

……..

Sample Output:

3
3 4 1
3 5 2
3 5 1

Sample Input:

5 5
.*…
****.
.****
..**.
…..

Sample Output:

3
2 2 1
3 3 1
3 4 1

Sample Input:

5 5
.
***..
.

.*…
…..

Sample Output:

-1

Sample Input:

3 3
.
.*.
.

Sample Output:

-1

题目链接

同上。

AC代码:

评论

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