Algorithm course

struct Node {
    int from, to, cost;
    
    // interesting way of making a constrctor;
    // This is faster than the latter one, so stick with this.
    Node(int from, int to, int cost):
    from(from), to(to), cost(cost){}
    
    // usually it goes like;
    Node(int _from, int _to, int _cost){
    	from = _from;
        to = _to;
        cost = _cost;
    }
    
    // when you need 'std::sort' function, 
    // this helps without making another compare function.
    // const before '{' means that member variable wouldn't be changed.
    bool operator<(const Node& a)const{
        return a.cost < cost;
    }
}

struct Node{
    int a,b,c;
    Node(int _a, int _b, int _c):a(_a),b(_b),c(_c){}
    
    // overriding comparator
    bool operator<(const Node& t) const {
        return /*my*/a > x.a;
    }
}

// Segment tree example:
// every node has to have its coverage, but in this example, parameter shows the coverage.


/*
	1. update
	
	index : 트리 노드 인덱스(tree 기준 != array 기준)
	left, right : 노드가 커버하는 범위
	targer : 변경하고자 하는 인덱스(array 기준)
	value : 변경하고자 하는 값
*/
void update(int index, int left, int right, int target, int value) {
	// 이 두개는 end condition

	// 범위를 벗어났다면 끝
	if (target < left || right < target) {
		return;
	}
	// 도착
	if (left == right) { 
		tree[index] = value; 
		return;
	}

	// 범위 안에 들어가는 경우, left, right로 보내본다.
	// coverage : left ~ (left+right)/2
	update(index * 2, left, (left + right) / 2, target, value);		
	// coverage : (left+right)/2 + 1 ~ right
	update(index * 2 + 1, (left + right) / 2 + 1, right, target, value);	
	
	// 보내본 것이 다 끝나면 왼쪽, 오른쪽 값이 update가 되었을 것.
	// 자식들의 노드 값을 가지고 자기 값을 변경한다.
	tree[index] = tree[index * 2] + tree[index * 2 + 1];
}
// 이게 펜윅트리와 더 비슷하다
/*
void update(vector<long long> &tree, int node, int start, int end, int index, long long diff) {
	if (index < start || index > end) return;
	tree[node] = tree[node] + diff;
	if (start != end) {
		update(tree,node*2, start, (start+end)/2, index, diff);
		update(tree,node*2+1, (start+end)/2+1, end, index, diff);
	}
}
*/



/*
	2. query
	
	index : 트리 노드 인덱스(tree 기준 != array 기준)
	left, right : 노드가 커버하는 범위
	query_left, query_right : 더셈을 구하고자 하는 구간
*/
//query_left, query_right 가 구해야하는 범위
int query(int index, int left, int right, int query_left, int query_right) {
	//범위를 완전히 벗어났을 때
	if (left > query_right || right < query_left) return 0;
	//범위에 들어갔을 때
	if (query_left <= left && right <= query_right) return tree[index];

	//범위에 들어왔을때
	return (query(index * 2, left, (left + right) / 2, query_left, query_right) +
		query(index * 2 + 1, (left + right) / 2 + 1, right, query_left, query_right));
}


/*
	3. init
	
*/
void init(int index, int left, int right) {
	if (left == right) {
		//hard to understand, so I recommend you to drawing a tree and try it
		tree[index] = data[left];
		return;
	}
	init(index * 2, left, (left + right) / 2);
	init(index * 2 + 1, (left + right) / 2 + 1, right);
	tree[index] = tree[index * 2] + tree[index * 2 + 1];
	return;
}

#include <iostream>
#include <vector>
#include <stack>

using namespace std;

int N, T;
stack<pair<int, int>> s;
vector<int> ans;

int main() {
    scanf("%d", &N);

    ans.resize(N);
    for (int i = 1; i <= N; i++) {
        int temp;
        scanf("%d", &temp);

        while (!s.empty() && s.top().first <= temp) s.pop();
        if (!s.empty()) ans[i-1] = s.top().second;
        s.push(pair<int, int>(temp, i));
    }

    for(auto item : ans){
        printf("%d ", item);
    }

	return 0;
}

// [연습A-0022] 소수경로 

#include <queue>
#include <algorithm>
#include <iostream>
#include <math.h>
#include <string.h>

using namespace std;

struct MyStruct
{
	int startN, cnt;
	MyStruct(int _start, int _cnt) :startN(_start), cnt(_cnt) {}
};

int T, startN, endN;
bool prime[10000] = { true, };
bool visited[10000];
int ans, offset[] = { 1, 10 ,100, 1000 };
queue<MyStruct> q;

bool bfsFn(const MyStruct& tempS) {
	for (int i = 0; i < 4; i++) {
		// pow 대신에 offset으로 하는게 좋다.
		// 까먹지 말것 1
		int base = tempS.startN - tempS.startN/offset[i]%10*offset[i];
		for (int j = 0; j < 10; j++) {
			int temp = base + j * offset[i];
			if (temp == endN) {
				ans = tempS.cnt;
				return true;
			}
			else if (!visited[temp] && prime[temp]) {
				q.push(MyStruct(temp, tempS.cnt+1));
				visited[temp];
			}
		}
	}
	return false;
}

int main() {
	scanf("%d", &T);

	for(int i = 0; i < 10000; i++){
		prime[i] = true;
	}

	for (int i = 2; i < 10000; i++) {
		if (prime[i]) {
			for (int j = i * 2; j < 10000; j += i) {
				prime[j] = false;
			}
		}
	}
	//1000 미만은 범위에서 벗어나니까 나중에 queue에 넣지 않도록
	// 까먹지 말것 2
	for (int i = 0; i < 1000; i++) {
		prime[i] = false;
	}

	memset(visited, 0, sizeof(visited));
	for (int loop = 1; loop <= T; loop++) {
		scanf("%d%d", &startN, &endN);
		
		ans = 0;
		visited[startN] = true;
		
		q.push(MyStruct(startN, 1));
		while (!q.empty()) {
			MyStruct tempS = q.front();
			q.pop();
			if (bfsFn(tempS)) {
				queue<MyStruct>().swap(q);
			}
		}

		printf("#%d %d\n", loop, startN == endN? 0:ans);
	}

	return 0;
}

//[교육A-0004] 금괴 

#include <queue>
#include <iostream>

using namespace std;

int T, N, M, ans;

int gcd(int a, int b) {
	if (b == 0) return a;
	else return gcd(b, a%b);
}

int main() {
	scanf("%d", &T);

	for (int loop = 1; loop <= T; loop++) {
		scanf("%d%d", &N, &M);

		int dividor = gcd(N%M, M);
		// 금괴를 이러붙여 1개라고 생각하면 됩.
		// 서로 서로소일 때, 자르는 갯수는 사람수-1이다.
		// 여기서 * gcd 값을 하면 된다.
		ans = (M / dividor - 1) * dividor;

		printf("#%d %d\n", loop, ans);
	}

	return 0;
}

#include <iostream>

using namespace std;

//This will be overflowed
long long pas[100][100];

int main()
{
    for(int i = 1; i < 100; i++){
        //제일 처음과 마지막 값은 넣어주기.
        pas[i][0] = pas[i][i] = 1;
        for(int j = 1; j < i; j++){
            pas[i][j] = pas[i-1][j-1] + pas[i-1][j];
        }
    }
    
    for(int i = 0; i < 100; i++){
        pas[i][0] = pas[i][i] = 1;
        for(int j = 0; j <= i; j++){
            printf("%lld ", pas[i][j]);
        }
        printf("\n");
    }
    
    return 0;
}

// for example
int upDownRightLeft[] = { {-1,0}, {1,0}, {0,1}, {-1,0} };

for(int i = 0; i < 4; i++){
    int x += upDownRightLeft[0];
    int y += upDownRightLeft[1];
    if(!visited[x][y] && x >= 0 && x < size && y >= 0 && y < size){
        doDfsOrBfs(arr[x][y]);
    }
}