Codeforces Round 860 Div. 2 题解_codeforces860c. candy store

目录

A. Showstopper（签到）

题面翻译：

思路:

代码: 

B. Three Sevens（模拟）

题面翻译：

思路：

代码：

C. Candy Store（数学）

题面翻译

思路

代码

D. Shocking Arrangement （贪心，构造）

题面翻译

思路

代码

---

A. Showstopper（签到）

You are given two arrays a1,a2,…,anand b1,b2,…,bn

In one operation, you can choose any integer i from 11 to n and swap the numbers ai and bi.

Determine whether, after using any (possibly zero) number of operations, the following two conditions can be satisfied simultaneously:

• an=max(a1,a2,…,an)
• bn=max(b1,b2,…,bn)

Here max(c1,c2,…,ck)max denotes the maximum number among c1,c2,…,ck. For example, max(3,5,4)=5max(3,5,4)=5, max(1,7,7)=7, max(6,2)=6.

Input

Each test contains multiple test cases. The first line contains the number of test cases t (1≤t≤200. The description of the test cases follows.

The first line of each test case contains a single integer n (1≤n≤100) — the length of the arrays.

The second line of each test case contains n integers a1,a2,…,an (1≤ai≤100) — elements of the first array.

The third line of each test case contains n integers b1,b2,…,bn(1≤bi≤100) — elements of the second array.

Output

For each test case, print "Yes" if after using any (possibly zero) number of operations the conditions described above are satisfied. Otherwise, print "No".

You can output the answer in any case (upper or lower). For example, the strings "yEs", "yes", "Yes", and "YES" will be recognized as positive responses.

Example

input

7

3

7 9 7

7 6 9

4

10 10 15 15

10 16 15 15

2

100 99

99 100

1

1

1

9

1 2 3 4 5 6 7 8 9

9 9 9 9 9 9 6 6 6

7

1 1 2 2 1 1 2

1 2 1 2 1 2 1

2

30 4

5 30

output

Yes
No
Yes
Yes
Yes
No
No

题面翻译：

给两个长为n的数列，每次可以随意交换a[i]和b[i]，问能不能使a[n]和b[n]为各自数列的最大值

思路:

记录每个i对应a[i],b[i]的最大值最小值，取最大的最大值和最小值

a[n]和b[n]一个比最大值大，一个比最小值大即可

代码: 

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int a[100005],b[100005];
int main(){
    int T;
    cin>>T;
    while(T--){
 
        int n;
        cin>>n;
        for(int i=1;i<=n;i++){
            cin>>a[i];
        }
        for(int i=1;i<=n;i++){
            cin>>b[i];
        }
 
        int max0=max(a[1],b[1]),min0=min(a[1],b[1]);
 
        for(int i=1;i<n;i++){
            int tmp1=min(a[i],b[i]),tmp2=max(a[i],b[i]);
            max0=max(max0,tmp2),min0=max(min0,tmp1);
        }
 
        bool flag=0;
        if(a[n]>=max0&&b[n]>=min0)flag=1;
        if(b[n]>=max0&&a[n]>=min0)flag=1;
 
        if(flag)cout<<"Yes"<<endl;
        else cout<<"No"<<endl;
    }
    return 0;
}

---

B. Three Sevens（模拟）

Lottery "Three Sevens" was held for m days. On day ini people with the numbers ai,1,…,ai,ni participated in the lottery.

It is known that in each of the m days, only one winner was selected from the lottery participants. The lottery winner on day i was not allowed to participate in the lottery in the days from i+1 to m.

Unfortunately, the information about the lottery winners has been lost. You need to find any possible list of lottery winners on days from 1 to m or determine that no solution exists.

Input

Each test contains multiple test cases. The first line contains the number of test cases t (1≤t≤500001). The description of the test cases follows.

The first line of each test case contains a single integer m (1≤m≤50000) — the number of days in which the lottery was held.

Next, for each i from 11 to m follows a two-line block of data.

The first line of each block contains a single integer ni (1≤ni≤50000) — the number of lottery participants on day i

The second line of the block contains integers ai,1,…,ai,n (1≤ai,j≤50000) — lottery participants on day i. It is guaranteed that all the numbers ai,1,…,ai,ni are pairwise distinct.

It is guaranteed that the sum of ni over all blocks of all test cases does not exceed 5000050000.

Output

For each test case, if there is no solution, print a single integer −1−1.

Otherwise, print m integers p1,p2,…,pm (1≤pi≤50000) — lottery winners on days from 11 to m. If there are multiple solutions, print any of them.

Example

input

3

3

4

1 2 4 8

3

2 9 1

2

1 4

2

2

1 2

2

2 1

4

4

1 2 3 4

1

1

1

4

1

3

output

8 2 1 
-1
2 1 4 3 

Note

In the first test case, one of the answers is [8,2,1]since the participant with the number 88 participated on day 1, but did not participate on days 2and 3; the participant with the number 22 participated on day 2, but did not participate on day 33; and the participant with the number 1 participated on day 3. Note that this is not the only possible answer, for example, [8,9,4] is also a correct answer.

In the second test case, both lottery participants participated on both days, so any possible lottery winner on the day 1 must have participated on the day 2, which is not allowed. Thus, there is no correct answer.

In the third test case, only one participant participated on days 2, 3, 4, and on day 1 there is only one participant who did not participate in the lottery on days 2,3,4 — participant 2, which means [2,1,4,3] is the only correct answer to this test case.

题面翻译：

每个人都有一个号码

在m天里，每天有 n[i] 个人抽奖，抽一个人中奖，中过奖的人不能再参加抽奖

给定每天来抽奖的人的号码，问是否合法，输出合法的开奖顺序

思路：

从最后一天往前枚举每天来抽奖的人号码

如果这个人来抽奖了，那么他在前几天一定不可能中奖

如果这个人第一次出现，即最后一次抽奖，我们当做他中奖了，输出

代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n[50005];
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<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    return x*f;
}
 
int main(){
    int T=read();
    while(T--){
        int m=read();
        
        vector<vector<int> >a(m+1);
        
        for(int i=1;i<=m;i++){      //把数据储存起来，第i天
            a[i].push_back(0);
            n[i]=read();
            for(int j=1;j<=n[i];j++){       //第j个人的编号
                int t;
                t=read();
                a[i].push_back(t);
            }
        }
        
        unordered_set<int>s;
        vector<int>ans;
        
        bool flag=1;
        for(int i=m;i>=1;i--){      //倒着扫一遍
            bool tmp=1;     //标记有没有没出现过的数
            
            for(int j=1;j<=n[i];j++){       //枚举每个人的号码
                if(s.count(a[i][j]))continue;   //出现过则跳过
                
                if(tmp==1){     //第一个没出现过的，放进答案数组里
                    tmp=0;
                    ans.push_back(a[i][j]);
                }
                s.insert(a[i][j]);      //其他号码标记
            }
            
            if(tmp==1){     //如果没有没出现过的编号，这一天没人中奖，标记flag
                flag=0;
                break;
            }
        }
        
        if(flag==0){
            printf("-1\n");
            continue;
        }
        
        for(int i=ans.size()-1;i>=0;i--){   //ans是倒着储存的，再反过来输出
            printf("%d ",ans[i]);
        }
        cout<<endl;
    }
    return 0;
}

---

C. Candy Store（数学）

The store sells types of candies with numbers from 11 to n. One candy of type i costs bi coins. In total, there are ai candies of type i in the store.

You need to pack all available candies in packs, each pack should contain only one type of candies. Formally, for each type of candy i you need to choose the integer di, denoting the number of type i candies in one pack, so that ai is divided without remainder by di.

Then the cost of one pack of candies of type i will be equal to bi⋅di. Let's denote this cost by ci, that is, ci=bi⋅di

After packaging, packs will be placed on the shelf. Consider the cost of the packs placed on the shelf, in order c1,c2,…,cn. Price tags will be used to describe costs of the packs. One price tag can describe the cost of all packs from l to r inclusive if cl=cl+1=…=cr. Each of the packs from 11 to n must be described by at least one price tag. For example, if c1,…,cn=[4,4,2,4,4] to describe all the packs, a 33 price tags will be enough, the first price tag describes the packs 1,21,2, the second: 33, the third: 4,54,5.

You are given the integers a1,b1,a2,b2,…,an,bn. Your task is to choose integers di so that ai is divisible by di for all i, and the required number of price tags to describe the values of c1,c2,…,cnis the minimum possible.

For a better understanding of the statement, look at the illustration of the first test case of the first test:

Let's repeat the meaning of the notation used in the problem:

ai — the number of candies of type iavailable in the store.

bi — the cost of one candy of type i.

di— the number of candies of type i in one pack.

ci — the cost of one pack of candies of type i is expressed by the formula ci=bi⋅d

Input

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

The first line of each test case contains a single integer n(2≤n≤200000) — the number of types of candies.

Each of the next n lines of each test case contains two integers ai and bi (1≤ai≤109, 1≤bi≤10000) — the number of candies and the cost of one candy of type i, respectively.

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

Output

For each test case, output the minimum number of price tags required to describe the costs of all packs of candies in the store.

Example

input

5

4

20 3

6 2

14 5

20 7

3

444 5

2002 10

2020 2

5

7 7

6 5

15 2

10 3

7 7

5

10 1

11 5

5 1

2 2

8 2

6

7 12

12 3

5 3

9 12

9 3

1000000000 10000

output

2
1
3
2
5

Note

In the first test case, you can choose d1=4, d2=6, d3=7, d4=5. Then the cost of packs will be equal to [12,12,35,35][12,12,35,35]. 22 price tags are enough to describe them, the first price tag for c1,c2 and the second price tag for c3,c4. It can be shown that with any correct choice of di, at least 22 of the price tag will be needed to describe all the packs. Also note that this example is illustrated by a picture in the statement.

In the second test case, with d1=4, the costs of all packs will be equal to 2020. Thus, 1 price tag is enough to describe all the packs. Note that ai is divisible by di for all i, which is necessary condition.

In the third test case, it is not difficult to understand that one price tag can be used to describe 22nd, 33rd and 44th packs. And additionally a price tag for pack 1 and pack 55. Total: 3 price tags

题面翻译

给你n种糖果的数量和单价，每个糖果可以分任意袋装，但是每一袋中糖果数量必须相同
每个价格标签可以贴相邻种类的糖果袋装价相同的袋子
求最少需要多少标签贴所有糖果

思路

数学题，维护糖果总价的最大公约数和糖果单价的最小公倍数，如果最大公约数可以整除最小公倍数，则上一个标签可以贴当前糖果

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
 
ll gcd(ll x,ll y){   //最大公约数
    while(y^=x^=y^=x%=y);
    return x;
}
 
ll lcm(ll x,ll y){   //最小公倍数
    return x/gcd(x,y)*y;
}
 
ll a[2000005],b[2000005],c[2000005];
 
int main(){
    int T;
    cin>>T;
    while(T--){
 
        int n;
        cin>>n;
        for(int i=1;i<=n;i++){
            cin>>a[i]>>b[i];
            c[i]=a[i]*b[i];
        }
 
        ll ans=1;
        ll Lcm=b[1],Gcd=c[1];
 
        for(int i=2;i<=n;i++){
 
            Gcd=gcd(c[i],Gcd);
            Lcm=lcm(b[i],Lcm);
 
            if(Gcd%Lcm==0){    //如果最大公约数整除最小公倍数，则标签可以贴
                continue;
            }
 
            else{       //反之，另开一个标签
                ans++;
                Gcd=c[i];
                Lcm=b[i];
            }
 
        }
        cout<<ans<<endl;
    }
    return 0;
}

---

D. Shocking Arrangement （贪心，构造）

You are given an array a1,a2,…,an consisting of integers such that a1+a2+…+an=0

You have to rearrange the elements of the array a so that the following condition is satisfied:

max1≤l≤r≤n|al+al+1+…+ar|<max(a1,a2,…,an)−min(a1,a2,…,an),max

where |x| denotes the absolute value of x.

More formally, determine if there exists a permutation p1,p2,…,pn that for the array ap1,ap2,…,apn, the condition above is satisfied, and find the corresponding array.

Recall that the array p1,p2,…,pn is called a permutation if for each integer x from 11 to n there is exactly one i from 1 to nsuch that pi=x.

Input

Each test contains multiple test cases. The first line contains the number of test cases t (1≤t≤50000). The description of the test cases follows.

The first line of each test case contains a single integer n (1≤n≤300000) — the length of the array a.

The second line of each test case contains n integers a1,a2,…,an (−109≤ai≤109) — elements of the array a. It is guaranteed that the sum of the array a is zero, in other words: a1+a2+…+an=0

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

Output

For each test case, if it is impossible to rearrange the elements of the array a in the required way, print "No" in a single line.

If possible, print "Yes" in the first line, and then in a separate line n numbers — elements a1,a2,…,an rearranged in a valid order (ap1,ap2,…,apn.

If there are several possible answers, you can output any of them.

Example

input

7
4
3 4 -2 -5
5
2 2 2 -3 -3
8
-3 -3 1 1 1 1 1 1
3
0 1 -1
7
-3 4 3 4 -4 -4 0
1
0
7
-18 13 -18 -17 12 15 13

output

Yes
-5 -2 3 4
Yes
-3 2 -3 2 2
Yes
1 1 1 -3 1 1 1 -3
Yes
-1 0 1
Yes
4 -4 4 -4 0 3 -3
No
Yes
13 12 -18 15 -18 13 -17

Note

In the first test case max(a1,…,an)−min(a1,…,an)=9max. Therefore, the elements can be rearranged as[−5,−2,3,4]. It is easy to see that for such an arrangement |al+…+ar| is always not greater than 7, and therefore less than 9.

In the second test case you can rearrange the elements of the array as [−3,2,−3,2,2]. Then the maximum modulus of the sum will be reached on the subarray [−3,2,−3], and will be equal to |−3+2+−3|=|−4|=4, which is less than 55.

In the fourth test example, any rearrangement of the array awill be suitable as an answer, including [−1,0,1]

题面翻译

给你一个和为0的数列，对它重新排序，使任意一段区间的和的绝对值都不大于最大值和最小值的差

思路

贪心直接干碎，分两个数组储存大于等于0和小于0的数，然后分别降序、升序排序

优先从正数中取数，如果正数取完了或者和大于了最大值，则从负数中取数

如果该从负数中取数，却没数取了，数组不可能构成

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int a[3000005];
 
int main(){
    int T;
    cin>>T;
    while(T--){
 
        int n;
        cin>>n;
        vector<int>v1,v2,ans;
 
        for(int i=1;i<=n;i++){
            scanf("%d",&a[i]);
 
            if(a[i]>=0)v1.push_back(a[i]);      //分两个数组储存
            else v2.push_back(a[i]);
        }
 
        sort(v1.begin(),v1.end(),greater<int>());   //大于0的降序排列
        sort(v2.begin(),v2.end());                  //小于0的升序排列
 
        int tmp=*max_element(a+1,a+n+1)-*min_element(a+1,a+n+1);
                    //tmp储存不能超过的值
 
        ll sum=0,p1=0,p2=0;     //两个数组的指针
        bool flag=0;
        while(1){
 
            if(p1+p2==n){       //如果数列完全构成，退出循环
                flag=1;
                break;
            }
 
            if(p1<v1.size()&&sum+v1[p1]<tmp){   //如果可以放大数，则往里放
                sum+=v1[p1];
                ans.push_back(v1[p1]);
                p1++;
            }
 
            else{           //反之往数列放小数
 
                if(p2==v2.size()){      //数列不可能构造成，退出
                    flag=0;
                    break;
                }
 
                sum+=v2[p2];
                ans.push_back(v2[p2]);
                p2++;
            }
        }
        if(flag==0){
            cout<<"No"<<endl;
            continue;
 
        }
        cout<<"Yes"<<endl;
        for(auto it:ans){
            cout<<it<<' ';
        }
        cout<<endl;
    }
    return 0;
}