Accordion

　

accordion

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

4

input

|]:[|:]

output

-1

本来不难的题，wa了很多发。

就是判断口琴的长度，口琴开头结尾分别为["     :]

1、[::], [:||:] and [:|||:] are accordions having length 4, 6 and 7样例中的|并没有配对，我还是按配对来计算的，导致wa了几发。

2、ss (1≤|s|≤500000) ，开的数组太小了，导致溢出。

3、没有看懂题意~~~~~想成了栈去做这道题~

#include<stdio.h>
#include<algorithm>
using namespace std;
int l,r,d;

char a[500005];
int main()
{
    scanf("%s",a);
    int l=strlen(a);
    int left=0,right=0;
    int i,j;
    for(i=0;i<l;++i)
    {
        if(a[i]=='[')
        {
            ++left;
            break;
        }
    }
    for(;i<l;++i)
    {
        if(a[i]==':')
        {
            ++left;
            break;
        }
    }
    for(j=l-1;j>i;--j)
    {
        if(a[j]==']')
        {
            ++right;
            break;
        }

    }
    for(;j>i;--j)
    {
        if(a[j]==':')
        {
            ++right;
            break;
        }
    }
    int num=0;
    if(left!=right)
    {
        printf("-1\n");
    }
    else
    {
        for(int kk=i+1;kk<j;++kk)
        {
            if(a[kk]=='|')
                ++num;
        }
        printf("%d\n",num+4);
    }
    return 0;
}

for循环外面的执行部分可以移动到for循环里面，这样就可以让代码更简洁

下面给出C++的一个AC代码

#include<iOStream>
#include<algorithm>
using namespace std;
int main()
{
    string s;
    cin>>s;
    long int i,k,d,j;
    for(i=0; i<s.size() && s[i]!='['; i++)
        ;
    for(; i<s.size() && s[i]!=':'; i++)
        ;
    for(j=s.size()-1; j>=0 && s[j]!=']'; j--)
        ;
    for(; j>=0 && s[j]!=':'; j--)
        ;
    if(i>=j)
        cout<<"-1";
    else
    {
        d=4;
        for(k=i+1; k<j; k++)
            if(s[k]=='|')
                d++;
        cout<<d;
    }
}

相关阅读

Accordion

https://codeforces.com/contest/1101/problem/B 题解： 从左往右找到 [: 记:下标为l 从右往左找到 :] 记:下标为r 查找【l+1，r-1