Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|
Бүх бодолтууд Шилдэг бодолтууд PDF Жагсаалт руу буцах

RGB7797 - Дугуйн уралдаан

 

М унадаг дугуйтай хотод (тэгш өнцөгт координат дээр байгаа) N тооны дугуйчид байдаг.

Бүх дугуйчид HackerRace тэмцээнд оролцохыг хүсч байгаа боловч харамсалтай нь уралдаанд зөвхөн

K дугуйчдыг оролцуулах боломжтой. Жэк нь HackerRace-ийг зохион байгуулж байгаа бөгөөд уралдааныг

аль болох хурдан эхлүүлэхийг хүсч байна.

Тэрээр ямар ч дугуйчныг хот дахь аль ч дугуйгаар явахыг зааж өгч чадна. Уралдаан эхлэх цагийг багасгахын

тулд Жэк K дугуйчдад унадаг дугуйг хамгийн бага хугацаанд олж авах боломжийг зааж өгөх гэж байна.

Дугуйчин бүр нэгж хурдтайгаар хөдөлдөг бөгөөд зөвхөн ганц унадаг дугуйг зөвхөн нэг дугуйчин авах боломжтой.

Дугуйчин ямар ч чиглэлд явж болно. Дугуй ба дугуйчдын хоорондох зайг Евклидийн зайгаар хэмждэг гэж үзье.

Жэк уралдааныг аль болох уралдааныг хурдан эхлүүлэхэд шаардлагатай хугацааны квадратыг мэдэхийг хүсч байна.

Оролтын хэлбэр

Эхний мөрд N, M, K тоонууд зайгаар тусгаарлагдан өгөгдөнө.

Дараагийн N мөрд N дугаар дугуйчны координатыг илэрхийлэх хос тоонуудыг зайгаар тусгаарлан өгөгдөнө.

Сүүлийн M мөр өмнөхийн адил M дугуйны байршлыг илэрхийлэх хосууд хоосон зайгаар тусгаарлан өгөгдөнө. 

Зааглалт

 

  • 1 <= N <= 250
  • 1 <= M <= 250
  • 1 <= K <= min(N,M)
  • 1 <= xi, yi  <= 107

    •  

    Гаралтын хэлбэр

    Шаардагдах хамгийн бага хугацааны квадратыг агуулсан ганц мөр байна.

    Жишээ

    Оролт

     3 3 2

    0 1

    0 2

    0 3

    100 1

    200 2

    300 3

    Гаралт

    40000

    Тайлбар

    Уралдаанд оролцох хоёр дугуйчин хэрэгтэй болно.

    Эхний унадаг дугуйчин (0,1) байрлалаас (100,1)-д байгаа эхний дугуйнд 100 хугацаанд очно. 

    (0,2) байрлалд байгаа хоёр дахь дугуйчин нь 200 нэгж цагаар (200,2)-д байгаа хоёр дахь дугуйд хүрэх боломжтой.

    Энэ нь хамгийн оновчтой шийдэл тул 200 нэгж цаг шаардана.

    Тэгэхээр гаралт 2002 = 40000 болно.


    Орчуулсан : Р.Мижиддорж МУБИС, доктор

     

    Submit solution!
    Нэмсэн:Bataa
    Огноо:2020-04-14
    Хугацааны хязгаарлалт:1s
    Эх кодын хэмжээний хязгаарлалт:50000B
    Memory limit:1536MB
    Cluster: Cube (Intel G860)
    Програмчлалын хэлүүд:ADA95 ASM32 ASM64 BASH BF C NCSHARP CSHARP C++ 4.3.2 CPP C99 CLPS LISP sbcl LISP clisp D ERL FORTRAN HASK ICON ICK JAVA JS-RHINO JULIA LUA NEM NICE OCAML PAS-GPC PAS-FPC PERL PHP PIKE PRLG-swi PYTHON PYPY3 PYTHON3 RUBY SCALA SCM guile ST TCL WHITESPACE
    Эх сурвалж:https://www.hackerrank.com/challenges/bike-racers/problem
    hide comments
    2024-05-22 04:29:03
    #include <iostream>
    #include <vector>
    #include <cmath>
    #include <limits>
    #include <algorithm>

    using namespace std;
    bool bpm(int u, vector<vector<double>> &dist, vector<bool> &seen, vector<int> &match, int K) {
    for (int v = 0; v < K; ++v) {
    if (dist[u][v] <= 1e-6 && !seen[v]) {
    seen[v] = true;
    if (match[v] < 0 || bpm(match[v], dist, seen, match, K)) {
    match[v] = u;
    return true;
    }
    }
    }
    return false;
    }
    double minTime(vector<pair<int, int>> &cyclists, vector<pair<int, int>> &bikes, int K) {
    int N = cyclists.size();
    vector<vector<double>> dist(N, vector<double>(K));

    for (int i = 0; i < N; ++i) {
    for (int j = 0; j < K; ++j) {
    dist[i][j] = sqrt(pow(cyclists[i].first - bikes[j].first, 2) +
    pow(cyclists[i].second - bikes[j].second, 2));
    }
    }

    double low = 0, high = 1e6;
    while (high - low > 1e-6) {
    double mid = (low + high) / 2;
    vector<vector<double>> new_dist = dist;

    for (int i = 0; i < N; ++i) {
    for (int j = 0; j < K; ++j) {
    new_dist[i][j] = (dist[i][j] <= mid) ? 0 : 1e9;
    }
    }

    vector<int> match(K, -1);
    int matches = 0;

    for (int i = 0; i < N; ++i) {
    vector<bool> seen(K, false);
    if (bpm(i, new_dist, seen, match, K))
    ++matches;
    }

    if (matches >= K) {
    high = mid;
    } else {
    low = mid;
    }
    }

    return low * low;
    }

    int main() {
    int N, M, K;
    cin >> N >> M >> K;

    vector<pair<int, int>> cyclists(N);
    vector<pair<int, int>> bikes(M);

    for (int i = 0; i < N; ++i) {
    cin >> cyclists[i].first >> cyclists[i].second;
    }

    for (int i = 0; i < M; ++i) {
    cin >> bikes[i].first >> bikes[i].second;
    }

    cout << fixed << minTime(cyclists, bikes, K) << endl;
    return 0;
    }
    huultsga guys c++ shv
    2024-03-02 13:41:00
    bodoosh

    2023-06-05 09:38:30
    ene goy bodlogo bn
    2021-01-04 10:15:41
    #include<iostream>
    using namespace std;
    int main() {
    string a,b,c=0;
    cin>>a;
    cout<<a;
    }
    © Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.