Summary of Code Practice Techniques Môn Thuật toán ứng dụng | Đại học Bách Khoa Hà Nội

lOMoAR cPSD| 61601590 Contents
CBUS ............................................................................................................................................................................................... 2
Balanced Courses Assignments ..................................................................................................................................................... 3
Count Integer Solutions ................................................................................................................................................................. 4
Disjoint Segment ............................................................................................................................................................................ 5
Inversion ......................................................................................................................................................................................... 5
Max-Distance Sub-Sequence ......................................................................................................................................................... 6
Gold Mining .................................................................................................................................................................................... 7
Max Even Subsequence ................................................................................................................................................................. 8
Nurse .............................................................................................................................................................................................. 9
Warehouse ..................................................................................................................................................................................... 9
Bridges .......................................................................................................................................................................................... 10
Bus Inner City ............................................................................................................................................................................... 11
Make Span Schedule .................................................................................................................................................................... 13
Strongly Connected Components ................................................................................................................................................ 13
Telco data check & query ............................................................................................................................................................. 14
Maze ............................................................................................................................................................................................. 15
Range Minimum Query ................................................................................................................................................................ 16
Largest black subrectangle ........................................................................................................................................................... 17
Max-Distance Sub-Sequence ....................................................................................................................................................... 18
Cut Material.................................................................................................................................................................................. 19
Max Matching on Bipartie Graph ................................................................................................................................................ 20
Pair of equal items in a sequence ................................................................................................................................................ 21
Quàtặngsữa .................................................................................................................................................................................. 21
Truytìmkhobáu ............................................................................................................................................................................. 22
Given a sequence of n integers a0,. . .,an-1. We denote rmq(i,j) the minimum element of the
sequence ai, ai+1, . . .,aj. Given m pairs (i1, j1),. . .,(im, jm), compute the sum Q = rmq(i1,j1) + . . .
+ rmq(im, jm) ............................................................................................................................................................................... 22
Find Husband................................................................................................................................................................................ 23
Longest Increasing subsequence ................................................................................................................................................. 24
Longest Common Subsequence ................................................................................................................................................... 24
Hunting_dog ................................................................................................................................................................................. 25
Convert hh:mm:ss to seconds ...................................................................................................................................................... 26
Binary sequence generation ........................................................................................................................................................ 26
Binary sequences generation without consecutive 11 ............................................................................................................... 26
Count number of sudoku solutions ............................................................................................................................................. 27
Permutation generation ............................................................................................................................................................... 28
Family Tree ................................................................................................................................................................................... 28
WATER JUGS ................................................................................................................................................................................. 29
Hamiton Cycle .............................................................................................................................................................................. 30
List order of nodes visited by a DFS ............................................................................................................................................. 31
Minimum Spanning Tree - Kruskal ............................................................................................................................................... 32
Sequence of nodes visited by BFS ............................................................................................................................................... 33
All pair shortest paths .................................................................................................................................................................. 33
Max Flow ...................................................................................................................................................................................... 34
Shortest Path between 2 nodes on a directed graph with non-negative weights ..................................................................... 36
Bank Transaction .......................................................................................................................................................................... 37
Analyze Code Submission of a Programming Contest ................................................................................................................ 38 lOMoAR cPSD| 61601590
Citizen Data Analysis .................................................................................................................................................................... 39
Longest Path on a Tree .................................................................................................................................................................. 41
Problem: Sum of length of paths from root on a tree .................................................................................................................. 42
bank_money_transfer .................................................................................................................................................................. 42
Given a sequence of distinct integers a1, a2, . . ., an . Compute the number P of triples of distinct
indices (i, j, k) such that among 3 items ai, aj , ak there is an item which is equal to the sum of 2
remaining items ............................................................................................................................................................................ 43
After parity lis ............................................................................................................................................................................... 43
stone_castle .................................................................................................................................................................................. 44
CBUS_UPPER_BOUND_CSTR_LENGTH_PICKUP_DROPOFF .......................................................................................................... 45
Compute C_k_n ............................................................................................................................................................................ 46
Check Parenthesis ........................................................................................................................................................................ 47
Equal to the sum of 2 remaining items ....................................................................................................................................... 47
chuyển n túi tiền từ trụ sở chính ................................................................................................................................................. 48 CBUS #include using namespace std ;
int n, K, load,x[10000], Fmin = 99999999, F = 0,M[1000][1000],Cmin=999999 ; bool visited[10000] ;
bool check(int v) { if(visited[v] == true) return false ; if(v>n) { if(visited[v-n]==false) { return false ; } }
else if(load+ 1 > K) return false ; return true ; } void updateBest() {
Fmin = min(Fmin,M[x[2*n]][0]+F) ; return ; }
void Try(int k){ for(int v = 1 ; v<=2*n; v++) {
if(check(v)){ x[k] = v ; visited[v] = true ; if(v<=n) { load ++ ; } else { load-- ; }
F += M[x[k-1]][x[k]] ; if(k==2*n) { updateBest() ; }
else if(F+(2*n-k)*Cmin Try(k+1); } F-= M[x[k-1]][x[k]] ; visited[x[k]] = false ; if(v<=n) { load-- ; } else load++ ; } } }
int main() { memset(x,0, sizeof(x)) ;
memset(visited, false, sizeof(visited)); load = 0 ; cin>>n>>K ;
for(int i =0 ; i<= 2*n ;i++ ) { for(int j = 0 ; j <=
2*n ; j++) { cin>>M[i][j] ; lOMoAR cPSD| 61601590 if(i!=j) { Cmin=min(M[i][j],Cmin) ; } } } x[0] = 0 ; visited[0] = true ; Try(1) ; cout<}
Balanced Courses Assignments #include using namespace std; int m, n, k; vector>favor; bool conflict[31][31]; vectorload; vector>assigned; int ans =
INT_MAX; bool is_valid(int teacher, int course) {
if(find(favor[teacher].begin(), favor[teacher].end(), course + 1) == favor[teacher].end()) return false;
for(int i = 0; i< assigned[teacher].size(); i++) {
if(conflict[course][assigned[teacher][i]]) return false; } return true; } void Try(int index) { if(index == n) {
int max_load_curr = *max_element(load.begin(), load.end()); ans = min(ans, max_load_curr); return; }
for(int teacher = 0; teacher < m; teacher++) {
if(is_valid(teacher, index) && load[teacher] + 1 <= ans) { load[teacher]++;
assigned[teacher].push_back(index); Try(index + 1); load[teacher]--;
assigned[teacher].pop_back(); } } } int main() { cin>> m >>n;
favor.resize(m); load.resize(m,
0); assigned.resize(m); for(int i = 0; i< m; i++) { int k; cin>>k; lOMoAR cPSD| 61601590 favor[i].resize(k); for(int j = 0; j < k; j++) { cin>> favor[i][j]; } } cin>>k;
memset(conflict, false, sizeof(conflict)); for(int i = 0; i< k; i++) { int temp1, temp2;
cin>> temp1 >>temp2;
conflict[temp1 - 1][temp2 - 1] = true;
conflict[temp2 - 1][temp1 - 1] = true; } Try(0); if (ans == INT_MAX) { cout<< -1 < } else { cout< } return 0; }
Count Integer Solutions #include using namespace std; int n, m, a[1000];
int countSolutions(int currentSum, int index) { //
Nếutổnghiệntạibằng M, cómộtnghiệmtìmthấy if
(currentSum == m) { return 1; }
// Nếutổnghiệntạilớnhơn M hoặcđãkiểmtrahếtcáchệsố
if (currentSum> m || index >= n) { return 0; } int totalWays = 0;
for (int x = 0; currentSum + a[index] * x <= m; x++) {
totalWays += countSolutions(currentSum + a[index] * x, index + 1); } return totalWays; } int main() { cin>> n >>m;
for (int i = 0; i< n; i++) { cin>> a[i]; }
int result = countSolutions(0, 0); cout<< result < return 0; } lOMoAR cPSD| 61601590 Disjoint Segment #include using namespace std; struct Edge { int start, end;
Edge(int s = 0, int e = 0) : start(s), end(e) {} };
int disjoint_sets(vector&arr) { int n = arr.size();
sort(arr.begin(), arr.end(), [](Edge a, Edge b) { return a.end }); int res = 1; int last_end = arr[0].end;
for(int i = 0; i< n; i++) {
if(arr[i].start>last_end) { res++; last_end = arr[i].end; } } return res; } int main() { int n; cin>>n; vectorarr(n); for(int i = 0; i< n; i++) {
cin>>arr[i].start>>arr[i].end; } cout<} Inversion #include using namespace std;
const int MOD = 1e9 + 7; // Hằng sốchophéplấykếtquả modulo
// Hàmđểhợpnhấthaimảng con vàđếmsốlượngđảongược long
longmerge_and_count(vector&arr, int left, int mid, int right) { int n1 = mid - left + 1; int n2 = right - mid; vector L(n1), R(n2); for
(int i = 0; i< n1; i++) L[i] =
arr[left + i]; for (int j = 0; j < n2; j++) R[j] = arr[mid + 1 + j]; long long count = 0; int i = 0, j = 0, k = left;
while (i< n1 && j < n2) {
if (L[i] <= R[j]) { arr[k++] = L[i++]; } else {
count += (n1 - i); // Đếmsốđảongược arr[k++] = R[j++]; } } lOMoAR cPSD| 61601590
while (i< n1) arr[k++] = L[i++]; while (j < n2) arr[k++] = R[j++]; return count % MOD; }
// Hàmđệquy merge sort vàđếmđảongược
long longmerge_sort_and_count(vector&arr, int left, int right) { long long
count = 0; if (left < right) {
int mid = left + (right - left) / 2;
count += merge_sort_and_count(arr, left, mid); count +=
merge_sort_and_count(arr, mid + 1, right);
count += merge_and_count(arr, left, mid, right); } return count % MOD; } int main() { int n;
cin>> n; // Nhậpsốlượngphầntử vectorarr(n);
for (int i = 0; i< n; i++) {
cin>>arr[i]; // Nhậpdãysố }
long long result = merge_sort_and_count(arr, 0, n - 1); // Tínhsốđảongược cout<< result <}
Max-Distance Sub-Sequence #include #include #include using namespace std;
// Hàmkiểmtraxemcóthểđặt C phầntửvớikhoảngcáchtốithiểulàdist hay không bool
canPlaceCows(const vector& positions, int n, int c, int dist) { int count = 1; //
Đếmsốphầntửđãđặt
int last_position = positions[0]; // Vịtrícủaphầntửđãđặtcuốicùng for (int i = 1; i< n; i++) {
// Nếukhoảngcáchtừphầntửhiệntạiđếnphầntửđãđặtcuốicùng>= dist if
(positions[i] - last_position>= dist) { count++; // Đặtphầntửmới
last_position = positions[i]; // Cậpnhậtvịtríđãđặt }
if (count == c) return true; // Nếuđãđặtđủ C phầntử }
return false; // Khôngthểđặtđủ C phầntử }
// Hàmtìmkhoảngcáchtốithiểulớnnhất
int findMaxDistance(vector& positions, int n, int c) {
sort(positions.begin(), positions.end()); // Sắpxếpcácvịtrí int left = 1; //
Khoảngcáchnhỏnhấtcóthể
int right = positions[n - 1] - positions[0]; // Khoảngcáchlớnnhấtcóthể int result = 0; while (left <= right) {
int mid = left + (right - left) / 2; // Khoảngcáchthửnghiệm //
Kiểmtraxemcóthểđặt C phầntửvớikhoảngcách mid hay không if lOMoAR cPSD| 61601590
(canPlaceCows(positions, n, c, mid)) { result = mid; // Cậpnhậtkếtquả
left = mid + 1; // Tăngkhoảngcách } else {
right = mid - 1; // Giảmkhoảngcách } }
return result; // Trảvềkhoảngcáchtốiđatìmđược } int main() { int t;
cin>> t; // Nhậpsốlượng test cases while (t--) { int n, c;
cin>> n >> c; // Nhập N và C vector positions(n);
for (int i = 0; i< n; i++) {
cin>> positions[i]; // Nhập các vịtrí }
// Tìmkhoảngcáchtốithiểulớnnhất int result =
findMaxDistance(positions, n, c); cout<< result <Xuấtkếtquả } return 0; } Gold Mining #include using namespace std; int main() { int n, L1, L2;
cin>> n >> L1 >>L2;
vector a(n), dp(n); for (int i = 0; i< n; ++i) cin>> a[i];
// Khởitạo deque đểlưutrữcácchỉsốcủadp
dequedq; long longmax_gold = 0;
for (int i = 0; i< n; ++i) {
// Xóacácphầntửkhôngcầnthiếttrong deque while
(!dq.empty() &&dp[dq.back()] <= dp[i - L1]) { dq.pop_back(); }
// Thêmchỉsốcủadp[i - L1] vào deque if (i - L1 >= 0) { dq.push_back(i - L1); }
// Xóaphầntửđầutiêntrong deque nếunórangoàikhoảng [i - L2] while
(!dq.empty() &&dq.front() } // Tính giá trịdp[i] if (!dq.empty()) { dp[i] = dp[dq.front()] + a[i]; } else {
dp[i] = a[i]; // Nếukhôngcóphầntử nào trong deque lOMoAR cPSD| 61601590 }
max_gold = ((max_gold>dp[i]) ?max_gold : dp[i]); } cout< return 0; } Max Even Subsequence #include using namespace std;
int main() { ios_base::sync_with_stdio(0); cin.tie(0); int n; cin>>n;
long long sum = 0; long longmaxEven =
LLONG_MIN; long longminEven = 0;
long longmaxOdd = LLONG_MIN; long
longminOdd = LLONG_MAX; bool hasEven = false;
for(int i = 0; i< n; i++) { int x; cin>>x; sum += x; if(sum % 2 == 0) {
maxEven = max(maxEven, sum - minEven); minEven = min(minEven, sum); hasEven = true; } else {
if(minOdd != LLONG_MAX) { maxEven = max(maxEven, sum - minOdd); }
if(maxOdd != LLONG_MIN) { maxEven = max(maxEven, sum - maxOdd); } maxOdd = max(maxOdd, sum); minOdd = min(minOdd, sum); } }
if(!hasEven&&maxEven == LLONG_MIN) { cout<< "NOT_FOUND\n"; } else { cout< } return 0; } lOMoAR cPSD| 61601590 Nurse #include using
namespace std; const int MOD = 1e9 + 7; int main() { int n, K1, K2;
cin>> n >> K1 >>K2; // Khởitạomảng f
vector>f(n + 1, vector(2, 0)); // Cơsở
f[0][0] = 1; // 1 cáchđểkhônglàmgìtrong 0 ngày f[0][1] = 1; //
Khôngcócáchnàođểlàmviệctrong 0 ngày
for (int i = 1; i<= n; ++i) { // Tính
f[i][0]: ngàynghỉ f[i][0] = f[i - 1][1];
// Tính f[i][1]: ngàykếtthúccủamộtđợtlàmviệc for (int
j = K1; j <= K2; ++j) { if (i - j >= 0) {
f[i][1] = (f[i][1] + f[i - j][0]) % MOD; } } }
// Kếtquảlàtổngsốcáchlậplịchcho N ngày long long
result = (f[n][0] + f[n][1]) % MOD;
cout<< result < return 0; } Warehouse #include using namespace std;
const int MAXN = 1000; const int
MAXT = 100; const int MOD = 1e9 + 7; int main() { int N, T, D;
cin>> N >> T >>D; vector a(N), t(N);
for (int i = 0; i< N; ++i) cin>> a[i]; for (int i = 0;
i< N; ++i) cin>> t[i];
// DP table to track max goods collected vector>dp(N, vector(T + 1, 0));
// Initialize starting DP values for (int
i = 0; i< N; ++i) { if (t[i] <= T) dp[i][t[i]] = a[i]; } int max_goods = 0; lOMoAR cPSD| 61601590
// DP transitions for (int i = 0; i< N;
++i) { for (int j = 0; j <= T; ++j) { if (dp[i][j] == 0) continue;
// Transition from station i to i + d (1 <= d <= D) for (int d
= 1; d <= D; ++d) { int next_station = i + d; if (next_station>= N) break;
int next_time = j + t[next_station]; if (next_time<= T) {
dp[next_station][next_time] = max(dp[next_station][next_time], dp[i][j] + a[next_station]); max_goods =
max(max_goods, dp[next_station][next_time]); } } } } cout< return 0; } Bridges #include #include #include #include using namespace std; class Graph { public:
Graph(int vertices); void addEdge(int u, int v);
void findArticulationPointsAndBridges(); private:
void dfs(int u, int parent); int V; // Sốđỉnh
vector> adj; // Danh sáchkề vector disc, low; vectorvisited;
setarticulationPoints; vectorint>>bridges; int time; }; Graph::Graph(int vertices) {
V = vertices; adj.resize(V + 1);
disc.resize(V + 1); low.resize(V + 1); visited.resize(V + 1); time = 0; }
void Graph::addEdge(int u, int v) {
adj[u].push_back(v); adj[v].push_back(u); }
void Graph::dfs(int u, int parent) {
visited[u] = true; disc[u] = low[u] = ++time; int children = 0;
for (int v : adj[u]) { if (!visited[v]) {
children++; dfs(v, u); low[u] = min(low[u], low[v]); lOMoAR cPSD| 61601590
// Điềukiệnchođiểmcắt
if (parent != -1 && low[v] >= disc[u]) { articulationPoints.insert(u); } // Điềukiệnchocầu if (low[v] > disc[u]) { bridges.push_back({u, v}); }
} else if (v != parent) { low[u] = min(low[u], disc[v]); } } // Gốccủa DFS
if (parent == -1 && children > 1) { articulationPoints.insert(u); } }
void Graph::findArticulationPointsAndBridges() { for (int i = 1; i<= V; ++i) { if (!visited[i]) { dfs(i, -1); } } cout<} int main() { int N, M; cin>> N >>M; Graph g(N);
for (int i = 0; i< M; ++i) { int u, v; cin>> u >>v; g.addEdge(u, v); }
g.findArticulationPointsAndBridges(); return 0; } Bus Inner City #include
#define FOR(i, x, y) for(int i = x; i<= y; i++) using namespace std;
int n, m; // Sốthànhphốvàsốđườngkếtnối long longcost[5001], maxCities[5001]; // Chi
phívàsốthànhphốtốiđamàtuyếnbuýtcóthểđi long longdp[5001][5001]; // Mảnglưu chi phítốithiểu
vectorgraph[5001]; // Đồthịbiểudiễncácthànhphốvàcácđườngnối
// Định nghĩachocáckiểudữliệuđểsửdụngtronghàngđợiưutiên typedef
pairCostPair; typedef pairState;
priority_queue, greater>pq; // Hàngđợiưutiên
long longfindMinimumCost(int start, int finish) { lOMoAR cPSD| 61601590
// Khởitạomảngdpvớigiátrịlớn FOR(i, 1, n) { FOR(j, 0, n) {
dp[i][j] = LLONG_MAX; // Sửdụng LLONG_MAX đểđạidiệnchovôcùng } }
dp[start][maxCities[start]] = cost[start]; // Chi phíkhibắtđầutừthànhphốbắtđầu
pq.push(State(CostPair(dp[start][maxCities[start]], maxCities[start]), start)); while (!pq.empty()) {
int currentCity = pq.top().second; long
longcurrentCost = pq.top().first.first; int
remainingCities = pq.top().first.second; pq.pop();
// Kiểmtraxem chi phíhiệntạicótươngứngvớigiátrị trong dpkhông if
(currentCost != dp[currentCity][remainingCities]) continue;
// Nếuđãđếnthànhphốđích, trảvề chi phí if
(currentCity == finish) return currentCost;
// Duyệt qua cácthànhphố lân cận for (int
neighbor : graph[currentCity]) {
// Nếucònthànhphốđể đi if (remainingCities> 0) {
// Cậpnhật chi phínếuđiđếnthànhphốlâncậnmàkhôngtínhthêm chi phí if
(dp[neighbor][remainingCities - 1] >currentCost) { dp[neighbor][remainingCities - 1] = currentCost;
pq.push(State(CostPair(currentCost, remainingCities - 1), neighbor)); }
// Cậpnhật chi phínếulênxebuýtmới
if (dp[neighbor][maxCities[neighbor]] > currentCost + cost[neighbor]) {
dp[neighbor][maxCities[neighbor]] = currentCost + cost[neighbor];
pq.push(State(CostPair(currentCost + cost[neighbor], maxCities[neighbor]), neighbor)); } } } }
return -1; // Nếukhôngtìmthấyđườngđiđếnthànhphốđích } int main() {
// Nhậpsốlượngthànhphốvàđườngkếtnối cin>> n >>m; FOR(i, 1, n) {
cin>> cost[i] >>maxCities[i]; // Nhập chi phívàsốthànhphốtốiđachomỗituyếnbuýt }
// Nhậpcácđườngkếtnốigiữacácthànhphố while (m--) { int a, b; cin>> a >>b; graph[a].push_back(b);
graph[b].push_back(a); // Đồthịvôhướng }
// Tìm chi phítốithiểuđểđitừthànhphố 1 đếnthànhphố n cout< return 0; } lOMoAR cPSD| 61601590 Make Span Schedule #include using namespace std; int main() { int n, m;
cin>> n >>m; vector d(n+1);
for (int i = 1; i<= n; ++i) { cin>> d[i]; } vector> graph(n+1);
vector bac (n+1, 0); for (int i = 0; i< m; ++i) { int u, v;
cin>> u >>v; graph[u].push_back(v); bac[v]++; } queueq;
vectorcompletion(n+1, 0); for (int i
= 1; i<= n; ++i) { if (bac[i] == 0) { q.push(i); completion[i] = d[i]; } } while (!q.empty()) { int u = q.front(); q.pop();
for (int neighbor : graph[u]) { bac[neighbor]--;
completion[neighbor] = max(completion[neighbor], completion[u] + d[neighbor]); if (bac[neighbor] == 0) { q.push(neighbor); } } } int res = 0;
for (int i = 1; i<= n; i++) { res = max(res, completion[i]);
} cout<< res <return 0; }
Strongly Connected Components
#include using namespace std; void dfs(vector>& graph, vector& visited,
stack&finishStack, int start) { visited[start] = true; for (int neighbor : graph[start]) { if (!visited[neighbor]) {
dfs(graph, visited, finishStack, neighbor); } } finishStack.push(start); }
void dfs_reverse(vector>&reverse_graph, vector& visited, int start) { visited[start] = true; lOMoAR cPSD| 61601590
for (int neighbor :reverse_graph[start]) { if (!visited[neighbor]) {
dfs_reverse(reverse_graph, visited, neighbor); } } } int main() { int n, m; cin>> n >>m; vector> graph(n+1); vector>reverse_graph(n+1);
for (int i = 0; i< m; ++i) { int u, v;
cin>> u >>v; graph[u].push_back(v);
reverse_graph[v].push_back(u); } // dfs G
vector visited (n+1, false); stackfinishStack;
for(int i = 1; i<= n; i++) { if (!visited[i]) { dfs(graph, visited, finishStack, i); } } // dfs G_T
visited.assign(n+1, false); int cnt = 0;
while (!finishStack.empty()) { int u = finishStack.top();
finishStack.pop(); if(!visited[u]) {
dfs_reverse(reverse_graph, visited, u); cnt++; } } cout<return 0; }
Telco data check & query #include using namespace std; struct CallLog { string from_number; string to_number; string date; string from_time; string end_time; };
// Hàmkiểmtratínhhợplệcủasốđiệnthoại bool
isValidPhoneNumber(const string& number) { if
(number.size()!= 10) return false; for (int i = 0;
i if (!(number[i] >= '0' && number[i] <= '9')) return false; } return true; }
// Hàmtínhtổngthờigiancuộcgọitheogiây
int calculateDuration(const string& start, const string& end) { int startTime=
3600*((start[0]-'0')*10 + start[1]-'0') lOMoAR cPSD| 61601590
+ 60*((start[3]-'0')*10 + start[4]-'0') +
((start[6]-'0')*10 + start[7]-'0'); int endTime= 3600*((end[0]- '0')*10 + end[1]-'0')
+ 60*((end[3]-'0')*10 + end[4]-'0') +
((end[6]-'0')*10 + end[7]-'0'); return endTime - startTime; }
int main() { vectorlogs; unordered_mapint>calls_from; unordered_maplong>total_time_from; string line;
while (true) { getline(cin, line); if (line == "#") break; if
(line.find("call") == 0) { stringstream ss(line);
string keyword, from_number, to_number, date, from_time, end_time; ss >> keyword
>>from_number>>to_number>> date >>from_time>>end_time; logs.push_back({from_number, to_number,
date, from_time, end_time}); calls_from[from_number]++;
total_time_from[from_number] += calculateDuration(from_time, end_time); } } while (true) { cin>>line; if (line == "#") break;
if (line == "?check_phone_number") {
bool all_valid = true; for (const auto&log : logs) {
if (!isValidPhoneNumber(log.from_number) || !isValidPhoneNumber(log.to_number)) { all_valid = false; break; } }
cout<< (all_valid ?1 : 0) < } else if (line == "?number_calls_from") { string
phone_number; cin>>phone_number;
cout< } else if (line == "?number_total_calls") { cout< } else if (line == "?count_time_calls_from") { string
phone_number; cin>>phone_number; cout< } } return 0; } Maze #include using namespace std;
int BFS(int n, int m, int r, int c, vector>& maze) {
// Các hướng di chuyển: lên, xuống, trái, phải
vector> directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; queue>
q; // Queue đểlưutọađộ q.push({r, c});
// Mảng 2 chiềukiểmtrađãghéthămchưa lOMoAR cPSD| 61601590
vector>visited(n, vector(m, false)); visited[r][c] =
true; int steps = 0; // Đếmsốbướcđãđi while (!q.empty()) { int size = q.size();
steps++; // Tăngsốbướcsaumỗilầnlặp
for (int i = 0; i< size; ++i) { int x = q.front().first; int y = q.front().second; q.pop();
// Kiểmtranếuđãra biên
if (x == 0 || x == n - 1 || y == 0 || y == m - 1) { return steps; // Trảvềsốbước }
// Kiểmtracác ô lâncận
for (pairdirection : directions) { int
new_x = x + direction.first; int new_y = y + direction.second;
// Kiểmtraxem ô mớicóhợplệkhông
if (new_x>= 0 &&new_x< n &&new_y>= 0 &&new_y< m &&
maze[new_x][new_y] == 0 && !visited[new_x][new_y]) {
visited[new_x][new_y] = true; q.push({new_x, new_y}); } } } }
// Nếukhôngtìmthấyđườngthoát return -1; } int main() { int n, m, r, c;
cin>> n >> m >> r >>c;
r--; c--; // Chuyển sang chỉsố 0 vector>maze(n, vector(m)); //
Sửdụng vector for (int i = 0; i< n; ++i) {
for (int j = 0; j < m; ++j) { cin>> maze[i][j]; } } cout<} Range Minimum Query #include using namespace std; int main() {
int n, queries, i, j, sum = 0; cin>>n; int a[n];
int maxLog = log2(n) + 1; // so hang cuamang 2 chieu int b[n][maxLog];
for (int k = 0; k < n; k++) cin>> a[k];
// preprocessing for (int k = 0; k < n; k++) {
b[k][0] = k; // khoitao hang dautien lOMoAR cPSD| 61601590 }
// tinhtoancac hang con lai for (int h = 1; (1 << h) <= n; h++) {
for (int k = 0; k + (1 << h) - 1 < n; k++) { if (a[b[k][h - 1]] < a[b[k +
(1 << (h - 1))][h - 1]]) { b[k][h] = b[k][h - 1]; } else {
b[k][h] = b[k + (1 << (h - 1))][h - 1]; } } } // processing cin>>queries;
while (queries--) { cin>>i>>j;
int range = (1 << (int)log2(j - i + 1)); // do dai moi khoang int column = (int)log2(j -
i + 1); // toa do theo cot trenmang 2 chieu
// tim min trongcackhoang int minIndex1 = b[i][column];
int minIndex2 = b[j - range + 1][column]; int minValue =
min(a[minIndex1], a[minIndex2]); sum += minValue; }
cout<< sum < return 0; }
Largest black subrectangle #include using namespace std;
// Hàmtínhdiệntíchlớnnhấttrongmộtmảngchiềucao int
maxRectangleArea(int heights[], int m) { stacks; int maxArea = 0;
for (int j = 0; j <= m; j++) { int h = (j == m) ?0 :
heights[j]; while (!s.empty() && heights[s.top()] > h) {
int height = heights[s.top()]; s.pop();
int width = s.empty() ? j : j - s.top() - 1; maxArea = max(maxArea, height * width); } s.push(j); } return maxArea; } int main() { int n, m; cin>> n >>m;
int matrix[n][m]; for (int i = 0; i< n;
i++) { for (int j = 0; j < m; j++) { cin>> matrix[i][j]; } } // Tạomảngchiềucao int height[m];
for (int j = 0; j < m; j++) height[j] = 0; int maxArea = 0; lOMoAR cPSD| 61601590
for (int i = 0; i< n; ++i) { for (int j = 0; j < m; ++j) { //
Cậpnhậtchiềucao if (matrix[i][j] == 1) { height[j]++; } else { height[j] = 0; } }
// Tínhdiệntíchlớnnhấtchohànghiệntại
maxArea = max(maxArea, maxRectangleArea(height, m)); } cout< return 0; }
Max-Distance Sub-Sequence #include #include #include using namespace std;
// Hàmkiểmtraxemcóthểđặt C phầntửvớikhoảngcáchtốithiểulàdist hay không bool
canPlaceCows(const vector& positions, int n, int c, int dist) { int count = 1; //
Đếmsốphầntửđãđặt
int last_position = positions[0]; // Vịtrícủaphầntửđãđặtcuốicùng for (int i = 1; i< n; i++) {
// Nếukhoảngcáchtừphầntửhiệntạiđếnphầntửđãđặtcuốicùng>= dist if
(positions[i] - last_position>= dist) { count++; // Đặtphầntửmới
last_position = positions[i]; // Cậpnhậtvịtríđãđặt }
if (count == c) return true; // Nếuđãđặtđủ C phầntử }
return false; // Khôngthểđặtđủ C phầntử }
// Hàmtìmkhoảngcáchtốithiểulớnnhất
int findMaxDistance(vector& positions, int n, int c) {
sort(positions.begin(), positions.end()); // Sắpxếpcácvịtrí int left = 1; //
Khoảngcáchnhỏnhấtcóthể
int right = positions[n - 1] - positions[0]; // Khoảngcáchlớnnhấtcóthể int result = 0; while (left <= right) {
int mid = left + (right - left) / 2; // Khoảngcáchthửnghiệm //
Kiểmtraxemcóthểđặt C phầntửvớikhoảngcách mid hay không if
(canPlaceCows(positions, n, c, mid)) { result = mid; // Cậpnhậtkếtquả
left = mid + 1; // Tăngkhoảngcách } else {
right = mid - 1; // Giảmkhoảngcách } }
return result; // Trảvềkhoảngcáchtốiđatìmđược } int main() { int t;
cin>> t; // Nhậpsốlượng test cases while (t--) { lOMoAR cPSD| 61601590 int n, c;
cin>> n >> c; // Nhập N và C vector positions(n);
for (int i = 0; i< n; i++) {
cin>> positions[i]; // Nhập các vịtrí }
// Tìmkhoảngcáchtốithiểulớnnhất int result =
findMaxDistance(positions, n, c); cout<< result <Xuấtkếtquả } return 0; } Cut Material #include using namespace std;
int height, width, n; int h[10], w[10], mark[10][10]; void doMark(int x,
int y, int xoay, int k, bool mark_value) { int wk = w[k]; int hk = h[k]; if (xoay == 1) { swap(wk, hk); }
for (int i = x; i<= x + wk -1; i++) { for (int j = y; j <= y + hk -1; j++) { mark[i][j] = mark_value; } } }
bool check(int xoay, int x, int y, int k) { int wk =
w[k]; int hk = h[k]; if (xoay == 1) { swap(wk, hk); }
if (x + wk> width || y + hk> height) return false; for (int i =
x; i<= x + wk -1; i++) { for (int j = y; j <= y + hk - 1; j++) {
if (mark[i][j]) { return false; } } } return true; } bool tryy(int k) { if (k == n) { return true; }
for (int xoay = 0; xoay<= 1; xoay++) { int wk =
w[k]; int hk = h[k]; if (xoay == 1) { swap(wk, hk); }
for (int x = 0; x <= width - wk; x++) { for (int y =
0; y <= height - hk; y++) { if (check(xoay, x, y, k)) { doMark(x, y, xoay, k, true); lOMoAR cPSD| 61601590
if (tryy(k + 1)) return true; doMark(x, y, xoay, k, false); } } } } return false; }
int main() { cin>> height >>width; cin>>n;
for (int i = 0; i< n; i++) {
cin>> w[i] >> h[i]; } if (tryy(0)) { cout<< 1 < } else { cout<< 0 < } return 0; }
Max Matching on Bipartie Graph #include #include #include
using namespace std; const int MAX_N = 10000;
vectortasks[MAX_N + 1]; // Danh sáchnhiệmvụchotừngnhânviên int staffAssignment[MAX_N +
1]; // Mảnglưunhânviênđãđượcphâncôngchonhiệmvụ bool visited[MAX_N + 1]; //
Mảngđánhdấunhânviênđãđượcthăm
bool canAssign(int task) { for (int staff : tasks[task]) { if (!visited[staff]) {
visited[staff] = true; // Đánhdấunhânviênđã thăm //
Nếunhânviênchưađượcphâncônghoặccóthểphâncônglại if (staffAssignment[staff] == 0 ||
canAssign(staffAssignment[staff])) { staffAssignment[staff] = task; // Phâncôngnhiệmvụcho nhân viên return true; } } } return false; } int main() { int n, m; cin>> n >>m;
// Đọcnhiệmvụvànhânviêncóthểthựchiện
for (int i = 1; i<= n; ++i) { int k;
cin>> k; // Sốnhânviênchonhiệmvụi tasks[i].resize(k);
for (int j = 0; j < k; ++j) {