暑假过的很累,,但是也每天三点一线学了不少东西,所谓苦尽甘来大概就是这种感 觉。






Codeforces-1004B. Sonya and Exhibition

Sonya decided that having her own hotel business is the best way of earning money because she can profit and rest wherever she wants.

The country where Sonya lives is an endless line. There is a city in each integer coordinate on this line. She has nn hotels, where the ii-th hotel is located in the city with coordinate xi. Sonya is a smart girl, so she does not open two or more hotels in the same city.

Sonya understands that her business needs to be expanded by opening new hotels, so she decides to build one more. She wants to make the minimum distance from this hotel to all others to be equal to dd. The girl understands that there are many possible locations to construct such a hotel. Thus she wants to know the number of possible coordinates of the cities where she can build a new hotel.

Because Sonya is lounging in a jacuzzi in one of her hotels, she is asking you to find the number of cities where she can build a new hotel so that the minimum distance from the original nn hotels to the new one is equal to d.

继续阅读Codeforces-1004B. Sonya and Exhibition

Codeforces round 493 div2 B.Cutting

There are a lot of things which could be cut — trees, paper, “the rope”. In this problem you are going to cut a sequence of integers.

There is a sequence of integers, which contains the equal number of even and odd numbers. Given a limited budget, you need to make maximum possible number of cuts such that each resulting segment will have the same number of odd and even integers.

Cuts separate a sequence to continuous (contiguous) segments. You may think about each cut as a break between two adjacent elements in a sequence. So after cutting each element belongs to exactly one segment. Say, [4,1,2,3,4,5,4,4,5,5][4,1,2,3,4,5,4,4,5,5]  two cuts →→[4,1|2,3,4,5|4,4,5,5][4,1|2,3,4,5|4,4,5,5].  On each segment the number of even elements should be equal to the number of odd elements.

The cost of the cut between xx and yy numbers is |xy|bitcoins. Find the maximum possible number of cuts that can be made while spending no more than Bbitcoins.

继续阅读Codeforces round 493 div2 B.Cutting

Codeforces-1009B B. Minimum Ternary String

You are given a ternary string (it is a string which consists only of characters ‘0‘, ‘1‘ and ‘2‘).

You can swap any two adjacent (consecutive) characters ‘0‘ and ‘1‘ (i.e. replace “01” with “10” or vice versa) or any two adjacent (consecutive) characters ‘1‘ and ‘2‘ (i.e. replace “12” with “21” or vice versa).

For example, for string “010210” we can perform the following moves:

  • 010210”  “100210“;
  • 010210”  “001210“;
  • 010210”  “010120“;
  • 010210”  “010201“.

Note than you cannot swap “02”  “20” and vice versa. You cannot perform any other operations with the given string excluding described above.

You task is to obtain the minimum possible (lexicographically) string by using these swaps arbitrary number of times (possibly, zero).

String aa is lexicographically less than string bb (if strings aa and bb have the same length) if there exists some position i (1i|a|, where |s| is the length of the string s) such that for every j<i holds aj=bj, and ai<bi.

继续阅读Codeforces-1009B B. Minimum Ternary String

Codeforces-1008B B. Turn the Rectangles

There are n rectangles in a row. You can either turn each rectangle by 90 degrees or leave it as it is. If you turn a rectangle, its width will be height, and its height will be width. Notice that you can turn any number of rectangles, you also can turn all or none of them. You can not change the order of the rectangles.

继续阅读Codeforces-1008B B. Turn the Rectangles