03 Jan 2021 |
PS
AtCoder Beginner Contest 182 B번 Almost GCD
문제
https://atcoder.jp/contests/abc182/tasks/abc182_b
풀이
정수 k의 GCD-ness를 A1 ~ Ak의 수중 k로 나누어지는 정수의 개수라고 했을 때
가장 큰 GCD-ness를 갖는 정수 k를 찾는 문제
입력받은 수열 중 최댓값까지의 소수들을 k로 하여 해당 값들의 GCD-ness를 구하여 GCD-ness가 가장 큰 값 하나를 출력하면 된다.
코드
#pragma warning(disable : 4996)
#include <bits/stdc++.h>
#define all(x) (x).begin(), (x).end()
using namespace std;
typedef long long ll;
typedef long double ld;
typedef vector<ll> vll;
typedef pair<ll, ll> pll;
typedef pair<ld, ld> pld;
typedef tuple<ll, ll, ll> tl3;
#define FOR(a, b, c) for (int(a) = (b); (a) < (c); ++(a))
#define FORN(a, b, c) for (int(a) = (b); (a) <= (c); ++(a))
#define rep(i, n) FOR(i, 0, n)
#define repn(i, n) FORN(i, 1, n)
#define tc(t) while (t--)
// https://atcoder.jp/contests/abc182/tasks/abc182_b
ll che[1001] ={0,};
vll prime;
void getChe(ll num) {
for (int i = 2; i <= num; i++) {
che[i] = i;
}
for (int i = 2; i <= num; i++) {
if (che[i] == 0)
continue;
for (int j = i + i; j <= num; j += i) {
che[j] = 0;
}
}
}
void getPrime(ll num){
for(int i = 2;i<=num;i++){
if(che[i])
prime.push_back(i);
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
ll max = 0;
ll ans = 0;
ll n;
cin >> n;
vll v(n);
rep(i,n) cin >> v[i];
sort(all(v));
getChe(v[v.size()-1]);
getPrime(v[v.size()-1]);
for(auto k : prime){
ll cnt = 0;
for(int i =0;i<n;i++){
if(v[i] % k == 0) cnt++;
}
if(cnt > max) {
max = cnt;
ans = k;
}
}
cout << ans;
return 0;
}
03 Jan 2021 |
PS
AtCoder Beginner Contest 182 A번 twiblr
문제
https://atcoder.jp/contests/abc182/tasks/abc182_a
풀이
단순한 산수 문제
현재 B명을 팔로잉 중일 때 추가로 몇 명을 더 팔로잉 할 수 있는지 구하는 문제
코드
#pragma warning(disable : 4996)
#include <bits/stdc++.h>
#define all(x) (x).begin(), (x).end()
using namespace std;
typedef long long ll;
typedef long double ld;
typedef vector<ll> vll;
typedef pair<ll, ll> pll;
typedef pair<ld, ld> pld;
typedef tuple<ll, ll, ll> tl3;
#define FOR(a, b, c) for (int(a) = (b); (a) < (c); ++(a))
#define FORN(a, b, c) for (int(a) = (b); (a) <= (c); ++(a))
#define rep(i, n) FOR(i, 0, n)
#define repn(i, n) FORN(i, 1, n)
#define tc(t) while (t--)
// https://atcoder.jp/contests/abc182/tasks/abc182_a
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
ll a,b;
cin >> a >> b;
cout << (2 * a + 100) - b;
return 0;
}
15 Nov 2020 |
PS
AtCoder Beginner Contest 181 C번 Collinearity
문제
https://atcoder.jp/contests/abc181/tasks/abc181_c
풀이
n개의 (x,y) 좌표가 있을때 3개의 점이 일직선에 있는 경우가 있는지 없는지를 판별하는 문제
n의 최대치가 100으로 매우 작기 떄문에 O(n^3)으로 돌려도 무난하게 AC를 받을 수 있다.
코드
#pragma warning(disable : 4996)
#include <bits/stdc++.h>
#define all(x) (x).begin(), (x).end()
using namespace std;
typedef long long ll;
typedef long double ld;
typedef vector<ll> vll;
typedef pair<ll, ll> pll;
typedef pair<ld, ld> pld;
typedef tuple<ll, ll, ll> tl3;
#define FOR(a, b, c) for (int(a) = (b); (a) < (c); ++(a))
#define FORN(a, b, c) for (int(a) = (b); (a) <= (c); ++(a))
#define rep(i, n) FOR(i, 0, n)
#define repn(i, n) FORN(i, 1, n)
#define tc(t) while (t--)
// https://atcoder.jp/contests/abc181/tasks/abc181_c
ll x[101];
ll y[101];
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
ll n;
cin >> n;
ll ans = 0;
rep(i, n)
{
cin >> x[i] >> y[i];
}
for (ll i = 0; i < n - 2; i++) {
for (ll j = i+1; j < n - 1; j++) {
for (ll k = j+1; k < n; k++) {
ll a, b, c, d;
a = x[j] - x[i];
b = x[k] - x[j];
c = y[j] - y[i];
d = y[k] - y[j];
if(a*d == b*c){
cout << "Yes";
return 0;
}
}
}
}
cout << "No";
return 0;
}
15 Nov 2020 |
PS
AtCoder Beginner Contest 181 B번 Trapezoid Sum
문제
https://atcoder.jp/contests/abc181/tasks/abc181_b
풀이
Trapezoid은 사다리꼴이라는 이야긴데 왜 사다리꼴인지는 모르겠다.
n까지의 모든 i에 대해 A_i부터 B_i 까지의 모든 합을 더하면 되는 문제이다.
코드
#pragma warning(disable : 4996)
#include <bits/stdc++.h>
#define all(x) (x).begin(), (x).end()
using namespace std;
typedef long long ll;
typedef long double ld;
typedef vector<ll> vll;
typedef pair<ll, ll> pll;
typedef pair<ld, ld> pld;
typedef tuple<ll, ll, ll> tl3;
#define FOR(a, b, c) for (int(a) = (b); (a) < (c); ++(a))
#define FORN(a, b, c) for (int(a) = (b); (a) <= (c); ++(a))
#define rep(i, n) FOR(i, 0, n)
#define repn(i, n) FORN(i, 1, n)
#define tc(t) while (t--)
// https://atcoder.jp/contests/abc181/tasks/abc181_b
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
ll n;
cin >> n;
ll ans = 0;
rep(i,n){
ll s,e;
cin >> s >> e;
ans += (e * (e+1))/2 - (s*(s-1))/2;
}
cout << ans;
return 0;
}
15 Nov 2020 |
PS
AtCoder Beginner Contest 181 A번 Heavy Rotation
문제
https://atcoder.jp/contests/abc181/tasks/abc181_a
풀이
일본의 모 아이돌의 노래와 동일한 제목이다.
문제는 그냥 까만옷과 하얀옷을 번갈아 입을 때 N일 뒤에는 무슨옷을 입을 지 선택하는 문제
코드
#pragma warning(disable : 4996)
#include <bits/stdc++.h>
#define all(x) (x).begin(), (x).end()
using namespace std;
typedef long long ll;
typedef long double ld;
typedef vector<ll> vll;
typedef pair<ll, ll> pll;
typedef pair<ld, ld> pld;
typedef tuple<ll, ll, ll> tl3;
#define FOR(a, b, c) for (int(a) = (b); (a) < (c); ++(a))
#define FORN(a, b, c) for (int(a) = (b); (a) <= (c); ++(a))
#define rep(i, n) FOR(i, 0, n)
#define repn(i, n) FORN(i, 1, n)
#define tc(t) while (t--)
// https://atcoder.jp/contests/abc181/tasks/abc181_a
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
ll n;
cin >> n;
if(n&1) cout << "Black";
else cout << "White";
return 0;
}