本场战绩：+451

题目如下：

A. Make Even

time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard output

Polycarp has an integer nn that doesn't contain the digit 0. He can do the following operation with his number several (possibly zero) times:

• Reverse the prefix of length ll (in other words, ll leftmost digits) of nn. So, the leftmost digit is swapped with the ll-th digit from the left, the second digit from the left swapped with (l−1)-th left, etc. For example, if n=123456789 and l=5, then the new value of nn will be 543216789.

Note that for different operations, the values of ll can be different. The number ll can be equal to the length of the number n — in this case, the whole number nn is reversed.

Polycarp loves even numbers. Therefore, he wants to make his number even. At the same time, Polycarp is very impatient. He wants to do as few operations as possible.

Help Polycarp. Determine the minimum number of operations he needs to perform with the number nn to make it even or determine that this is impossible.

You need to answer tt independent test cases.

Input

The first line contains the number tt (1≤t≤104) — the number of test cases.

Each of the following tt lines contains one integer n (1≤n<1091). It is guaranteed that the given number doesn't contain the digit 0.

Output

Print tt lines. On each line print one integer — the answer to the corresponding test case. If it is impossible to make an even number, print -1.

Note

In the first test case, n=3876, which is already an even number. Polycarp doesn't need to do anything, so the answer is 0.

In the second test case, n=387. Polycarp needs to do 22 operations:

1. Select l=2l=2 and reverse the prefix 387. The number nn becomes 837. This number is odd.
2. Select l=3l=3 and reverse the prefix 837. The number nn becomes 738. This number is even.

It can be shown that 22 is the minimum possible number of operations that Polycarp needs to do with his number to make it even.

In the third test case, n=4489. Polycarp can reverse the whole number (choose a prefix of length l=4). It will become 9844and this is an even number.

In the fourth test case, n=3. No matter how hard Polycarp tried, he would not be able to make an even number.

题意分析及解题思路：

题意很简单，一个数，每次都让其前n个数字倒序，问最少几次能让它变成一个偶数。

很显然，有四种情况，一、这个数本身是偶数，输出0.二、这个数每一位数字都是奇数，那么不可能能转成偶数，输出-1。三、这个数字的第一位数字为偶数，最后一位为奇数，那么直接整个倒序即可，输出1.四、头尾均为奇数，中间有偶数，那么先通过一次倒序把这个偶数弄到第一位，然后再一次转到最后，也就是2次，输出2。总而言之水题，代码：

#include
using namespace std;

int main()
{
int t;
cin >> t;
while (t--)
{
string str;
cin >> str;
int temp = -1;
int n;
for (int i = 0; i < str.size(); i++)
{
n = str[i] - '0';
if (n % 2 == 0)
{
temp = 2;
break;
}
}
n = str[0] - '0';
if (n % 2 == 0)
{
temp = 1;
}
n = str[str.size() - 1] - '0';
if (n % 2 == 0)
{
temp = 0;
}
cout << temp << endl;
}
return 0;
}

B. Team Composition: Programmers and Mathematicians

time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard output

The All-Berland Team Programming Contest will take place very soon. This year, teams of four are allowed to participate.

There are a programmers and b mathematicians at Berland State University. How many maximum teams can be made if:

• each team must consist of exactly 4 students,
• teams of 4 mathematicians or 4 programmers are unlikely to perform well, so the decision was made not to compose such teams.

Thus, each team must have at least one programmer and at least one mathematician.

Print the required maximum number of teams. Each person can be a member of no more than one team.

Input

The first line contains an integer tt (1≤t≤104) —the number of test cases.

This is followed by descriptions of tt sets, one per line. Each set is given by two integers aa and bb (0≤a,b≤109).

Output

Print tt lines. Each line must contain the answer to the corresponding set of input data — the required maximum number of teams.

Note

In the first test case of the example, two teams can be composed. One way to compose two teams is to compose two teams of 2 programmers and 2 mathematicians.

In the second test case of the example, only one team can be composed: 3 programmers and 1 mathematician in the team。

题意分析及解题思路：

输入两个数代表科学家和数学家的数量，他们要四个人一组去旅游，这四个人中间必须要有一个数学家一个科学家才行，问一共能组成几个队。

也是水题，比较2个值就行了，一个是(a+b)/4，还有一个是两个中的较小值，输出这两个数的较小值就是答案。

代码：

#include
#include
#include
#include

using namespace std;

int main()
{
int t;
cin>>t;
int a,b;
int temp;
while(t--)
{
cin>>a>>b;
temp=(a+b)/4;
if(a>b)swap(a,b);
if(temp>=a)cout<<a;
else cout<<temp;
cout<<endl;
}
}

C. Polycarp Recovers the Permutation

time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

Polycarp wrote on a whiteboard an array p of length n, which is a permutation of numbers from 1 to n. In other words, in pp each number from 1 to nn occurs exactly once.

He also prepared a resulting array a, which is initially empty (that is, it has a length of 0).

After that, he did exactly nn steps. Each step looked like this:

• Look at the leftmost and rightmost elements of p, and pick the smaller of the two.
• If you picked the leftmost element of p, append it to the left of a; otherwise, if you picked the rightmost element of p, append it to the right of a.
• The picked element is erased from p.

Note that on the last step, p has a length of 1 and its minimum element is both leftmost and rightmost. In this case, Polycarp can choose what role the minimum element plays. In other words, this element can be added to a both on the left and on the right (at the discretion of Polycarp).

Let's look at an example. Let n=4, p=[3,1,4,2]. Initially a=[]. Then:

• During the first step, the minimum is on the right (with a value of 2), so after this step, p=[3,1,4] and a=[2] (he added the value 2 to the right).
• During the second step, the minimum is on the left (with a value of 3), so after this step, p=[1,4] and a=[3,2] (he added the value 3 to the left).
• During the third step, the minimum is on the left (with a value of 1), so after this step, p=[4] and a=[1,3,2] (he added the value 1 to the left).
• During the fourth step, the minimum is both left and right (this value is 4). Let's say Polycarp chose the right option. After this step, p=[] and a=[1,3,2,4] (he added the value 44 to the right).

Thus, a possible value of aa after n steps could be a=[1,3,2,4].

You are given the final value of the resulting array a. Find any possible initial value for p that can result the given a, or determine that there is no solution.

Input

The first line of the input contains an integer tt (1≤t≤104) — the number of test cases in the test.

Each test case consists of two lines. The first of them contains an integer nn (1≤n≤2⋅105) — the length of the array a. The second line contains n integers a1,a2,…,an (1≤ai≤n) — the elements of the array aa. All elements of the aa array are distinct numbers.

It is guaranteed that the sum of the values nn over all test cases in the test does not exceed 2⋅105.

Output

Print tt lines, each of the lines must contain the answer to the corresponding set of input data: numbers p1,p2,…,pn  — any of the possible initial values of the array p, which will lead to the given array aa. All elements of pp are distinct integers from 1 to nn. Thus, if there are several solutions, print any. If there is no solution, then print -1 on the line.

题意分析及解题思路：

这是道很有意思的题目，首先要了解以下的概念，给你一个由1到n组成的乱序数字，如n=4，p=[3 1 4 2],接下来将p数组中的头和尾元素进行比较，2<3，并且2在p的右边，那么就把2这个元素插入一个新数组a=[](初始为空)的右边，a=[2]，接下来p=[3 1 4],3<4,并且3在p的左边，把3插入a的左边，a=[3 2]。如此以往，直到p中只剩下一个元素4，把它放在a的左边或者右边都可以，也就是a=[1 3 2 4]或a=[4 1 3 2]都是可以的。

了解了这个概念以后，现在给你转换后的a数组，问你能不能找出初始的p数组，经过这个转换以后能变成现在的a数组。

首先要排除暴力反推的方法，因为肯定会超时(经常尝试也确实是超时了)，所以这题肯定是通过找规律的方法做的

确定这个思路以后，我们首先要思考，什么样的数组a是没有对应的p的？

认真观察推导a的过程，我们不难看出啊，每次都是找出小的那个值插到a里面去的，这说明什么？说明什么？说明最大的值肯定会留到最后，也就是最大的值肯定在a数组的头或者尾。那么只要头和尾都不是n的a，肯定是没有对应的p的。其次，再仔细观察，每次比较之后都是较小值插入进去，较大值留下，其实每个数都是在和大值的比较之后被插入进入，也就是相当于对于最大值逆序了一遍。所以我们只要分最大值在左和在右的两种情况，将其他的a倒序输出，得到的就是对应的p(这个规律比较难理解，需要慢慢通过例子推才能知道)。

代码：

#include
using namespace std;

int num1[200000];

int main()
{
int t;
cin >> t;
while (t--)
{
int b; cin >> b;

    for (int i = 0; i < b; i++)  
    {  
        cin >> num1\[i\];  
    }  
    if (num1\[b - 1\] != b && num1\[0\] != b)  
    {  
        cout << -1 << endl; continue;  
    }  
    if (b == 1 && num1\[0\] == b) cout << b;  
    else if (num1\[0\] == b) {  
        cout << num1\[0\] << " ";  
        for (int i = 0; i < b - 1; i++)  
        {  
            cout << num1\[b - 1 - i\] << " ";  
        }  
        cout << endl;  
    }  
    else if (num1\[b - 1\] == b) {  
        for (int i = 0; i < b - 1; i++)  
        {  
            cout << num1\[b - 2 - i\] << " ";  
        }  
        cout << num1\[b - 1\];  
    }  
    cout << endl;  
}  
return 0;  

}

总结：

这场基本都是找规律的题目，分清几种情况，弄出来就行了，就是有些题目的规模比较难想明白，需要慢慢琢磨。