B2. Palindrome Game (hard version)
The only difference between the easy and hard versions is that the given string s in the easy version is initially a palindrome, this condition is not always true for the hard version.

A palindrome is a string that reads the same left to right and right to left. For example, "101101" is a palindrome, while "0101" is not.

Alice and Bob are playing a game on a string s of length n consisting of the characters '0' and '1'. Both players take alternate turns with Alice going first.

In each turn, the player can perform one of the following operations:

Choose any i (1≤i≤n), where s[i]= '0' and change s[i] to '1'. Pay 1 dollar.
Reverse the whole string, pay 0 dollars. This operation is only allowed if the string is currently not a palindrome, and the last operation was not reverse. That is, if Alice reverses the string, then Bob can't reverse in the next move, and vice versa.
Reversing a string means reordering its letters from the last to the first. For example, "01001" becomes "10010" after reversing.

The game ends when every character of string becomes '1'. The player who spends minimum dollars till this point wins the game and it is a draw if both spend equal dollars. If both players play optimally, output whether Alice wins, Bob wins, or if it is a draw.

Input
The first line contains a single integer t (1≤t≤103). Then t test cases follow.

The first line of each test case contains a single integer n (1≤n≤103).

The second line of each test case contains the string s of length n, consisting of the characters '0' and '1'. It is guaranteed that the string s contains at least one '0'.

Note that there is no limit on the sum of n over test cases.

Output
For each test case print a single word in a new line:

"ALICE", if Alice will win the game,
"BOB", if Bob will win the game,
"DRAW", if the game ends in a draw.
Example
inputCopy
3
3
110
2
00
4
1010
outputCopy
ALICE
BOB
ALICE
Note
In the first test case of example,

in the 1-st move, Alice will use the 2-nd operation to reverse the string, since doing the 1-st operation will result in her loss anyway. This also forces Bob to use the 1-st operation.
in the 2-nd move, Bob has to perform the 1-st operation, since the 2-nd operation cannot be performed twice in a row. All characters of the string are '1', game over.
Alice spends 0 dollars while Bob spends 1 dollar. Hence, Alice wins.
In the second test case of example,

in the 1-st move Alice has to perform the 1-st operation, since the string is currently a palindrome.
in the 2-nd move Bob reverses the string.
in the 3-rd move Alice again has to perform the 1-st operation. All characters of the string are '1', game over.
Alice spends 2 dollars while Bob spends 0 dollars. Hence, Bob wins.

题解：本题题意就是两个人玩游戏，要注意两条规则：1.花一元钱使字符串中0变成一2.在字符串是非回文并且上一步没有反转情况下，反转字符串（反转：将字符串倒置）。
最终字符串全变成一时，谁花钱的少谁赢，输出赢得那个人的名字。
思路：分成两种情况：1.初始字符串为回文时，列举情况2.不是回文时，列举情况。
总结：本题思维多一点，想明白游戏的本质有点难度，多加练习吧。
代码如下：

```cpp
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll nl=1e5+5;
bool find(string a){//判断是否为回文字符串
ll ml=0;
for(ll i=0;i<a.size()/2;i++){
if(a[i]!=a[a.size()-i-1]){
ml=1;
break;
}
}
if(ml==1){
return false;
}else{
return true;
}
}
ll fl(string a){//判断有几对不对称的字符。
ll ml=0;
for(ll i=0;i<a.size()/2;i++){
if(a[i]!=a[a.size()-i-1]){
ml++;
}
}
return ml;
}
int main(){
ll t;
cin>>t;
while(t--){
ll n;
cin>>n;
string s;
cin>>s;
ll i,j;
ll f=0;
string sl="";
ll cl=0;
for(i=0;i<n;i++){
if(s[i]=='0'){
cl++;
}
}
if(find(s)==true){//初始字符串为回文
if(cl%2==0){//当0的个数为偶数时，首先第一个人必须先花钱，而第二个人继续花钱使字符串又变成回文，这样直到最后剩下两个0时，第二个人可以选择反转，这样就赢了。
cout<<"BOB"<<endl;
}else{
if(cl==1){//这种情况第一个必须花钱，所以第二个人直接胜出。
cout<<"BOB"<<endl;
}else{//这种情况中间那个数一定为0，第一个人可以令中间那个0变成1，这样字符串还是回文，然后同理。。。
cout<<"ALICE"<<endl;
}

}
}else{
if(cl==2){
ll f=0;
if(fl(s)==1){//如果有一对不对称的字符，则平手
cout<<"DRAW"<<endl;
}else{//这种情况改变一对字符串，字符串依然不是回文，所以第一个人赢
cout<<"ALICE"<<endl;
}

}else{//当cl为1时，第一个人反转；不为1时，第一个人可以在字符串选择在字符串差一对变成回文时花钱，其他情况反转即可。
cout<<"ALICE"<<endl;
}
}
}
}
```
C. Sequence Pair Weight
The weight of a sequence is defined as the number of unordered pairs of indexes (i,j) (here i<j) with same value (ai=aj). For example, the weight of sequence a=[1,1,2,2,1] is 4. The set of unordered pairs of indexes with same value are (1,2), (1,5), (2,5), and (3,4).

You are given a sequence a of n integers. Print the sum of the weight of all subsegments of a.

A sequence b is a subsegment of a sequence a if b can be obtained from a by deletion of several (possibly, zero or all) elements from the beginning and several (possibly, zero or all) elements from the end.

Input
Each test contains multiple test cases. The first line contains the number of test cases t (1≤t≤105). Description of the test cases follows.

The first line of each test case contains a single integer n (1≤n≤105).

The second line of each test case contains n integers a1,a2,…,an (1≤ai≤109).

It is guaranteed that the sum of n over all test cases does not exceed 105.

Output
For each test case, print a single integer — the sum of the weight of all subsegments of a.

Example
inputCopy
2
4
1 2 1 1
4
1 2 3 4
outputCopy
6
0
Note
In test case 1, all possible subsegments of sequence [1,2,1,1] having size more than 1 are:
[1,2] having 0 valid unordered pairs;
[2,1] having 0 valid unordered pairs;
[1,1] having 1 valid unordered pair;
[1,2,1] having 1 valid unordered pairs;
[2,1,1] having 1 valid unordered pair;
[1,2,1,1] having 3 valid unordered pairs.
Answer is 6.
In test case 2, all elements of the sequence are distinct. So, there is no valid unordered pair with the same value for any subarray. Answer is 0.

题解：本题就是求数组的所有子数组的相同数字的和。
思路：一对一对的计算，对于每一对计算它的贡献。
总结：没想到这样做，思路还是窄。
代码如下：

```cpp
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll nl=1e5+5;
map<ll,ll>m;//其作用是不断加入新的端点
ll a[nl];
int main(){
ll t;
cin>>t;
while(t--){
ll n;
cin>>n;
ll i,j;
ll ans=0;
for(i=1;i<=n;i++){
cin>>a[i];
}
for(i=1;i<=n;i++){
ans+=m[a[i]]*(n-i+1);//（左边可以包含的数据个数*右边的）
m[a[i]]+=i;//这里要加入新的左端点。
}
cout<<ans<<endl;
m.clear();
}
}
```
B. Combination
Ilya plays a card game by the following rules.

A player has several cards. Each card contains two non-negative integers inscribed, one at the top of the card and one at the bottom. At the beginning of the round the player chooses one of his cards to play it. If the top of the card contains number ai, and the bottom contains number bi, then when the player is playing the card, he gets ai points and also gets the opportunity to play additional bi cards. After the playing the card is discarded.

More formally: let's say that there is a counter of the cards that can be played. At the beginning of the round the counter equals one. When a card is played, the counter decreases by one for the played card and increases by the number bi, which is written at the bottom of the card. Then the played card is discarded. If after that the counter is not equal to zero, the player gets the opportunity to play another card from the remaining cards. The round ends when the counter reaches zero or the player runs out of cards.

Of course, Ilya wants to get as many points as possible. Can you determine the maximum number of points he can score provided that you know his cards?

Input
The first line contains a single integer n (1 ≤ n ≤ 1000) — the number of cards Ilya has.

Each of the next n lines contains two non-negative space-separated integers — ai and bi (0 ≤ ai, bi ≤ 104) — the numbers, written at the top and the bottom of the i-th card correspondingly.

Output
Print the single number — the maximum number of points you can score in one round by the described rules.

Examples
inputCopy
2
1 0
2 0
outputCopy
2
inputCopy
3
1 0
2 0
0 2
outputCopy
3
Note
In the first sample none of two cards brings extra moves, so you should play the one that will bring more points.

In the second sample you should first play the third card that doesn't bring any points but lets you play both remaining cards.

题解：每一张牌上都有两个数，a,b。a代表牌的值，b代表可以在出几张牌。有一个记牌器，初始为数字1，b可以加在记牌器上，每出一张牌，记牌器数字减1，当记牌器数字为零时，一个回合结束。求一个回合所出牌的最大累加值是多少。
思路：这个题还是思维，看透本质不难，难的是看透本质的过程。计算出所有牌的数字b的和，如果b>=n-1，直接将n张牌的数字a累加就是所求；b<n-1,则将数字b不为0的牌的数字a累加，最后在加上数字b为0的牌中数字a最大的牌就是所求。
总结：一开始对一回合没有理解透彻，没想到它其实是递归的过程，后来想用递归做，但其实没有必要用递归。
代码如下：

```cpp
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll nl=1e3+5;
struct node{
ll a;
ll b;
}v[nl];
bool cmp1(node al,node bl){//b值大的放前面，b值相等的情况下a值大的放前面。
if(al.b!=bl.b){
return al.b>bl.b;
}else{
return al.a>bl.a;
}
}
ll num=0;
ll n;
int main(){
cin>>n;
ll i,j;
ll sum=0;
for(i=0;i<n;i++){
cin>>v[i].a;
cin>>v[i].b;
sum+=v[i].b;
}
sort(v,v+n,cmp1);
if(sum<n-1){
for(i=0;i<sum;i++){
num+=v[i].a;
}
num+=v[sum].a;//这里画个图就可以理解了
}else{
for(i=0;i<n;i++){
num+=v[i].a;
}
}
cout<<num;
}
```
B. Burning Midnight Oil
One day a highly important task was commissioned to Vasya — writing a program in a night. The program consists of n lines of code. Vasya is already exhausted, so he works like that: first he writes v lines of code, drinks a cup of tea, then he writes as much as lines, drinks another cup of tea, then he writes lines and so on: , , , ...

The expression is regarded as the integral part from dividing number a by number b.

The moment the current value equals 0, Vasya immediately falls asleep and he wakes up only in the morning, when the program should already be finished.

Vasya is wondering, what minimum allowable value v can take to let him write not less than n lines of code before he falls asleep.

Input
The input consists of two integers n and k, separated by spaces — the size of the program in lines and the productivity reduction coefficient, 1 ≤ n ≤ 109, 2 ≤ k ≤ 10.

Output
Print the only integer — the minimum value of v that lets Vasya write the program in one night.

Examples
inputCopy
7 2
outputCopy
4
inputCopy
59 9
outputCopy
54
Note
In the first sample the answer is v = 4. Vasya writes the code in the following portions: first 4 lines, then 2, then 1, and then Vasya falls asleep. Thus, he manages to write 4 + 2 + 1 = 7 lines in a night and complete the task.

In the second sample the answer is v = 54. Vasya writes the code in the following portions: 54, 6. The total sum is 54 + 6 = 60, that's even more than n = 59.
题解：二分水题。
思路：二分法
总结：二分法多练习，不然容易想不到。
代码如下：

```cpp
#include<stdio.h>
int n,k;
int chek(int x)
{
int sum=x;
while(x)
{
sum+=x/k;
x=x/k;
}
//printf("%d\n",sum);
if(sum>=n)
{
return 1;
}
return 0;
}
int main()
{
while(scanf("%d%d",&n,&k)!=EOF)
{
int head=0,tail=n;
while(tail>=head)
{
int mid=(head+tail)/2;
if(chek(mid))
{
tail=mid-1;
}
else
{
head=mid+1;
}
}
printf("%d\n",head);
}

}
```
A. Wizards and Demonstration
Some country is populated by wizards. They want to organize a demonstration.

There are n people living in the city, x of them are the wizards who will surely go to the demonstration. Other city people (n - x people) do not support the wizards and aren't going to go to the demonstration. We know that the city administration will react only to the demonstration involving at least y percent of the city people. Having considered the matter, the wizards decided to create clone puppets which can substitute the city people on the demonstration.

So all in all, the demonstration will involve only the wizards and their puppets. The city administration cannot tell the difference between a puppet and a person, so, as they calculate the percentage, the administration will consider the city to be consisting of only n people and not containing any clone puppets.

Help the wizards and find the minimum number of clones to create to that the demonstration had no less than y percent of the city people.

Input
The first line contains three space-separated integers, n, x, y (1 ≤ n, x, y ≤ 104, x ≤ n) — the number of citizens in the city, the number of wizards and the percentage the administration needs, correspondingly.

Please note that y can exceed 100 percent, that is, the administration wants to see on a demonstration more people that actually live in the city ( > n).

Output
Print a single integer — the answer to the problem, the minimum number of clones to create, so that the demonstration involved no less than y percent of n (the real total city population).

Examples
inputCopy
10 1 14
outputCopy
1
inputCopy
20 10 50
outputCopy
0
inputCopy
1000 352 146
outputCopy
1108
Note
In the first sample it is necessary that at least 14% of 10 people came to the demonstration. As the number of people should be integer, then at least two people should come. There is only one wizard living in the city and he is going to come. That isn't enough, so he needs to create one clone.

In the second sample 10 people should come to the demonstration. The city has 10 wizards. They will all come to the demonstration, so nobody has to create any clones.
题解：本题不难，就是容易错，别忘了给定的x值大于n*y%100的情况，这里真的容易错。

```cpp
#include<bits/stdc++.h>
using namespace std;
#define ll long long
int main(){
ll n,m,k;
cin>>n>>m>>k;
ll i,j;
double z;
z=n*(k*1.0/100);
ll zl;
zl=n*k/100;
if(z*1.0>zl*1.0){//遇到整数与浮点数比较，可以*1.0
zl+=1;//只可能大1
}
if(m>zl){
cout<<"0";
}else{
cout<<zl-m;
}
}
```
B. Growing Mushrooms
Each year in the castle of Dwarven King there is a competition in growing mushrooms among the dwarves. The competition is one of the most prestigious ones, and the winner gets a wooden salad bowl. This year's event brought together the best mushroom growers from around the world, so we had to slightly change the rules so that the event gets more interesting to watch.

Each mushroom grower has a mushroom that he will grow on the competition. Under the new rules, the competition consists of two parts. The first part lasts t1 seconds and the second part lasts t2 seconds. The first and the second part are separated by a little break.

After the starting whistle the first part of the contest starts, and all mushroom growers start growing mushrooms at once, each at his individual speed of vi meters per second. After t1 seconds, the mushroom growers stop growing mushrooms and go to have a break. During the break, for unexplained reasons, the growth of all mushrooms is reduced by k percent. After the break the second part of the contest starts and all mushrooms growers at the same time continue to grow mushrooms, each at his individual speed of ui meters per second. After a t2 seconds after the end of the break, the competition ends. Note that the speeds before and after the break may vary.

Before the match dwarf Pasha learned from all participants, what two speeds they have chosen. However, the participants did not want to disclose to him all their strategy and therefore, did not say in what order they will be using these speeds. That is, if a participant chose speeds ai and bi, then there are two strategies: he either uses speed ai before the break and speed bi after it, or vice versa.

Dwarf Pasha really wants to win the totalizer. He knows that each participant chooses the strategy that maximizes the height of the mushroom. Help Dwarf Pasha make the final table of competition results.

The participants are sorted in the result table by the mushroom height (the participants with higher mushrooms follow earlier in the table). In case of equal mushroom heights, the participants are sorted by their numbers (the participants with a smaller number follow earlier).

Input
The first input line contains four integer numbers n, t1, t2, k (1 ≤ n, t1, t2 ≤ 1000; 1 ≤ k ≤ 100) — the number of participants, the time before the break, the time after the break and the percentage, by which the mushroom growth drops during the break, correspondingly.

Each of the following n lines contains two integers. The i-th (1 ≤ i ≤ n) line contains space-separated integers ai, bi (1 ≤ ai, bi ≤ 1000) — the speeds which the participant number i chose.

Output
Print the final results' table: n lines, each line should contain the number of the corresponding dwarf and the final maximum height of his mushroom with exactly two digits after the decimal point. The answer will be considered correct if it is absolutely accurate.

Examples
inputCopy
2 3 3 50
2 4
4 2
outputCopy
1 15.00
2 15.00
inputCopy
4 1 1 1
544 397
280 101
280 101
693 970
outputCopy
4 1656.07
1 937.03
2 379.99
3 379.99
Note
First example: for each contestant it is optimal to use firstly speed 2 and afterwards speed 4, because 2·3·0.5 + 4·3 > 4·3·0.5 + 2·3.
题解：本题不难，就是用结构体和sort，但是wa了一次。
本题所给样例有迷惑作用，所给时间一样（t1==t2），这样容易忽略时间不相等的情况。
```cpp
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll nl=1e3+5;
struct node{
ll a;
ll b;
double z;
ll id;
}v[nl];
bool cmp(node x,node y){
if(x.z!=y.z){
return x.z>y.z;
}else{
return x.id<y.id;
}
}
int main(){
ll n,t1,t2,k;
cin>>n>>t1>>t2>>k;
ll i,j;
for(i=0;i<n;i++){
cin>>v[i].a;
cin>>v[i].b;

v[i].z=max(v[i].a*1.0*(1.0-k*1.0/100)*t1*1.0+v[i].b*1.0*t2,v[i].b*1.0*(1.0-k*1.0/100)*t1*1.0+v[i].a*1.0*t2);//这里一开始直接比较的v[i].a和v[i].b的大小，忽略了时间的比较，正确做法应加上时间。

v[i].id=i+1;
}
sort(v,v+n,cmp);
for(i=0;i<n;i++){
printf("%lld %.2lf\n",v[i].id,v[i].z);
}
}
```
C. Plant
time limit per test2 seconds
memory limit per test256 megabytes
inputstandard input
outputstandard output
Dwarfs have planted a very interesting plant, which is a triangle directed "upwards". This plant has an amusing feature. After one year a triangle plant directed "upwards" divides into four triangle plants: three of them will point "upwards" and one will point "downwards". After another year, each triangle plant divides into four triangle plants: three of them will be directed in the same direction as the parent plant, and one of them will be directed in the opposite direction. Then each year the process repeats. The figure below illustrates this process.

Help the dwarfs find out how many triangle plants that point "upwards" will be in n years.

Input
The first line contains a single integer n (0 ≤ n ≤ 1018) — the number of full years when the plant grew.

Please do not use the %lld specifier to read or write 64-bit integers in С++. It is preferred to use cin, cout streams or the %I64d specifier.

Output
Print a single integer — the remainder of dividing the number of plants that will point "upwards" in n years by 1000000007 (109 + 7).

Examples
inputCopy
1
outputCopy
3
inputCopy
2
outputCopy
10
Note
The first test sample corresponds to the second triangle on the figure in the statement. The second test sample corresponds to the third
题解：快速幂经典题目
快速幂：指数分成两半，而相应的底数做平方运算
```cpp
int pow3(int x, int n){
if(n == 0) return 1;
int t = 1;
while(n != 0){
if(n & 1) t *= x;
n >>= 1;
x *= x;
}
return t;
}
```
题目代码：
```cpp
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll nl=1e9+7;
int main(){
ll n;
cin>>n;
ll i,j;
ll s=1;
ll t=2;
while(n){
if(n&1){
s=s*t%nl;//取模
}
n>>=1;
t=t*t%nl; //取模
}
cout<<(s*(s+1)/2)%nl;//在最后取模
}
```