Codeforces Round #628 (Div. 2)
A. EhAb AnD gCd
You are given a positive integer . Find any such positive integers and such that .
As a reminder, is the greatest integer that divides both and . Similarly, is the smallest integer such that both and divide it.
It’s guaranteed that the solution always exists. If there are several such pairs , you can output any of them.
Input
The first line contains a single integer — the number of testcases.
Each testcase consists of one line containing a single integer, .
Output
For each testcase, output a pair of positive integers and such that . It’s guaranteed that the solution always exists. If there are several such pairs , you can output any of them.
Example
input
2
2
14
output
1 1
6 4
Note
In the first testcase of the sample, .
In the second testcase of the sample, .
Translation
给一个数,任意输出一个数对,满足。
Idea
如官方题解所说:“ and always work.”
Code
1 |
|
Postscript
有时候只需要灵机一动。
B. CopyCopyCopyCopyCopy
Ehab has an array of length . He has just enough free time to make a new array consisting of copies of the old array, written back-to-back. What will be the length of the new array’s longest increasing subsequence?
A sequence is a subsequence of an array if can be obtained from by deletion of several (possibly, zero or all) elements. The longest increasing subsequence of an array is the longest subsequence such that its elements are ordered in strictly increasing order.
Input
The first line contains an integer — the number of test cases you need to solve. The description of the test cases follows.
The first line of each test case contains an integer — the number of elements in the array .
The second line contains n space-separated integers $ (1≤a_i≤10^9)$ — the elements of the array .
The sum of across the test cases doesn’t exceed .
Output
For each testcase, output the length of the longest increasing subsequence of a if you concatenate it to itself times.
Example
input
2
3
3 2 1
6
3 1 4 1 5 9
output
3
5
Note
In the first sample, the new array is . The longest increasing subsequence is marked in bold.
In the second sample, the longest increasing subsequence will be .
Translation
给一个数列,将该数列复制次,依次拼接到的尾部。得到新数列,问最长严格上升子序列的长度。
Idea
观察样例,能够猜到答案就是数列中数字的种类数。
下面给出证明:
将这个不重复的数字从大到小排序,我们可以从原数列中拿出第一个,从第一个复制数列中拿出第二个……从第个复制数列中拿出第个。由于恒成立,必能找到一个长度为的严格上升子序列。假设存在比更长的严格上升子序列,那么原数列中数字的种类数大于,矛盾。所以答案就是原数列中数字的种类数,证毕。
代码实现就是用中的存一下。
Code
1 |
|
Postscript
大胆假设,小心求证。
C. Ehab and Path-etic MEXs
You are given a tree consisting of nodes. You want to write some labels on the tree’s edges such that the following conditions hold:
- Every label is an integer between and inclusive.
- All the written labels are distinct.
- The largest value among over all pairs of nodes is as small as possible.
Here, denotes the smallest non-negative integer that isn’t written on any edge on the unique simple path from node to node .
Input
The first line contains the integer — the number of nodes in the tree.
Each of the next lines contains two space-separated integers and that mean there’s an edge between nodes and . It’s guaranteed that the given graph is a tree.
Output
Output integers. The of them will be the number written on the edge (in the input order).
Examples
input
3
1 2
1 3
output
0
1
input
6
1 2
1 3
2 4
2 5
5 6
output
0
3
2
4
1
Note
The tree from the second sample:
Translation
给一棵个顶点的树,将树的边从到编号,使得任意两点的最大值尽可能小。
指之间的简单路径上不存在的最小非负边权。
Idea
先来理解一下。样例中。
可以观察到,如果这棵树是一条链,那么无论怎么排,整条链的都为;对于一颗正常的树,无论怎样给边赋值,总会有一条简单路径存在两条边权为和的边;因此,我们的目标是使的最大值为。
对于一棵正常树,如果存在某一个节点度数大于等于,选择其中三条边编号。这样其他的路径一定不会同时经过。而无论怎么排列,一定无法避免其中会有一条路径同时经过。所以所有路径的的最大值一定为;剩余的边随便排就可以了。
Code
1 |
|
Postscript
思维题,多想,多看,多写,多画。
D. Ehab the Xorcist
Given integers and , find the shortest array such that bitwise-xor of its elements is , and the sum of its elements is .
Input
The only line contains integers and .
Output
If there’s no array that satisfies the condition, print “-1”. Otherwise:
The first line should contain one integer, , representing the length of the desired array. The next line should contain positive integers, the array itself. If there are multiple possible answers, print any.
Examples
input
2 4
output
2
3 1
input
1 3
output
3
1 1 1
input
8 5
output
-1
input
0 0
output
0
Note
In the first sample, and . There is no valid array of smaller length.
Notice that in the fourth sample the array is empty.
Translation
给两个整数,找到一个最短的非负整数数列,使得数列的异或和为,加法和为。
将拆分,。可以看到,当,无解;当奇偶性不同,无解。如果有解,当,时,我们需要特判一下;当,一定可以找到一个含三个元素的数列,若满足,则,则构造出了两个元素的数列。
Code
1 |
|
Postscript
需要灵机一动。注意不要爆int。