Untitled
unknown
plain_text
2 months ago
19 kB
7
Indexable
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;
}Editor is loading...
Leave a Comment