csa Round #66 (Div. 2 only)

csa66

Risk Rolls

Time limit: 1000 ms
Memory limit: 256 MB

Alena and Boris are playing Risk today. We'll call an outcome the sum of values on the faces of

In how many turns does Alena win? What about Boris?

Standard input

The first line contains two integers

The second contains

The third line contains

Standard output

Print two integers

Constraints and notes

Input	Output	Explanation
1 3 24 1 2 3	1 0	In the first turn, Alena will play
3 1 2 1 3 24	0 1	This is the first sample with reversed outcomes for Alena and Boris.
2 2 10 1 5 5	1 1
4 3 3 4 5 24 9 9 9	1 2	In the first turn Alena will beat Boris because she will play
3 3 8 9 10 10 8 8	1 2	In the first turn they will play

直接做就好了，排序，注意有个strictly就是大于

#include <bits/stdc++.h>
using namespace std;
int a[15],b[15];
int cmp(int a,int b)
{
    return a>b;
}
int main()
{
    int n,m;
    cin>>n>>m;
    int mi=min(n,m);
    for(int i=0;i<n;i++)
        cin>>a[i];
    for(int i=0;i<m;i++)
        cin>>b[i];
    sort(a,a+n,cmp);
    sort(b,b+n,cmp);
    int af=0,bf=0;
    for(int i=0;i<mi;i++)
        if(a[i]>b[i])af++;
        else bf++;
        cout<<af<<" "<<bf;
    return 0;
}

Processing Discounts

Time limit: 1000 ms
Memory limit: 256 MB

You've just placed an order of $AiA_iAi USD, you get back BiB_iBi USD. It may be advantageous to increase your order bill just so you would be eligible of certain discount offers.$

What's the minimum amount of USD that you have to pay in the end, after processing the discounts?

Standard input

The first line contains two integers,

The next $AiA_iAi and BiB_iBi.$

Standard output

Print the answer on the first line.

Constraints and notes

$10^51≤N≤105$
$A_i, B_i leq 10^61≤X,Ai,Bi≤106$
The online shopping website will never become in debt to you, i.e. the discount offers are chosen in such a way that you'd never reach a negative amount of payment.

Input	Output	Explanation
3 99 50 5 75 10 100 5	80	We're eligible for the first two discount offers, so we get If we increase our order up to
5 50 10 1 20 2 30 3 30 3 100 10	41	We're eligible for all the discount offers besides the last one. If we were to increase our payment in order to get the last offer, we would end up with It's better to only consider the first
1 10 100 95	5
1 200 100 95	105

B就是一个优惠券的问题，排下序，找到付款最小值就行了

#include<bits/stdc++.h>
using namespace std;
int n,x;
const int N=1e5+5;
pair<int,int> a[N];
int main()
{
    scanf("%d%d",&n,&x);
    for(int i=0; i<n; i++)
        scanf("%d%d",&a[i].first,&a[i].second);
    sort(a,a+n);
    int sum=x, s=0;
    for(int i=0; i<n; i++)
        s+=a[i].second,sum=min(sum,max(a[i].first,x)-s);
    printf("%d
",sum);
    return 0;
}

Counting Quacks

Time limit: 1000 ms
Memory limit: 256 MB

There are $X_iXi moments of time; i.e. it quacks for the first time at the X_i^{ ext{th}}Xith moment of time, it quacks for the second time at the {2 * X_i}^{ ext{th}}2∗Xith moment and so on...$

Alex is sitting near this lake and he asks himself:

What's the maximum number of quacks i'll hear at the same moment of time?
How many times i'll hear this many quacks throughout my staying at the lake?

Alex isn't feeling so contemplative today, so he's leaving the lake after

Standard input

The first line contains two integers,

The next line contains

Standard output

The first line contains two integers separated by space, as described in the statement.

Constraints and notes

$10^51≤N≤105$
$10^61≤T≤106$
$X_i leq 10^61≤Xi≤106 for each 1 leq i leq N1≤i≤N$
Alex comes at the lake at the moment of time

Input	Output
3 6 2 2 3	3 1
3 5 2 2 3	2 2
6 10 1 2 3 4 5 6	4 1

Ｃ当时太脑残了，没想到正确的做法，甚至想着去维护这些数，但是Ｔ不大啊，直接用埃筛的思想处理下就行了，复杂度Ｏ（Ｔ＋ＴｏｇＴ）

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+5;
int n,T,a[N],M[N];
int main()
{
    scanf("%d%d",&n,&T);
    for(int i=0,x; i<n; i++)
        scanf("%d",&x),++M[x];
    for(int i=1; i<=T; i++)
    {
        if(!M[i])continue;
        for(int j=i; j<=T; j+=i)a[j]+=M[i];
    }
    int ans=0,cnt=0;
    for(int i=1; i<=T; i++)
        if(a[i]>ans)ans=a[i],cnt=1;
        else if(a[i]==ans) cnt++;
    printf("%d %d
",ans,cnt);
    return 0;
}

Flipping Matrix

Time limit: 1000 ms
Memory limit: 256 MB

You are given a binary matrix

Take two rows and swap them. If we want to swap rows
Take two columns and swap them. If we want to swap columns

Is it possible to obtain only values of

Standard input

The first line contains

The next

Standard output

If there is no solution, print

Otherwise, print every operation on a separated line.

Constraints and notes

$10^32≤N≤103$
$A_{i, j} leq 10≤Ai,j≤1 for every 1 leq i, j leq N1≤i,j≤N$

Input	Output
3 0 0 1 0 1 0 1 0 0	C 1 3
4 1 1 0 0 0 1 0 1 1 1 0 0 0 0 0 1	-1
5 0 1 0 0 1 0 0 1 0 0 0 1 0 0 0 0 0 1 1 0 1 0 0 0 0	R 1 5 C 2 3

是个特判题，虽说可以交换行和列，但是其实交换哪个都一样，dfs遍历看看有没有机会得到对角线全是1，需要优秀的暴力，因为n还是很大的

#include<bits/stdc++.h>
using namespace std;
const int N=1005;
int a[N][N],F[N],n,y[N];
int dfs(int x)
{
    for(int i=1; i<=n; i++)
        if(a[x][i]&&!y[i])
        {
            y[i]=1;
            if(!F[i]||dfs(F[i]))
            {
                F[i]=x;
                return 1;
            }
        }
    return 0;
}
int la()
{
    for(int i=1; i<=n; i++)
    {
        memset(y,0,sizeof y);
        if(!dfs(i))return 0;
    }
return 1;
}
int main()
{
    scanf("%d",&n);
    for(int i=1; i<=n; i++)
        for(int j=1; j<=n; j++)
            scanf("%d",a[i]+j);
    if(!la())puts("-1");
    else
    {
        for(int i=1; i<=n; i++)
            for(int j=1; j<=n; j++)
                if(F[j]==i)
                {
                    if(j!=i)swap(F[j],F[i]),printf("C %d %d
",i,j);
                    break;
                }
    }
    return 0;
}