B번 문제입니다. 사과의 풍미(flavor) 값은 연속된 수열 값으로 나타납니다. 전체 값 중에서 사과 하나를 뺏을 때 차이가 가장 적을려면, 전체 값 중에 절대값이 가장 작은 것을 하나 빼버리면 됩니다.
O(N)으로 해결할 수 있습니다.
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
typedef long long ll;
typedef pair<int, int> pii;
int main() {
int N, L;
cin >> N >> L;
int S = (N - 1) * N / 2 + N * L;
int dect = 987654321;
for (int i = 0; i < N; i++) {
int cand = i + L;
if (abs(cand) < abs(dect)) {
dect = cand;
}
}
cout << (S - dect) << endl;
}
(전체) - (C로 나누어 떨어지는 수) - (D로 나누어 떨어지는 수) + (C와 D 둘다 나누어 떨어지는 수)
가 됩니다.
C와 D 둘다 나누어 떨어지는 수는 C와 D의 LCM(최소공배수)으로 나누어 떨어지는 수와 같습니다.
C와 D의 최소 공배수는 C*D / gcd(C, D)와 같습니다.
gcd(C, D)는 C와 D의 최대공약수를 뜻합니다.
#include <bits/stdc++.h>
#include <algorithm>
using namespace std;
#define endl '\n'
typedef long long ll;
typedef pair<int, int> pii;
template<class T>
T gcd(T a, T b)
{
if (b == 0) return a;
a %= b;
return gcd(b, a);
}
int main() {
ll A, B, C, D;
cin >> A >> B >> C >> D;
ll total = B - A + 1;
ll Cdiv = B / C - ((A - 1) / C);
ll Ddiv = B / D - ((A - 1) / D);
ll LCM = C * D / gcd(C, D);
ll CDdiv = B / LCM - ((A - 1) / LCM);
ll ans = total - Cdiv - Ddiv + CDdiv;
cout << ans << endl;
}
E번 문제입니다. 문제 내용을 잘못 이해해서 좀 해맸었는데, 일단 N개의 vertex로 shortest path = 2인 pair를 최대한 많이 만드는 구성을 한번 생각해봤습니다.
N=7이라 한다면, 대충 위와 같이 생겼을 때 가장 많은 shortest path = 2인 쌍이 생깁니다. 1을 제외한 모든 조합들이 가능한거죠.
즉 //(\dbinom{6}{2}//)개 만큼 생깁니다.
N에 대하여 일반화를 하면 //(\dbinom{N-1}{2}//)가지가 나오는 것이죠. 요렇게 나오는 경우가 최대 경우입니다.
따라서 //(K > \dbinom{N-1}{2} //)이면 불가능한 경우입니다.
그렇다면 저 최대값 이하의 값은 다 만들수가 있느냐?
이에 대한 답은 Yes입니다. 위 그림에서 예를 들어 4와 5를 연결해버리면, 4에서 5로 가는 최단거리가 1이 되어서, 만족하는 쌍의 수가 하나 줄게 됩니다. 그리고 그 추가된 Edge는 다른 pair들에는 전혀 영향을 끼치지 않죠. 이런식으로 하나하나씩 줄여서 K값을 0으로 만들수도 있습니다.
따라서 N값에 따라서 0~최대값까지 죄다 만들 수 있는 것이죠. 이 범위 안에 들어있다면 저런 형태의 graph를 리턴하고, 그렇지 않다면 불가능하다라고 출력하면 됩니다.
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
typedef long long ll;
typedef pair<int, int> pii;
int main() {
int N, K;
cin >> N >> K;
int maxi = (N - 1)*(N - 2) / 2;
if (K > maxi) {
cout << -1;
return 0;
}
int M = N - 1;
int diff = maxi - K;
cout << (M + diff) << endl;
for (int i = 0; i < M; i++) {
cout << 1 << ' ' << i + 2 << endl;
}
int src = 2;
int dst = 3;
for (int i = 0; i < diff; i++) {
cout << src << ' ' << dst << endl;
dst++;
if (dst == N + 1) {
src++;
dst = src + 1;
}
}
}
