304768: CF909D. Colorful Points

Memory Limit:256 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

Colorful Points

题意翻译

你将得到一些在同一条线上的点,每一个点都有一种颜色。对于点a,他的邻居是他左边最靠近他的点和他左边最靠近他的点。(每个点最多有两个邻居,左边的和右边的) 你要对这些点做一些操作:每次同时删除颜色与邻居不同的点 。 解词: 同时:不会出现本来a点不用删,但删除a的邻居后,a需要删除,举个例子: 一开始:aabb 第一次后:ab(第二个a和第一个b删掉) 最后: (没了) 现在问你你要执行几次操作后,这些点无法再进行删除。(相当于几次后这些点都删完了或颜色都一样) Translated by @风格雨关

题目描述

You are given a set of points on a straight line. Each point has a color assigned to it. For point $ a $ , its neighbors are the points which don't have any other points between them and $ a $ . Each point has at most two neighbors - one from the left and one from the right. You perform a sequence of operations on this set of points. In one operation, you delete all points which have a neighbor point of a different color than the point itself. Points are deleted simultaneously, i.e. first you decide which points have to be deleted and then delete them. After that you can perform the next operation etc. If an operation would not delete any points, you can't perform it. How many operations will you need to perform until the next operation does not have any points to delete?

输入输出格式

输入格式


Input contains a single string of lowercase English letters 'a'-'z'. The letters give the points' colors in the order in which they are arranged on the line: the first letter gives the color of the leftmost point, the second gives the color of the second point from the left etc. The number of the points is between 1 and $ 10^{6} $ .

输出格式


Output one line containing an integer - the number of operations which can be performed on the given set of points until there are no more points to delete.

输入输出样例

输入样例 #1

aabb

输出样例 #1

2

输入样例 #2

aabcaa

输出样例 #2

1

说明

In the first test case, the first operation will delete two middle points and leave points "ab", which will be deleted with the second operation. There will be no points left to apply the third operation to. In the second test case, the first operation will delete the four points in the middle, leaving points "aa". None of them have neighbors of other colors, so the second operation can't be applied.

Input

题意翻译

你将得到一些在同一条线上的点,每一个点都有一种颜色。对于点a,他的邻居是他左边最靠近他的点和他左边最靠近他的点。(每个点最多有两个邻居,左边的和右边的) 你要对这些点做一些操作:每次同时删除颜色与邻居不同的点 。 解词: 同时:不会出现本来a点不用删,但删除a的邻居后,a需要删除,举个例子: 一开始:aabb 第一次后:ab(第二个a和第一个b删掉) 最后: (没了) 现在问你你要执行几次操作后,这些点无法再进行删除。(相当于几次后这些点都删完了或颜色都一样) Translated by @风格雨关

加入题单

上一题 下一题 算法标签: