algospot : https://algospot.com/judge/problem/read/FOSSIL

github : https://github.com/junho0956/Algorithm/blob/master/algospot%20FOSSIL/algospot%20FOSSIL/%EC%86%8C%EC%8A%A4.cpp

 

 

algospot FOSSIL 문제입니다. 

삼분탐색을 통해서 해결한 문제이고 기하문제를 처음풀어보는거라서

개념다잡는데 시간이 좀 걸렸습니다.

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
#include <iostream>
#include <vector>
#include <queue>
#include <stack>
#include <algorithm>
#include <set>
#include <cmath>
#include <limits>
using namespace std;
 
struct point {
    double x, y;
};
typedef vector<pair<point, point> > vp;
 
void decompose(vp & upper, vp& lower, vector<point>& a) {
    int n = a.size();
    for (int i = 0; i < n; i++) {
        if (a[i].x < a[(i + 1) % n].x) {
            lower.push_back({ a[i], a[(i + 1) % n] });
        }
        else {
            upper.push_back({ a[i], a[(i + 1) % n] });
        }
    }
}
 
double minX(vector<point>& a) {
    double ans = 1e9;
    for (int i = 0; i < a.size(); i++) {
        ans = min(ans, a[i].x);
    }
    return ans;
}
 
double maxX(vector<point>& a) {
    double ans = -1;
    for (int i = 0; i < a.size(); i++) {
        ans = max(ans, a[i].x);
    }
    return ans;
}
 
bool between(pair<point,point>& line, double x) {
    return (line.first.x <= x && x <= line.second.x) || (line.second.x <= x && x <= line.first.x);
}
 
double calY(point& a, point& b, double x) {
    // 직선의 방정식
    // y = m(x-x1)+y1
    return (b.y - a.y) / (b.x - a.x) * (x - a.x) + a.y;
}
 
// 주어진 x좌표에 대해서 껍질들의 y좌표를 확인하여 그 차액(길이)를 리턴한다.
double len(vp& upper, vp& lower, double x) {
    double minY, maxY;
    minY = 1e9, maxY = -1;
    // 위껍질의 선분들을 확인하여 주어진 x와 겹치는 y의 최솟값을 찾는다
    for (int i = 0; i < upper.size(); i++) {
        // 위껍질의 선분이 현재 x점의 수직선과 마주치는지 확인한다
        if (between(upper[i], x)) {
            // 만약 마주친다면(겹쳐진다면) 직선의 방정식 공식을 이용하여 x에 대한 y점을 가져온다.
            minY = min(minY, calY(upper[i].first, upper[i].second, x));
        }
    }
 
    // 아래껍질의 선분들을 확인하여 주어진 x와 겹치는 y의 최댓값을 찾는다
    for (int i = 0; i < lower.size(); i++) {
        // 위껍질의 선분이 현재 x점의 수직선과 마주치는지 확인한다
        if (between(lower[i], x)) {
            // 만약 마주친다면(겹쳐진다면) 직선의 방정식 공식을 이용하여 x에 대한 y점을 가져온다.
            maxY = max(maxY, calY(lower[i].first, lower[i].second, x));
        }
    }
 
    // 길이를 반환한다
    return minY - maxY;
}
 
double solve(vp& upper, vp& lower, vector<point>& a, vector<point>& b) {
    double lo = max(minX(a), minX(b));
    double hi = min(maxX(a), maxX(b));
    // 겹치지 않는 경우
    if (hi < lo) return 0;
 
    for (int i = 0; i < 100; i++) {
        double lp = (2 * lo + hi) / 3;
        double rp = (lo + 2 * hi) / 3;
        if (len(upper, lower, lp) < len(upper, lower, rp))
            lo = lp;
        else
            hi = rp;
    }
 
    // 경우에 따라 교집합의 길이가 아닌 부분이 반환될 수 있으니 (음수) 조건을 주어서 반환한다
    return max(0.0, len(upper, lower, hi));
}
 
int main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
 
    int T; cin >> T;
    while (T--) {
        int n, m;
        cin >> n >> m;
 
        vector<point> poly1, poly2;
 
        for (int i = 0; i < n; i++) {
            point a;
            cin >> a.x >> a.y;
            poly1.push_back(a);
        }
        for (int i = 0; i < m; i++) {
            point a;
            cin >> a.x >> a.y;
            poly2.push_back(a);
        }
 
        // 아래, 위 껍질을 구분해준다
        // 껍질의 구분으로 받게 될 값들은 "선분" 이 기준이 된다
        vp upper, lower;
 
        decompose(upper, lower, poly1);
        decompose(upper, lower, poly2);
 
        // 껍질을 구분했으면 삼분탐색을 통해 문제를 해결한다
        cout << fixed;
        cout.precision(10);
        cout << solve(upper, lower, poly1, poly2) << "\n";
    }
 
    return 0;
}
http://colorscripter.com/info#e" target="_blank" style="color:#e5e5e5text-decoration:none">Colored by Color Scripter

'algorithm > algospot' 카테고리의 다른 글

algospot PASS486  (0) 2020.02.27
algospot RATIO  (0) 2020.02.25
algospot LOAN  (0) 2020.02.24
algospot ROOTS  (0) 2020.02.24
algospot FESTIVAL  (0) 2019.10.27

algospot : https://algospot.com/judge/problem/read/RATIO

github : https://github.com/junho0956/Algorithm/blob/master/algospot%20RATIO/algospot%20RATIO/%EC%86%8C%EC%8A%A4.cpp

 

algospot RATIO 문제입니다.

(백준에서 같은 문제를 찾으라면 https://www.acmicpc.net/problem/1072)

이분탐색을 이용하여 쉽게 해결할 수 있었습니다.

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
#include <iostream>
#include <vector>
#include <queue>
#include <stack>
#include <algorithm>
#include <set>
#include <cmath>
#include <limits>
using namespace std;
 
 
int main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
 
    /*
    싸비는 윈도우XP 운영체제에 포함되어 있는 스파이더 카드게임을 매우 좋아한다. 
    처음에는 지는 경우가 있었는데, 점점 연습을 함에 따라 필승법을 발견하였고 매번 승리를 하게 되었다.
    스파이더 게임을 하면 플레이어에 대한 정보가 다음과 같이 주어지는데
    싸비는 이것을 보다 표시되고 있는 승률을 1%이상 올리기 위해선 최소한 몇 번의 연승이 필요한지 의구심이 들었다.
 
    플레이 횟수 : N
    승리 횟수 : M(Z %)
 
    여기서 Z%의 경우 소수점을 제외한 부분의 승률이다.
    즉, 승률이 88.68% 일 경우 Z = 88% 이다.
 
    N, M이 주어졌을 때, Z를 올리기 위한 최소한의 연승횟수가 필요한지 구하는 프로그램을 작성하라.
    여기서 답이 되는 연승횟수는 2,000,000,000 이하라고 가정한다.
    */
 
    /*
    입력의 첫번째 줄에는 테스트 케이스의 개수 T가 입력되고,
    다음 줄 부터 한줄에 하나씩 T개의 테스트 케이스가 입력된다.
    테스트케이스는 두 개의 숫자로 이루어진다.
    처음에 들어오는 숫자는 스파이더를 플레이를 한 횟수N(1<=N<=1,000,000,000)를 의미하며
    나중에 들어온 숫자는 승리한 횟수M(0<=M<=N)를 의미한다.
    */
 
    int T; cin >> T;
    while (T--) {
        long long n, m;
        cin >> n >> m;
        long long standRate = (m * 100) / n;
        if (standRate >= 99) {
            cout << "-1\n";
            continue;
        }
        standRate++;
        // 연승횟수는 20억 이하
        long long left, right;
        left = 0, right = 2e9 + 1;
        for (int i = 0; i < 100; i++) {
            long long mid = (left + right) / 2;
            long long rate = ((m+mid) * 100) / (n + mid);
            if (rate >= standRate)
                right = mid;
            else
                left = mid;
        }
        cout << right << "\n";
    }
 
    return 0;
}
http://colorscripter.com/info#e" target="_blank" style="color:#e5e5e5text-decoration:none">Colored by Color Scripter

'algorithm > algospot' 카테고리의 다른 글

algospot PASS486  (0) 2020.02.27
algospot FOSSIL  (0) 2020.02.26
algospot LOAN  (0) 2020.02.24
algospot ROOTS  (0) 2020.02.24
algospot FESTIVAL  (0) 2019.10.27

algospot : https://algospot.com/judge/problem/read/LOAN

github : https://github.com/junho0956/Algorithm/blob/master/algospot%20LOAN/algospot%20LOAN/%EC%86%8C%EC%8A%A4.cpp

 

algospot LOAN 문제입니다.

이분법을 이용하였으며, 초기 이분법 값을 잡아주는 방법과 대출 잔금을 계산하는 방법을 알고 계신다면

해결할 수 있습니다.

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
/*
집을 떠나 혼자 살게 된 재훈이는 회사 근처의 전세집을 알아보고 있습니다.
전세금은 N원인데, 재훈이는 이것을 연이율 P%로 대출받을 수 있습니다.
재훈이는 M개월 동안 매달 일정액 C원씩을 갚으려고 합니다.
 
대출의 잔금은 대출 기간 동안 다음과 같이 변화합니다.
 
ᆞ대출의 잔금은 대출 금액 N원에서 시작합니다.
ᆞ한 달이 지날 때마다 대출 잔금이 월 이자 (P/12)% 만큼 불어납니다.
ᆞ이자가 추가된 다음 월 상환액 C를 대출 잔금에서 제합니다.
M개월 걸려 모든 대출 금액을 갚기 위해서는 한 달에 최소 얼마씩을 갚아야 할까요?
*/
 
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
 
// 매달 C원씩 갚았을 때 남게 되는 대출 잔금을 반환합니다.
 
double balance(double money, int month, double rates, double C) {
    for (int i = 0; i < month; i++) {
        money *= (1 + (rates / 12 / 100));
        money -= C;
    }
    return money;
}
 
// 한달에 갚아야 하는 최소 금액을 반환합니다
double payment(double money, int month, double rates) {
    double lo = 0;
    double hi = money * (1 + (rates / 12 / 100));
 
    for (int i = 0; i < 100; i++) {
        double mid = (lo + hi) / 2;
        if (balance(money, month, rates, mid) <= 0) {
            hi = mid;
        }
        else {
            lo = mid;
        }
    }
 
    return hi;
}
 
int main() {
    ios::sync_with_stdio(0), cin.tie(0);
 
    /*
    입력의 첫 줄에는 테스트 케이스의 수 T(<= 50)가 주어집니다.
    각 테스트 케이스는 3개의 수 N, M, P(1 <= N <= 100,000,000, 1 <= M <= 120, 0 < P <= 50)으로 주어집니다.
    N과 P는 실수이며, M은 정수입니다.
    */
 
    int T; cin >> T;
    while (T--) {
        // N : 대출금액
        // M : M개월
        // P : 연이율
        double N, P;
        int M;
        cin >> N >> M >> P;
 
        /*
        각 테스트 케이스마다 한 줄에 한 달마다 상환할 금액 C를 출력합니다.
        10-7 이하의 절대/상대 오차가 있는 답은 정답으로 인정됩니다.
        */
        cout << fixed;
        cout.precision(10);
        cout << payment(N, M, P) << endl;
    }
 
    return 0;
}
http://colorscripter.com/info#e" target="_blank" style="color:#e5e5e5text-decoration:none">Colored by Color Scripter

'algorithm > algospot' 카테고리의 다른 글

algospot PASS486  (0) 2020.02.27
algospot FOSSIL  (0) 2020.02.26
algospot RATIO  (0) 2020.02.25
algospot ROOTS  (0) 2020.02.24
algospot FESTIVAL  (0) 2019.10.27

algospot : https://algospot.com/judge/problem/read/ROOTS

github : https://github.com/junho0956/Algorithm

 

algospot ROOTS 단변수 다항 방정식 해결하기 문제입니다.

풀이는 코드에 주석처리 되어있으며 문제해결기법을 참조하였습니다.

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
/*
실수 근만을 갖는 ax2 + bx + c = 0과 같은 형태의 단변수 다항 방정식이 주어질 때
이들의 근을 계산하는 프로그램을 작성하세요.
*/
 
#include <iostream>
#include <cmath>
#include <algorithm>
#include <vector>
using namespace std;
 
// 모든 해의 절대값은 10 이하라고 가정해도 좋습니다.
const int L = 10;
 
// 단일 변수 다항식p의 계수가 주어질 때 미분한 결과 p'의 계수를 반환한다
vector<double> differentiate(const vector<double>& poly) {
    int n = poly.size() - 1;
    vector<double> res;
 
    for (int i = 0; i < n; i++) {
        res.push_back(poly[i] * (n - i));
    }
    return res;
}
 
// 1차 혹은 2차 방정식을 푼다
vector<double> solveNative(const vector<double>& poly) {
    int n = poly.size() - 1;
    vector<double> res;
    if (n == 1) {
        res.push_back((-1) * (poly[1] / poly[0]));
        return res;
    }
    if (n == 2) {
        double a, b, c;
        a = poly[0], b = poly[1], c = poly[2];
        res.push_back(((-b) + (sqrt(pow(b, 2) - 4 * a * c))) / (2 * a));
        res.push_back(((-b) - (sqrt(pow(b, 2) - 4 * a * c))) / (2 * a));
        sort(res.begin(), res.end());
        return res;
    }
}
 
// 다항식 f(x)의 계수 poly가 주어질 때, f(val)를 반환한다
double evaluate(const vector<double>& poly, double val) {
    double ans = 0;
    int n = poly.size() - 1;
    for (int i = 0; i <= n; i++) {
        ans += pow(val, n - i) * poly[i];
    }
 
    return ans;
}
 
// 방정식의 근을 반환한다
vector<double> solve(const vector<double>& poly) {
    
    // 방정식의 계수를 확인한다
    int n = poly.size() - 1;
 
    // 만약 2차 이하라면 바로 해결한다
    if (n <= 2) return solveNative(poly);
 
    // 3차 이상이라면 미분한 방정식을 구한다
    vector<double> different = differentiate(poly);
    // 미분한 방정식에 대한 극점을 재귀를 통하여 구한다
    vector<double> sol = solve(different);
 
    // 왼쪽, 오른쪽 끝의 극점은 그 옆에 또 다른 극점이 존재하지 않으므로 근을 구할 수 없다.
    // 그러므로 초기화 해놓은 L을 이용하여 근을 구한다.
    sol.insert(sol.begin(), -L - 1);
    sol.insert(sol.end(), L + 1);
 
    // 각 극점을 이분법을 이용하여 근을 구한다
    vector<double> res;
 
    for (int i = 0; i < sol.size()-1; i++) {
        double x1 = sol[i], x2 = sol[i + 1];
        double y1 = evaluate(poly, x1), y2 = evaluate(poly, x2);
 
        // y가 같은 부호이면 근이 존재할 수 없다.
        if (y1 * y2 > 0) continue;
        // 불변 조건 : 이분법의 진행과정에 따라 반드시 f(x1) < f(x2) 일 수는 없다.
        // f(x1) <= 0 < f(x2) 를 강제하여 이분법 상의 두 부분중 어느곳을 선택해야 할지 판단한다.
        if (y1 > y2) {
            swap(y1, y2);
            swap(x1, x2);
        }
        // while 이 아닌 최대 100 정도의 for문으로 이분법을 돌리는 것은
        // 이분법 과정에서 무한루프를 방지할 수 있다.
        for (int i = 0; i < 100; i++) {
            double x = (x1 + x2) / 2;
            double y = evaluate(poly, x);
 
            if (y <= 0) x1 = x;
            else x2 = x;
        }
 
        res.push_back(x1);
    }
    sort(res.begin(), res.end());
    return res;
}
 
int main() {
    ios::sync_with_stdio(0), cin.tie(0);
 
    // 입력의 첫 줄에는 테스트 케이스의 수 C(C<=50)가 주어집니다.
    // 각 테스트 케이스의 첫 줄에는 방정식의 차수 n(2 <= n <= 5)이 주어지고,
    // 그 다음 줄에 n+1개의 실수로 방정식의 차수가 고차항부터 주어집니다.
 
    int C; cin >> C;
    while (C--) {
        int n; cin >> n;
        vector<double> poly;
        for (int i = 0; i < n + 1; i++) {
            double val; cin >> val;
            poly.push_back(val);
        }
        // 각 테스트 케이스마다 n개의 실수로 오름차순으로 정렬된 방정식의 해를 출력합니다.
        // 방정식의 해는 모두 다르다고 가정해도 좋습니다.
        // 10 - 8 이하의 상대 / 절대 오차가 있는 답은 정답으로 처리됩니다.
        vector<double> res = solve(poly);
        sort(res.begin(), res.end());
 
        cout << fixed;
        cout.precision(10);
        for (int i = 0; i < res.size(); i++) {
            cout << res[i] << " ";
        }
        cout << endl;
    }
    return 0;
}
http://colorscripter.com/info#e" target="_blank" style="color:#e5e5e5text-decoration:none">Colored by Color Scripter

'algorithm > algospot' 카테고리의 다른 글

algospot PASS486  (0) 2020.02.27
algospot FOSSIL  (0) 2020.02.26
algospot RATIO  (0) 2020.02.25
algospot LOAN  (0) 2020.02.24
algospot FESTIVAL  (0) 2019.10.27

+ Recent posts

티스토리툴바