AtCoderBeginnerContest112

---

AtCoder Beginner Contest 112比赛链接

emm.第一次在AtCoder上的比赛. rank:754th rating:113. AC. WA.表示比赛时候的状态

A - Programming Education

AC

题目大意: 输入1的时候输出”Hello World”. 输入2的时候会输入a,b.计算a+b.

题解: emm.入门操作.beginner出这个题还是很不错的.

#include <bits/stdc++.h>
using namespace std;

int main(){
	//freopen("in.txt", "r", stdin);
	ios::sync_with_stdio(0); cin.tie(0);
    int kind,a,b;
    while(cin >> kind){
        if(kind == 1){
            cout << "Hello World" << endl;
        } else {
            cin >> a >> b;
            cout << (a+b) << endl;
        }
    }
	return 0;
}

B - Time Limit Exceeded

AC

题目大意:
给两个数N,T. N组数.每组两个数$c_i$和$t_i$.求所有不超过T的$t_i$中$c_i$的最小值.

题解:
emm.入门操作.beginner出这个题还是很不错的.

#include <bits/stdc++.h>
using namespace std;

#define MAX_N 105
int N,T;

int main(){
	//freopen("in.txt", "r", stdin);
	ios::sync_with_stdio(0); cin.tie(0);
    int c,t;
    while(cin >> N >> T){
        int ans = INT_MAX;
        for(int i = 1; i <= N; ++i){
            cin >> c >> t;
            if(t <= T) ans = min(ans, c);
        }
        if(ans == INT_MAX) cout << "TLE" << endl;
        else cout << ans << endl;
    }
	return 0;
}

C - Pyramid

WA

ps: 到最后没做出这道题.想暴力.然后看到

The center coordinates and the height of the pyramid can be uniquely identified

这句话.理解成中心点的坐标和h可能是无穷的.orz
应该是:
可以唯一地识别金字塔的中心坐标和高度. by google translate

题目大意:
有N个点.$(x_i, y_i,h_i)$. $h_i$表示这个点的高度.求一个点$(C_x, C_y, H)$满足.
$h_i = max(H-|x_i - C_x| + |y_i - C_y|, 0)$.

题解:
由于$0 <= C_x, C_y <= 100.$所以暴力即可.

#include <bits/stdc++.h>
using namespace std;



#define MAX_N 110
int n;
int x[MAX_N], y[MAX_N], h[MAX_N];

int main(){
	//freopen("in.txt", "r", stdin);
	ios::sync_with_stdio(0); cin.tie(0);
    while(cin >> n){
        for(int i = 1; i <= n; ++i){
            cin >> x[i] >> y[i] >> h[i];
            if(h[i] > 0) {
                swap(h[i], h[1]);
                swap(x[i], x[1]);
                swap(y[i], y[1]);
            }
        }
        for(int cx = 0; cx <= 100; ++cx){
            for(int cy = 0; cy <= 100; ++cy){
                int ch = h[1] + abs(x[1] - cx) + abs(y[1] - cy);
                bool is = true;
                for(int i = 2; i <= n; ++i){
                    if(max(ch - abs(x[i] - cx) - abs(y[i] - cy), 0) != h[i]) {
                        is = false;
                        break;
                    }
                }
                if(is){
                    cout << cx << " " << cy << " " << ch << endl;
                    return 0;
                }
            }
        }
    }
	return 0;
}

D - Partition

AC

题目大意:
两个数N,M.可以有多种方案找N个数之和是M.每种方案N个数的最大公约数是x.这多种方案中x最大

$$\sum_{i=1}^{N}a_i = M$$
$$ans = max(gcd(a_1, a_2,…,a_N))$$

题解:
可以确定.答案不超过M/N.如果答案是x.那么.这个N个数一定是x的倍数.所以只要从M/N到1枚举.第一个满足
M每次减去x的k倍.最后如果M是0.说明当前x是答案.因为是从大到小枚举.所以第一个肯定是最大的.

#include <bits/stdc++.h>
using namespace std;

#define MAX_N 105
int N,M;

bool can(int x){
    int m = M;
    m -= x;
    while(m > 0 && m/x){
        m -= (m/x * x);
    }
    return m == 0;
}

int main(){
	//freopen("in.txt", "r", stdin);
	ios::sync_with_stdio(0); cin.tie(0);
    while(cin >> N >> M){
        for(int ans = M/N; ans >= 1; --ans){
            if(can(ans)) {
                cout << ans << endl;
                break;
            }
        }
    }
	return 0;
}