Cerinta completa
Quality Blimps Inc. is looking to expand their sales to other cities (), so they hired you as a salesman to fly to other cities to sell blimps. Blimps can be expensive to travel with, so you will need to determine how many blimps to take along with you on each trip and when to return to headquarters to get more. Quality Blimps has an unlimited supply of blimps.
You will be able to sell only one blimp in each city you visit, but you do not need to visit every city, since some have expensive travel costs. Each city has an initial price that blimps sell for, but this goes down by a certain percentage as more blimps are sold (and the novelty wears off). Find a good route that will maximize profits.
Details
Blimp Decline – The blimps will decline () in price every time you visit of the cities (the number of cities will always be a multiple of ). For example, if is and there are cities, then for every city you visit (except headquarters), the price of blimps will be multiplied by . So after visits, every city’s blimp price will be about of the initial value ().
Note that if the price declines after you visit some city, then it will only happen after you made the sale on that city, so your sale on that city will not be affected. In particular, each blimp you sell in the first of the cities will always be sold at their corresponding city’s initial price.
Input Format
The first line of input for each test case will contain three parameters:
- number of cities ()
- blimp cost per mile ()
- blimp factor of decline ()
This will be followed by lines, which will each contain three integers , the city location (x and y coordinates the grid, in miles) and the initial blimp sales price, respectively.
Constraints
- The city locations will be distinct
Output Format
On each line, output the x and y coordinates of the next city you are visiting. When leaving the headquarters, also output the number of blimps you are taking with you for that part of the trip. You do not need to return to headquarters when you finish your sales.
You can only visit each city at most once.
Sample Input
10 3 0.95
1 1 30
2 2 35
0 8 50
7 2 20
7 3 25
10 7 90
9 8 35
5 15 10
8 18 15
1 9 60
Sample Output
1 1 2
2 2
0 0
10 7 2
9 8
0 0
0 8 2
1 9
Explanation
The salesman first travels a distance of √2 dollars to (1,1) carrying 2 blimps. This will cost him √2 dollars for his own travel and 6√2 dollars for the 2 blimps. He will then earn 30 dollars selling 1 blimp. He then continues to (2,2) with only 1 blimp, which will cost him 1√2 dollars for his travel and 3√2 dollars for his blimp. He will then earn 33.25 dollars selling the blimp, since the prices have declined by 5%. After his return to HQ (a distance of 2√2) he will have earned an approximate profit of 44.87 dollars.
Scoring
The goal of this challenge is to achieve the maximum profit on each test case. Your profits for each test case will be:
Total Blimp Sales – Total Travel Costs
You will receive a score for each test case based on the ratio of your profit to the estimated maximum profit. Your total score for this challenge will be a weighted sum of your scores for each test case.
If your profit is negative, you’ll receive a zero score.
Limbajul de programare folosit: cpp14
Cod:
#include <bits/stdc++.h>
using namespace std;
struct City {
int x, y;
double price;
double d0;
};
struct Line {
int x, y, cnt; // cnt = -1 means print only x y
};
struct Candidate {
vector<Line> lines;
double profit = -1e100;
};
#ifndef BLOCK_CITY_TAX
#define BLOCK_CITY_TAX 0.0
#endif
#ifndef GREEDY_LITE_BUDGET
#define GREEDY_LITE_BUDGET 0.16
#endif
#ifndef GREEDY_K_BIAS
#define GREEDY_K_BIAS 0
#endif
static int N;
static double C, D;
static vector<City> cities;
static int gridPos[2001][2001];
static double dPow[16];
static inline double distXY(int x1, int y1, int x2, int y2) {
double dx = (double)x1 - x2;
double dy = (double)y1 - y2;
return sqrt(dx * dx + dy * dy);
}
static inline int decayExp(int sold) {
return (10 * sold) / N;
}
static inline double saleValue(int id, int sold) {
return cities[id].price * dPow[decayExp(sold)];
}
static inline void pushLine(vector<Line>& out, int x, int y, int cnt) {
out.push_back({x, y, cnt});
}
static inline pair<double, pair<int, int>> tripProfit(const vector<int>& trip, int soldStart) {
if (trip.empty()) return {0.0, {0, 0}};
double p = 0.0;
int px = 0, py = 0;
int sold = soldStart;
int m = (int)trip.size();
for (int i = 0; i < m; ++i) {
int id = trip[i];
int rem = m - i;
p += saleValue(id, sold) - distXY(px, py, cities[id].x, cities[id].y) * (1.0 + C * rem);
px = cities[id].x;
py = cities[id].y;
++sold;
}
return {p, {px, py}};
}
static void twoOptImprove(vector<int>& trip, int soldStart) {
int m = (int)trip.size();
if (m <= 3 || m > 16) return;
auto curEval = tripProfit(trip, soldStart);
double best = curEval.first;
for (int it = 0; it < 4; ++it) {
bool improved = false;
for (int i = 0; i < m - 1; ++i) {
for (int j = i + 1; j < m; ++j) {
reverse(trip.begin() + i, trip.begin() + j + 1);
double p = tripProfit(trip, soldStart).first;
if (p > best + 1e-9) {
best = p;
improved = true;
} else {
reverse(trip.begin() + i, trip.begin() + j + 1);
}
}
}
if (!improved) break;
}
}
static void twoOptImproveBounded(vector<int>& trip, int soldStart) {
int m = (int)trip.size();
if (m <= 3 || m > 24) return;
auto curEval = tripProfit(trip, soldStart);
double best = curEval.first;
int maxIt = (m <= 12 ? 4 : (m <= 18 ? 2 : 1));
for (int it = 0; it < maxIt; ++it) {
bool improved = false;
for (int i = 0; i < m - 1; ++i) {
for (int j = i + 1; j < m; ++j) {
reverse(trip.begin() + i, trip.begin() + j + 1);
double p = tripProfit(trip, soldStart).first;
if (p > best + 1e-9) {
best = p;
improved = true;
} else {
reverse(trip.begin() + i, trip.begin() + j + 1);
}
}
}
if (!improved) break;
}
}
struct GreedyCtx {
vector<unsigned char> used;
vector<int> byPrice;
vector<int> tripStamp;
vector<int> candStamp;
int curTripStamp = 1;
int curCandStamp = 1;
int topPtr = 0;
explicit GreedyCtx(int n) : used(n, 0), byPrice(n), tripStamp(n, 0), candStamp(n, 0) {}
};
static inline void addCandidate(vector<int>& cands, GreedyCtx& ctx, int id) {
if (id < 0) return;
if (ctx.used[id]) return;
if (ctx.tripStamp[id] == ctx.curTripStamp) return;
if (ctx.candStamp[id] == ctx.curCandStamp) return;
ctx.candStamp[id] = ctx.curCandStamp;
cands.push_back(id);
}
static void gatherCandidates(
int px,
int py,
GreedyCtx& ctx,
vector<int>& cands,
int needNear,
int needTop,
int rMax
) {
cands.clear();
++ctx.curCandStamp;
if (ctx.curCandStamp == INT_MAX) {
fill(ctx.candStamp.begin(), ctx.candStamp.end(), 0);
ctx.curCandStamp = 1;
}
int cx = px + 1000;
int cy = py + 1000;
for (int r = 0; r <= rMax && (int)cands.size() < needNear; ++r) {
int x1 = max(0, cx - r), x2 = min(2000, cx + r);
int y1 = max(0, cy - r), y2 = min(2000, cy + r);
for (int x = x1; x <= x2; ++x) {
addCandidate(cands, ctx, gridPos[x][y1]);
if (y2 != y1) addCandidate(cands, ctx, gridPos[x][y2]);
if ((int)cands.size() >= needNear) break;
}
if ((int)cands.size() >= needNear) break;
for (int y = y1 + 1; y <= y2 - 1; ++y) {
addCandidate(cands, ctx, gridPos[x1][y]);
if (x2 != x1) addCandidate(cands, ctx, gridPos[x2][y]);
if ((int)cands.size() >= needNear) break;
}
}
while (ctx.topPtr < N && ctx.used[ctx.byPrice[ctx.topPtr]]) ++ctx.topPtr;
int addedTop = 0;
int scanned = 0;
for (int i = ctx.topPtr; i < N && addedTop < needTop && scanned < 300; ++i, ++scanned) {
int id = ctx.byPrice[i];
if (ctx.used[id]) continue;
if (ctx.tripStamp[id] == ctx.curTripStamp) continue;
if (ctx.candStamp[id] == ctx.curCandStamp) continue;
ctx.candStamp[id] = ctx.curCandStamp;
cands.push_back(id);
++addedTop;
}
}
static vector<int> buildTripGreedy(int K, int soldStart, GreedyCtx& ctx, int mode) {
vector<int> trip;
vector<int> cands;
++ctx.curTripStamp;
if (ctx.curTripStamp == INT_MAX) {
fill(ctx.tripStamp.begin(), ctx.tripStamp.end(), 0);
ctx.curTripStamp = 1;
}
int px = 0, py = 0;
int sold = soldStart;
int rem = K;
while (rem > 0) {
gatherCandidates(px, py, ctx, cands, 90, 35, 90);
if (cands.empty()) break;
double best = -1e100;
int bestId = -1;
for (int id : cands) {
double g = saleValue(id, sold) - distXY(px, py, cities[id].x, cities[id].y) * (1.0 + C * rem);
if (mode == 1) {
g += 0.04 * (cities[id].price / (1.0 + cities[id].d0));
}
if (g > best) {
best = g;
bestId = id;
}
}
if (bestId < 0 || best <= 0.0) break;
trip.push_back(bestId);
ctx.tripStamp[bestId] = ctx.curTripStamp;
px = cities[bestId].x;
py = cities[bestId].y;
++sold;
--rem;
}
return trip;
}
static vector<int> buildTripGreedyLite(int K, int soldStart, GreedyCtx& ctx, int mode) {
vector<int> trip;
vector<int> cands;
++ctx.curTripStamp;
if (ctx.curTripStamp == INT_MAX) {
fill(ctx.tripStamp.begin(), ctx.tripStamp.end(), 0);
ctx.curTripStamp = 1;
}
int px = 0, py = 0;
int sold = soldStart;
int rem = K;
while (rem > 0) {
gatherCandidates(px, py, ctx, cands, 60, 20, 70);
if (cands.empty()) break;
double best = -1e100;
int bestId = -1;
for (int id : cands) {
double g = saleValue(id, sold) - distXY(px, py, cities[id].x, cities[id].y) * (1.0 + C * rem);
if (mode == 1) {
g += 0.03 * (cities[id].price / (1.0 + cities[id].d0));
}
if (g > best) {
best = g;
bestId = id;
}
}
if (bestId < 0 || best <= 0.0) break;
trip.push_back(bestId);
ctx.tripStamp[bestId] = ctx.curTripStamp;
px = cities[bestId].x;
py = cities[bestId].y;
++sold;
--rem;
}
return trip;
}
static Candidate solveGreedyFamily() {
Candidate best;
vector<int> kSet;
if (N <= 4000) kSet = {1,2,3,4,5,6,8,10,12,15,20,24};
else if (N <= 15000) kSet = {1,2,3,4,5,6,8,10,12,15};
else kSet = {1,2,3,4,5,6,8,10,12};
for (int mode = 0; mode <= 1; ++mode) {
for (int K : kSet) {
GreedyCtx ctx(N);
iota(ctx.byPrice.begin(), ctx.byPrice.end(), 0);
sort(ctx.byPrice.begin(), ctx.byPrice.end(), [&](int i, int j) {
if (cities[i].price != cities[j].price) return cities[i].price > cities[j].price;
return cities[i].d0 < cities[j].d0;
});
vector<Line> lines;
double total = 0.0;
int sold = 0;
int lastX = 0, lastY = 0;
for (;;) {
vector<int> trip = buildTripGreedy(K, sold, ctx, mode);
if (trip.empty()) break;
if ((int)trip.size() <= 16) twoOptImprove(trip, sold);
auto eval = tripProfit(trip, sold);
double tripP = eval.first;
double backCost = (sold > 0 ? distXY(lastX, lastY, 0, 0) : 0.0);
if (tripP - backCost <= 0.0) break;
if (sold > 0) {
total -= backCost;
pushLine(lines, 0, 0, -1);
}
int m = (int)trip.size();
for (int i = 0; i < m; ++i) {
int id = trip[i];
pushLine(lines, cities[id].x, cities[id].y, i == 0 ? m : -1);
ctx.used[id] = 1;
}
total += tripP;
sold += m;
lastX = eval.second.first;
lastY = eval.second.second;
if (sold >= N) break;
}
if (total > best.profit) {
best.profit = total;
best.lines.swap(lines);
}
}
}
return best;
}
static Candidate solveGreedyLargeLite(double budgetSec) {
Candidate best;
best.profit = -1e100;
auto t0 = chrono::steady_clock::now();
int k0 = 10;
if (C >= 3.0) k0 = 6;
else if (C >= 2.2) k0 = 8;
else if (C >= 1.3) k0 = 10;
else k0 = 12;
if (D < 0.75) k0 = max(4, k0 - 2);
if (D > 0.92 && C < 1.0) k0 = min(14, k0 + 2);
k0 = max(3, min(16, k0 + GREEDY_K_BIAS));
vector<int> kSet = {max(3, k0 - 2), k0, min(18, k0 + 2)};
sort(kSet.begin(), kSet.end());
kSet.erase(unique(kSet.begin(), kSet.end()), kSet.end());
for (int mode = 0; mode <= 1; ++mode) {
for (int K : kSet) {
GreedyCtx ctx(N);
iota(ctx.byPrice.begin(), ctx.byPrice.end(), 0);
sort(ctx.byPrice.begin(), ctx.byPrice.end(), [&](int i, int j) {
if (cities[i].price != cities[j].price) return cities[i].price > cities[j].price;
return cities[i].d0 < cities[j].d0;
});
vector<Line> lines;
double total = 0.0;
int sold = 0;
int lastX = 0, lastY = 0;
int trips = 0;
for (;;) {
double elapsed = chrono::duration<double>(chrono::steady_clock::now() - t0).count();
if (elapsed > budgetSec) break;
if (trips >= 3000) break;
vector<int> trip = buildTripGreedyLite(K, sold, ctx, mode);
if (trip.empty()) break;
auto eval = tripProfit(trip, sold);
double tripP = eval.first;
double backCost = (sold > 0 ? distXY(lastX, lastY, 0, 0) : 0.0);
if (tripP - backCost <= 0.0) break;
if (sold > 0) {
total -= backCost;
pushLine(lines, 0, 0, -1);
}
int m = (int)trip.size();
for (int i = 0; i < m; ++i) {
int id = trip[i];
pushLine(lines, cities[id].x, cities[id].y, i == 0 ? m : -1);
ctx.used[id] = 1;
}
total += tripP;
sold += m;
lastX = eval.second.first;
lastY = eval.second.second;
++trips;
if (sold >= N) break;
}
if (total > best.profit) {
best.profit = total;
best.lines.swap(lines);
}
}
}
return best;
}
static Candidate runBlockConfig(int L, int blockOrderMode) {
unordered_map<int, vector<int>> mp;
mp.reserve((size_t)N * 2 + 64);
for (int id = 0; id < N; ++id) {
int bx = (cities[id].x + 1000) / L;
int by = (cities[id].y + 1000) / L;
int key = (bx << 12) ^ by;
mp[key].push_back(id);
}
vector<pair<int, vector<int>>> blocks;
blocks.reserve(mp.size());
for (auto &kv : mp) blocks.push_back(move(kv));
sort(blocks.begin(), blocks.end(), [&](const auto& a, const auto& b) {
return a.first < b.first;
});
for (auto &b : blocks) {
auto &ids = b.second;
sort(ids.begin(), ids.end(), [&](int i, int j) {
double si = cities[i].price / (1.0 + 0.35 * cities[i].d0);
double sj = cities[j].price / (1.0 + 0.35 * cities[j].d0);
if (si != sj) return si > sj;
if (cities[i].price != cities[j].price) return cities[i].price > cities[j].price;
return cities[i].d0 < cities[j].d0;
});
}
vector<int> ord(blocks.size());
iota(ord.begin(), ord.end(), 0);
vector<double> blockValue(blocks.size(), 0.0);
vector<double> blockNear(blocks.size(), 0.0);
vector<double> blockProfit0(blocks.size(), 0.0);
for (int i = 0; i < (int)blocks.size(); ++i) {
const auto &ids = blocks[i].second;
if (ids.empty()) continue;
blockNear[i] = cities[ids[0]].d0;
double v = 0.0;
int take = min((int)ids.size(), 64);
for (int j = 0; j < take; ++j) v += cities[ids[j]].price;
blockValue[i] = v;
// Estimated profit if this block is executed first from HQ,
// using a capped prefix to avoid over-penalizing large blocks.
double p0 = 0.0;
int px = 0, py = 0;
int m = (int)ids.size();
int lim = min(m, 96);
for (int j = 0; j < lim; ++j) {
int id = ids[j];
int rem = lim - j;
p0 += cities[id].price - distXY(px, py, cities[id].x, cities[id].y) * (1.0 + C * rem);
px = cities[id].x;
py = cities[id].y;
}
blockProfit0[i] = p0;
}
if (blockOrderMode == 1) {
sort(ord.begin(), ord.end(), [&](int a, int b) {
double da = cities[blocks[a].second[0]].d0;
double db = cities[blocks[b].second[0]].d0;
return da < db;
});
} else if (blockOrderMode == 2) {
reverse(ord.begin(), ord.end());
} else if (blockOrderMode == 3) {
sort(ord.begin(), ord.end(), [&](int a, int b) {
if (blockValue[a] != blockValue[b]) return blockValue[a] > blockValue[b];
return blockNear[a] < blockNear[b];
});
} else if (blockOrderMode == 4) {
sort(ord.begin(), ord.end(), [&](int a, int b) {
double sa = blockValue[a] / (1.0 + blockNear[a]);
double sb = blockValue[b] / (1.0 + blockNear[b]);
if (sa != sb) return sa > sb;
return blockValue[a] > blockValue[b];
});
} else if (blockOrderMode == 5) {
sort(ord.begin(), ord.end(), [&](int a, int b) {
if (blockProfit0[a] != blockProfit0[b]) return blockProfit0[a] > blockProfit0[b];
return blockNear[a] < blockNear[b];
});
} else if (blockOrderMode == 6) {
sort(ord.begin(), ord.end(), [&](int a, int b) {
double sa = blockProfit0[a] / (1.0 + blockNear[a]);
double sb = blockProfit0[b] / (1.0 + blockNear[b]);
if (sa != sb) return sa > sb;
return blockProfit0[a] > blockProfit0[b];
});
}
Candidate out;
out.profit = 0.0;
int sold = 0;
int lastX = 0, lastY = 0;
for (int bi : ord) {
const vector<int>& ids = blocks[bi].second;
if (ids.empty()) continue;
int m = (int)ids.size();
double backCost = (sold > 0 ? distXY(lastX, lastY, 0, 0) : 0.0);
// Evaluate all prefixes in O(m):
// profit(p) = backDelta + Ssale - Sdist - C * (p * Sdist - SiDist),
// where SiDist = sum(i * dist_i), i is 0-based leg index.
int px = 0, py = 0;
double Ssale = 0.0;
double Sdist = 0.0;
double SiDist = 0.0;
double bestScore = -1e100;
double bestDelta = -1e100;
int bestPref = 0;
for (int i = 0; i < m; ++i) {
int id = ids[i];
double dseg = distXY(px, py, cities[id].x, cities[id].y);
Sdist += dseg;
SiDist += (double)i * dseg;
Ssale += saleValue(id, sold + i);
int p = i + 1;
double delta = -backCost + Ssale - Sdist - C * ((double)p * Sdist - SiDist);
double score = delta - BLOCK_CITY_TAX * p;
if (score > bestScore) {
bestScore = score;
bestDelta = delta;
bestPref = p;
}
px = cities[id].x;
py = cities[id].y;
}
vector<int> chosenTrip;
if (bestDelta > 0.0 && bestPref > 0) {
chosenTrip.assign(ids.begin(), ids.begin() + bestPref);
if (bestPref <= 24) {
twoOptImproveBounded(chosenTrip, sold);
double improvedDelta = tripProfit(chosenTrip, sold).first - backCost;
if (improvedDelta > bestDelta) {
bestDelta = improvedDelta;
bestScore = bestDelta - BLOCK_CITY_TAX * bestPref;
}
} else {
int headCand = min(bestPref, 64);
int headOpt = min(bestPref, 24);
vector<int> trial;
trial.reserve(bestPref);
vector<unsigned char> take(headCand, 0);
int px = 0, py = 0;
for (int pos = 0; pos < headOpt; ++pos) {
double bestGain = -1e100;
int bestIdx = -1;
for (int t = 0; t < headCand; ++t) {
if (take[t]) continue;
int id = chosenTrip[t];
double g = saleValue(id, sold + pos) -
distXY(px, py, cities[id].x, cities[id].y) *
(1.0 + C * (bestPref - pos));
if (g > bestGain) {
bestGain = g;
bestIdx = t;
}
}
if (bestIdx < 0) break;
take[bestIdx] = 1;
int id = chosenTrip[bestIdx];
trial.push_back(id);
px = cities[id].x;
py = cities[id].y;
}
for (int t = 0; t < headCand; ++t) {
if (!take[t]) trial.push_back(chosenTrip[t]);
}
for (int t = headCand; t < bestPref; ++t) {
trial.push_back(chosenTrip[t]);
}
if ((int)trial.size() == bestPref) {
double improvedDelta = tripProfit(trial, sold).first - backCost;
if (improvedDelta > bestDelta) {
bestDelta = improvedDelta;
bestScore = bestDelta - BLOCK_CITY_TAX * bestPref;
chosenTrip.swap(trial);
}
}
}
}
if (bestPref > 0 && bestScore > 0.0 && !chosenTrip.empty()) {
out.profit += bestDelta;
if (sold > 0) {
out.lines.push_back({0, 0, -1});
}
for (int i = 0; i < bestPref; ++i) {
int id = chosenTrip[i];
out.lines.push_back({cities[id].x, cities[id].y, i == 0 ? bestPref : -1});
}
sold += bestPref;
int lastId = chosenTrip[bestPref - 1];
lastX = cities[lastId].x;
lastY = cities[lastId].y;
}
}
return out;
}
static Candidate solveBlockFamily() {
Candidate best;
vector<int> lens;
if (N > 50000) {
lens = {1,2,3,4,6,8,12,16,24,32,48,64,96,128,192,256,384,512,768,1024};
} else {
lens = {1,2,3,4,6,8,12,16,24,32,48,64,72,96,128,144,192,256,288,384,512,576,768,1024,1152,1536,2048};
}
for (int L : lens) {
int bmMax = (N <= 30000 ? 6 : 5);
for (int bm = 0; bm <= bmMax; ++bm) {
Candidate c = runBlockConfig(L, bm);
if (c.profit > best.profit) best = move(c);
}
}
// For larger inputs, probe block mode 6 on a small lens subset
// to avoid timeout while still exploring a different ordering.
if (N > 30000) {
const int lens6[] = {64, 96, 128, 192, 256, 384, 512, 768};
for (int L : lens6) {
Candidate c = runBlockConfig(L, 6);
if (c.profit > best.profit) best = move(c);
}
}
return best;
}
static Candidate solveSingleCityFamily() {
Candidate best;
best.profit = -1e100;
vector<int> ids(N);
iota(ids.begin(), ids.end(), 0);
vector<int> modes = {0, 1, 2, 3};
for (int mode : modes) {
vector<int> ord = ids;
if (mode == 0) {
sort(ord.begin(), ord.end(), [&](int a, int b) {
if (cities[a].price != cities[b].price) return cities[a].price > cities[b].price;
return cities[a].d0 < cities[b].d0;
});
} else if (mode == 1) {
sort(ord.begin(), ord.end(), [&](int a, int b) {
double sa = cities[a].price / (1.0 + cities[a].d0);
double sb = cities[b].price / (1.0 + cities[b].d0);
if (sa != sb) return sa > sb;
return cities[a].price > cities[b].price;
});
} else if (mode == 2) {
double coeff = 1.0 + C;
sort(ord.begin(), ord.end(), [&](int a, int b) {
double sa = cities[a].price - coeff * cities[a].d0;
double sb = cities[b].price - coeff * cities[b].d0;
if (sa != sb) return sa > sb;
return cities[a].price > cities[b].price;
});
} else {
double coeff = 2.0 + C;
sort(ord.begin(), ord.end(), [&](int a, int b) {
double sa = cities[a].price - coeff * cities[a].d0;
double sb = cities[b].price - coeff * cities[b].d0;
if (sa != sb) return sa > sb;
return cities[a].price > cities[b].price;
});
}
Candidate cur;
cur.profit = 0.0;
int sold = 0;
int lastId = -1;
int badStreak = 0;
int maxBad = 500;
for (int id : ord) {
if (sold >= N) break;
double sale = saleValue(id, sold);
double gain = sale - cities[id].d0 * (1.0 + C);
if (sold > 0) gain -= cities[lastId].d0;
if (gain <= 0.0) {
++badStreak;
if (badStreak >= maxBad) break;
continue;
}
badStreak = 0;
if (sold > 0) {
cur.profit -= cities[lastId].d0;
cur.lines.push_back({0, 0, -1});
}
cur.profit += sale - cities[id].d0 * (1.0 + C);
cur.lines.push_back({cities[id].x, cities[id].y, 1});
lastId = id;
++sold;
}
if (cur.profit > best.profit) best = move(cur);
}
return best;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> N >> C >> D;
cities.resize(N);
for (int i = 0; i < 2001; ++i) {
for (int j = 0; j < 2001; ++j) gridPos[i][j] = -1;
}
for (int i = 0; i < N; ++i) {
cin >> cities[i].x >> cities[i].y >> cities[i].price;
cities[i].d0 = sqrt((double)cities[i].x * cities[i].x + (double)cities[i].y * cities[i].y);
gridPos[cities[i].x + 1000][cities[i].y + 1000] = i;
}
dPow[0] = 1.0;
for (int i = 1; i < 16; ++i) dPow[i] = dPow[i - 1] * D;
Candidate bestBlock = solveBlockFamily();
Candidate bestGreedy;
if (N <= 25000) {
bestGreedy = solveGreedyFamily();
}
Candidate bestGreedyLarge;
Candidate bestSingle;
if (N <= 25000) {
bestSingle = solveSingleCityFamily();
}
Candidate best = bestBlock;
if (bestGreedy.profit > best.profit) best = move(bestGreedy);
if (bestGreedyLarge.profit > best.profit) best = move(bestGreedyLarge);
if (bestSingle.profit > best.profit) best = move(bestSingle);
for (const auto &ln : best.lines) {
cout << ln.x << ' ' << ln.y;
if (ln.cnt != -1) cout << ' ' << ln.cnt;
cout << '\n';
}
return 0;
}
Scor obtinut: 0.211
Submission ID: 464695219
Link challenge: https://www.hackerrank.com/challenges/tbsp/problem
TBS Problem