Educational Codeforces Round 003. A, B, C, D

A. USB Flash Drives ( Флеш-карты )

문제

https://codeforces.com/contest/609/problem/A

Problem - A - Codeforces

 

문제 요약

여러 크기의 usb가 있는데 최소한의 개수로 주어진 파일 크기를 옮기자

 

풀이

DP를 사용합니다

usb의 개수가 n이고 주어진 파일 크기가 m일 때,

각 크기 a0, a1, ..., a(n-1)에 대해 순차적으로 보면서

배열 s의 j번째 칸이 의미하는 바를 용량 j를 만들기 위한 최소 usb개수로 정의하면 됩니다.

 

식으로 나타내면

 

s[j]가 존재할 때

s[j+a] = min( s[j+a] , s[j] + 1 )

 

모든 a에 대해 진행이 되었다면 s의 m번째 칸부터 끝까지 보면서 0이 아닌 모든 수들 중 가장 작은걸 골라주면 됩니다.

 

주어진 입력 예제

3

5

2

1

3

에 대해 보면

N=3. M=5, A = [2, 1, 3]인 상태이고

 

a = 2일 때

s	0	1	2	3	4	5
개수	-	-	1	-	-	-

 

a = 1일 때

s	0	1	2	3	4	5
개수	-	1	1	2	-	-

 

a = 3일 때

s	0	1	2	3	4	5
개수	-	1	1	1	2	2

 

M = 5에 대해 최소 2개의 USB로 파일을 옮길 수 있습니다

 

소스코드

#include <stdio.h>

int mn(int a,int b){return a<b?a:b;}

const int MAXN=110000;
int s[MAXN];

int main(){
    int n, m;
    scanf("%d%d",&n,&m);
    for(int i=0; i<n; ++i){
        int a;
        scanf("%d",&a);
        for(int j=m; --j;){
            if(s[j] && (!s[j+a] || s[j+a]>s[j]+1)) s[j+a]=s[j]+1;
        }
        s[a]=1;
    }
    int pmn=0;
    for(int i=m; i<MAXN; ++i){
        if(s[i]) {
            if(!pmn) pmn=s[i];
            else pmn=mn(pmn,s[i]);
        }
    }
    printf("%d",pmn);
}

 

B. The Best Gift ( Книга - лучший подарок )

문제

https://codeforces.com/contest/609/problem/B

Problem - B - Codeforces

문제요약

각 책마다 장르가 다르다. 서로 장르가 다른 두 책을 고르는 방법의 가지 수를 구해라(순서가 다른것은 동형이다.)

 

풀이

현재 책에 대해서 지금까지 책 중 자신의 장르와 다른 책들의 가지수를 누적하면 된다.

 

소스코드

 

#include <bits/stdc++.h>
using namespace std;
int t[11], p, n, m, k;
int main(){
	scanf("%d%d",&n,&k);
	for(int i=0; i<n; ++i) scanf("%d",&m), p+=i-t[m]++;
	printf("%d",p);
}

C. Load Balancing

https://codeforces.com/contest/609/problem/C

Problem - C - Codeforces

 

문제요약

숫자들이 주어졌을 때 이들을 잘 옮겨서 서로간 차이가 1이하가 될 수 있도록 하라

 

풀이

옮기는건 한 작업에서 1빼고 다른 작업에서 1더하는것

배열을 정렬해두고 n-sum%n개는 평균, 나머지 sum%n개는 평균+1만큼 뺀값의 절댓값들의 합을 구한다.

이를 반으로 나누어 출력한다. 정렬때문에 O(NlogN)

 

소스코드

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5+10;
ll n, a[N], b[N], q, r, p;
 
int main() {
	scanf("%lld",&n);
	for(int i=0; i<n; ++i) scanf("%lld",&a[i]), q+=a[i];
	sort(a,a+n);
	r=q%n, q/=n;
	for(int i=0; i<n-r; ++i) p+=abs(a[i]-q);
	for(int i=n-r; i<n; ++i) p+=abs(a[i]-q-1);
	printf("%lld",p>>1);
}

 

D. Gadgets for dollars and pounds

문제

https://codeforces.com/contest/609/problem/D

Problem - D - Codeforces

 

문제요약

전체 m개의 물건들 중 k개를 사고자 한다. 각 물건은 $d_i$ 또는 $p_i$의 값어치를 가진다.

공통화폐 b를 s만큼 들고있는데 이는 d 또는 p와 교환할 수 있다. 매일 매일 d, p의 환율이 바뀌는데 k개의 물건을 사는데 몇 일이 걸릴까?

물건을 마지막날까지 k개만큼 살 수 없다면 -1을 출력한다.

 

풀이

특정 날짜까지의 d, p 각각의 최소 환율을 구하는건 매우 간단하다.

이분탐색을 해당 날짜에서의 물건 k개를 사는데 드는 돈을 찾고 이것이 s(단위 b)보다 큰지 작은지 판별하면서 탐색한다.

 

소스코드

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e5+1;
ll n, m, k, s;
ll d[N], dd[N], p[N], pp[N], t[N], c[N];
vector<pair<ll,ll>> f;

int main(){
	scanf("%lld%lld%lld%lld",&n,&m,&k,&s);
	for(int i=0; i<n; ++i) scanf("%lld",&d[i]), dd[i]=(i&&d[dd[i-1]]<d[i])?dd[i-1]:i;
	for(int i=0; i<n; ++i) scanf("%lld",&p[i]), pp[i]=(i&&p[pp[i-1]]<p[i])?pp[i-1]:i;
	for(int i=0; i<m; ++i) scanf("%lld%lld",&t[i],&c[i]), --t[i];
	ll S=0, E=n-1, M;
	while(S < E){
		M = (S+E)>>1;
		ll bb=0;
		f.clear();
		for(int i=0; i<m; ++i) f.push_back({c[i]*(t[i]?p[pp[M]]:d[dd[M]]), 0});
		sort(f.begin(),f.end());
		for(int i=0; i<k; i++) bb+=f[i].first;
		bb<=s?E=M:S=M+1;
	}
	ll bb=0;
	f.clear();
	for(int i=0; i<m; ++i) f.push_back({c[i]*(t[i]?p[pp[S]]:d[dd[S]]), 0});
	sort(f.begin(),f.end());
	for(int i=0; i<k; i++) bb+=f[i].first;
	if(bb>s) {puts("-1"); return 0;}
	f.clear();
	for(int i=0; i<m; ++i) f.push_back({c[i]*(t[i]?p[pp[S]]:d[dd[S]]),i});
	sort(f.begin(),f.end());
	printf("%lld\n",S+1);
	for(int i=0; i<k; ++i) printf("%lld %lld\n",f[i].second+1,(t[f[i].second]?pp[S]:dd[S])+1);
}