CodeForces - 1101B

水深无声 2022-01-12 10:59 163阅读 0赞

题目：

B. Accordion

time limit per test

3 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

An accordion is a string (yes, in the real world accordions are musical instruments, but let's forget about it for a while) which can be represented as a concatenation of: an opening bracket (ASCII code 091091), a colon (ASCII code 058058), some (possibly zero) vertical line characters (ASCII code 124124), another colon, and a closing bracket (ASCII code 093093). The length of the accordion is the number of characters in it.

For example, \[::\], \[:||:\] and \[:|||:\] are accordions having length 44, 66 and 77. (:|:), \{:||:\}, \[:\], \]:||:\[ are not accordions.

You are given a string ss. You want to transform it into an accordion by removing some (possibly zero) characters from it. Note that you may not insert new characters or reorder existing ones. Is it possible to obtain an accordion by removing characters from ss, and if so, what is the maximum possible length of the result?

Input

The only line contains one string ss (1≤|s|≤5000001≤|s|≤500000). It consists of lowercase Latin letters and characters \[, \], : and |.

Output

If it is not possible to obtain an accordion by removing some characters from ss, print −1−1. Otherwise print maximum possible length of the resulting accordion.

Examples

Input

|[a:b:|]

Output

Input

|]:[|:]

Output

-1
    
    题目大意：
    
    由[::]这样的顺序可以构造手风琴，冒号之间可以有|用来增加手风琴的长度，给出一个串，问串构成的手风琴最长为多少。
    
    思路：
    
    首先，要判断能否构成手风琴，也就是说满足格式[::],不满足就输出-1，满足的话在两个冒号之间数有多少个|，最后加上4就是最长的手风琴长度。要注意，串给出的手风琴可能不止一个，所有要从前向后寻找[,从后往前寻找]。
    
    AC代码如下：

#include<stdio.h>
    #include<string.h>
    
    int main()
    {
    	char a[500010];
    	int A=-1,B=-1,C=-1,D=-1,cnt=0;
    	scanf("%s",a);
    	int len=strlen(a);
    	for(int i=0;i<len;i++)
    	{
    		if(a[i]=='['){
    			A=i;break;
    		}
    	}
    	for(int i=len-1;i>A;i--)
    	{
    		if(a[i]==']'){
    			B=i;break;
    		} 
    	}
    	for(int i=A+1;i<B;i++)
    	{
    		if(a[i]==':'){
    			C=i;break;
    		} 
    	}
    	for(int i=B-1;i>C;i--)
    	{
    		if(a[i]==':'){
    			D=i;break;
    		}
    	}
    	for(int i=C;i<D;i++)
    	{
    		if(a[i]=='|') cnt++;
    	}
    	if(A==-1||B==-1||C==-1||D==-1) printf("-1\n");
    	else printf("%d\n",cnt+4);
    	return 0;
    }

转载于:https://www.cnblogs.com/noback-go/p/10497097.html