# Codeforces Round 350 (Div. 2) ABCD1D2()-其他

## Codeforces Round 350 (Div. 2) ABCD1D2()

https://codeforces.com/contest/670

### A. Holidays

``````题目大意：

``````
``````input
14
output
4 4
``````
``````#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<LL,LL> PII;
const LL MAXN=1e18,MINN=-MAXN;
const LL N=2e5+10,M=2023;
const LL mod=998244353;
const double PI=3.1415926535;
#define endl '\n'
LL a[N];
int main()
{
cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);
int T=1;
//cin>>T;
while(T--)
{
LL n;
cin>>n;
if(n<=2) cout<<"0 "<<n<<endl;
else
{
LL sum1=n/7*2+max((LL)0,n%7-5);
LL sum2=2;
n-=2;
sum2+=n/7*2+max((LL)0,n%7-5);
cout<<sum1<<" "<<sum2<<endl;
}
}
return 0;
}
``````

### B. Game of Robots

``````题目大意：

``````
``````input
4 5
10 4 18 3
output
4
``````
``````#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<LL,LL> PII;
const LL MAXN=1e18,MINN=-MAXN;
const LL N=2e5+10,M=2023;
const LL mod=998244353;
const double PI=3.1415926535;
#define endl '\n'
LL a[N],b[N];
int main()
{
cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);
int T=1;
//cin>>T;
while(T--)
{
LL n,m;
cin>>n>>m;
b[0]=0;
for(int i=1;i<=n;i++)
{
cin>>a[i];
b[i]=b[i-1]+i;
}
LL idx=lower_bound(b+1,b+1+n,m)-b-1;
LL op=m-b[idx];
cout<<a[op]<<endl;
}
return 0;
}
``````

### C. Cinema

``````题目大意：

n个人一起看电影，每个人都有自己认识的语言；

m部电影，每一部电影都有值ai，bi，

ai值和看电影的人符合，则特别满意度上升；bi值和看电影的人符合，则满意度上升。

``````
``````input
3
2 3 2
2
3 2
2 3
output
2
``````
``````#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<LL,LL> PII;
const LL MAXN=1e18,MINN=-MAXN;
const LL N=2e5+10,M=2023;
const LL mod=998244353;
const double PI=3.1415926535;
#define endl '\n'
struct node
{
LL l=0,r=0;
LL idx;
}a[N];
bool cmp(node xx,node yy)
{
if(xx.l!=yy.l) return xx.l>yy.l;
else return xx.r>yy.r;
}
int main()
{
cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);
int T=1;
//cin>>T;
while(T--)
{
LL n;
cin>>n;
map<LL,LL> know;
for(int i=1;i<=n;i++)
{
LL x;
cin>>x;
know[x]++;
}
LL m;
cin>>m;
for(int i=1;i<=m;i++)
{
LL x;
cin>>x;
a[i].l+=know[x];
}
for(int i=1;i<=m;i++)
{
LL x;
cin>>x;
a[i].r+=know[x];
a[i].idx=i;
}
sort(a+1,a+1+m,cmp);
/*
for(int i=1;i<=n;i++)
{
cout<<a[i].idx<<" "<<a[i].l<<" "<<a[i].r<<endl;
}
*/
cout<<a[1].idx<<endl;
}
return 0;
}
``````

### D1. Magic Powder – 1

``````题目大意：

``````
``````input
3 1
2 1 4
11 3 16
output
4
``````
``````#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<LL,LL> PII;
const LL MAXN=1e18,MINN=-MAXN;
const LL N=2e5+10,M=2023;
const LL mod=998244353;
const double PI=3.1415926535;
#define endl '\n'
LL a[N],b[N];
LL ans=0;
LL n,m;
bool check(LL x)
{
LL res=0;
for(int i=1;i<=n;i++)
{
if(x*a[i]<=b[i]) ;
else res+=(x*a[i]-b[i]);
if(res>m) return false;
}
if(res<=m) return true;
}
int main()
{
cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);
int T=1;
//cin>>T;
while(T--)
{
cin>>n>>m;
LL l=MAXN,r=1e9;
for(int i=1;i<=n;i++)
{
cin>>a[i];
}
for(int i=1;i<=n;i++)
{
cin>>b[i];
l=min(l,b[i]/a[i]);
}
while(l<=r)
{
LL mid=(l+r)/2;
if(check(mid))
{
l=mid+1;
ans=mid;
}
else r=mid-1;
}
cout<<ans<<endl;
}
return 0;
}
``````

### D2. Magic Powder – 2

``````题目大意：

``````
``````input
1 1000000000
1
1000000000
output
2000000000
``````
``````#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<LL,LL> PII;
const LL MAXN=1e18,MINN=-MAXN;
const LL N=2e5+10,M=2023;
const LL mod=998244353;
const double PI=3.1415926535;
#define endl '\n'
int a[N],b[N],ans=0,n,m;
bool check(int x)
{
LL res=0;
for(int i=1;i<=n;i++)
{
LL flag=(LL)a[i]*x;
if(flag>b[i])
res+=(flag-b[i]);
if(res>m) return false;
}
if(res<=m) return true;
}
int main()
{
cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);
int T=1;
//cin>>T;
while(T--)
{
cin>>n>>m;
LL l=0,r=2e9+1;
for(int i=1;i<=n;i++)
{
cin>>a[i];
}
for(int i=1;i<=n;i++)
{
cin>>b[i];
}
while(l<=r)
{
int mid=(l+r)/2;
if(check(mid))
{
l=mid+1;
ans=mid;
}
else r=mid-1;
}
cout<<ans<<endl;
}
return 0;
}
``````

————————

https://codeforces.com/contest/670

### A. Holidays

``````题目大意：

``````
``````input
14
output
4 4
``````
``````#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<LL,LL> PII;
const LL MAXN=1e18,MINN=-MAXN;
const LL N=2e5+10,M=2023;
const LL mod=998244353;
const double PI=3.1415926535;
#define endl '\n'
LL a[N];
int main()
{
cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);
int T=1;
//cin>>T;
while(T--)
{
LL n;
cin>>n;
if(n<=2) cout<<"0 "<<n<<endl;
else
{
LL sum1=n/7*2+max((LL)0,n%7-5);
LL sum2=2;
n-=2;
sum2+=n/7*2+max((LL)0,n%7-5);
cout<<sum1<<" "<<sum2<<endl;
}
}
return 0;
}
``````

### B. Game of Robots

``````题目大意：

``````
``````input
4 5
10 4 18 3
output
4
``````
``````#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<LL,LL> PII;
const LL MAXN=1e18,MINN=-MAXN;
const LL N=2e5+10,M=2023;
const LL mod=998244353;
const double PI=3.1415926535;
#define endl '\n'
LL a[N],b[N];
int main()
{
cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);
int T=1;
//cin>>T;
while(T--)
{
LL n,m;
cin>>n>>m;
b[0]=0;
for(int i=1;i<=n;i++)
{
cin>>a[i];
b[i]=b[i-1]+i;
}
LL idx=lower_bound(b+1,b+1+n,m)-b-1;
LL op=m-b[idx];
cout<<a[op]<<endl;
}
return 0;
}
``````

### C. Cinema

``````题目大意：

n个人一起看电影，每个人都有自己认识的语言；

m部电影，每一部电影都有值ai，bi，

ai值和看电影的人符合，则特别满意度上升；bi值和看电影的人符合，则满意度上升。

``````
``````input
3
2 3 2
2
3 2
2 3
output
2
``````
``````#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<LL,LL> PII;
const LL MAXN=1e18,MINN=-MAXN;
const LL N=2e5+10,M=2023;
const LL mod=998244353;
const double PI=3.1415926535;
#define endl '\n'
struct node
{
LL l=0,r=0;
LL idx;
}a[N];
bool cmp(node xx,node yy)
{
if(xx.l!=yy.l) return xx.l>yy.l;
else return xx.r>yy.r;
}
int main()
{
cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);
int T=1;
//cin>>T;
while(T--)
{
LL n;
cin>>n;
map<LL,LL> know;
for(int i=1;i<=n;i++)
{
LL x;
cin>>x;
know[x]++;
}
LL m;
cin>>m;
for(int i=1;i<=m;i++)
{
LL x;
cin>>x;
a[i].l+=know[x];
}
for(int i=1;i<=m;i++)
{
LL x;
cin>>x;
a[i].r+=know[x];
a[i].idx=i;
}
sort(a+1,a+1+m,cmp);
/*
for(int i=1;i<=n;i++)
{
cout<<a[i].idx<<" "<<a[i].l<<" "<<a[i].r<<endl;
}
*/
cout<<a[1].idx<<endl;
}
return 0;
}
``````

### D1. Magic Powder – 1

``````题目大意：

``````
``````input
3 1
2 1 4
11 3 16
output
4
``````
``````#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<LL,LL> PII;
const LL MAXN=1e18,MINN=-MAXN;
const LL N=2e5+10,M=2023;
const LL mod=998244353;
const double PI=3.1415926535;
#define endl '\n'
LL a[N],b[N];
LL ans=0;
LL n,m;
bool check(LL x)
{
LL res=0;
for(int i=1;i<=n;i++)
{
if(x*a[i]<=b[i]) ;
else res+=(x*a[i]-b[i]);
if(res>m) return false;
}
if(res<=m) return true;
}
int main()
{
cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);
int T=1;
//cin>>T;
while(T--)
{
cin>>n>>m;
LL l=MAXN,r=1e9;
for(int i=1;i<=n;i++)
{
cin>>a[i];
}
for(int i=1;i<=n;i++)
{
cin>>b[i];
l=min(l,b[i]/a[i]);
}
while(l<=r)
{
LL mid=(l+r)/2;
if(check(mid))
{
l=mid+1;
ans=mid;
}
else r=mid-1;
}
cout<<ans<<endl;
}
return 0;
}
``````

### D2. Magic Powder – 2

``````题目大意：

``````
``````input
1 1000000000
1
1000000000
output
2000000000
``````
``````#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<LL,LL> PII;
const LL MAXN=1e18,MINN=-MAXN;
const LL N=2e5+10,M=2023;
const LL mod=998244353;
const double PI=3.1415926535;
#define endl '\n'
int a[N],b[N],ans=0,n,m;
bool check(int x)
{
LL res=0;
for(int i=1;i<=n;i++)
{
LL flag=(LL)a[i]*x;
if(flag>b[i])
res+=(flag-b[i]);
if(res>m) return false;
}
if(res<=m) return true;
}
int main()
{
cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);
int T=1;
//cin>>T;
while(T--)
{
cin>>n>>m;
LL l=0,r=2e9+1;
for(int i=1;i<=n;i++)
{
cin>>a[i];
}
for(int i=1;i<=n;i++)
{
cin>>b[i];
}
while(l<=r)
{
int mid=(l+r)/2;
if(check(mid))
{
l=mid+1;
ans=mid;
}
else r=mid-1;
}
cout<<ans<<endl;
}
return 0;
}
``````