A. Mike and palindrome(TwoPoints)

Mike has a string s consisting of only lowercase English letters. He wants to change exactly one character from the string so that the resulting one is a palindrome.

A palindrome is a string that reads the same backward as forward, for example strings "z", "aaa", "aba", "abccba" are palindromes, but strings "codeforces", "reality", "ab" are not.

Input

The first and single line contains string s (1 ≤ |s| ≤ 15).

Output

Print "YES" (without quotes) if Mike can change exactly one character so that the resulting string is palindrome or "NO" (without quotes) otherwise.

Examples

input

abccaa

output

YES

input

abbcca

output

NO

input

abcda

output

YES

Means:

给定一串字符串,问你恰好,注意,恰好,改变一个使得这个字符串变成回文串

Solve:

直接two points扫一下,注意aba是可以恰好改变一个变成回文串的

Code:

 1 #include <bits/stdc++.h> 2 using namespace std; 3 #define CLR(x , v)        memset(x , v , sizeof(x)) 4 static const int MAXN = 20; 5 char data[MAXN]; 6 int main(int argc, char const *argv[]) 7 { 8     scanf(" %s" , data); 9     int si = 0;10     int l = 0 , r = strlen(data) - 1;11     si = strlen(data);12     int no = 0;13     while(l < r)14     {15         if(data[l] != data[r])16             ++no;17         ++l , --r;18     }19     if(no == 1)20         puts("YES");21     else if(no == 0 && (si % 2 != 0))22         puts("YES");23     else24         puts("NO");25     return 0;26 }

View Code

B. Mike and strings(枚举 + 模拟)

Mike has n strings s1, s2, ..., sn each consisting of lowercase English letters. In one move he can choose a string si, erase the first character and append it to the end of the string. For example, if he has the string "coolmike", in one move he can transform it into the string "oolmikec".

Now Mike asks himself: what is minimal number of moves that he needs to do in order to make all the strings equal?

Input

The first line contains integer n (1 ≤ n ≤ 50) — the number of strings.

This is followed by n lines which contain a string each. The i-th line corresponding to string si. Lengths of strings are equal. Lengths of each string is positive and don‘t exceed 50.

Output

Print the minimal number of moves Mike needs in order to make all the strings equal or print  - 1 if there is no solution.

Examples

input

4
xzzwo
zwoxz
zzwox
xzzwo

output

5

input

2
molzv
lzvmo

output

2

input

3
kc
kc
kc

output

0

input

3
aa
aa
ab

output

-1

Note

In the first sample testcase the optimal scenario is to perform operations in such a way as to transform all strings into "zwoxz".

Means:

给定n个字符串,每次变换字符串只能把首字母放到尾部,现在问你能不能用最少次数变换

Solve:

数据规模比较小,直接模拟,用第一个串枚举可能形成的串,然后枚举下面其他串的移动

Code:

 1 #include <bits/stdc++.h> 2 using namespace std; 3 static const int MAXN = 166; 4 static const int oo = 0x3fffffff; 5 int n; 6 string data[MAXN]; 7 int main() 8 { 9     //freopen("D:\\系统优化\\Desktop\\littlepea\\in.data" , "r" , stdin);10     scanf("%d" , &n);11     cin >> data[0];12     int len = data[0].size();13     data[0] += data[0];14     for(int i = 1 ; i < n ; ++i)15     {16         cin >> data[i];17         data[i] += data[i];18     }19     int ol = len;20     len <<= 1;21     int ans = oo;22     bool have = 0;23     for(int i = 0 ; i < ol ; ++i)24     {25         int j;26         int tp = i;27         string pp = data[0].substr(i , ol);28         for(j = 1 ; j < n ; ++j)29         {30             bool flag = 0;31             for(int k = 0 ; k < ol ; ++k)32             {33                 string wp = data[j].substr(k , ol);34                 if(wp == pp)35                 {//printf("%d %d\n" , k , i);36                     flag = 1;37                     tp += k;38                     break;39                 }40             }41             if(!flag)42                 break;43         }44         if(j == n)45             have = 1 , ans = min(ans , tp);46     }47     if(!have)48         puts("-1");49     else50         printf("%d\n" , ans);51 }

View Code

C. Mike and gcd problem(分析结论)

Mike has a sequence A = [a1, a2, ..., an] of length n. He considers the sequence B = [b1, b2, ..., bn] beautiful if the gcd of all its elements is bigger than 1, i.e. .

Mike wants to change his sequence in order to make it beautiful. In one move he can choose an index i (1 ≤ i < n), delete numbers ai, ai + 1 and put numbers ai - ai + 1, ai + ai + 1 in their place instead, in this order. He wants perform as few operations as possible. Find the minimal number of operations to make sequence A beautiful if it‘s possible, or tell him that it is impossible to do so.

 is the biggest non-negative number d such that d divides bi for every i (1 ≤ i ≤ n).

Input

The first line contains a single integer n (2 ≤ n ≤ 100 000) — length of sequence A.

The second line contains n space-separated integers a1, a2, ..., an (1 ≤ ai ≤ 109) — elements of sequence A.

Output

Output on the first line "YES" (without quotes) if it is possible to make sequence A beautiful by performing operations described above, and "NO" (without quotes) otherwise.

If the answer was "YES", output the minimal number of moves needed to make sequence A beautiful.

Examples

input

2
1 1

output

YES
1

input

3
6 2 4

output

YES
0

input

2
1 3

output

YES
1

Note

In the first example you can simply make one move to obtain sequence [0, 2] with .

In the second example the gcd of the sequence is already greater than 1.

Means:

给你一串数列,每个数可以这样变,a[i] -> a[i ] - a[i + 1] , a[i + 1] -> a[i] + a[i + 1],问你能不能得到gcd>1的,输出最小步数

Solve:

结论题,使劲猜?首先肯定是YES的,然后如果一个数是奇数,并且它的两边都是奇数,那么需要两步把它变成偶数(1 0 -> 1 1 -> 0 0),如果旁边有奇数,那么一起搞掉只要1步,然后再跳到旁边

Code:

 1 #include <bits/stdc++.h> 2 using namespace std; 3 typedef __int64 LL; 4 static const int MAXN = 1e6 + 10; 5 int n; 6 LL data[MAXN]; 7 int main(int argc, char const *argv[]) 8 { 9     //freopen("D:\\系统优化\\Desktop\\littlepea\\in.data" , "r" , stdin);10     scanf("%d" , &n);11     for(int i = 1 ; i <= n ; ++i)12         scanf("%d" , data + i);13     LL g = __gcd(data[1] , data[2]);14     for(int i = 3 ; i <= n ; ++i)15         g = __gcd(data[i] , g);16     puts("YES");17     LL ans = 0;18     if(g != 1)19     {20         puts("0");21         return 0;22     }23     for(int i = 1 ; i <= n ; ++i)24     {25         if(data[i] & data[i + 1] & 1)26             ++ans , ++i;27         else if(data[i] & 1)28             ans += 2;29     }30     printf("%d\n" , ans);31     return 0;32 }

View Code

D. Mike and distribution(random_shuffle随机排序)

Mike has always been thinking about the harshness of social inequality. He‘s so obsessed with it that sometimes it even affects him while solving problems. At the moment, Mike has two sequences of positive integers A = [a1, a2, ..., an] and B = [b1, b2, ..., bn] of length neach which he uses to ask people some quite peculiar questions.

To test you on how good are you at spotting inequality in life, he wants you to find an "unfair" subset of the original sequence. To be more precise, he wants you to select k numbers P = [p1, p2, ..., pk] such that 1 ≤ pi ≤ n for 1 ≤ i ≤ k and elements in P are distinct. Sequence P will represent indices of elements that you‘ll select from both sequences. He calls such a subset P "unfair" if and only if the following conditions are satisfied: 2·(ap1 + ... + apk) is greater than the sum of all elements from sequence A, and 2·(bp1 + ... + bpk) isgreater than the sum of all elements from the sequence B. Also, k should be smaller or equal to  because it will be to easy to find sequence P if he allowed you to select too many elements!

Mike guarantees you that a solution will always exist given the conditions described above, so please help him satisfy his curiosity!

Input

The first line contains integer n (1 ≤ n ≤ 105) — the number of elements in the sequences.

On the second line there are n space-separated integers a1, ..., an (1 ≤ ai ≤ 109) — elements of sequence A.

On the third line there are also n space-separated integers b1, ..., bn (1 ≤ bi ≤ 109) — elements of sequence B.

Output

On the first line output an integer k which represents the size of the found subset. k should be less or equal to .

On the next line print k integers p1, p2, ..., pk (1 ≤ pi ≤ n) — the elements of sequence P. You can print the numbers in any order you want. Elements in sequence P should be distinct.

Example

input

5
8 7 4 8 3
4 2 5 3 7

output

3
1 4 5

Means:

给你一串数列A,一串数列B,问你能否使得数列A、B取相同位置上的数(不超过[n/2+1]个),A数列取的数的相加两倍大于A所有数的和,B也一样

Solve:

贪心GG了,看了大神写的,玄学啊。。。Random_shuffle随机排序也能,学到新姿势了

Code:

 1 #include <bits/stdc++.h> 2 using namespace std; 3 typedef __int64 LL; 4 static const int MAXN = 1e5; 5 LL a[MAXN] , b[MAXN]; 6 int pos[MAXN]; 7 LL suma , sumb; 8 int n; 9 int main(int argc, char const *argv[])10 {11     //freopen("D:\\系统优化\\Desktop\\littlepea\\in.data" , "r" , stdin);12     scanf("%d" , &n);13     for(int i = 0 ; i < n ; ++i)14     {15         scanf("%I64d" , a + i);16         suma += a[i];17         a[i] <<= 1;18     }19     for(int i = 0 ; i < n ; ++i)20     {21         scanf("%lld" , b + i);22         sumb += b[i];23         b[i] <<= 1;24         pos[i] = i;25     }26     int p = n / 2 + 1;27     srand(time(0));28     while(1)29     {30         LL s1 , s2;31         s1 = s2 = 0;32         random_shuffle(pos , pos + n);33         for(int i = 0 ; i < p ; ++i)34             s1 += a[pos[i]] , s2 += b[pos[i]];35         if(s1 > suma && s2 >sumb)36         {37             printf("%d\n" , p);38             for(int i = 0 ; i < p ; ++i)39                 printf("%d " , pos[i] + 1);40             return 0;41         }42     }43     return 0;44 }

View Code

Codeforces Round #410 (Div. 2)