Panasonic Programming Contest (AtCoder Beginner Contest 195)

A. Health M Death

Takahashi가 M만큼 몬스터를 때릴 수 있고 몬스터의 체력이 H일 때, H가 M의 배수가 아니라면 공격해도 소용이 없다. 즉, H가 M의 배수인지 확인하는 문제이다.

#include <iostream>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;
 
typedef long long ll;
typedef pair<int,int> pii;
 
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    // freopen("input.txt","r",stdin);
    int M,H;
    cin>>M>>H;
    if(H%M==0) {
        cout<<"Yes"<<endl;
        return 0;
    }
    cout<<"No"<<endl;
    return 0;
}

---

B. Many Oranges

오렌지의 최소 \(A\) g, 최대 \(B\) g이 주어지고 만들어야 하는 무게 \(W\) Kg가 가능한 지 확인하는 문제이다.

사실 이 문제는 풀지 못하고 에디토리얼로 확인했는데 아래 풀이가 맞는지는 모르겠다.

어떠한 수 \(N\) 이 \(AN ≤ 1000W ≤ BN\) 을 만족하면 \($A\) \(N\) 개 또는 \(B\) \(N\) 개를 가지고 \(W\) Kg을 만들 수 있다.

먼저, \(A\)g \(N\)개를 가지고 있다고 가정하자. 그러면 다음 골라아 하는 오렌지는 \(A\) 보다 크거나 같아야 한다. 이 오렌지의 무게를 \(C\)g이라하고, \(X\)개를 골라야 하는데 당연히 \(N\)개보다 작아야 한다. (\(A≤C≤B, \space 0≤X≤N\))

따라서, \(CX ≤ BN\)이어야 하고 \(CX=1000W-AN\)이므로 \(AN ≤ 1000W ≤ BN\)을 만족하는 \(N\)을 찾으면 된다.

#include <iostream>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;
 
typedef long long ll;
typedef pair<int,int> pii;
const ll INF=1e10+1;
 
int main(){
    //freopen("input.txt","r",stdin);
    int a,b,w;
    cin >> a >> b >> w;
    int m=1e9,M=0;
    for(int n=1;n<=1000000;n++){
        if(a*n<=1000*w && 1000*w<=b*n){
            m=min(m,n);
            M=max(M,n);
        }
    }
    if(M==0)cout << "UNSATISFIABLE";
    else cout << m << ' ' << M;
    return 0;
}

---

C. Comma

1,000 과 같이 \(10^3\) 마다 “,”를 찍어야 할 때, 주어진 N에 대해 1부터 N까지 모든 수에 콤마를 몇번 찍어야 하는지 계산하는 문제이다.

#include <iostream>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;
 
typedef long long ll;
typedef pair<int,int> pii;
const ll INF=1e10+1;
 
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    //freopen("input.txt","r",stdin);
    ll n;
    cin>>n;
    ll ans=0;
    if(n>=1e3) ans+=n-(1e3-1);
    if(n>=1e6) ans+=n-(1e6-1);
    if(n>=1e9) ans+=n-(1e9-1);
    if(n>=1e12) ans+=n-(1e12-1);
    if(n>=1e15) ans+=n-(1e15-1);
    cout<<ans;
    return 0;
}

---

D. Shipping Center

L번부터 R번 까지의 박스가 제외된 상태에서 가방을 나머지 박스에 넣어 최대 value를 계산하는 문제이다.

이 문제는 두 가지 방법으로 해결 할 수 있다.

1. 가방의 사이즈를 기준으로 오름차순 정렬하여 가능한 박스에 넣어서 최대 value를 계산하는 방법
2. 가방의 value를 기준으로 내림차순 정렬하여 가능한 박스에 넣어서 최대 value를 계산하는 방법

증명은 다음 링크에 있다.

#include <iostream>
#include <cstring>
#include <vector>
#include <algorithm>
#define endl '\n'
using namespace std;
 
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
const ll INF=1e10+1;
 
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    //freopen("input.txt","r",stdin);
    int n,m,q;
    cin>>n>>m>>q;
    vector<int> w(n),v(n),x(m);
    for(int i=0;i<n;i++) cin>>w[i]>>v[i];
    for(int i=0;i<m;i++) cin>>x[i];
    vector<pii> vw(n);
    for(int i=0;i<n;i++) vw[i]={v[i],w[i]};
    sort(vw.rbegin(),vw.rend()); // value를 기준으로 내림차순 정렬
    while(q--) {
        int l,r;
        cin>>l>>r;
        l--; r--;
        vector<int> px; // l-1 ~ r-1의 박스 제외
        for(int i=0;i<l;i++) px.push_back(x[i]);
        for(int i=r+1;i<m;i++) px.push_back(x[i]);
        sort(px.begin(),px.end()); // 박스 오름차순 정렬
        vector<bool> used(px.size());
        ll ans=0;
        for(int i=0;i<vw.size();i++) {
            for(int j=0;j<px.size();j++) {
                if(!used[j] && px[j]>=vw[i].second) {
                    ans+=vw[i].first;
                    used[j]=true;
                    break;
                }
            }
        }
        cout<<ans<<endl;
    }
    return 0;
}