Cloud Service Billing Calculation

Develop a program to calculate customer bills for a cloud service based on usage logs and pricing factors. The input consists of billing logs and a list of billing factors with thier unit prices. Each billing log entry contains timestamp, customer ID, billing factor, and usage duration. If multiple log entries exist for the same customer and billing factor with the same timestamp, only the first entry should be billed. Calculate the total bill amount for each customer.

Requirements

• Time Limit: C/C++ 1000ms, Other Languages 2000ms
• Memory Limit: C/C++ 256MB, Other Languages 512MB

Input

• First line: Number of billing logs n (1 ≤ n ≤ 1000)
• Next n lines: Billing logs with 4 comma-separated fields:
  • Timestamp (10-digit numeric string)
  • Customer ID (string, length 1-16)
  • Billing factor (string, length 1-16, default price 0 if not found)
  • Usage duration (integer 0-100, treat as 0 if out of range)
• Next line: Number of billing factors m (1 ≤ m ≤ 100)
• Next m lines: Billing factor pricing with 2 comma-separated fields:
  • Billing factor (string, length 1-16)
  • Unit price (integer 1-100)

Output

Total bill amount for each customer, formatted as customer ID and total amount separated by comma. Results should be sorted in ascending alphabetical order by customer ID.

Example

Input:
5
1627845600,client1,factorA,10
1627845605,client2,factorB,15
1627845610,client1,factorA,5
1627845610,client1,factorB,8
1627845620,client2,factorB,20
2
factorA,5
factorB,7

Output:
client1,131
client2,245

Solution Approach

1. Parse input billing logs and store in a data structure
2. Use a set to identify duplicate entries (same timestamp, customer ID, and billing factor)
3. Store unique entries in a map with customer ID and biling factor as key
4. Parse billing factor pricing into a hash map for quick lookup
5. Calculate total bills for each customer using the pricing information
6. Output results sorted by customer ID

Implementation

#include<iostream>
#include<unordered_map>
#include<string>
#include<vector>
#include<map>
#include<unordered_set>
#include<algorithm>

using namespace std;

int main() {
    int logCount, factorCount;
    cin >> logCount;
    
    vector<string> logFields(4), factorFields(2); 
    unordered_map<string, int> pricingMap; 
    unordered_set<string> uniqueEntries; 
    map<pair<string, string>, int> usageMap; 
    map<string, int> customerBills; 
    
    string inputLine;
    
    // Process billing logs
    for (int i = 0; i < logCount; ++i) {
        cin >> inputLine;
        size_t pos = 0;
        int fieldIndex = 0;
        
        // Parse comma-separated fields
        while (pos < inputLine.size() && fieldIndex < 4) {
            size_t nextPos = inputLine.find(',', pos);
            if (nextPos == string::npos) nextPos = inputLine.size();
            
            logFields[fieldIndex++] = inputLine.substr(pos, nextPos - pos);
            pos = nextPos + 1;
        }
        
        string timestamp = logFields[0];
        string customerId = logFields[1];
        string factor = logFields[2];
        string durationStr = logFields[3];
        
        // Check for duplicates
        string uniqueKey = timestamp + customerId + factor;
        if (uniqueEntries.count(uniqueKey)) {
            continue; // Skip duplicate entries
        }
        uniqueEntries.insert(uniqueKey);
        
        // Convert duration to integer and validate
        int duration = 0;
        for (char c : durationStr) {
            duration = duration * 10 + (c - '0');
        }
        
        if (duration < 0 || duration > 100) {
            continue; // Skip invalid durations
        }
        
        // Aggregate usage by customer and factor
        pair<string, string> customerFactor = make_pair(customerId, factor);
        usageMap[customerFactor] += duration;
    }
    
    // Process pricing factors
    cin >> factorCount;
    for (int i = 0; i < factorCount; ++i) {
        cin >> inputLine;
        size_t pos = inputLine.find(',');
        string factor = inputLine.substr(0, pos);
        string priceStr = inputLine.substr(pos + 1);
        
        int price = 0;
        for (char c : priceStr) {
            price = price * 10 + (c - '0');
        }
        
        pricingMap[factor] = price;
    }
    
    // Calculate total bills for each customer
    for (const auto& entry : usageMap) {
        string customerId = entry.first.first;
        string factor = entry.first.second;
        int duration = entry.second;
        
        int unitPrice = pricingMap.count(factor) ? pricingMap[factor] : 0;
        int cost = unitPrice * duration;
        
        customerBills[customerId] += cost;
    }
    
    // Output results sorted by customer ID
    for (const auto& customer : customerBills) {
        cout << customer.first << "," << customer.second << endl;
    }
    
    return 0;
}

Similar Image Classification

Implement a system to classify similar images into groups based on their similarity matrix. Images are considered similar if their similarity value is greater than 0. If image A is similar to B and B is similar to C, but A is not similar to C, then A and C are considered indirectly similar and can be grouped together. Images with no similarities form their own groups with similarity sum of 0. Return the similarity sums for each group in descending order.

Requirements

• Time Limit: C/C++ 1000ms, Other Languages 2000ms
• Memory Limit: C/C++ 256MB, Other Languages 512MB

Input

• First line: Number of images N (0 < N <= 900)
• Next N lines: N×N similarity matrix where M[i][j] represents similarity between image i and j
  • M[i][i] = 0
  • M[i][j] = M[j][i]
  • 0 ≤ M[i][j] ≤ 100

Output

Similarity sums for each group in descending order, separated by spaces.

Example

Input:
5
0 0 50 0 0
0 0 0 25 0
50 0 0 0 15
0 25 0 0 0
0 0 15 0 0

Output:
65 25

Solution Approach

1. Use Union-Find (Disjoint Set Union) data structure to group similar images
2. For each pair of images with similarity > 0, union them and accumulate their similarity scores
3. Track the total similarity score for each group in the root node
4. Collect scores from root nodes and sort them in descending order

Implementation

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <sstream>

using namespace std;

vector<int> parent;
vector<int> groupScore;

// Find the root of the set containing element u
int findSet(int u) {
    if (parent[u] == u) return u;
    return parent[u] = findSet(parent[u]);
}

// Union two sets and update their combined score
void unionSets(int u, int v, int similarity) {
    int rootU = findSet(u);
    int rootV = findSet(v);
    
    if (rootU != rootV) {
        parent[rootV] = rootU;
        groupScore[rootU] += similarity + groupScore[rootV];
        groupScore[rootV] = 0;
    }
}

int main() {
    int n;
    cin >> n;
    
    // Initialize parent and score vectors
    parent.resize(n);
    groupScore.resize(n, 0);
    
    for (int i = 0; i < n; ++i) {
        parent[i] = i;
    }
    
    // Read similarity matrix
    vector<vector<int>> similarityMatrix(n, vector<int>(n, 0));
    for (int i = 0; i < n; ++i) {
        string line;
        getline(cin, line);
        getline(cin, line); // Skip empty line if needed
        
        istringstream iss(line);
        for (int j = 0; j < n; ++j) {
            iss >> similarityMatrix[i][j];
        }
    }
    
    // Process similarity matrix
    for (int i = 0; i < n; ++i) {
        for (int j = i + 1; j < n; ++j) {
            if (similarityMatrix[i][j] > 0) {
                unionSets(i, j, similarityMatrix[i][j]);
            }
        }
    }
    
    // Collect group scores
    vector<int> result;
    for (int i = 0; i < n; ++i) {
        if (parent[i] == i && groupScore[i] > 0) {
            result.push_back(groupScore[i]);
        }
    }
    
    // Sort in descending order
    sort(result.begin(), result.end(), greater<int>());
    
    // Output results
    for (size_t i = 0; i < result.size(); ++i) {
        if (i != 0) cout << " ";
        cout << result[i];
    }
    cout << endl;
    
    return 0;
}

Network Defense Strategy

In a cloud network with N nodes represented by an N×N matrix, where matrix[i][j] = p indicates that accessing node j from node i requires permission level ≥ p. When a node is succesfully accessed, the permission level is adjusted to p. Some nodes are exposed to the public internet and are under attack. Attackers gain ROOT permissions (level 10) when accessing exposed nodes. The attack can propagate through the network. To minimize damage, one exposed node should be taken offline. Determine which exposed node, when taken offline, results in the fewest nodes being compromised during the attack.

Requirements

• Time Limit: C/C++ 5000ms, Other Languages 10000ms
• Memory Limit: C/C++ 128MB, Other Languages 256MB

Input

• First line: Number of network nodes N (2 ≤ N ≤ 24)
• Next N lines: N×N permission matrix where matrix[i][j] = p
  • 0 ≤ p ≤ 10
  • matrix[i][i] = 0
• Last line: List of exposed node IDs (no duplicates)

Output

The ID of the exposed node that, when taken offline, minimizes the number of compromised nodes. If multiple nodes yield the same result, return the smallest ID.

Example

Input:
4
1 0 0 0
0 1 2 0
0 1 1 4
0 0 3 1
1 3

Output:
3

Solution Approach

1. For each exposed node, simulate the attack propagation
2. Use DFS to explore all nodes that can be reached from the exposed node with sufficient permissions
3. Count the total number of compromised nodes for each scenario
4. Select the node whose removal results in the smallest attack footprint

Implementation

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <sstream>
#include <unordered_set>

using namespace std;

vector<vector<int>> network;
vector<int> exposedNodes;
int nodeCount;

// DFS to count compromised nodes from a starting node
int countCompromised(int start, vector<bool>& offlineNodes) {
    vector<bool> visited(nodeCount, false);
    vector<int> permissions(nodeCount, 0);
    int compromised = 0;
    
    // Use a stack for DFS
    vector<pair<int, int>> stack;
    stack.push_back({start, 10}); // Start with ROOT permissions
    
    while (!stack.empty()) {
        int current = stack.back().first;
        int currentPerm = stack.back().second;
        stack.pop_back();
        
        if (visited[current] || offlineNodes[current]) continue;
        
        visited[current] = true;
        compromised++;
        permissions[current] = currentPerm;
        
        // Explore all reachable nodes
        for (int neighbor = 0; neighbor < nodeCount; ++neighbor) {
            if (neighbor != current && network[current][neighbor] != 0) {
                int requiredPerm = network[current][neighbor];
                if (currentPerm >= requiredPerm) {
                    int newPerm = network[current][neighbor]; // Permission resets at new node
                    stack.push_back({neighbor, newPerm});
                }
            }
        }
    }
    
    return compromised;
}

int main() {
    // Read network size
    cin >> nodeCount;
    
    // Read network matrix
    network.resize(nodeCount, vector<int>(nodeCount, 0));
    for (int i = 0; i < nodeCount; ++i) {
        string line;
        getline(cin, line);
        getline(cin, line); // Skip empty line if needed
        
        istringstream iss(line);
        for (int j = 0; j < nodeCount; ++j) {
            iss >> network[i][j];
        }
    }
    
    // Read exposed nodes
    string exposedLine;
    getline(cin, exposedLine);
    istringstream iss(exposedLine);
    int nodeId;
    while (iss >> nodeId) {
        exposedNodes.push_back(nodeId);
    }
    
    int minCompromised = nodeCount; // Initialize with maximum possible
    int bestNode = -1;
    
    // Try taking each exposed node offline
    for (int node : exposedNodes) {
        vector<bool> offlineNodes(nodeCount, false);
        offlineNodes[node] = true;
        
        int totalCompromised = 0;
        
        // Simulate attack from all other exposed nodes
        for (int exposed : exposedNodes) {
            if (exposed != node) {
                totalCompromised += countCompromised(exposed, offlineNodes);
            }
        }
        
        // Update best node if this one minimizes compromised nodes
        if (totalCompromised < minCompromised) {
            minCompromised = totalCompromised;
            bestNode = node;
        }
        // If same number of compromised nodes, choose smaller ID
        else if (totalCompromised == minCompromised && node < bestNode) {
            bestNode = node;
        }
    }
    
    cout << bestNode << endl;
    return 0;
}