Codeforces Round #410 (Div. 2)(A,字符串,水坑,B,暴力枚举,C,思维题,D,区间贪心)

A. Mike and palindrome

time limit per test:2 seconds

memory limit per test:256 megabytes

input:standard input

output:standard output

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
题目链接:http://codeforces.com/contest/798/problem/A
题意:
改变一个字符,让这组字符串变成回文序列,能的话输出YES,不能输出NO
分析:
这道题有点坑,应该是卡了三组数据,aa输出NO,a输出YES,aba也输出YES,估计过了这三组,就可以AC了吧
这题我的做法是分奇偶性,判断条件s[i]==s[len-i-1]是否成立,成立的话ans++,然后判断奇数项长度ans==(len)/2-1||ans==len/2是否成立,成立输出YES,否则输出NO
偶数项长度只需判断ans==(len)/2-1是否成立,成立为YES,否则为NO
下面给出AC代码:
 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 int main()
 4 {
 5     char s[20];
 6     while(cin>>s)
 7     {
 8         int len=strlen(s);
 9         for(int i=0;i<len;i++)
10         {
11             for(int j='a';j<='z';j++)
12             {
13                 if(s[i]==j)
14                     continue;
15             }
16         }
17         int ans=0;
18         if(len%2!=0)
19         {
20             for(int i=0;i<(len)/2;i++)
21             {
22                 if(s[i]==s[len-i-1])
23                     ans++;
24             }
25             if(ans==(len)/2-1||ans==len/2)
26                 cout<<"YES"<<endl;
27             else cout<<"NO"<<endl;
28 
29         }
30         else if(len%2==0)
31         {
32         for(int i=0;i<(len)/2;i++)
33         {
34                 if(s[i]==s[len-i-1])
35                     ans++;
36         }
37             if(ans==(len)/2-1)
38                 cout<<"YES"<<endl;
39             else cout<<"NO"<<endl;
40         }
41     }
42     return 0;
43 }

B. Mike and strings

time limit per test:2 seconds

memory limit per test:256 megabytes

input:standard input

output:standard output

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".

题目链接:http://codeforces.com/contest/798/problem/B

题意:

枚举一个字符串为标准,求答案,找最小

分析:

调用一个substr函数,具体函数详解请参看http://www.cnblogs.com/ECJTUACM-873284962/p/6763801.html

下面给出AC代码:

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 void change(string &s)
 4 {
 5     s=s.substr(1)+s.substr(0,1);//字符串截取函数,这里的目的就是一个一个换字符,找最小次数
 6 }
 7 int main()
 8 {
 9     int n;
10     while(cin>>n)
11     {
12         string s[n];
13         for(int i=0;i<n;i++)
14             cin>>s[i];
15         int ans=1e+8;
16         int sum;
17         for(int i=0;i<n;i++)
18         {
19             sum=0;
20             for(int j=0;j<n;j++)
21             {
22                 string t=s[j];
23                 while(t!=s[i])
24                 {
25                     change(t);
26                     sum++;
27                     if(sum>3000)
28                     {
29                         ans=-1;
30                         break;
31                     }
32                 }
33             }
34             ans=min(ans,sum);
35         }
36         cout<<ans<<endl;
37     }
38     return 0;
39 }

C. Mike and gcd problem

time limit per test:2 seconds

memory limit per test:256 megabytes

input:standard input

output:standard output

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.

题目链接:http://codeforces.com/contest/798/problem/C

分析:

容易发现对于两个数连续做2次之后就都是偶数。2个奇数操作一次就成为偶数。 先对本身所有数求gcd,如果有公共因子则已经成立,不然就按照上述规则,将所有数变为偶数。

下面给出AC代码:

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 const int maxn=1e+7;
 4 int gcd(int a,int b)
 5 {
 6     return b==0?a:gcd(b,a%b);
 7 }
 8 int a[maxn];
 9 int main()
10 {
11     int n,i;
12     cin>>n;
13     for(int i=0;i<n;i++)
14     cin>>a[i];
15     int gccd=a[0];
16     for(i=1;i<n;i++)
17     {
18         gccd=gcd(gccd,a[i]);
19         if(gccd==1)
20             break;
21     }
22     if(i==n)
23     {
24         cout<<"YES"<<endl<<0<<endl;
25         return 0;
26     }
27     else
28     {
29         int c=0,cnt=0;
30         a[n]=0;
31         for(i=0;i<=n;i++)
32         {
33             if(a[i]%2!=0)
34                 cnt++;//求这组数中有多少个奇数
35             else
36             {
37                 c+=(cnt/2);
38                 cnt%=2;
39                 if(cnt!=0)
40                     c+=2;//一个奇数要变2次到偶数
41                 cnt=0;
42             }
43         }
44         cout<<"YES"<<endl<<c<<endl;
45     }
46     return 0;
47 }

D. Mike and distribution

time limit per test:2 seconds

memory limit per test:256 megabytes

input:standard input

output:standard output

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 n each 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) is greater 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

题目链接:http://codeforces.com/contest/798/problem/D

题意:

给定两个数组大小为n的数组a,b,让你从里面拿k个,使得对于每个数组,拿的元素之和的二倍大于整个数组的元素之和,其中k<=n/2+1

分析:

实在是太套路的一个题目……只描述奇数的情况,偶数随便取一个数之后就变成了奇数的情况。按A排序,取第一个。之后下标2k,2k+1两个数取其中b大的。按这种构造方法得到的即为符合题意的解。

下面给出AC代码:

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 const int maxn=1e+6;
 4 struct node
 5 {
 6     int a,b,j;
 7 }p[maxn];
 8 bool cmp(node c,node d)
 9 {
10     if(c.a!=d.a)
11         return c.a>d.a;
12     else return c.b>d.b;
13 }
14 int main()
15 {
16     int n;
17     while(scanf("%d",&n)!=EOF)
18     {
19         for(int i=1;i<=n;i++)
20         {
21             scanf("%d",&p[i].a);
22             p[i].j=i;
23         }
24         for(int i=1;i<=n;i++)
25             scanf("%d",&p[i].b);;
26         sort(p+1,p+1+n,cmp);
27         printf("%d\n",n/2+1);
28         printf("%d ",p[1].j);
29         for(int i=1;i<=(n-1)/2;i++)
30         {
31             if(p[2*i].b>p[2*i+1].b)
32                 printf("%d ",p[2*i].j);
33             else printf("%d ",p[2*i+1].j);
34         }
35         if(n%2==0)
36             printf("%d ",p[n].j);
37         printf("\n");
38     }
39     return 0;
40 }

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏Golang语言社区

Go语言实现冒泡和快速排序

冒泡和快速排序都属于交换类排序,所谓交换排序是指借助数据元素之间互相交换进行排序的方法。 冒泡排序法 冒泡排序法是一种最简单的交换类排序方法,它是通过相邻数据的...

33460
来自专栏顶级程序员

各大排序算法性能比较及演示实例

所谓排序,即将原来无序的一个序列重新排列成有序的序列。 排序方法中涉及到稳定性,所谓稳定性,是指待排序的序列中有两个或两个以上相同的项,在排序前和排序后看这些相...

368100
来自专栏TensorFlow从0到N

讨厌算法的程序员 7 - 归并排序的时间复杂度分析

? 递归树 上一篇归并排序基于分治思想通过递归的调用自身完成了排序,本篇是关于归并排序的最后一部分——分析其时间复杂度。 这个过程中会解释清楚在各种时间复杂度...

26160
来自专栏老九学堂

常用排序算法总结

一种是比较排序,时间复杂度O(nlogn) ~ O(n^2),主要有:冒泡排序,选择排序,插入排序,归并排序,堆排序,快速排序等。

16230
来自专栏轮子工厂

快速搞定8大排序算法

11220
来自专栏Golang语言社区

Go语言实现冒泡和快速排序

冒泡和快速排序都属于交换类排序,所谓交换排序是指借助数据元素之间互相交换进行排序的方法。 冒泡排序法 冒泡排序法是一种最简单的交换类排序方法,它是通过相邻数据的...

36370
来自专栏糊一笑

非比较排序算法总结与实现

之前一篇文章介绍了几种常用的比较排序算法,下面介绍的是几种非比较排序算法。 非比较排序算法内部引用的都是计数排序,当然你也可以将计数排序换为其他的比较排序算法。...

32780
来自专栏苦逼的码农

从0打卡leetcode之day9--字符串转整型

好久没更新了,今天是开学的第一天,这学期选了门算法的课,打算好好刷下《算法导论》这本书,可能接下来会一边分享leetcode的刷题贴,一边分享自己在书上所学的一...

9430
来自专栏玄魂工作室

面试题解:输入一个数A,找到大于A的一个最小数B,且B中不存在连续相当的两个数字

昨天发的算法有一处情况没考虑到,比如加一后有进位,导致又出现重复数字的情况,修正后今天重新发一次。

13910
来自专栏chenjx85的技术专栏

leetcode-908-最小差值 I

给定一个整数数组 A,对于每个整数 A[i],我们可以选择任意 x 满足 -K <= x <= K,并将 x 加到 A[i] 中。

18620

扫码关注云+社区

领取腾讯云代金券