国庆练习7

 Vitya in the Countryside CF 719A

Description

Every summer Vitya comes to visit his grandmother in the countryside. This summer, he got a huge wart. Every grandma knows that one should treat warts when the moon goes down. Thus, Vitya has to catch the moment when the moon is down.

Moon cycle lasts 30 days. The size of the visible part of the moon (in Vitya's units) for each day is 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11,12, 13, 14, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, and then cycle repeats, thus after the second 1 again goes 0.

As there is no internet in the countryside, Vitya has been watching the moon for n consecutive days and for each of these days he wrote down the size of the visible part of the moon. Help him find out whether the moon will be up or down next day, or this cannot be determined by the data he has.

Input

The first line of the input contains a single integer n (1 ≤ n ≤ 92) — the number of consecutive days Vitya was watching the size of the visible part of the moon.

The second line contains n integers a_i (0 ≤ a_i ≤ 15) — Vitya's records.

It's guaranteed that the input data is consistent.

Output

If Vitya can be sure that the size of visible part of the moon on day n + 1 will be less than the size of the visible part on day n, then print "DOWN" at the only line of the output. If he might be sure that the size of the visible part will increase, then print "UP". If it's impossible to determine what exactly will happen with the moon, print -1.

Sample Input

Input

5 3 4 5 6 7

Output

UP

Input

7 12 13 14 15 14 13 12

Output

DOWN

Input

1 8

Output

-1

Hint

In the first sample, the size of the moon on the next day will be equal to 8, thus the answer is "UP".

In the second sample, the size of the moon on the next day will be 11, thus the answer is "DOWN".

In the third sample, there is no way to determine whether the size of the moon on the next day will be 7 or 9, thus the answer is -1.

题目意思：观察月亮的圆缺变化，给你了近来n天的观察数据，问下一天月亮是会向上还是会向下。

解题思路：我们只需要看看最后两天观察月亮的变化就行了，不过需要注意边界条件。

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int a[100];
int main()
{
    int n,i,flag;
    scanf("%d",&n);
    flag=0;
    for(i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
    }
    if(n==1&&a[n]!=0&&a[n]!=15)
    {
        printf("-1
");
        return 0;
    }
    if(a[n]==0)
    {
        flag=1;
    }
    else if(a[n]==15)
    {
        flag=2;
    }
    else if(a[n]>a[n-1])
    {
        flag=1;
    }
    else if(a[n]<a[n-1])
    {
        flag=2;
    }

    if(flag==1)
    {
        printf("UP
");
    }
    else
    {
         printf("DOWN
");
    }
    return 0;
}

 Vitya in the Countryside  CF 719B

Description

Anatoly lives in the university dorm as many other students do. As you know, cockroaches（蟑螂） are also living there together with students. Cockroaches might be of two colors: black and red. There are n cockroaches living in Anatoly's room.

Anatoly just made all his cockroaches to form a single line. As he is a perfectionist, he would like the colors of cockroaches in the line toalternate. He has a can of black paint and a can of red paint. In one turn he can either swap any two cockroaches, or take any single cockroach and change it's color.

Help Anatoly find out the minimum number of turns he needs to make the colors of cockroaches in the line alternate.

Input

The first line of the input contains a single integer n (1 ≤ n ≤ 100 000) — the number of cockroaches.

The second line contains a string of length n, consisting of characters 'b' and 'r' that denote black cockroach and red cockroach respectively.

Output

Print one integer — the minimum number of moves Anatoly has to perform in order to make the colors of cockroaches in the line to alternate.

Sample Input

Input

5
rbbrr

Output

1

Input

5
bbbbb

Output

2

Input

3
rbr

Output

0

Hint

In the first sample, Anatoly has to swap third and fourth cockroaches. He needs 1 turn to do this.

In the second sample, the optimum（最佳） answer is to paint the second and the fourth cockroaches red. This requires 2 turns.

In the third sample, the colors of cockroaches in the line are alternating already, thus the answer is 0.

 

题目意思：强迫症干蟑螂。蟑螂有两种颜色black和red,强迫症要将蟑螂红黑相间排列，可以交换两个蟑螂，也可以给蟑螂重新上色，这两种方式都算一次操作，问最少几次操作就能红黑相间了。

解题思路：不管怎样变化,最后的序列一定是rbrb或者brbr样式的,在这2种结果的情况下,分别找对应位置上没有匹配好的个数cnt1,cnt2,那么还需要操作：

1.替换：abs(cnt1-cnt2)

2.交换：(cnt1+cnt2-abs(cnt1-cnt2))/2

#include<cstdio>
#include<cstring>
#include<map>
#include<cmath>
#include<algorithm>
using namespace std;
char s[1000010];
int main()
{
    int n,i,a,b,c,d,ans1,ans2;
    a=0,b=0,c=0,d=0;
    ans1=0,ans2=0;
    scanf("%d",&n);
    getchar();
    gets(s);
    for(i=0;i<n;i++)///brbr顺序
    {
        if(i%2==0&&s[i]=='r')///偶数位上没有匹配上b的
        {
            a++;
        }
        else if(i%2==1&&s[i]=='b')///奇数位上没有匹配上r的
        {
            b++;
        }
    }
    for(i=0;i<n;i++)///rbrb顺序
    {
        if(i%2==0&&s[i]=='b')///偶数位上没有匹配上r的
        {
            c++;
        }
        else if(i%2==1&&s[i]=='r')///奇数位上没有匹配上b的
        {
            d++;
        }
    }
    ans1=abs(a-b)+(a+b-fabs(a-b))/2;
    ans2=abs(c-d)+(c+d-fabs(c-d))/2;
    printf("%d
",min(ans1,ans2));
    return 0;
}

 Complete the Word  CF 716B

Description

ZS the Coder loves to read the dictionary. He thinks that a word is nice if there exists a substring (子串) (contiguous segment of letters) of it of length 26 where each letter of English alphabet appears exactly once. In particular, if the string has length strictly less than 26, no such substring exists and thus it is not nice.

Now, ZS the Coder tells you a word, where some of its letters are missing as he forgot them. He wants to determine if it is possible to fill in the missing letters so that the resulting word is nice. If it is possible, he needs you to find an example of such a word as well. Can you help him?

Input

The first and only line of the input contains a single string s (1 ≤ |s| ≤ 50 000), the word that ZS the Coder remembers. Each character of the string is the uppercase letter of English alphabet ('A'-'Z') or is a question mark ('?'), where the question marks denotes the letters that ZS the Coder can't remember.

Output

If there is no way to replace all the question marks with uppercase letters such that the resulting word is nice, then print  - 1 in the only line.

Otherwise, print a string which denotes a possible nice word that ZS the Coder learned. This string should match the string from the input, except for the question marks replaced with uppercase English letters.

If there are multiple solutions, you may print any of them.

Sample Input

Input

ABC??FGHIJK???OPQR?TUVWXY?

Output

ABCDEFGHIJKLMNOPQRZTUVWXYS

Input

WELCOMETOCODEFORCESROUNDTHREEHUNDREDANDSEVENTYTWO

Output

-1

Input

??????????????????????????

Output

MNBVCXZLKJHGFDSAQPWOEIRUYT

Input

AABCDEFGHIJKLMNOPQRSTUVW??M

Output

-1

Hint

In the first sample case, ABCDEFGHIJKLMNOPQRZTUVWXYS is a valid answer beacuse it contains a substring of length 26 (the whole string in this case) which contains all the letters of the English alphabet exactly once. Note that there are many possible solutions, such as ABCDEFGHIJKLMNOPQRSTUVWXYZ or ABCEDFGHIJKLMNOPQRZTUVWXYS.

In the second sample case, there are no missing letters. In addition, the given string does not have a substring of length 26 that contains all the letters of the alphabet, so the answer is  - 1.

In the third sample case, any string of length 26 that contains all letters of the English alphabet fits as an answer.

 

题目意思:这是我最近做过的最恶心的一道题了，开始就理解错了意思。。。导致后面一直WA。给你一个字符串，其中有一个子串长度为26，含有或者部分含有26个字母，不重复，这个子串中可能会含有'？'。你需要用剩下没有出现的字母填充‘？’,直到这一个子串完全变为含有26个大写字母的字符串。除了这个子串的母串部分没有出现‘?’的部分保留，‘？’用任意一个大写字母替换。

解题思路：直接按要求模拟即可，不过不得不说这个代码水平还是很高的，在循环和选择的控制上很有技巧。

#include<cstdio>
#include<cstring>
#include<map>
#include<algorithm>
using namespace std;
char s[500010];
char a[30]="ABCDEFGHIJKLMNOPQRSTUVWXYZ";
int vis[30];
int x[30];
int main()
{
    int i,j,k,len,ans,flag;
    gets(s);
    len=strlen(s);
    if(len<26)///小于26不符合
    {
        printf("-1
");
        return 0;
    }
    ans=0;
    for(i=0; i<len-25; i++)///之所以是25而不是26是为了给全是？留出可能性
    {///大循环是为了找子串
        memset(x,0,sizeof(x));
        memset(vis,0,sizeof(vis));
        flag=1;
        for(j=i; j<i+26; j++)
        {
            if(s[j]>='A'&&s[j]<='Z')
            {
                x[s[j]-'A']++;
                vis[s[j]-'A']=1;///出现过的字母标记一下
                if(x[s[j]-'A']>=2)///子串中的26个字母只能出现一次
                {
                    flag=0;
                    break;
                }
            }
        }
        if(flag)
        {
            ans=1;
            for(j=i; j<i+26; j++)
            {
                if(s[j]=='?')///将？换成剩下的字母
                {
                    for(k=0; k<26; k++)
                    {
                        if(vis[k]==0)
                        {
                            s[j]=a[k];
                            vis[k]=1;///换好了以后要标记
                            break;
                        }
                    }
                }
            }
            if(ans)
            {
                break;
            }
        }
    }
    if(ans)
    {
        for(i=0; i<len; i++)///若是母串中还有？将换成A
        {
            if(s[i]=='?')
            {
                s[i]='A';
            }
        }
        puts(s);
    }
    else
    {
        puts("-1");
    }
    return 0;
}