Rezolvare completă PbInfo #2158 Orase2

În tărâmul Jupânului există N + 1 orașe. Acestea au fost construite în linie dreaptă, începând cu cel în care este casa Jupânului. Între oricare 2 orașe consecutive s-a construit câte un drum. Pentru fiecare drum, se cunoaște lungimea lui, exprimată în metri și viteza cu care se poate parcurge, exprimată în metri pe secundă.

Cerința

Jupânul trebuie să ajungă din orașul 0 în orașul N. Acesta știe că poate îmbunătăți un drum, mărindu-i viteza de la V metri pe secundă la V + 1 metri pe secundă, cu costul de 1 dolar. Acesta poate îmbunătăți un drum de mai multe ori.

Jupânul are un buget de X dolari și ar vrea să-i folosească pentru a micșora timpul în care ajunge din orașul 0 în orașul N.

Date de intrare

Fișierul de intrare orase2.in are următoarea structură:

  • Pe prima linie se află numărul T, reprezentând tipul de restricții pe care îl respectă testul.
  • Pe a doua linie, se află două numere naturale N și X.
  • Pe a treia linie se află N numere naturale, al i-lea număr reprezentând distanța între orașele i–1 și i.
  • Pe a patra linie se află N numere naturale, al i-lea număr reprezentând viteza între orașele i–1 și i.

Date de ieșire

Fișierul de ieșire orase2.out va conține pe prima linie un număr natural R ce reprezintă partea întreagă a timpului minim de parcurgere a distanței dintre orașul 0 și orașul N.

Restricții și precizări

  • 1 ≤ N ≤ 50.000
  • 1 ≤ X ≤ 10.000.000
  • lungimea drumului dintre oricare două orașe este un număr natural din intervalul [1, 10.000]
  • viteza inițială dintre oricare două orașe consecutive este un număr natural din intervalul [1, 10.000]
  • tipuri de restricții
    • tipul 1: pentru 5% din punctaj N ≤ 10 și X ≤ 10
    • tipul 2: pentru alte 10% din punctaj N ≤ 1000 și X ≤ 1000
    • tipul 3: pentru alte 15% din punctaj 1 ≤ N ≤ 50.000, 1 ≤ X ≤ 10.000, distanţele sunt mai mici decât 200 şi se garantează că vitezele finale vor fi mai mici sau egale decât 1000
    • tipul 4: pentru alte 20% din punctaj 1 ≤ N ≤ 50.000, 1 ≤ X ≤ 10.000.000 și toate distanțele sunt egale
    • tipul 5: pentru restul de 50% din punctaj 1 ≤ N ≤ 50.000 și 1 ≤ X ≤ 10.000.000

Exemplul 1

orase2.in

1
3 5
5 3 7
2 1 4

orase2.out

3

Explicație

Timpul minim este 3.65, iar rezultatul este [3.65]=3. Vitezele finale vor fi 4, 3, 5. 5 / 4 + 3 / 3 + 7 / 5 = 3.65

Exemplul 2

orase2.in

1
4 6
3 8 10 5
4 3 7 3

orase2.out

4

Explicație

Timpul minim este 4.321, iar rezultatul este [4.321]=4. Vitezele finale vor fi 4, 7, 7, 5. 3 / 4 + 8 / 7 + 10 / 7 + 5 / 5 = 4.32142857

Exemplul 3

orase2.in

1
5 6
2 5 3 2 4
5 1 2 1 3

orase2.out

4

Explicație

Timpul minim este 4.65, iar rezultatul este [4.65]=4. Vitezele finale vor fi 5, 4, 3, 3, 3. 2 / 5 + 5 / 4 + 3 / 3 + 2 / 3 + 4 / 3 = 4.65

Cum e corect?

cout < "As la info"; cout << "As la info"; cout >> "As la info";

Felicitări! Poți mai mult?

Avem sute de probleme pentru tine, fiecare cu explicații ușor de înțeles.

Greșit, dar nu-i bai!

Antrenează-te cu sutele de probleme pe care ți le-am pregătit. Îți explicăm fiecare problemă în parte.

Rezolvare

Iată rezolvarea de 100 de puncte pentru problema Orase2:

// Problema Orase - Oni clasa a 9-a
// sursa Velea Alexandru
// time O(n * log2(x))
// 100 points

#include <cmath>

#include <iomanip>
#include <fstream>
#include <iostream>
#include <queue>
#include <vector>
using namespace std;

typedef long long int64;

const int kAcceptedRemaining = 2e4;

struct Road {
    int distance;
    int speed;
    int id;

    long double SavedTime(int bonus_time = 0) const {
        return 1.0 * distance / (speed + bonus_time) / (speed + 1 + bonus_time);
    }

    long double Time(int bonus_time = 0) const {
        return 1.0 * distance / (speed + bonus_time);
    }

    bool operator<(const Road& rhs) const {
        return SavedTime() < rhs.SavedTime();
    }
};

int64 x;
vector<Road> roads;

int Read() {
    ifstream cin("orase2.in");
    int test_type;
    cin >> test_type;

    int n;
    cin >> n >> x;

    roads.resize(n);

    for (int i = 0; i < n; i += 1) {
        roads[i].id = i;
    }

    for (auto& itr : roads) {
        cin >> itr.distance;
    }

    for (auto& itr : roads) {
        cin >> itr.speed;
    }

    return 1;
}

int is_read = Read();

int64 UpgradeRoad(int index, long double saved_time) {
    return max(0LL, int64(1.0 + -0.5 + sqrt(1.0 + 4.0 * roads[index].distance / saved_time) / 2.0 + 1e-10) -
                        roads[index].speed);
}

vector<int64> GetUpgrades(long double saved_time) {
    vector<int64> answer(roads.size(), 0);
    for (int i = 0; i < (int)roads.size(); i += 1) {
        answer[i] = UpgradeRoad(i, saved_time);
    }

    return answer;
}

int64 GetNumOperations(long double saved_time) {
    auto upgrades = GetUpgrades(saved_time);

    int64 answer = 0;
    for (auto itr : upgrades) {
        answer += itr;
    }

    return answer;
}

long double EstimateSolution() {
    long double mx_save = 0;
    for (auto& itr : roads) {
        mx_save = max(mx_save, itr.SavedTime());
    }

    long double left = 0, right = mx_save;

    int64 mx_upgrades = 0;
    long double mx_where = 0;

    int64 mn_upgrades = 1e9;
    long double mn_where = 0;

    for (int i = 0; i < 100; i += 1) {
        long double mid = (right + left) / 2;
        int64 num_operations = GetNumOperations(mid);

        if (num_operations == x) {
            mx_upgrades = num_operations;
            mx_where = mid;
            break;
        }

        if (num_operations > x) {
            left = mid;

            if (mn_upgrades >= num_operations) {
                mn_upgrades = num_operations;
                mn_where = mid;
            }
        } else {
            right = mid;

            if (mx_upgrades <= num_operations) {
                mx_upgrades = num_operations;
                mx_where = mid;
            }
        }
    }

    auto upgrades = GetUpgrades(mx_where);

    int64 sum = 0;
    for (int i = 0; i < (int)roads.size(); i += 1) {
        roads[i].speed += upgrades[i];
        sum += upgrades[i];
    }

    x -= sum;

    double answer = 0;
    for (auto& itr : roads) {
        answer += itr.Time();
    }

    answer -= 1.0 * mx_where * x;

    return answer;
}

long double Solve() {
    return EstimateSolution();
}

int main() {
    long double answer = Solve();
    
    ofstream cout("orase2.out");
    cout << int64(answer) << '\n';

    return 0;
}

Atenție

Enunțurile afișate pe această pagină aparțin exclusiv site-ului PbInfo. Astfel, pentru ștergerea conținutului, puteți să ne contactați la adresa Adresa de email.

Rezolvarea problemei #2158 Orase2

Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #2158 Orase2 de pe PbInfo.ro. Atenție: nu încurajăm copiatul codului! Totuși, credem cu tărie că analizarea unei soluții corecte este o metodă foarte ușoară de a învăța informatică, astfel că oferim sursele pentru peste 1500 de probleme de pe platforma PbInfo.ro.

Pentru rezolvări PbInfo de la peste 1500 de probleme, vă invităm să intrați pe site-ul nostru!