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
オレンジの最小AAAG、最大BBBgは、製造する必要がある重量WWKGが可能かどうかを確認します.
実は、この問題は答えられず、カタログで確認しただけで、次の答えが正しいかどうか分かりません.
任意の数のNNNはAN≦1000 W≦BNAN≦1000 W≦BNAN≦1000 W≦BNを満たし、AAA NNN個またはBBB NNN個を用いてWWWWKGを作成することができる.
まず、AAAG-NNを持っているとします.では、次のオレンジはAAA以上であるべきです.このオレンジの重さはCCCgと言いますが、XXX個を選びます.もちろんNNN個より小さいです.(A≤C≤B, 0≤X≤NA≤C≤B,\space 0≤X≤NA≤C≤B, 0≤X≤N)
したがって、CX≦BNX≦BNX≦BNである必要があり、CX=1000 W−ANCX=1000 W−ANCX=1000 W−ANCX=1000 W−ANである必要があるので、AN≦1000 W≦BNN≦1000 W≦BNN≦1000 W≦BNNを満たすNNNを見つければよい.

#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
1000に示すように、10310^3103ごとに「,」を付けると、与えられた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番までの箱を除く場合、残りの箱にバッグを入れて最大値を計算する問題です.
この問題は二つの方法で解決できる.

包の寸法に従って昇順に並べ、それを可能な箱に入れ、最大値を計算する方法

.

パケットの値に基づいて降順に並べ替え、可能なボックスに入れる、最大値を算出する方法

.
証明は次のリンクです.

#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;
}