• Codeforces暑期训练周报（8.4~8.10）

    A. Pashmak and Garden

    time limit per test: 1 second

    memory limit per test: 256 megabytes

    input: standard input

    output: standard output

    Pashmak has fallen in love with an attractive girl called Parmida since one year ago...

    Today, Pashmak set up a meeting with his partner in a romantic garden. Unfortunately, Pashmak has forgotten where the garden is. But he remembers that the garden looks like a square with sides parallel to the coordinate axes. He also remembers that there is exactly one tree on each vertex of the square. Now, Pashmak knows the position of only two of the trees. Help him to find the position of two remaining ones.

    Input

    The first line contains four space-separated x_1, y_1, x_2, y_2 ( - 100 ≤ x_1, y_1, x_2, y_2 ≤ 100) integers, where x_1 and y_1 are coordinates of the first tree and x_2 and y_2 are coordinates of the second tree. It's guaranteed that the given points are distinct. 

    Output

    If there is no solution to the problem, print -1. Otherwise print four space-separated integers x_3, y_3, x_4, y_4 that correspond to the coordinates of the two other trees. If there are several solutions you can output any of them.

    Note that x_3, y_3, x_4, y_4 must be in the range ( - 1000 ≤ x_3, y_3, x_4, y_4 ≤ 1000). 

    Examples

    input

    0 0 0 1

    output

    1 0 1 1

    input

    0 0 1 1

    output

    0 1 1 0

    input

    0 0 1 2

    output

    -1

    题解：

            一道比较简单的模拟题，样例中几乎给出了所有的可能情况，稍加修改即可得出答案。当a=c时，即x相同，则另外两个点的b、d不变，a、c变为a-abs(b-d)和c-abs(b-d)；同理b=d时也一样，只是反过来而已；当两点处于对角线时，直接把原输入的b、d反过来或者a、c反过来即可；否则输出-1.

    AC代码：

    1. #include 
    2. #define BUFF ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
    3. #define ll long long
    4. #define endl '\n'
    5. #define F(i,st,ed) for(int i=st;i
    6. #define M(x) memset(x,0,sizeof(x))
    7. #define pb push_back
    8. using namespace std;
    9.  
    10. void solve(){
    11. 	int a,b,c,d;
    12. 	cin>>a>>b>>c>>d;
    13. 	if (a==c){
    14. 		cout<abs(b-d)<<" "<" "<abs(b-d)<<" "<
    15. 	}
    16. 	else if (b==d){
    17. 		cout<" "<abs(a-c)<<" "<" "<abs(a-c)<
    18. 	}
    19. 	else if (abs(a-c)==abs(b-d)){
    20. 		cout<" "<" "<" "<
    21. 	}
    22. 	else{
    23. 		cout<<"-1"<
    24. 	}
    25. }
    26. int main()
    27. {
    28. 	BUFF;
    29. 	int _;
    30. 	//cin>>_;
    31. 	_=1; 
    32. 	while (_--){
    33. 		solve();
    34. 	}
    35. 	return 0;
    36. }

    C. Ternary XOR

    time limit per test: 1 second

    memory limit per test: 256 megabytes

    input: standard input

    output: standard output

    A number is ternary if it contains only digits 0, 1 and 2. For example, the following numbers are ternary: 1022, 11, 21, 2002.

    You are given a long ternary number x. The first (leftmost) digit of x is guaranteed to be 2, the other digits of x can be 0, 1 or 2.

    Let's define the ternary XOR operation ⊙ of two ternary numbers a and b (both of length n) as a number c=a⊙b of length n, where c_i=(a_i+b_i)%3 (where % is modulo operation). In other words, add the corresponding digits and take the remainders of the sums when divided by 3. For example, 10222⊙11021=21210.

    Your task is to find such ternary numbers a and b both of length n and both without leading zeros that a⊙b=x and max(a,b) is the minimum possible.

    You have to answer t independent test cases.

    Input

    The first line of the input contains one integer t (1≤t≤10^4) — the number of test cases. Then t test cases follow. The first line of the test case contains one integer n (1≤n≤5⋅10^4) — the length of x. The second line of the test case contains ternary number x consisting of n digits 0,1 or 2. It is guaranteed that the first digit of x is 2. It is guaranteed that the sum of n over all test cases does not exceed 5⋅10^4 (∑n≤5⋅10^4).

    Output

    For each test case, print the answer — two ternary integers a and b both of length n and both without leading zeros such that a⊙b=x and max(a,b) is the minimum possible. If there are several answers, you can print any.

    Example

    input

    4
5
22222
5
21211
1
2
9
220222021

    output

    11111
11111
11000
10211
1
1
110111011
110111010

    题解：

            一道比较简单的贪心题目，如果不看题直接看样例结果的话，不难发现只需要将已知的数字拆解成两个数字运算即可得到答案，但是题目要求输出的越小越好，所以在a、b中要做一步判断，保证a、b的值最小。

    AC代码：

    1. #include 
    2. #define BUFF ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
    3. #define ll long long
    4. #define endl '\n'
    5. #define F(i,st,ed) for(int i=st;i
    6. #define M(x) memset(x,0,sizeof(x))
    7. #define pb push_back
    8. using namespace std;
    9.  
    10. void solve(){
    11. 	int n;
    12. 	cin>>n;
    13. 	string s;
    14. 	cin>>s;
    15. 	string a="";
    16. 	string b="";
    17. 	for (int i=0;ilength();i++){
    18. 		if (s[i]=='2'){
    19. 			if (a==b){
    20. 				a+="1",b+="1";
    21. 			}
    22. 			else if (a
    23. 				a+="2",b+="0";
    24. 			}
    25. 			else{
    26. 				a+="0",b+="2";
    27. 			}
    28. 		}
    29. 		else if (s[i]=='0'){
    30. 			a+="0",b+="0";
    31. 		}
    32. 		else{
    33. 			if (a>b){
    34. 				a+="0",b+="1";
    35. 			}
    36. 			else{
    37. 				a+="1",b+="0";
    38. 			}
    39. 		}
    40. 	}
    41. 	cout<
    42. }
    43. int main()
    44. {
    45. 	BUFF;
    46. 	int _;
    47. 	cin>>_;
    48. 	//_=1; 
    49. 	while (_--){
    50. 		solve();
    51. 	}
    52. 	return 0;
    53. }

    B. Kuriyama Mirai's Stones

    time limit per test: 2 seconds

    memory limit per test: 256 megabytes

    input: standard input

    output: standard output

    Kuriyama Mirai has killed many monsters and got many (namely n) stones. She numbers the stones from 1 to n. The cost of the i-th stone is v_i. Kuriyama Mirai wants to know something about these stones so she will ask you two kinds of questions:

    1. She will tell you two numbers, l and r (1 ≤ l ≤ r ≤ n), and you should tell her \sum_{i=l}^{r}v_i.
    2. Let u_i be the cost of the i-th cheapest stone (the cost that will be on the i-th place if we arrange all the stone costs in non-decreasing order). This time she will tell you two numbers, l and r (1 ≤ l ≤ r ≤ n), and you should tell her \sum_{i=l}^{r}u_i.

    For every question you should give the correct answer, or Kuriyama Mirai will say "fuyukai desu" and then become unhappy.

    Input

    The first line contains an integer n (1 ≤ n ≤ 10^5). The second line contains n integers: v_1,v_2,...,v_n (1 ≤ v_i ≤ 10^9) — costs of the stones.

    The third line contains an integer m (1 ≤ m ≤ 10^5) — the number of Kuriyama Mirai's questions. Then follow m lines, each line contains three integers type, l and r (1 ≤ l ≤ r ≤ n; 1 ≤ type ≤ 2), describing a question. If type equal to 1, then you should output the answer for the first question, else you should output the answer for the second one.

    Output

    Print m lines. Each line must contain an integer — the answer to Kuriyama Mirai's question. Print the answers to the questions in the order of input.

    Examples

    input

    6
6 4 2 7 2 7
3
2 3 6
1 3 4
1 1 6

    output

    24
9
28

    input

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

    output

    10
15
5
15
5
5
2
12
3
5

    Note

    Please note that the answers to the questions may overflow 32-bit integer type.

    题解：

            作为一个B题，往往都能用暴力去解决，没有必要使用线段树。暴力的做法就是拿前缀和去维护，一个用来记录原数组，另一个用来记录sort过后的，用前缀和的思想就可以做出来了。

    AC代码： 

    1. #include 
    2. #define BUFF ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
    3. #define ll long long
    4. #define endl '\n'
    5. #define F(i,st,ed) for(int i=st;i
    6. #define M(x) memset(x,0,sizeof(x))
    7. #define pb push_back
    8. using namespace std;
    9.  
    10. const int N=1e5+5;
    11. ll a[N],b[N],c[N];
    12. void solve(){
    13. 	int n;
    14. 	cin>>n;
    15. 	F(i,1,n+1){
    16. 		cin>>a[i];
    17. 		b[i]=b[i-1]+a[i];
    18. 	}
    19. 	sort(a+1,a+n+1);
    20. 	F(i,1,n+1){
    21. 		c[i]=c[i-1]+a[i];
    22. 	}
    23. 	int m;
    24. 	cin>>m;
    25. 	while (m--){
    26. 		int t,l,r;
    27. 		cin>>t>>l>>r;
    28. 		if (t==1){
    29. 			cout<-1]<
    30. 		}
    31. 		else if (t==2){
    32. 			cout<-1]<
    33. 		}
    34. 	}
    35. }
    36. int main()
    37. {
    38. 	BUFF;
    39. 	int _;
    40. 	//cin>>_;
    41. 	_=1; 
    42. 	while (_--){
    43. 		solve();
    44. 	}
    45. 	return 0;
    46. }

    D. Buying Shovels

    time limit per test: 2 seconds

    memory limit per test: 256 megabytes

    input: standard input

    output: standard output

    Polycarp wants to buy exactly n shovels. The shop sells packages with shovels. The store has k types of packages: the package of the i-th type consists of exactly i shovels (1≤i≤k). The store has an infinite number of packages of each type.

    Polycarp wants to choose one type of packages and then buy several (one or more) packages of this type. What is the smallest number of packages Polycarp will have to buy to get exactly nn shovels?

    For example, if n=8 and k=7, then Polycarp will buy 2 packages of 4 shovels.

    Help Polycarp find the minimum number of packages that he needs to buy, given that he:

    • will buy exactly nn shovels in total;
    • the sizes of all packages he will buy are all the same and the number of shovels in each package is an integer from 1 to k, inclusive.

    Input

    The first line contains an integer t (1≤t≤100) — the number of test cases in the input. Then, t test cases follow, one per line.

    Each test case consists of two positive integers n (1≤n≤10^9) and k (1≤k≤10^9) — the number of shovels and the number of types of packages.

    Output

    Print t answers to the test cases. Each answer is a positive integer — the minimum number of packages.

    Example

    input

    5
8 7
8 1
6 10
999999733 999999732
999999733 999999733

    output

    2
8
1
999999733
1

    Note

    The answer to the first test case was explained in the statement.

    In the second test case, there is only one way to buy 8 shovels — 8 packages of one shovel.

    In the third test case, you need to buy a 1 package of 6 shovels.

    题解：

            这个题目比较的容易。本题要求用最少的袋子数量装恰好n个铲子，不难想到因子的概念，我们只需要枚举n的因子，并从大到小排序，找到第一个小于等于k的值即可，最后输出的是n/因子。

    AC代码： 

    1. #include 
    2. #define BUFF ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
    3. #define ll long long
    4. #define endl '\n'
    5. #define F(i,st,ed) for(int i=st;i
    6. #define M(x) memset(x,0,sizeof(x))
    7. #define pb push_back
    8. using namespace std;
    9.  
    10. void solve(){
    11. 	int n,k;
    12. 	cin>>n>>k;
    13. 	if (n<=k){
    14. 		cout<<"1"<
    15. 		return;
    16. 	}
    17. 	else if (k==1){
    18. 		cout<
    19. 		return;
    20. 	}
    21. 	int nn=sqrt(n);
    22. 	priority_queue<int,vector<int> > q;
    23. 	F(i,1,nn+1){
    24. 		if (n%i==0){
    25. 			q.push(i);
    26. 			q.push(n/i);
    27. 		}
    28. 	}
    29. 	bool f=1;
    30. 	while (f){
    31. 		if (q.top()<=k){
    32. 			cout<top()<
    33. 			return;
    34. 		}
    35. 		q.pop();
    36. 	}
    37. }
    38. int main()
    39. {
    40. 	BUFF;
    41. 	int _;
    42. 	cin>>_;
    43. 	//_=1; 
    44. 	while (_--){
    45. 		solve();
    46. 	}
    47. 	return 0;
    48. }

    C. Product of Three Numbers

    time limit per test: 2 seconds

    memory limit per test: 256 megabytes

    input: standard input

    output: standard output

    You are given one integer number n. Find three distinct integers a,b,c such that 2≤a,b,c and a⋅b⋅c=n or say that it is impossible to do it.

    If there are several answers, you can print any.

    You have to answer t independent test cases.

    Input

    The first line of the input contains one integer t (1≤t≤100) — the number of test cases.

    The next n lines describe test cases. The i-th test case is given on a new line as one integer n (2≤n≤10^9).

    Output

    For each test case, print the answer on it. Print "NO" if it is impossible to represent n as a⋅b⋅c for some distinct integers a,b,c such that 2≤a,b,c.

    Otherwise, print "YES" and any possible such representation.

    Example

    input

    5
64
32
97
2
12345

    output

    YES
2 4 8 
NO
NO
NO
YES
3 5 823

    题解：

            这道题还是和因子有关，本体是让你找出三个不相等的大于2的数，使得这三个数相乘等于输入值n，问能不能做到。不难想到我们可以枚举这个数的所有因子，看看这个因子还能不能拆分成两个数相乘，所以用暴力的思想去解决这个问题再合适不过了。

    AC代码：

    1. #include 
    2. #define BUFF ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
    3. #define ll long long
    4. #define endl '\n'
    5. #define F(i,st,ed) for(int i=st;i
    6. #define M(x) memset(x,0,sizeof(x))
    7. #define pb push_back
    8. using namespace std;
    9.  
    10. void solve(){
    11. 	int n;
    12. 	cin>>n;
    13. 	int nn=sqrt(n);
    14. 	int a=0,b=0,c=0;
    15. 	bool f=0;
    16. 	F(i,2,nn+1){
    17. 		if (n%i==0){
    18. 			int n2=n/i;
    19. 			int nnn=sqrt(n2);
    20. 			F(j,2,nnn+1){
    21. 				if (n2%j==0){
    22. 					a=i,b=j,c=n2/j;
    23. 					if (a==b||a==c||b==c){
    24. 						continue;
    25. 					}
    26. 					f=1;
    27. 					break;
    28. 				}
    29. 			}
    30. 		}
    31. 		if (f){
    32. 			break;
    33. 		}
    34. 	}
    35. 	if (f){
    36. 		cout<<"YES"<
    37. 		cout<" "<" "<
    38. 	}
    39. 	else{
    40. 		cout<<"NO"<
    41. 	}
    42. }
    43. int main()
    44. {
    45. 	BUFF;
    46. 	int _;
    47. 	cin>>_;
    48. 	//_=1; 
    49. 	while (_--){
    50. 		solve();
    51. 	}
    52. 	return 0;
    53. }

            这周做的题目相较于前三周而言会少很多，主要也是为了完成指标，多做的话到时候没有什么简单的题练手了。

  • 相关阅读:
    java毕业生设计短视频交流点播系统计算机源码+系统+mysql+调试部署+lw
    含文档+PPT+源码等]精品基于SSM的网上水果生鲜超市商城[包运行成功]计算机毕设Java项目源码
    pytorch的自动求导和简单的线性函数机器学习
    webpack之Scope Hoisting（范围提升）
    【STM32】入门（七）：I2C硬件控制方式
    金三银四面试必问：Redis真的是单线程吗？
    C++11打断线程的几种方式
    代理IP与Socks5代理在技术世界的多元应用
    1688API接口接入|阿里1688-B类电商基础链路专业化体验升级
    一款超好用的神器Apifox，甩 Swagger 几条街...（荣耀典藏版）
  • 原文地址：https://blog.csdn.net/weixin_50961321/article/details/126154458