oj.uz

Submission #47549

# Submission time Handle Problem Language Result Execution time Memory
47549 2018-05-05T03:25:20 Z fallingstar Experiments with Gorlum (IZhO13_expgorl) C++17
0 / 100
 1000 ms 688 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));

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

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

Compilation message

expgorl.cpp: In function 'int main()':
expgorl.cpp:89:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int j = 0; j < s.size(); ++j)
                         ~~^~~~~~~~~~

Subtask #1
0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 226 ms 376 KB Output is correct
2 Correct 280 ms 484 KB Output is correct
3 Correct 309 ms 484 KB Output is correct
4 Correct 324 ms 612 KB Output is correct
5 Correct 171 ms 612 KB Output is correct
6 Correct 253 ms 612 KB Output is correct
7 Correct 272 ms 688 KB Output is correct
8 Correct 373 ms 688 KB Output is correct
9 Execution timed out 1091 ms 688 KB Time limit exceeded
10 Halted 0 ms 0 KB -