A. Erasing Zeroes

You are given a string s. Each character is either 0 or 1.
You want all 1’s in the string to form a contiguous subsegment. For example, if the string is 0, 1, 00111 or 01111100, then all 1’s form a contiguous subsegment, and if the string is 0101, 100001 or 11111111111101, then this condition is not met.
You may erase some (possibly none) 0’s from the string. What is the minimum number of 0’s that you have to erase?

Input

The first line contains one integer t (1≤t≤100) — the number of test cases.
Then t lines follow, each representing a test case. Each line contains one string s (1≤|s|≤100); each character of s is either 0 or 1.

Output

Print t integers, where the i-th integer is the answer to the i-th testcase (the minimum number of 0’s that you have to erase from s).

Example

input

3
010011
0
1111000

output

2
0
0

Note

In the first test case you have to delete the third and forth symbols from string 010011 (it turns into 0111).

Translation

给一个01字符串，我们可以去掉一些0，来获得一串完整的1，问最少要去掉几个0。

Idea

显然，如果字符串中没有1，那么答案是0。如果字符串中有1，我们只要找到最开头的1和最末尾的1，把中间的0去掉就行了。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include<iostream>
#include<string>
using namespace std;
int main()
{
	ios::sync_with_stdio(false);
	int t;
	cin>>t;
	while(t--)
	{
		int p1,p2;
		string s;
		p1=p2=0;
		cin>>s;
		int i;
		int l=s.size();
		for(i=0;i<l;i++)
		{
			if(s[i]=='1')
			{
				p1=i;
				break;
			}
		}
		for(i=l-1;i>=0;i--)
		{
			if(s[i]=='1')
			{
				p2=i;
				break;
			}
		}
		int ans=0;
		if(p1==0&&p2==0) ans=0;
		else
		{
			for(i=p1;i<=p2;i++)
			{			
				if(s[i]=='0') ans++;
			}
		}
		cout<<ans<<endl;
	}
	return 0;
}

B. National Project

Your company was appointed to lay new asphalt on the highway of length n. You know that every day you can either repair one unit of the highway (lay new asphalt over one unit of the highway) or skip repairing.
Skipping the repair is necessary because of the climate. The climate in your region is periodical: there are g days when the weather is good and if you lay new asphalt these days it becomes high-quality pavement; after that, the weather during the next b days is bad, and if you lay new asphalt these days it becomes low-quality pavement; again g good days, b bad days and so on.
You can be sure that you start repairing at the start of a good season, in other words, days 1,2,…,g are good.
You don’t really care about the quality of the highway, you just want to make sure that at least half of the highway will have high-quality pavement. For example, if the n=5 then at least 3 units of the highway should have high quality; if n=4 then at least 2 units should have high quality.
What is the minimum number of days is needed to finish the repair of the whole highway?

Input

The first line contains a single integer T (1⩽T⩽104)(1 \leqslant T \leqslant {10^4}) — the number of test cases.
Next T lines contain test cases — one per line. Each line contains three integers n, g and b (1⩽n,g,b⩽109)(1 \leqslant n,g,b \leqslant {10^9}) — the length of the highway and the number of good and bad days respectively.

Output

Print T integers — one per test case. For each test case, print the minimum number of days required to repair the whole highway if at least half of it should have high quality.

Example

input

3
5 1 1
8 10 10
1000000 1 1000000

output

5
8
499999500000

Note

In the first test case, you can just lay new asphalt each day, since days 1,3,5 are good.
In the second test case, you can also lay new asphalt each day, since days 1-8 are good.

Translation

要修一条高速公路，一开始修时有g个连续好天气，然后接着b个坏天气。之后g个好天气和b个坏天气交替。好天气修的路质量高，坏天气修的路质量差，每天修一个单位的路，要求质量高的路至少占总路程的一半且一定要把路修完，问至少需要花费几天。

Idea Ⅰ

由题意，消耗的天数越多，好天气就越多，这是一个单调的问题，不妨用二分法解决。假设最短需要l=nl = n天，最长需要r=1018r = {10^{18}}。寻找符合的最小的mid。

Code Ⅰ

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include<iostream>
#include<string>
#define ll long long
using namespace std;
void solve()
{
	ll n,g,b;
	cin>>n>>g>>b;
	ll l=n,r=1e18,ans;
	ll need=(n+1)/2;//计算出需要的好天气 
	while(l<=r)
	{
		ll mid=(l+r)/2;
		ll has=mid/(g+b)*g+min(mid%(g+b),g);
		if(has>=need) 
		{
			r=mid-1;
			ans=mid;
		}
		else l=mid+1;
	}
	cout<<ans<<endl;
}
int main()
{
	ios::sync_with_stdio(false);
	int t;
	cin>>t;
	while(t--)
	{
		solve();
	}
	return 0;
}

Postscript

二分的过程非常重要，在此采取了这样的二分。

1
2
3
4
5
6
7
8
9
10
11
while(l<=r)
{
	ll mid=(l+r)/2;
	ll has=mid/(g+b)*g+min(mid%(g+b),g);
	if(has>=need) 
	{
		r=mid-1;
		ans=mid;
	}
	else l=mid+1;
}

如下的二分不可采用：
①当得到ans后死循环。

1
2
3
4
5
6
7
8
while(l<=r)
{
	ll mid=(l+r)/2;
	ll has=mid/(g+b)*g+min(mid%(g+b),g);
	if(has>need) r=mid-1;
	else if(has<need) l=mid+1;
	else ans=mid;      
}

②跳出后得到的不一定是mid的最小值，mid的末尾可能包含几个没用的坏天气。

1
2
3
4
5
6
7
8
9
10
11
12
while(l<=r)
{
    ll mid=(l+r)/2;
    ll has=mid/(g+b)*g+min(mid%(g+b),g);
    if(has>need) r=mid-1;
    else if(has<need) l=mid+1;
    else
    {   
        ans=mid;
        break;                  
    }                          
}

AC代码的二分方式之所以可用，是因为其在找到第一个ans之后再进行二分，之后会因为r减过头了让l增加，最后找到最小的mid，并退出。

Idea Ⅱ

一方面，我们应该整修高速公路，因此我们必须花至少n天的时间来完成它。另一方面，至少有一半应铺设高质量的人行道，即需要在好天气下铺设。
那么，如何计算满足第二个条件的最小天数？铺设n长度的路，我们需要至少<!−−swig8−−>2\fracNaN{2}个好天气，记为need。我们可以把(g+b)看成一个block，需要的块数是<!−−swig9−−><!−−swig10−−>\frac,代表的天数是<!−−swig11−−>g⋅(g+b)\frac{g} \cdot (g + b)，如果g能整除need，那么实际需要的天数可以减少b，因为多出来的b天是坏天气，是浪费的。如果不能整除，那么一定这些天数用完后，路一定还没修完，于是还要加上need%g。

Code Ⅱ

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include<iostream>
using namespace std;
void solve()
{
	long long ans,n,g,b;
	cin>>n>>g>>b;
	long long need=(n+1)>>1;
	ans=need/g*(g+b);
	if(need%g) ans+=need%g;
	else ans-=b;
	ans=max(n,ans);
	cout<<ans<<endl;
}
int main()
{
	ios::sync_with_stdio(false);
	int t;
	cin>>t;
	while(t--)
	{
		solve();
	}
	return 0;
}

C. Perfect Keyboard

Polycarp wants to assemble his own keyboard. Layouts with multiple rows are too complicated for him — his keyboard will consist of only one row, where all 26 lowercase Latin letters will be arranged in some order.
Polycarp uses the same password s on all websites where he is registered (it is bad, but he doesn’t care). He wants to assemble a keyboard that will allow to type this password very easily. He doesn’t like to move his fingers while typing the password, so, for each pair of adjacent characters in s, they should be adjacent on the keyboard. For example, if the password is abacaba, then the layout cabdefghi… is perfect, since characters a and c are adjacent on the keyboard, and a and b are adjacent on the keyboard. It is guaranteed that there are no two adjacent equal characters in s, so, for example, the password cannot be password (two characters s are adjacent).
Can you help Polycarp with choosing the perfect layout of the keyboard, if it is possible?

Input

The first line contains one integer T (1≤T≤1000) — the number of test cases.
Then T lines follow, each containing one string s (1≤|s|≤200) representing the test case. s consists of lowercase Latin letters only. There are no two adjacent equal characters in s.

Output

For each test case, do the following:
if it is impossible to assemble a perfect keyboard, print NO (in upper case, it matters in this problem);
otherwise, print YES (in upper case), and then a string consisting of 26 lowercase Latin letters — the perfect layout. Each Latin letter should appear in this string exactly once. If there are multiple answers, print any of them.

Example

input

5
ababa
codedoca
abcda
zxzytyz
abcdefghijklmnopqrstuvwxyza

output

YES
bacdefghijklmnopqrstuvwxyz
YES
edocabfghijklmnpqrstuvwxyz
NO
YES
xzytabcdefghijklmnopqrsuvw
NO

Translation

给一个字符串，要设计一个键盘，这个键盘也是一个字符串。要求打字的时候每打一个字，打下一个字的位置与现在手指放的位置是相邻的。即对于s中的每对相邻字符，它们在键盘上都应该相邻。例如，如果密码是abacaba，则布局cabdefghi …是完美的，因为键盘上的字符a和c相邻，而键盘上的a和b则相邻。而且题目明确说了题给的字符串相邻两个字符不会相同。

Idea Ⅰ

我们可以贪心地考虑问题。当遍历到一个字母的时候，如果这个字母已经在键盘上，那么找当前位置左右的相邻位置，如果找不到字母与其相等，则方案不可行，如果有，则移动手指；如果字母不在键盘上，这时候有两种可能，如果手指在键盘的端点上，则可添加字母，如果不在，那么方案不可行。

Code Ⅰ

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
#include<iostream>
#include<string>
#include<vector>
using namespace std;
void solve()
{
	string s;
	cin>>s;
	vector<bool>used(26);
	used[s[0]-'a']=true;
	string t(1,s[0]);
	int pos=0;
	int i,len=s.size();
	for(i=1;i<len;i++)
	{
		if(used[s[i]-'a'])
		{
			if(pos>0&&t[pos-1]==s[i]) pos--;
			else if(pos<t.size()-1&&t[pos+1]==s[i]) pos++;
			else
			{
				cout<<"NO"<<endl;
				return;
			}
		}
		else 
		{
			if(pos==0) t=s[i]+t;
			else if(pos==t.size()-1)
			{
				t=t+s[i];
				pos++;
			}
			else
			{
				cout<<"NO"<<endl;
				return;
			}
			used[s[i]-'a']=true;			
		} 
	} 
	for(i=0;i<=25;i++)
	{
		if(!used[i]) t+=char(i+'a');
	}
	cout<<"YES"<<endl<<t<<endl;
}
int main()
{
	ios::sync_with_stdio(false);
	int t;
	cin>>t;
	while(t--)
	{
		solve();
	}
	return 0;
}

Code Ⅱ

用图的思想考虑问题。每遍历到一个字母，把该字母连接到手指在键盘上指向的字母。键盘上字母相邻的字母个数为1或2，相邻字母个数是1的字母位于键盘的端点，这样的字母只能为2个。
如果键盘可以设计出来，那么构图完成后，我们得到了一条链，我们从一个端点的字母开始，向前推进。

Idea Ⅱ

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
#include<iostream>
#include<string>
#include<map>
#include<vector>
#include<cstring>
#include<algorithm>
#define ll long long
using namespace std;
string s;
bool vis[30];
void solve()
{
	cin>>s;
	string ans;
	int i;
	if(s.size()==1)
	{
		ans="abcdefghijklmnopqrstuvwxyz";
		cout<<"YES"<<endl<<ans<<endl;
		return;
	}
	else
	{
		memset(vis,0,sizeof(vis));
		bool ok=1;
		map<pair<int,int>,int>mp;//字母、字母、边权   
		int x,y;
		int l=s.size();
		vector<int>v[30];
		for(i=1;i<l;i++)
		{
			x=s[i]-'a';
			y=s[i-1]-'a';
			if(x>y) swap(x,y);//(2,1)(1,2)其实是相同的，所以按照一定的次序组合可以去重。
			if(mp[make_pair(x,y)]==0)
			{
				mp[make_pair(x,y)]=1;
				v[x].push_back(y);
				v[y].push_back(x);
			}
			if(v[x].size()>2||v[y].size()>2)
			{
				ok=0;
				break;
			}
		}
		int cnt=0,plus;
		for(i=0;i<=25;i++)
		{
			if(v[i].size()==1)
			{
				plus=i;
				cnt++;
			}
		}
		if(ok==0||cnt!=2) cout<<"NO"<<endl;
		else
		{
			ans+='a'+plus;
			vis[plus]=1;
			while(1)
			{
				int nxt=-1;
				for(i=0;i<v[plus].size();i++)
				{
                //v[plus]最多有两个元素，一个元素已经在生成的链中了。
					if(vis[v[plus][i]]==0) nxt=v[plus][i];
				}
				if(nxt!=-1)
				{
					plus=nxt;
					ans+='a'+plus;
					vis[plus]=1;
				}
				else break;
			}
			for(i=0;i<=25;i++)
			{
				if(vis[i]) continue;
				else ans+='a'+i;
			}
			cout<<"YES"<<endl<<ans<<endl;
		}
	}
}
int main()
{
	ios::sync_with_stdio(false);
	int t;
	cin>>t;
	while(t--)
	{
		solve();
	}
	return 0;
}