技巧

快读

因为scanf和cin很慢，我们发现使用getchar读取字符非常快，所以我们读取数字也用getchar来加快读取速度。

1
2
3
4
5
6
7
inline ll read()
{
    ll x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}//负数情况
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}//读取字符，转换为整数
    return x*f;//考虑到负数，相乘以后再输出
}

Multiply by 2, divide by 6

You are given an integer nn. In one move, you can either multiply nn by two or divide nn by 66 (if it is divisible by 66 without the remainder).

Your task is to find the minimum number of moves needed to obtain 11 from nn or determine if it’s impossible to do that.

You have to answer tt independent test cases.

Input

The first line of the input contains one integer tt (1≤t≤2⋅1041≤t≤2⋅104) — the number of test cases. Then tt test cases follow.

The only line of the test case contains one integer nn (1≤n≤1091≤n≤109).

Output

For each test case, print the answer — the minimum number of moves needed to obtain 11 from nn if it’s possible to do that or -1 if it’s impossible to obtain 11 from nn.

Example

Input

1
2
3
4
5
6
7
8
7
1
2
3
12
12345
15116544
387420489

Output

1
2
3
4
5
6
7
0
-1
2
-1
-1
12
36

Note

Consider the sixth test case of the example. The answer can be obtained by the following sequence of moves from the given integer 1511654415116544:

  1. Divide by 66 and get 25194242519424;

  2. divide by 66 and get 419904419904;

  3. divide by 66 and get 6998469984;

  4. divide by 66 and get 1166411664;

  5. multiply by 22 and get 2332823328;

  6. divide by 66 and get 38883888;

  7. divide by 66 and get 648648;

  8. divide by 66 and get 108108;

  9. multiply by 22 and get 216216;

  10. divide by 66 and get 3636;

  11. divide by 66 and get 66;

  12. divide by 66 and get 11.

    分析：

    ×2÷6等价于÷3，而÷6等价于÷2÷3，分解因子，设x能分解成sum2个2和sum3个3，如果sum2的个数大于sum3的个数，则说明不能得到1，因为要÷2只能通过÷6这个操作，而这个操作本身又在÷3，所有直接输出-1即可。

    否则，3的个数大于2，那么可以通过×2乘回来，它们的差加上3的个数就是答案。

    另一种思路，也是最容易想到的，先一值除以6，如果不能整除了，就一直除以3，如果不能整除，则输出NO，否则输出yes

参考代码

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
#include <iostream>
#include <cstdio>
#include <algorithm>
typedef long long ll;
using namespace std;
int main(){
	ll t,x,sum3,sum2;
	cin>>t;
	while(t--){
		cin>>x;
		sum3=sum2=0;
		while(x%2==0){//分解因子2
			x/=2;
			sum2++;
		}
		while(x%3==0){//分解因子3
			x/=3;
			sum3++;
		}
		if(x>1||sum2>sum3)cout<<"-1"<<endl;
		else cout<<(sum3-sum2)+sum3<<endl;
	}
	return 0;
}

Zero Remainder Array

You are given an array aa consisting of nn positive integers.

Initially, you have an integer x=0x=0. During one move, you can do one of the following two operations:

  1. Choose exactly one ii from 11 to nn and increase aiai by xx (ai:=ai+xai:=ai+x), then increase xx by 11 (x:=x+1x:=x+1).
  2. Just increase xx by 11 (x:=x+1x:=x+1).

The first operation can be applied no more than once to each ii from 11 to nn.

Your task is to find the minimum number of moves required to obtain such an array that each its element is divisible by kk (the value kk is given).

You have to answer tt independent test cases.

Input

The first line of the input contains one integer tt (1≤t≤2⋅1041≤t≤2⋅104) — the number of test cases. Then tt test cases follow.

The first line of the test case contains two integers nn and kk (1≤n≤2⋅105;1≤k≤1091≤n≤2⋅105;1≤k≤109) — the length of aa and the required divisior. The second line of the test case contains nn integers a1,a2,…,ana1,a2,…,an (1≤ai≤1091≤ai≤109), where aiai is the ii-th element of aa.

It is guaranteed that the sum of nn does not exceed 2⋅1052⋅105 (∑n≤2⋅105∑n≤2⋅105).

Output

For each test case, print the answer — the minimum number of moves required to obtain such an array that each its element is divisible by kk.

Example

Input

1
2
3
4
5
6
7
8
9
10
11
5
4 3
1 2 1 3
10 6
8 7 1 8 3 7 5 10 8 9
5 10
20 100 50 20 100500
10 25
24 24 24 24 24 24 24 24 24 24
8 8
1 2 3 4 5 6 7 8

Output

1
2
3
4
5
6
18
0
227
8

Note

Consider the first test case of the example:

  1. x=0x=0, a=[1,2,1,3]a=[1,2,1,3]. Just increase xx;
  2. x=1x=1, a=[1,2,1,3]a=[1,2,1,3]. Add xx to the second element and increase xx;
  3. x=2x=2, a=[1,3,1,3]a=[1,3,1,3]. Add xx to the third element and increase xx;
  4. x=3x=3, a=[1,3,3,3]a=[1,3,3,3]. Add xx to the fourth element and increase xx;
  5. x=4x=4, a=[1,3,3,6]a=[1,3,3,6]. Just increase xx;
  6. x=5x=5, a=[1,3,3,6]a=[1,3,3,6]. Add xx to the first element and increase xx;
  7. x=6x=6, a=[6,3,3,6]a=[6,3,3,6]. We obtained the required array.

Note that you can’t add xx to the same element more than once.

题目大意：最开始给你一个x=0，还有一个长度为n的数组，你可以执行两个操作：

①要么x+1

②要么ai+x，然后x再+1

最后要让数组a的所有元素都能整除k，问最少的操作次数。

这个题目有点绕，就是先对ai求余，然后找到相同余数x出现最多的次数maxx，如果出现次数相同那就找最小的，

比如余数3 3 2 2 1，假设k=4，这里2和3都出现2次，找2，因为2要变成4，要加2,3要变成4，要加1，处理2要比处理3麻烦，所以要找最小的。因为有两个2，x是递增的，第一个2加2，就能变成4，而第二个只能变成8，即2k，要加上6，（maxx-1）*k，答案就是（maxx-1）×k+k-余数x+1

参考代码

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 <stdio.h>
#include <iostream>
#include <algorithm>
#include <string.h>
#include <map>
using namespace std;
typedef long long ll;
map<ll,ll>m;
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	ll t,n,k,x;
	cin>>t;
	while(t--){
		cin>>n>>k;
		m.clear();
		ll ans=0;
		ll maxx=0;
		for(int i=0;i<n;i++){
			cin>>x;
			x%=k;
			m[x]++;
			if(x&&maxx<m[x]){
				maxx=m[x];
				ans=x;
			}else if(x&&m[x]==maxx&&x<ans){
				ans=x;
			}
		}
		if(ans==0)cout<<"0"<<endl;
		else cout<<(maxx-1)*k+k-ans+1<<endl; 
	} 
}

Social Distance

Polycarp and his friends want to visit a new restaurant. The restaurant has nn tables arranged along a straight line. People are already sitting at some tables. The tables are numbered from 11 to nn in the order from left to right. The state of the restaurant is described by a string of length nn which contains characters “1” (the table is occupied) and “0” (the table is empty).

Restaurant rules prohibit people to sit at a distance of kk or less from each other. That is, if a person sits at the table number ii, then all tables with numbers from i−ki−k to i+ki+k (except for the ii-th) should be free. In other words, the absolute difference of the numbers of any two occupied tables must be strictly greater than kk.

For example, if n=8n=8 and k=2k=2, then:

  • strings “10010001”, “10000010”, “00000000”, “00100000” satisfy the rules of the restaurant;
  • strings “10100100”, “10011001”, “11111111” do not satisfy to the rules of the restaurant, since each of them has a pair of “1” with a distance less than or equal to k=2k=2.

In particular, if the state of the restaurant is described by a string without “1” or a string with one “1”, then the requirement of the restaurant is satisfied.

You are given a binary string ss that describes the current state of the restaurant. It is guaranteed that the rules of the restaurant are satisfied for the string ss.

Find the maximum number of free tables that you can occupy so as not to violate the rules of the restaurant. Formally, what is the maximum number of “0” that can be replaced by “1” such that the requirement will still be satisfied?

For example, if n=6n=6, k=1k=1, s=s= “100010”, then the answer to the problem will be 11, since only the table at position 33 can be occupied such that the rules are still satisfied.

Input

The first line contains a single integer tt (1≤t≤1041≤t≤104) — the number of test cases in the test. Then tt test cases follow.

Each test case starts with a line containing two integers nn and kk (1≤k≤n≤2⋅1051≤k≤n≤2⋅105) — the number of tables in the restaurant and the minimum allowed distance between two people.

The second line of each test case contains a binary string ss of length nn consisting of “0” and “1” — a description of the free and occupied tables in the restaurant. The given string satisfy to the rules of the restaurant — the difference between indices of any two “1” is more than kk.

The sum of nn for all test cases in one test does not exceed 2⋅1052⋅105.

Output

For each test case output one integer — the number of tables that you can occupy so as not to violate the rules of the restaurant. If additional tables cannot be taken, then, obviously, you need to output 00.

Example

Input

1
2
3
4
5
6
7
8
9
10
11
12
13
6
6 1
100010
6 2
000000
5 1
10101
3 1
001
2 2
00
1 1
0

Output

1
2
3
4
5
6
1
2
0
1
1
1

参考代码：

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
#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <string.h>
const int maxn=1e5+5;
int a[maxn];
using namespace std;
int main(){
	int t;
	cin>>t;
	while(t--){
		int n,k,ans=0,j;
		cin>>n>>k;
		string s;
		cin>>s;
		for(int i=0;i<s.size();i++){
			if(s[i]=='0'){
				j=i+1;
				while(s[j]=='0'&&j<s.size()&&j-i<=k)j++;
				if(j-i>k||j==s.size()){
					ans++;
					i+=k;
				}
				else i=j-1; 
			}
			else i+=k;
		}
		cout<<ans<<endl;
	}
	return 0;
}

XXXXX

Ehab loves number theory, but for some reason he hates the number xx. Given an array aa, find the length of its longest subarray such that the sum of its elements isn’t divisible by xx, or determine that such subarray doesn’t exist.

An array aa is a subarray of an array bb if aa can be obtained from bb by deletion of several (possibly, zero or all) elements from the beginning and several (possibly, zero or all) elements from the end.

Input

The first line contains an integer tt (1≤t≤5)(1≤t≤5) — the number of test cases you need to solve. The description of the test cases follows.

The first line of each test case contains 2 integers nn and xx (1≤n≤1051≤n≤105, 1≤x≤1041≤x≤104) — the number of elements in the array aa and the number that Ehab hates.

The second line contains nn space-separated integers a1a1, a2a2, ……, anan (0≤ai≤1040≤ai≤104) — the elements of the array aa.

Output

For each testcase, print the length of the longest subarray whose sum isn’t divisible by xx. If there’s no such subarray, print −1−1.

Example

Input

1
2
3
4
5
6
7
3
3 3
1 2 3
3 4
1 2 3
2 2
0 6

Output

1
2
3
2
3
-1

参考代码

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
#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <string.h> 
const int maxn=1e5+5;
int a[maxn];
using namespace std;
int main(){
	int t;
	cin>>t;
	while(t--){
		int n,x,ans=0,sum=0,i,j;
		cin>>n>>x;
		for(int i=1;i<=n;i++){
			cin>>a[i];
			if(a[i]%x==0)ans++;
			sum+=a[i]; 
		}
		if(sum%x!=0)cout<<n<<endl;//如果整个数组的和可以不整除x，则数组长度就是最大长度
		else if(ans==n)cout<<"-1"<<endl;//如果数组的每个元素都能整除x，则输出-1
		else{
			for(i=1;i<=n;i++)//整个数组 的和不可以整除x，分别从左边和右边找到第一个不能整除x的元素，比较左边的长度和右边，谁大输出谁即可
			if(a[i]%x!=0)break;
			for(j=n;j>0;j--)
			if(a[j]%x!=0)break;
			cout<<max(n-i,j-1)<<endl;
		}
	}
	return 0;
}

Most socially-distanced subsequence

Given a permutation pp of length nn, find its subsequence s1s1, s2s2, ……, sksk of length at least 22 such that:

  • |s1−s2|+|s2−s3|+…+|sk−1−sk||s1−s2|+|s2−s3|+…+|sk−1−sk| is as big as possible over all subsequences of pp with length at least 22.
  • Among all such subsequences, choose the one whose length, kk, is as small as possible.

If multiple subsequences satisfy these conditions, you are allowed to find any of them.

A sequence aa is a subsequence of an array bb if aa can be obtained from bb by deleting some (possibly, zero or all) elements.

A permutation of length nn is an array of length nn in which every element from 11 to nn occurs exactly once.

Input

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

The first line of each test case contains an integer nn (2≤n≤1052≤n≤105) — the length of the permutation pp.

The second line of each test case contains nn integers p1p1, p2p2, ……, pnpn (1≤pi≤n1≤pi≤n, pipi are distinct) — the elements of the permutation pp.

The sum of nn across the test cases doesn’t exceed 105105.

Output

For each test case, the first line should contain the length of the found subsequence, kk. The second line should contain s1s1, s2s2, ……, sksk — its elements.

If multiple subsequences satisfy these conditions, you are allowed to find any of them.

Example

Input

1
2
3
4
5
2
3
3 2 1
4
1 3 4 2

Output

1
2
3
4
2
3 1 
3
1 4 2

参考代码

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
#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <string.h>
const int maxn=1e5+5;
int a[maxn],t[maxn];
using namespace std;
int main(){
	int test;
	cin>>test;
	while(test--){
		int n,k=1;
		cin>>n;
		memset(a,0,sizeof(a));
		memset(t,0,sizeof(t));
		t[1]=1;
		for(int i=1;i<=n;i++){
			cin>>a[i];
		}
		for(int i=2;i<=n-1;i++){
			if(a[i]>a[i-1]&&a[i]>a[i+1]||a[i]<a[i-1]&&a[i]<a[i+1])t[++k]=i;
		}
		t[++k]=n;
		cout<<k<<endl;
		for(int i=1;i<=k;i++)cout<<a[t[i]]<<" ";
		cout<<endl;
	}
	return 0;
}

博弈论

Road to Arabella

Ayoub and Kilani felt board while they are going to ArabellaCPC in (Amman-Irbid) road, so Kilani invented a new game to play with Ayoub.

The game is described by the following rules :

Ayoub picks a random integer $$$n$$$ $$$(1 \leq n \leq 10^{9})$$$ , and Kilani picks a random integer $$$k$$$ $$$(1 \leq k \leq n)$$$, then they will start playing. In each turn a player can choose any number $$$x$$$ $$$(1 \leq x \leq max(1 , m-k) )$$$ (which $$$m$$$ is the current value of $$$n$$$) and subtract it from $$$n$$$. if $$$n$$$ equals zero then the player can’t make a move. The player who can’t make a move is considered to lose the game.

If Kilani starts, and each player played optimally, who would be the winner?

题目炸了，这里给出链接：

Road to Arabella - Gym 102263B - Virtual Judge (vjudge.net)

题解：

考虑极端情况，如果n-k<=1,这种情况每次只能减1，可以改变奇偶性，这时，如果n是奇数，先手就会获胜，否则后手获胜

其他情况先手总能找到一个x使一轮以后出现极端情况并且让n是奇数，这种情况下先手必胜

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <iostream>
using namespace std;
int main(){
	int n,k;
	int t;
	cin>>t;
	while(t--){
		cin>>n>>k;
		if(n-k<=1){
			if(n%2==1)
			cout<<"Kilani"<<endl;
			else cout<<"Ayoub"<<endl;
		}
		else cout<< "Kilani"<<endl;
		}
	return 0;
}

Check The Text

Roze has a special keyboard which consists only of 29 keys:

-26 alphabetic a-z keys, which prints the 26 lowercase Latin letters.

-“Space” key, which prints a single space.

-“CapsLock” key, which converts the status of the letters keys from lowercase to uppercase and vice versa. The status initially is lowercase.

-“Backspace” key, which deletes the last letter/space that was written on the screen.

If Roze presses “Backspace” and there is nothing to delete on the screen, nothing will happen.

Given the text that Roze had to print and the order of the keys she has pressed on the keyboard, check if Roze has printed the text correctly (including exactly one space between every two words).

由于题目还是乱码，我先放个链接

Check The Text - Gym 102263C - Virtual Judge (vjudge.net)

简单模拟即可，不过如果像我这样写很多分支的话，一定要注意，第一次这样卡在45个样例，贴一下WA代码：

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
#include<iostream>
#include<cstring>
using namespace std;
int main(){
	int n,flag=0;//0代表小写 
	string sum,s="",total,ans;
	cin>>n;
	for(int i=0;i<n;i++)
	{
		cin>>s;
		total+=s+' ';
	}
    //注意这里会多一个空格
	int m;
	cin>>m;
	cout<<sum.length()<<endl;
	for(int i=0;i<m;i++){
		cin>>s;
		if(s=="Backspace"&&sum.length()!=0){//注意这里，如果s=backspace并且sum.length=0就会进入下面那个flag的分支，导致错误
			sum=sum.substr(0,sum.length()-1);
		}
		else if(s=="CapsLock"){
			flag=1-flag;
		}
		else if(s=="Space"){
		sum+=' ';
	    }
	    else if(flag==0){
	    	sum+=s[0];
		}
		else if(flag==1){
			sum+=(s[0]-32);
		}
	}
	sum+=' ';
	//cout<<total<<endl;
	//cout<<sum<<endl;
	if(total==sum)cout<<"Correct"<<endl;
	else cout<<"Incorrect"<<endl;
	return 0;
}

AC代码：

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
#include<iostream>
#include<cstring>
using namespace std;
int main(){
	int n,flag=0;//0代表小写 
	string sum,s="",total,ans;
	cin>>n;
	for(int i=0;i<n;i++)
	{
		cin>>s;
		total+=s+' ';
	}
   //注意这里会多一个空格
	int m;
	cin>>m;
	cout<<sum.length()<<endl;
	for(int i=0;i<m;i++){
		cin>>s;
		if(s=="Backspace"){//这样如果s=backspace就会保证它一定会进入这个分支
			if(sum.length()!=0)
			sum=sum.substr(0,sum.length()-1);
		}
		else if(s=="CapsLock"){
			flag=1-flag;
		}
		else if(s=="Space"){
		sum+=' ';
	    }
	    else if(flag==0){
	    	sum+=s[0];
		}
		else if(flag==1){
			sum+=(s[0]-32);
		}
	}
	sum+=' ';
	cout<<total<<endl;
	cout<<sum<<endl;
	if(total==sum)cout<<"Correct"<<endl;
	else cout<<"Incorrect"<<endl;
	return 0;
}

Kefa and Company

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

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
#include <cstdio>
#include <algorithm>
using namespace std;
const int maxn=1e5+5;
typedef long long ll;
struct Node{
	int m,s;
}num[maxn]; 
int cmp(Node a,Node b){
	return a.m<b.m;
}
inline ll read()
{
    ll x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}//负数情况
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}//读取字符，转换为整数
    return x*f;//考虑到负数，相乘以后再输出
}
int main(){
	int n,d;
	ll sum,maxn,ans,j;
	while(n=read(),d=read()){
		for(int i=0;i<n;i++){
			num[i].m=read();
			num[i].s=read();
		}
		sort(num,num+n,cmp);
		sum=0;
		maxn=0;
		j=0;
		for(int i=0;i<n;i++){
			sum+=num[i].s;
			while(num[i].m-num[j].m>=d){
				sum-=num[j].s;
				j++;
			}
			if(maxn<sum)maxn=sum;
			
		}
		printf("%lld\n",maxn);
	}
	return 0;
}