آقای پنگ، رئیس کل زندان اوین است. در این زندان n n خلافکار در بند هستند و از 1 1 تا n n…
- User
آقای پنگ، رئیس کل زندان اوین است. در این زندان n n خلافکار در بند هستند و از 1 1 تا n n شمارهگذاری شدهاند. میزان ارتباط دو زندانی i i و j j برابر با a i , j a i,j است.
امروز با آقای پنگ تماس اضطراری گرفتهاند و به او گفتهاند که تا ۲۴ ساعت آینده، بمبی در این زندان منفجر خواهد شد. او باید هر چه سریعتر زندانیان را جابجا کند.
او باید زندانیان را تا رفع خطر به یکی از دو جزیره نخیلو و مولیات تبعید کند. قدرت افراد تبعید شده به یک جزیره، برابر با بیشینه میزان ارتباط بین هر جفت آنهاست. به صورت دقیقتر اگر مجموعه S S زندانیان تبعید شده به یک جزیره باشند، قدرت آنها برابر با max i , j ∈ S a i , j max i,j∈S a i,j خواهد بود (اگر ∣ S ∣ ≤ 1 ∣S∣≤1 قدرت آن جزیره صفر خواهد بود). به آقای پنگ کمک کنید که طوری زندانیان را بین دو جزیره تقسیم (و تبعید) کند که جمع قدرت افراد جزیره نخیلو و قدرت افراد جزیره مولیات کمینه شود. .
ورودی در سطر اول n n، تعداد زندانیان آمدهاست.
سپس در i i امین سطر از n n سطر بعدی، n − i n−i عدد آمدهاست که j j امین عدد برابر با a i , j + i a i,j+i است. همچنین a i + j , i
a i , i + j a i+j,i =a i,i+j
1 ≤ n ≤ 200 1≤n≤200 0 ≤ a i , j ≤ 1 0 9 0≤a i,j ≤10 9
خروجی در تنها سطر خروجی کمترین قدرت زندانیان را پس از تبعید چاپ کنید.
زیرمسئلهها زیرمسئله نمره محدودیت ۱ ۱۳ n ≤ 20 n≤20 ۲ ۶۴ n ≤ 50 n≤50 ۳ ۲۳ بدون محدودیت اضافی مثال ورودی نمونه ۱ 5 4 5 0 2 1 3 7 2 0 4 Plain text خروجی نمونه ۱ 4 Plain text ورودی نمونه ۲ 7 1 10 5 5 5 5 5 10 5 5 5 100 100 5 5 10 5 5 98 99 3 Plain text خروجی نمونه ۲ 15 c++
- Assistant
To solve this problem, we need to determine the most efficient way to partition prisoners into two different islands, Nakhilo and Molyat, such that the sum of the "power" of both islands is minimized. The "power" of an island is defined as the maximum connection value between any two prisoners on the island.
Step-by-Step Reasoning:
-
Understanding the Problem:
- We have
nprisoners with unique connections represented bya[i][j]. - Our goal is to split them into two groups such that the sum of the highest connection value in each group (power) is minimized.
- If the number of prisoners in a group is 1 or less, its power is 0.
- We have
-
Binary Search Approach:
- We'll use a binary search to find the minimum possible sum of the powers (
K = c + d). - For a given
K, we'll try to split the prisoners such that:- One group has a maximum connection value
cand the other hasd, wherec + d = K. - We need to ensure that no two prisoners with a connection value greater than
cin group S or greater thandin group T end up in the same group.
- One group has a maximum connection value
- We'll use a binary search to find the minimum possible sum of the powers (
-
Checking Bipartition:
- For each potential value of
K, determine the thresholdt_min = ceil(K / 2). - Create a graph where edges represent connections greater than
t_min. - Use BFS to check if this graph can be bipartitioned (split into two groups without having conflicting connections).
- If it can be bipartitioned, then
Kis feasible.
- For each potential value of
-
Implementation:
- We iterate through possible values of
Kusing binary search, and for eachK, we test if the prisoner split is possible. - If a valid split is found, we adjust our search range to find a potentially smaller
K. If not, increaseK.
- We iterate through possible values of
-
Edge Cases and Optimization:
- The algorithm efficiently handles up to 200 prisoners by carefully building and checking bipartitioned graphs.
- The entire procedure runs in logarithmic time relative to the maximum connection value due to the binary search, ensuring it works within constraints.
C++ Implementation:
#include <bits/stdc++.h> using namespace std; typedef long long ll; // Function to check if a graph is bipartite bool isBipartite(int n, vector<vector<int>> &adj) { vector<int> color(n, -1); queue<int> q; for(int i=0;i<n;i++) { if(color[i]==-1){ color[i]=0; q.push(i); while(!q.empty()){ int u = q.front(); q.pop(); for(auto &v: adj[u]){ if(color[v]==-1){ color[v]=color[u]^1; q.push(v); } else if(color[v] == color[u]){ return false; } } } } } return true; } int main(){ ios::sync_with_stdio(false); cin.tie(0); int n; cin >> n; vector<tuple<int, int, int>> edges; int aij; for(int i=0;i<n;i++){ for(int j=i+1;j<n;j++){ cin >> aij; edges.emplace_back(i, j, aij); } } // Collect all unique a's vector<int> W; for(auto &[i,j,a]: edges){ W.push_back(a); } sort(W.begin(), W.end()); W.erase(unique(W.begin(), W.end()), W.end()); // Binary search over K ll low=0, high=2000000000; while(low < high){ ll mid = low + (high - low)/2; // Find all c from 0 to K // Implement feasibility: exists c in [0, K] where G_c,d is bipartite // where d=K -c // To optimize, iterate through c in 0 to K, but c can be any a's or 0 // To make it faster, iterate through unique c's <= K // Include c=0 bool feasible=false; // To iterate c from 0 to K // Since a's are sorted, iterate c in W where c <= K, and include c=0 // To include c=0, check separately // Create a list of possible c's vector<int> possible_c; possible_c.push_back(0); for(auto &c_val: W){ if(c_val <= mid){ possible_c.push_back(c_val); } } // Remove duplicates sort(possible_c.begin(), possible_c.end()); possible_c.erase(unique(possible_c.begin(), possible_c.end()), possible_c.end()); for(auto &c: possible_c){ ll d = mid - c; if(d <0) continue; // Now, define G_c,d as edges with a_{i,j} >c and >d // Which is a_{i,j} > max(c,d) int t = max((int)c, (int)d); // Build adjacency list for G_t vector<vector<int>> adj(n, vector<int>()); for(auto &[i,j,a]: edges){ if(a > t){ adj[i].push_back(j); adj[j].push_back(i); } } // Check if G_t is bipartite if(isBipartite(n, adj)){ feasible=true; break; } } if(feasible){ high=mid; } else{ low=mid +1; } } cout << low; } -
Other models, same or similar prompt
Responses were produced in different, uncontrolled contexts (system prompts, settings, prior turns). This is not a benchmark.