2018-2019 ICPC, NEERC, Northern Eurasia Finals (Unrated, Online Mirror, ICPC Rules, Teams Preferred)
L. Lazyland
time limit per test
1.5 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output
The kingdom of Lazyland is the home to nn idlers. These idlers are incredibly lazy and create many problems to their ruler, the mighty King of Lazyland.
Today kk important jobs for the kingdom (k≤nk≤n) should be performed. Every job should be done by one person and every person can do at most one job. The King allowed every idler to choose one job they wanted to do and the ii-th idler has chosen the job aiai.
Unfortunately, some jobs may not be chosen by anyone, so the King has to persuade some idlers to choose another job. The King knows that it takes bibi minutes to persuade the ii-th idler. He asked his minister of labour to calculate the minimum total time he needs to spend persuading the idlers to get all the jobs done. Can you help him?
Input
The first line of the input contains two integers nn and kk (1≤k≤n≤1051≤k≤n≤105) — the number of idlers and the number of jobs.
The second line of the input contains nn integers a1,a2,…,ana1,a2,…,an (1≤ai≤k1≤ai≤k) — the jobs chosen by each idler.
The third line of the input contains nn integers b1,b2,…,bnb1,b2,…,bn (1≤bi≤1091≤bi≤109) — the time the King needs to spend to persuade the ii-th idler.
Output
The only line of the output should contain one number — the minimum total time the King needs to spend persuading the idlers to get all the jobs done.
Examples
input
8 7
1 1 3 1 5 3 7 1
5 7 4 8 1 3 5 2
output
10
input
3 3
3 1 2
5 3 4
output
0
Note
In the first example the optimal plan is to persuade idlers 1, 6, and 8 to do jobs 2, 4, and 6.
In the second example each job was chosen by some idler, so there is no need to persuade anyone.
//将b排序，在保证a不小于0的情况下加上b；
#include<bits/stdc++.h>
using namespace std;
int a[100005];
int vis[100005];
struct node{
int a,b;
}c[100005];
int cmp(node x,node y){
return x.b<y.b;
}
int main(){
int n,k,cnt;
long long ans;
scanf("%d%d",&n,&k);
memset(vis,0,sizeof(vis));
for(int i=1;i<=n;i++){
scanf("%d",&c[i].a);
vis[c[i].a]++;
}
for(int i=1;i<=n;i++){
scanf("%d",&c[i].b);
}
sort(c+1,c+n+1,cmp);
cnt=0,ans=0;
for(int i=1;i<=k;i++){
if(vis[i]==0)
cnt++;
}
for(int i=1;i<=n;i++){
if(vis[c[i].a]==1)
continue;
if(cnt==0)
break;
vis[c[i].a]--;
cnt--;
ans+=c[i].b;
}
printf("%lld\n",ans);
}
G. Guest Student
time limit per test
1.5 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output
Berland State University invites people from all over the world as guest students. You can come to the capital of Berland and study with the best teachers in the country.
Berland State University works every day of the week, but classes for guest students are held on the following schedule. You know the sequence of seven integers a1,a2,…,a7a1,a2,…,a7 (ai=0ai=0 or ai=1ai=1):
- a1=1a1=1 if and only if there are classes for guest students on Sundays;
- a2=1a2=1 if and only if there are classes for guest students on Mondays;
- ...
- a7=1a7=1 if and only if there are classes for guest students on Saturdays.
The classes for guest students are held in at least one day of a week.
You want to visit the capital of Berland and spend the minimum number of days in it to study kk days as a guest student in Berland State University. Write a program to find the length of the shortest continuous period of days to stay in the capital to study exactly kk days as a guest student.
Input
The first line of the input contains integer tt (1≤t≤100001≤t≤10000) — the number of test cases to process. For each test case independently solve the problem and print the answer.
Each test case consists of two lines. The first of them contains integer kk (1≤k≤1081≤k≤108) — the required number of days to study as a guest student. The second line contains exactly seven integers a1,a2,…,a7a1,a2,…,a7 (ai=0ai=0 or ai=1ai=1) where ai=1ai=1 if and only if classes for guest students are held on the ii-th day of a week.
Output
Print tt lines, the ii-th line should contain the answer for the ii-th test case — the length of the shortest continuous period of days you need to stay to study exactly kk days as a guest student.
Example
input
3
2
0 1 0 0 0 0 0
100000000
1 0 0 0 1 0 1
1
1 0 0 0 0 0 0
output
8
233333332
1
Note
In the first test case you must arrive to the capital of Berland on Monday, have classes on this day, spend a week until next Monday and have classes on the next Monday. In total you need to spend 88 days in the capital of Berland.
#include<bits/stdc++.h>
using namespace std;
int a[8];
int main(){
int T;
scanf("%d",&T);
while(T--){
int k,day=0,week;
scanf("%d",&k);
for(int i=1;i<=7;i++){
scanf("%d",&a[i]);
day+=a[i];
}
int ans=1000;
for(int i=1;i<=7;i++){
week=k%day+day;
int tot=0;
int j=i;
for(tot=1;;tot++){
if(a[j]==1)
week--;
j=j%7+1;
if(week==0)
break;
}
ans=min(tot,ans);
}
printf("%d\n",ans+(k/day-1)*7);
}
}E Easy Chess
Elma is learning chess figures. She learned that a rook can move either horizontally or vertically. To enhance her understanding of rook movement Elma’s grandmother gave Elma an 8 × 8 chess board and asked her to find a way to move the rook from a1 to h8 making exactly n moves, so that all visited cells are different. A visited cell is the initial cell a1 and each cell on which the rook lands after a move.
Input The input contains a single integer n (2 ≤ n ≤ 63) — the desired number of moves.
Output Output a space-separated list of n+ 1 visited cells in the order they are visited by the rook. All cells must be different. The list should start with a1 and end with h8. A solution always exists.
Example
4 a1 f1 c1 c8 h8
#include<bits/stdc++.h>
using namespace std;
int n;
bool bo[10][10];
int main() {
scanf("%d", &n);
printf("a1 ");
bo[1][1] = 1;
bo[8][8] = 1;
int x = 1, y = 1;
while (--n) {
if (n <= 5 && x != 8 && y != 8) {
y = 8;
} else {
int nx = 0;
for (int i = 8; i; --i) if (!bo[i][y]) {
nx = i;
break;
}
if (nx) x = nx; else ++y;
}
bo[x][y] = 1;
printf("%c%d ", 'a' + x - 1, y);
}
puts("h8");
return 0;
}