Стоимость репетиторов по программированию в Перми

Язык программирования: Java, C++ Для себяещё

Начинающий. Возраст ребёнка: 10 лет.ещё

На старте добить задачу по динамическому программированию, ошибка по памяти на 42 тесте. Постройка тоннеля Максимум баллов : 100 Имя входного файла : tunnel.in Имя выходного файла : tunnel.out Ограничение по времени : 0.5 сек Ограничение по памяти : 64 Мб Для создания новой железнодорожной линии необходимо построить тоннель внутри горы. В связи с небольшим бюджетом, было решено простроить тоннель в уже существующем разломе внутри горы. Разлом представляет собой область, ограниченную двумя ломаными сверху и снизу. Верхняя ломаная состоит из N точек с координатами (1; A1), (2; A2), ..., (N; AN), где точки с соседними номерами соединены. Аналогично нижняя состоит из N точек с координатами (1; B1), (2; B2), ..., (N; BN), где точки с соседними номерами соединены. Перед постройкой тоннеля необходимо сначала проложить основу, которая состоит из нескольких пролетов, каждый из которых является отрезком между какими-то двумя вершинами нижней ломаной, причем все пролеты должны также образовывать одну непрерывную ломаную, а также все пролеты должны находиться строго внутри разлома (пролеты могут касаться обеих ломаных). Стоимость одного пролета равняется квадрату его длины, стоимость всей основы равняется сумме стоимостей входящих в нее пролетов. Для выполнения правил техники безопасности необходимо, чтобы: • первый пролет начинался в точке с номером 1, • последний пролет заканчивался в точке с номером N, • высота тоннеля в самом узком месте была не менее D (высота тоннеля - длина вертикального отрезка, соединяющего точку на верхней ломаной и точку на каком-либо из пролетов). По данным вам координатам точек и значению D помогите инженерам посчитать минимальную стоимость постройки основы для тоннеля, а из всех вариантов с такой стоимостью найти вариант с минимальным количеством пролетов. Формат файла входных данных: В первой строке даны числа N и D (2 ≤ N ≤ 5000, 1 ≤ D ≤ 106). Во второй строке дано N чисел A1 , A2 , ..., AN - координаты точек верхней ломаной по оси абсцисс, в третьей строке дано N чисел B1 , B2 , ..., BN - координаты точек нижней ломаной по оси абсцисс (0 ≤ Bi ≤ Ai ≤ 106). Формат файла выходных данных: Если построить основу для тоннеля в данном разломе невозможно, выведите -1. Иначе выведите 2 целых числа - минимальную стоимость постройки основы и минимальное число пролетов, необходимое для постройки основы с данной стоимостью. Система оценки: Правильные решения для N ≤ 100 и D, Ai , Bi ≤ 1000 оцениваются в 30 баллов. Пример: tunnel.in tunnel.out 5 1 6 7 3 7 7 3 2 1 3 0 19 4 3 2 4 3 4 2 2 2 -1 Иллюстрация к первому примеру: #include <bits/stdc++.h> using namespace std; #define EPS 1 #define MAX 1e6 #define ll long long #define ld long double struct point { ld x, y; }; struct spt { ll x, y; }; ll det(ll a1, ll a2, ll b1, ll b2 ){ return a1 * b2 - a2 * b1; } void input (spt f, spt s, ll &a, ll &b, ll &c) { a = s.y - f.y; b = f.x - s.x; c = -((s.x - f.x) * f.y - (s.y - f.y) * f.x); } point cross(spt f, spt s, spt f2, spt s2) { ll a1, a2, b1, b2, c1, c2; input(f, s, a1, b1, c1); input(f2, s2, a2, b2, c2); ld d, d1, d2; d = det(a1, b1, a2, b2); d1 = det(c1, b1, c2, b2 ); d2 = det(a1, c1, a2, c2 ); return {(ld) d1 / d, (ld) d2 / d}; } struct kof { double a, b, c; void __init__(point p1, point p2) { a = p2.y - p1.y; b = - (p2.x - p1.x); c = -(a * p1.x + b * p1.y); } }; double is_lefter(point a, point b, point o){ // a, b is b lefter than a o return ((a.x - o.x) * (b.y - o.y) - (a.y - o.y) * (b.x - o.x) >= 0); } double rast(point a, point b) { return (a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y); } double angle(point a, point b, point c) { point B, C; B.x = b.x - a.x; B.y = b.y - a.y; C.x = c.x - a.x; C.y = c.y - a.y; return B.x * C.x + B.y * C.y; } double point_to_vector(point p1, point p2, point p3) { point p; // point vector p.x = p2.x - p1.x; p.y = p2.y - p1.y; point pn; // point normal pn.x = -p.y; pn.y = p.x; point p4; // point p3 p4 p4.x = p3.x + pn.x; p4.y = p3.y + pn.y; kof line, vector; line.__init__(p3, p4); vector.__init__(p1, p2); double DET = vector.a * line.b - line.a * vector.b; double DETx = -vector.c * line.b - -line.c * vector.b; double DETy = vector.a * -line.c - line.a * -vector.c; point P; P.x = DETx / DET; P.y = DETy / DET; return rast(P, p3); } bool check(double a, double b) { return ((a < 0 && b > 0) || (a > 0 && b < 0)); } double vec(point a, point b) { return (a.x * b.y - a.y * b.x); } bool p(point a, point b, point c, point d) { point C; C.x = d.x - c.x; C.y = d.y - c.y; point CA, CB; CA.x = a.x - c.x; CA.y = a.y - c.y; CB.x = b.x - c.x; CB.y = b.y - c.y; return (check(vec(CA, C), vec(CB, C)) && angle(c,d,a) >= 0 && angle(c, d, b) >= 0); } bool for_p_p(vector<point> &v, spt i , spt j, ll o) { if (i.x > j.x) { swap(i, j); } for (int k = i.x; k <= j.x; k++) { if (v[k].x > cross(i, j, {k, (ll)(MAX)}, {k, (ll)(-MAX)}).y) { return false; } if (v[k].y - cross(i, j, {k, (ll)(MAX)}, {k, (ll)(-MAX)}).y < o) { return false; } } return true; } int main() { ifstream cin("tunnel.in", ios::in); ofstream cout("tunnel.out", ios::out); ll n, o; cin >> n >> o; vector<point> v(n); for (int i = 0; i < n; i++) { cin >> v[i].y; } for (int i = 0; i < n; i++) { cin >> v[i].x; } vector<pair<ll, ll>> dp(n, {1e18, 0}); dp[0] = {0, 0}; for (ll i = 1; i < n; i++) { for (ll j = 0; j < i; j++) { if (dp[i].first > dp[j].first + 1 && dp[i].first > dp[j].first + (ll)rast({(ld)j, (ld)v[j].x}, {(ld)i, (ld)v[i].x}) && for_p_p(v, {(ll)i, (ll)v[i].x}, {(ll)j, (ll)v[j].x}, o)) { dp[i] = {dp[j].first + (ll)rast({(ld)j, (ld)v[j].x}, {(ld)i, (ld)v[i].x}), dp[j].second + 1}; } } } if (dp.back().second == 0) { cout << "-1"; } else { cout << dp.back().first << " " << dp.back().second; } return 0; } 30 балов TLещё