oj.uz

Submission #47550

# Submission time Handle Problem Language Result Execution time Memory
47550 2018-05-05T03:25:55 Z fallingstar Experiments with Gorlum (IZhO13_expgorl) C++17
100 / 100
 6 ms 648 KB 
/**
    Problem: Experiments with Gorlum
    Source: IX Zhautykov Olympiad on Mathematics, Physics and Informatics (IZhO) 2013, day 1, problem A
*/

#include <cmath>
#include <iostream>
#include <iomanip>
#include <algorithm>
#include <string>

#define long long long

using namespace std;

const int N = 1e4 + 2;
const double INF = 1e12;

template<typename T> inline T sqr(T x) { return x * x; }

struct TPoint { int x, y; };
istream &operator >> (istream &inp, TPoint &a)
{
    inp >> a.x >> a.y;
    return inp;
}
TPoint operator + (TPoint a, TPoint b) { return {a.x + b.x, a.y + b.y}; }
TPoint operator * (TPoint a, int k) { return {a.x * k, a.y * k}; }
double Dist(TPoint a, TPoint b)
{
    return sqrt(sqr<long>(a.x - b.x) + sqr<long>(a.y - b.y));
}

int k;
string s;
TPoint laser, gorlum;
TPoint delta[N];
double minDist = INF, maxDist = 0;

double CalMin(int k)
{
    double ret = INF;
    for (size_t i = 0; i < s.size(); ++i)
    {
        TPoint cur = gorlum + delta[s.size() - 1] * (k - 1) + delta[i];
        ret = min(ret, Dist(laser, cur));
    }
    return ret;
}

int main()
{
    cin >> k >> s;
    cin >> laser >> gorlum;
    for (size_t i = 0; i < s.size(); ++i)
    {
        char ch = s[i];
        TPoint pre = (i ? delta[i - 1] : TPoint {0, 0});
        if (ch == 'L') delta[i] = pre + TPoint {-1, 0}; else
        if (ch == 'R') delta[i] = pre + TPoint {1, 0}; else
        if (ch == 'F') delta[i] = pre + TPoint {0, 1}; else
        if (ch == 'B') delta[i] = pre + TPoint {0, -1}; else
        delta[i] = pre;
    }

    minDist = Dist(laser, gorlum);
    maxDist = Dist(laser, gorlum);

    for (size_t i = 0; i < s.size(); ++i)
    {
        TPoint cur = gorlum + delta[i];
        maxDist = max({maxDist, Dist(laser, cur), Dist(laser, cur + delta[s.size() - 1] * (k - 1))});
    }

    int lo = 1, hi = k;
    while (lo < hi)
    {
        int mid = (lo + hi) / 2;
        double fmid = CalMin(mid), fmid1 = CalMin(mid + 1);
        minDist = min({minDist, fmid, fmid1});
        if (fmid <= fmid1)
            hi = mid;
        else
            lo = mid + 1;
    }
    minDist = min(minDist, CalMin(lo));

    cout << setprecision(9) << fixed << minDist << ' ' << maxDist;
    return 0;
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 464 KB Output is correct
3 Correct 2 ms 464 KB Output is correct
4 Correct 2 ms 468 KB Output is correct
5 Correct 2 ms 468 KB Output is correct
6 Correct 2 ms 468 KB Output is correct
7 Correct 2 ms 468 KB Output is correct
8 Correct 2 ms 468 KB Output is correct
9 Correct 4 ms 644 KB Output is correct
10 Correct 5 ms 644 KB Output is correct
11 Correct 4 ms 644 KB Output is correct
12 Correct 5 ms 644 KB Output is correct
13 Correct 5 ms 644 KB Output is correct
14 Correct 5 ms 644 KB Output is correct
15 Correct 5 ms 644 KB Output is correct
16 Correct 6 ms 644 KB Output is correct
17 Correct 6 ms 644 KB Output is correct
18 Correct 6 ms 644 KB Output is correct
19 Correct 6 ms 648 KB Output is correct
20 Correct 6 ms 648 KB Output is correct