Untitled

Answer 1:
 
#include <vector>
int CalLargestBlock(int id_ignore){
	vector<int> arr;
	for(int i = 0; i < N; i++)
	{
		if(id_ignore == ID[i])
	{
		continue;
	}
		arr.push_back(ID[i]);
	}
	int max_block_size = 0;
	int cur_size = 1;
	for (int i = 1; i < arr.size(); i++){
		if (arr[i] == arr[i - 1]) cur_size++;
		else cur_size = 1;
		if (max_block_size < cur_size) {
			max_block_size = cur_size;
		}
	}
	return max_block_size;
}

Answer 2:

for(int i = 0 ; i < N; i++)
	{
		int sum = 0;
		for(int j = 0; j < N; j++)
		{
			sum += Box[i][j];
		}
		rsum.push_back(sum);
		maxi = max(sum, maxi);
	}
	for(int i = 0 ; i < N; i++)
	{
		int sum = 0;
		for(int j = 0; j < N; j++)
		{
			sum += Box[j][i];
		}
		csum.push_back(sum);
		maxi = max(sum, maxi);
	}
	for(int i = 0; i< N; i++)
	{
		int diff = maxi - rsum[i];
		ans += diff;
	}
	
Answer 3:

#include <bits/stdc++.h>
#include <vector>
#include <queue>
#include <climits>
#include <cstring>
using namespace std;

int directions[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
int N, M;
char matrix[100][100];
// Check if a cell is within bounds and not a wall
bool isValid(int x, int y) {
    return x >= 0 && x < N && y >= 0 && y < M && matrix[x][y] != '*';
}
int dp[10][1 << 10];
// BFS to find the shortest distance between two points
int bfs(int startX, int startY, int endX, int endY) {
    vector<vector<int>> dist(N, vector<int>(M, -1));
    queue<pair<int, int>> q;
    q.push({startX, startY});
    dist[startX][startY] = 0;
    while (!q.empty()) {
        auto [x, y] = q.front();
        q.pop();
        for (auto& dir : directions) {
            int newX = x + dir[0], newY = y + dir[1];
            if (isValid(newX, newY) && dist[newX][newY] == -1) {
                dist[newX][newY] = dist[x][y] + 1;
                q.push({newX, newY});
                if (newX == endX && newY == endY) {
                    return dist[newX][newY];
                }
            }
        }
    }
    return -1; 
}
//krdo(dist,0,P-1,setBit);
int krdo(vector<vector<int>> dist, int lastVisited,int n, int setBit){
	if(setBit == (1  << n) - 1){
		return dist[lastVisited][0];
	}
	int ans = INT_MAX;
	for(int i = 0;i<n;i++){
		if(!(setBit & 1<<i)){
			// unset hai 
			ans = min(ans,dist[lastVisited][i] + krdo(dist,i,n,(setBit | 1 << i)));
		}
	}
	return ans;
}
int main() {
    cin >> N >> M;
    pair<int, int> source;
    vector<pair<int, int>> points;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            cin >> matrix[i][j];
            if (matrix[i][j] == 'S') {
                source = {i, j};
            } else if (isdigit(matrix[i][j])) {
                points.push_back({i, j});
            }
        }
    }

    points.insert(points.begin(), source);
    int P = points.size();
    vector<vector<int>> dist(P, vector<int>(P, -1));
    for (int i = 0; i < P; i++) {
        for (int j = 0; j < P; j++) {
					if(i==j){
						dist[i][j] = 0;
						continue;
					}
            if (i != j) {
                dist[i][j] = bfs(points[i].first, points[i].second, points[j].first, points[j].second);
                if (dist[i][j] == -1) {
                    return 0; 
                }
            }
        }
    }
 
	// for(int i = 0 ; i < P;i++){
	// 	for(int j = 0 ; j < P;j++){
	// 		cout << dist[i][j] << " ";
	// 	}
	// 	cout << endl;
	// }
 

    memset(dp, -1, sizeof(dp));
    cout << krdo(dist,0,P,1);
    return 0;
}

Answer 4:

int ComputeTime(void)
{
	int s = ConvertInt(start_time) * 60 + ConvertInt(start_time + 3);
	int e = ConvertInt(end_time) * 60 + ConvertInt(end_time + 3);
	
	if (e < s) e += 1440;

	return (e - s);
}

int Solve(void)
{
	int p;
	int t = ComputeTime();

	if (t < 30) return 500;
	p = 500 + ((int)((t - 30 + 9) / 10)) * 300;

	return min(p, 30000);
}

Answer 5:

#include <iostream>
#include <queue>
#include <vector>
 
using namespace std;
#define MAXN (100)
int N;
char map[MAXN + 10][MAXN + 10];
bool visited[MAXN + 10][MAXN + 10];
 
int dx[4] = {0, 0, 1, -1};
int dy[4] = {1, -1, 0, 0};
 
char ans;//구매자 이름 Buyer's name
int areacnt;//구매자 영역 개수 Number of buyer's area
 
void InputData() {
	cin >> N;
	for (int h = 0; h < N; h++) {
		cin >> map[h];
	}
}
 
bool isValid(int x, int y, char owner) {
    return x >= 0 && x < N && y >= 0 && y < N && map[x][y] == owner && !visited[x][y];
}
 
int bfs(int x, int y, char owner) {
    queue<pair<int, int>> q;
    q.push({x, y});
    visited[x][y] = true;
    int gridCount = 0;
    while (!q.empty()) {
        auto [cx, cy] = q.front();
        q.pop();
        gridCount++;
        for (int d = 0; d < 4; d++) {
            int nx = cx + dx[d];
            int ny = cy + dy[d];
            if (isValid(nx, ny, owner)) {
                visited[nx][ny] = true;
                q.push({nx, ny});
            }
        }
    }
    return gridCount;
}
 
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
 
	InputData();// 입력받는 부분 Input
 
	// 여기서부터 작성 Write from here
	int zonesR = 0, gridsR = 0;
    int zonesG = 0, gridsG = 0;
    int zonesB = 0, gridsB = 0;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            if (!visited[i][j]) {
                char owner = map[i][j];
                int gridCount = bfs(i, j, owner);
                if (owner == 'R') {
                    zonesR++;
                    gridsR += gridCount;
                } else if (owner == 'G') {
                    zonesG++;
                    gridsG += gridCount;
                } else if (owner == 'B') {
                    zonesB++;
                    gridsB += gridCount;
                }
            }
        }
    }
    // Determine the owner with the largest zones, breaking ties as specified
    char ans = 'R';
    int maxZones = zonesR;
    int maxGrids = gridsR;
    if (zonesG > maxZones || (zonesG == maxZones && gridsG > maxGrids)) {
        ans = 'G';
        maxZones = zonesG;
		maxGrids = gridsG;
    }
	if (zonesB > maxZones || (zonesB == maxZones && gridsB > maxGrids)) {
        ans = 'B';
        maxZones = zonesB;
        maxGrids = gridsB;
    }
 
	cout << ans << " " << maxZones << "\n";// 출력하는 부분 Output
	return 0;
}

Answer 6:

#include <bits/stdc++.h>
using namespace std;
int n; 
int arr[100000 + 10];
void InputData(void) {
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> arr[i];
	}
}
int solve() {
	vector<int> left(n, -1);
	stack<int> s;
	// Calculate the previous greater element for each index
	for (int i = 0; i < n; i++) {
			while (!s.empty() && arr[s.top()] <= arr[i]) {
					s.pop();
			}
			if (!s.empty()) {
					left[i] = arr[s.top()];
			}
			s.push(i);
	}
	// Clear the stack for calculating the next greater element
	while (!s.empty()) s.pop();
	// Stack for calculating the next greater element
	vector<int> right(n, -1);
	for (int i = n - 1; i >= 0; i--) {
			while (!s.empty() && arr[s.top()] <= arr[i]) {
					s.pop();
			}
			if (!s.empty()) {
					right[i] = arr[s.top()];
			}
			s.push(i);
	}
	// Count the valid pairs
	set<pair<int, pair<int ,int>>> st;
	for (int i = 0; i < n; i++) {
			// if it's valid
			if(arr[i]<left[i] && arr[i]<right[i]) st.insert({arr[i], {left[i], right[i]}});
	}
	return st.size()+n-1;
}
int main(void) {
	int ans = -1;
	InputData();
	ans = solve();
	cout << ans << endl;
	return 0;
}

Answer 7:

int dr[8] = { -1, 1, 0, 0, 1, 1, -1, -1 };
int dc[8] = { 0, 0, -1, 1, 1, -1, -1, 1 };

void Touch(int r, int c) {
	int V;

	if (A[r][c] == 0) V = 1;
	else V = 0;
	A[r][c] = V;

	for (int k = 0; k < 8; k++) {
		int nr = r;
		int nc = c;
		int flag = 0, bomb = 0;

		for (;;) {
			nr = nr + dr[k];
			nc = nc + dc[k];
			if (nr < 0 || nr >= H || nc < 0 || nc >= W) break;
			if (A[nr][nc] == 2) {
				bomb = 1;
			}
			if (A[nr][nc] == V) {
				flag = 1;
				break;
			}
		}
		if (flag == 1 && bomb == 0) {
			nr = r;
			nc = c;
			for (;;) {
				nr = nr + dr[k];
				nc = nc + dc[k];
				if (A[nr][nc] == V) {
					break;
				}
				A[nr][nc] = V;
			}
		}
		if (flag == 1 && bomb == 1) {
			nr = r;
			nc = c;
			for (;;) {
				nr = nr + dr[k];
				nc = nc + dc[k];
				if (nr < 0 || nr >= H || nc < 0 || nc >= W) break;
				A[nr][nc] = V;
			}
		}
	}
}

Answer 8:

#include <bits/stdc++.h>
using namespace std;

int N;//선수의 인원수 number of playersnumber of players
long long T;//시간 time
long long P[100000 + 10];//선수 초기 위치 player initial position
long long S[100000 + 10];//선수 속도 player speed
int group_first[100000 + 10];//각 그룹의 선두선수 leader of each group


void InputData() {
	cin >> N >> T;
	for (int i = 0; i < N; i++) {
		cin >> P[i] >> S[i];
	}
}

int main() {
	int ans = -1;
	InputData();//입력 Input

	//코드를 작성하세요 Write the code
	vector <long long> temp(N);
	for (int i = 0; i < N; i++){
		temp[i] = P[i];
	}
	for (int i = N - 1; i >= 0; i--){
		if (i == N - 1) temp[i] = temp[i] + S[i] * T;
		else {
			long long x = temp[i] + S[i] * T;
			if (x >= temp[i + 1]) {
				temp[i] = temp[i + 1];
			}
			else {
				temp[i] = x;
			}
		}
	}
 
	long long x = 1, count = 1;
	group_first[0] = N;
	for(int i = N-1; i > 0; i--){
		if(temp[i] != temp[i - 1]){
			count++;
			group_first[x++] = i;
		}
	}
	ans = count;

	//출력 Output
	cout << ans << endl;
	for (int i = 0; i < ans; i++) cout << group_first[i] << " ";
	return 0;
}

Answer 9:

#include <iostream>
#include <vector>
#include <cmath>
#include <climits>
#include <algorithm>
 
using namespace std;
 
const int MAX_N = 8;
 
struct POS {
    int x, y;
};
 
int N;
POS base[2];
vector<POS> pos(MAX_N);
long long min_fuel = LLONG_MAX;
 
int dist(const POS& a, const POS& b) {
    return abs(a.x - b.x) + abs(a.y - b.y);
}
 
void solve(vector<bool>& visited, int visited_count, int last1, int count1, int last2, int count2, long long current_fuel) {
    if (visited_count == N) { // All parcels collected
        current_fuel += dist(last1 == -1 ? base[0] : pos[last1], base[0]) * (1 + count1); // Return truck 1
        current_fuel += dist(last2 == -1 ? base[1] : pos[last2], base[1]) * (1 + count2); // Return truck 2
 
        min_fuel = min(min_fuel, current_fuel);
        return;
    }
 
    for (int next_parcel = 0; next_parcel < N; ++next_parcel) {
        if (!visited[next_parcel]) { // If the parcel has not been visited
            visited[next_parcel] = true;
 
            // Assign to truck 1
            long long new_fuel1 = current_fuel + dist(last1 == -1 ? base[0] : pos[last1], pos[next_parcel]) * (1 + count1);
            solve(visited, visited_count + 1, next_parcel, count1 + 1, last2, count2, new_fuel1);
 
            // Assign to truck 2
            long long new_fuel2 = current_fuel + dist(last2 == -1 ? base[1] : pos[last2], pos[next_parcel]) * (1 + count2);
            solve(visited, visited_count + 1, last1, count1, next_parcel, count2 + 1, new_fuel2);
 
            visited[next_parcel] = false; // Backtrack
        }
    }
}
 
void Input_Data() {
    cin >> N;
    for (int i = 0; i < 2; ++i) {
        cin >> base[i].x >> base[i].y;
    }
    for (int i = 0; i < N; ++i) {
        cin >> pos[i].x >> pos[i].y;
    }
}
 
int main() {
    Input_Data();
 
    // Initialize visited vector
    vector<bool> visited(N, false);
 
    // Start with no parcels assigned to either truck
    solve(visited, 0, -1, 0, -1, 0, 0);
 
    cout << min_fuel << endl;
 
    return 0;
}

Answer 10: 

int di1[8] = { -1,-1,0,1,1,1,0,-1 };
int dj1[8] = { 0,1,1,1,0,-1,-1,-1 };
int di2[8] = { 1,1,0,-1,-1,-1,0,1 };
int dj2[8] = { 0,-1,-1,-1,0,1,1,1 };

int Solve(void) {
	int count = 0;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			if (a[i][j] == X2) {
				for (int k = 0; k < 8; k++) {
					int ni1 = i + di1[k];
					int nj1 = j + dj1[k];
					int ni2 = i + di2[k];
					int nj2 = j + dj2[k];
					if ((ni1 < 0 || ni1 >= N) || (nj1 < 0 || nj1 >= N) || (ni2 < 0 || ni2 >= N) || (nj2 < 0 || nj2 >= N)) continue;
					if ((a[ni1][nj1] == X1 && a[ni2][nj2] == X3) || (a[ni1][nj1] == X3 && a[ni2][nj2] == X1)) {
						count++;
					}
				}
			}
		}
	}
	return count / 2;
}

Answer 11:

#include <iostream>
#include <bits/stdc++.h>
using namespace std;

int S, E1, E2;
int ans1, ans2;

// Function to input data
void InputData()
{
    cin >> S >> E1 >> E2;
}

// Function to precompute the number of factors for each number from 1 to 9999
void countFactors(vector<int>& factorCounts)
{
    for (int i = 1; i < 10000; ++i) {
        for (int j = i; j < 10000; j += i) {
            factorCounts[j]++;
        }
    }
}

// Function to find the minimum number of moves from start to end
int FindMoves(int start, int end, const vector<int>& factorCounts)
{
    queue<pair<int, int>> q;
    vector<bool> visited(10000, false);
    q.push({start, 0});
    visited[start] = true;

    while (!q.empty()) {
        int current = q.front().first;
        int moves = q.front().second;
        q.pop();
        if (current == end) {
            return moves;
        }
        string currentStr = to_string(current);
        for (int i = 0; i < 4; ++i) {
            for (char d = '0'; d <= '9'; ++d) {
                if (currentStr[i] == d) continue;
                string nextStr = currentStr;
                nextStr[i] = d;
                int next = stoi(nextStr);
                if (next >= 1000 && next <= 9999 && !visited[next] && abs(factorCounts[current] - factorCounts[next]) <= 1) {
                    visited[next] = true;
                    q.push({next, moves + 1});
                }
            }
        }
    }
    return -1;  // If no path is found
}

int main()
{
    InputData();  // Input the start and end numbers

    vector<int> factorCounts(10000, 0);
    countFactors(factorCounts);  // Precompute factor counts for numbers 1 to 9999

    // Find the minimum moves for both E1 and E2 from S
    cout << FindMoves(S, E1, factorCounts) << '\n';
    cout << FindMoves(S, E2, factorCounts) << '\n';

    return 0;
}

Answer 12:

#include <iostream>
#include <algorithm>
using namespace std;
int N; // Number of foreign matters
int K; // Maximum number of uses of the equipment
int X[50000]; // Positions of foreign matters
void InputData() {
   cin >> N >> K;
   for (int i = 0; i < N; i++) {
       cin >> X[i];
   }
}
bool isValid(int V) {
   int count = 0;
   int lastCovered = -1;
   for (int i = 0; i < N; i++) {
       if (X[i] > lastCovered) {
           count++;
           lastCovered = X[i] + 2 * V;
           if (count > K) return false;
       }
   }
   return true;
}
int main() {
   InputData(); // Input data
   sort(X, X + N);
   int left = 0, right = (X[N - 1] - X[0] + 1) / 2;
   while (left <= right) {
       int mid = (left + right) / 2;
       if (isValid(mid)) {
           right = mid - 1;
       } else {
           left = mid + 1;
       }
   }
   cout << left << endl;
   return 0;
}

Answer 13:
 
#define ValR  R / 2
#define ValC  C / 2
#define SWAP(a, b) {int temp = a;a = b;b = temp;}
void Rotate(int sr, int sc, int er, int ec) {
	int a = Mat[sr][sc];
	if(ValR <= sr || ValC <= sc){
		return;
	}
	for (int r = sr + 1; r <= er; r++) {
		SWAP(Mat[r][sc], a);
	}
	for (int c = sc + 1; c <= ec; c++) {  
		SWAP(Mat[er][c], a);
	}
	for (int r = er - 1; r >= sr; r--) {  
		SWAP(Mat[r][ec], a);
	}
		for (int c = ec - 1; c >= sc; c--) {
		SWAP(Mat[sr][c], a);
	}
}

Answer 14:

#include <iostream>
#include <vector>
#include <queue>
#include <map>
#include <string>
 
using namespace std;
 
const int MAX_LEN = 2003;
const long long INF = 1e18;
 
long long N, result = 0;
string moves;
map<pair<int, int>, vector<pair<int, int>>> graph;  
map<vector<int>, int> pathCount;  /
vector<vector<long long>> distances(MAX_LEN, vector<long long>(MAX_LEN, INF));
 
int dx[4] = {0, 0, 1, -1};  
int dy[4] = {1, -1, 0, 0};
 
void bfs(int startX, int startY) {
    distances[startX][startY] = 0;
    queue<pair<int, int>> q;
    q.push({startX, startY});
 
    while (!q.empty()) {
        int curX = q.front().first;
        int curY = q.front().second;
        q.pop();
 
        for (auto neighbor : graph[{curX, curY}]) {
            int newX = neighbor.first;
            int newY = neighbor.second;
 
            if (distances[newX][newY] < distances[curX][curY] + 1) continue;
            if (distances[newX][newY] == distances[curX][curY] + 1) {
                result += 1;
                continue;
            }
 
            distances[newX][newY] = distances[curX][curY] + 1;
            q.push({newX, newY});
        }
    }
}
 
void createPaths(int startX, int startY) {
    int curX = startX, curY = startY, newX, newY;
    for (char move : moves) {
        int direction = move - '0';  
 
        newX = curX + dx[direction];
        newY = curY + dy[direction];
 
        if (pathCount.count({curX, curY, newX, newY}) == 0) {
            pathCount[{curX, curY, newX, newY}]++;
            graph[{curX, curY}].push_back({newX, newY});
        }
 
        if (pathCount.count({newX, newY, curX, curY}) == 0) {
            pathCount[{newX, newY, curX, curY}]++;
            graph[{newX, newY}].push_back({curX, curY});
        }
 
        curX = newX;
        curY = newY;
    }
}
 
void solve() {
    cin >> N;  
    cin >> moves;  
 
    int startX = MAX_LEN / 2, startY = MAX_LEN / 2;  
 
    createPaths(startX, startY);  
    bfs(startX, startY);
 
    cout << result << endl;  
}
 
int main() {
    ios::sync_with_stdio(false);  
    cin.tie(nullptr);
 
    solve();  
    return 0;
}

Answer 15:

int calculate_count(map<int, int>& mp, int id)
{
	int count = mp[id];
	if (mp.find(id - 1) != mp.end())
	{
		count += mp[id - 1];
	}
	if (mp.find(id + 1) != mp.end())
	{
		count += mp[id + 1];
	}
	return count;
}
 
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
 
	int ans = 0;
	InputData();//입력
 
	//코드를 작성하세요
	map<int, int> mp;
	int maxi = 0;
	for (int i = 0; i < M; i++) {
		mp[ID[i]]++;
	}
	for (auto it : mp)
	{
		maxi = max(maxi, calculate_count(mp, it.first));
	}
	int x = 0;
	for (int i = M; i < N; i++)
	{
		mp[ID[x]]--;
		if (mp[ID[x]] == 0) 
		{
			mp.erase(ID[x]);
		}
		x++;
		mp[ID[i]]++;
		for (auto it : mp) 
		{
			maxi = max(maxi, calculate_count(mp, it.first));
		}
	}
	ans = maxi;
 
	cout << ans << "\n";//출력
	return 0;
}