9월 개인과제(최승주)

10244.cpp

#include <stdio.h>

int gcd(int a, int b){
   
    int m = 1;

    while(m){
        m = a % b;
        a = b;
        b = m;
    }

    return a;
    
}

bool chk[100003][103];
int g[103][103];

int e[100003];

int main(){

    for(int i=1; i<=100; i++){
        for(int j=1; j<=100; j++){
            g[i][j] = gcd(i, j);
        }
    }

    int n;

    while(scanf("%d", &n) == 1 && n){

        for(int i=1; i<=n; i++){
            scanf("%d", &e[i]);
            for(int j=1; j<=100; j++){
                chk[i][j] = false;
            }

        }

        bool ans[103] = {0};

        for(int i=1; i<=n; i++){

            if(chk[i][e[i]])continue;

            chk[i][e[i]] = true;
            ans[e[i]] = true;

            int j = i, c = e[i];

            while(j < n){
                
                int nc = g[c][e[j+1]];

                if(chk[j+1][nc])break;

                chk[j+1][nc] = true;
                ans[nc] = true;

                j++;
                c = nc;

            }
        
        }
        
        int c = 0;
        for(int i=1; i<=100; i++)if(ans[i])c++;

        printf("%d\n", c);

    }

}

10361.cpp

#include <stdio.h>

#define ll long long

#define mod 1000000007LL

int n, k;

ll dp[1003][1003];

ll dy(int o, int p){

	if(p == 0)return o == 0;

	ll &ret = dp[o][p];

	if(ret != -1)return ret;

	ret = 0;

	if(o)ret = (dy(o-1, p-1) * o) % mod;

	if(o+1 <= p-1)ret += (dy(o+1, p-1) * (n-o)) % mod;

	return ret %= mod;

}

int main(){

	int t;
	scanf("%d", &t);

	int tc = 0;

	while(t--){

		scanf("%d %d", &n, &k);

		int c = 0;

		for(int i=1; i<=n; i++){
			int x;
			scanf("%d", &x);
			if(x)c++;
		}

		printf("Case #%d: ", ++tc);

		if(k < c || (k-c)&1)printf("0\n");
		else{
			for(int i=0; i<=k; i++)for(int j=0; j<=k; j++)dp[i][j] = -1;
			printf("%lld\n", dy(c, k));
		}

	}
}

1135.cpp

#include <stdio.h>
 
#include <vector>
 
#include <algorithm>
 
using namespace std;
 
vector < vector <int> > lnk;
vector < int > dp;
 
int dy(int c){
 
    if(dp[c] != -1)return dp[c];
 
    dp[c] = 0;
 
    vector <int> p;
 
    for(int i=0; i<lnk[c].size(); i++)p.push_back(1 + dy(lnk[c][i]));
 
    sort(p.begin(), p.end());
 
    if(!p.empty()){
        int a = 0;
        for(int j=p.size()-1; j>=0; j--){
            dp[c] = max(dp[c], p[j] + a);
            a++;
        }
    }
 
    return dp[c];
 
}
 
int main(){
 
    int n;
    scanf("%d", &n);
 
    lnk.resize(n);
    dp.resize(n);
 
    for(int i=0; i<n; i++){
 
        int p;
        scanf("%d", &p);
 
        dp[i] = -1;
 
        if(p == -1)continue;
 
        lnk[p].push_back(i);
 
    }
 
    printf("%d\n", dy(0));
 
}

11583.cpp

#include <stdio.h>

#include <limits.h>

#include <algorithm>

using namespace std;

int n, k;

int fac[2][100003];

int dp[2][100003];

int main(){

	int t;
	scanf("%d", &t);

	while(t--){

		scanf("%d %d", &n, &k);

		for(int i=1; i<=n; i++){

			int v;
			scanf("%d", &v);

			fac[0][i] = fac[1][i] = 0;

			while(!(v&1)){
				v >>= 1;
				fac[0][i]++;
			}

			while(!(v%5)){
				v /= 5;
				fac[1][i]++;
			}

		}

		dp[0][1] = fac[0][1], dp[1][1] = fac[1][1];

		for(int i=2; i<=n; i++){

			dp[0][i] = dp[1][i] = INT_MAX;

			for(int j=i-1; j>=i-k && j>=1; j--){

				dp[0][i] = min(dp[0][i], dp[0][j] + fac[0][i]);
				dp[1][i] = min(dp[1][i], dp[1][j] + fac[1][i]);

			}

		}

		printf("%d\n", min(dp[0][n], dp[1][n]));

	}

}

11629.cpp

#include <cstdio>

#include <algorithm>

using namespace std;

const int cmod = 5318008;

int dp[5003][2];

int dy(int n, int s, int a, int b){

    for(int i=1; i<=n; i++)dp[i][0] = dp[i][1] = 0;

    dp[a][0] = 1;

    for(int i=1; i<=s; i++){

        int c = i&1;
        int p = 1^c;

        for(int j=1; j<=n; j++){

            dp[j][c] = dp[j][p];

            if(j > 1)dp[j][c] += dp[j-1][p];
            if(j < n)dp[j][c] += dp[j+1][p];

            dp[j][c] %= cmod;

        }
        
    }

    return dp[b][s&1];

}

int main(){

    int t;
    scanf("%d", &t);

    while(t--){

        int n;
        scanf("%d", &n);
        
        int x1, y1, x2, y2;
        scanf("%d %d %d %d", &x1, &y1, &x2, &y2);

        int x[] = {min(x1,x2), max(x1,x2)};
        int y[] = {min(y1,y2), max(y1,y2)};

        int w = x[1] - x[0];
        int h = y[1] - y[0];

        if(w > h)printf("%d\n", dy(n, w, y[0], y[1]));
        else
            printf("%d\n", dy(n, h, x[0], x[1]));

    }


}

11666.cpp

#include <stdio.h>

#include <functional>

#include <vector>
#include <queue>

#include <algorithm>

using namespace std;

class ele {
	public:
		int s, e;
		bool operator<(const ele &A)const {
			if (s == A.s)return e < A.e;
			return s < A.s;
		}
}I[300003];

int main() {

	int n, m;
	scanf("%d %d", &n, &m);

	for (int i = 0; i < n; i++){
		scanf("%d %d", &I[i].s, &I[i].e);
		I[i].e += I[i].s;
	}

	sort(I, I + n);

	priority_queue <int, vector <int>, greater <int> > work;

	int cur = -1;
	int maxi = n;
	int mini = 0;

	for (int i = 0; i < n; i++) {

		if (cur < I[i].s)cur = I[i].s;

		while (!work.empty()) {
			if (work.top() + m < cur) {
				work.pop();
			}
			else {
				break;
			}
		}

		if (work.empty()) {
			mini++;
			work.push(I[i].e);
		}else{
			if(work.top() <= cur){
				work.pop();
				work.push(I[i].e);
			}else{
				mini++;
				work.push(I[i].e);
			}
		}

	}

	printf("%d", maxi - mini);

}

11974.cpp

#include <stdio.h>

#include <vector>

#include <algorithm>

using namespace std;

int s[50003];

int main(){

	int n;
	scanf("%d", &n);

	vector <int> sexy[7];

	sexy[0].push_back(0);

	for(int i=1; i<=n; i++){

		scanf("%d", &s[i]);
		s[i] %= 7;

		s[i] += s[i-1];

		s[i] %= 7;

		sexy[s[i]].push_back(i);

	}

	int ans = 0;

	for(int i=0; i<7; i++){
		if(sexy[i].size() >= 2){
			ans = max(sexy[i].back() - sexy[i].front(), ans);	
		}
	}

	printf("%d\n", ans);

}

1285.cpp

#include <stdio.h>

#include <memory.h>

#include <algorithm>

using namespace std;

char str[23][23];
char tmp[23][23];

int main(){

    int n;
    scanf("%d", &n);

    for(int i=0; i<n; i++){
        scanf("%s", str[i]);
    }

    int ans = n*n;

    for(int i=0; i<(1<<n); i++){
        memcpy(tmp, str, sizeof(str));
        for(int j=0; j<n; j++){
            if(i & (1<<j)){
                for(int k=0; k<n; k++){
                    if(tmp[j][k] == 'H')tmp[j][k] = 'T';
                    else
                        tmp[j][k] = 'H';
                }
            }
        }
        int f = 0;
        for(int j=0; j<n; j++){
            int e = 0;
            for(int k=0; k<n; k++){
                if(tmp[k][j] == 'T')e++;
            }
            f += min(e, n-e);
        }

        ans = min(ans, f);

    }

    printf("%d\n", ans);

}

1315.cpp

#include <stdio.h>

#include <algorithm>

using namespace std;

int dp[1003][1003];

int wp[1003][1003], rq[1003][1003], cq[1003][1003];

int dy(int r, int c){

    if(r > 1000 || c > 1000)return 0;

    int &ret = dp[r][c];

    if(ret != -1)return ret;

    int rem = wp[r][1000] + wp[1000][c] - wp[r][c] - (r+c-2); // L

    ret = 0;

    if(rem){
        ret = max(cq[r+1][1000] - cq[r+1][c] + dy(r+1, c),
                rq[1000][c+1] - rq[r][c+1] + dy(r, c+1));
    }

    return ret;

}

int main(){

    int n;
    scanf("%d", &n);

    for(int i=1; i<=1000; i++)for(int j=1; j<=1000; j++)dp[i][j] = -1;

    for(int i=1; i<=n; i++){
        int x, y, a;
        scanf("%d %d %d", &x, &y, &a);
        wp[x][y] += a;
        rq[x][y]++;
        cq[x][y]++;
    }



    int aqw = 0, awp = 0;
    for(int i=1; i<=1001; i++){
        for(int j=1; j<=1001; j++){
            wp[i][j] += wp[i-1][j] + wp[i][j-1] - wp[i-1][j-1];
            rq[i][j] += rq[i-1][j];
            cq[i][j] += cq[i][j-1];
        }
    }

    printf("%d\n", rq[1000][1] + cq[1][1000] - cq[1][1] + dy(1, 1));

}

1541.cpp

#include <stdio.h>

#include <string.h>

#include <vector>

using namespace std;

char str[53];

int main(){

    vector <int> val;
    vector <char> op;

    scanf("%s", str);

    int s = strlen(str);

    int v = 0;

    for(int i=0; i<s; i++){

        if(str[i] == '+' || str[i] == '-'){
            val.push_back(v);
            op.push_back(str[i]);
            v = 0;
        }else{
            v = v * 10 + str[i] - '0';
            if(i == s-1)val.push_back(v);
        }

    }

    int ret = val[0];

    bool sub = false;

    for(int i=0; i<op.size(); i++){
        if(op[i] == '-'){
            sub = true;
            ret -= val[i+1];
        }else{
            if(sub)ret -= val[i+1];
            else
                ret += val[i+1];
        }
    }

    printf("%d\n", ret);

}

2904.cpp

#include <stdio.h>
#include <map>
#include <vector>

#include <algorithm>

using namespace std;

int e[103];

int main(){

    int n;
    scanf("%d", &n);

    vector <int> p, c;
    map <int, int> ex;

    int top = 0;

    for(int i=1; i<=n; i++){

        scanf("%d", &e[i]);

        int v = e[i];

        for(int j=2; j*j <= v; j++){

            if(v % j)continue;

            if(ex.find(j) == ex.end()){
                ex[j] = top++;

                p.push_back(j);
                c.push_back(0);
            }

            int s = ex[j];

            while(!(v%j)){
                v /= j;
                c[s]++;
            }

        }

        if(v != 1){
            if(ex.find(v) == ex.end()){
                ex[v] = top++;
                p.push_back(v);
                c.push_back(1);
            }else{
                c[ex[v]]++;
            }
        }

    }

    int ans = 1;

    // average

    for(int i=0; i<p.size(); i++){

        c[i] /= n;

        for(int j=1; j<=c[i]; j++)ans *= p[i];

    }

    printf("%d ", ans);

    int cnt = 0;

    for(int i=1; i<=n; i++){

        for(int j=0; j<p.size(); j++){

            int d = 0;

            if(e[i] >= p[j]){

                while(!(e[i] % p[j])){
                    e[i] /= p[j];
                    d++;
                }

            }

            cnt += max(c[j] - d, 0);

        }

    }

    printf("%d\n", cnt);

}

5012.cpp

#include <stdio.h>

#include <vector>

using namespace std;

using ll = long long;

class BIT{
    public:
        vector <int> T;
        int S;

        BIT(const int n){
            S = n;
            T.resize(S + 1);
        }

        void Update(int p, int v){
            while (p <= S){
                T[p] += v;
                p += p & (-p);
            }
        }

        ll Sum(int p){
            if(p == 0)return 0LL;
            ll ret = 0;
            while (p > 0){
                ret += T[p];
                p -= p & (-p);
            }return ret;
        }

};

int e[500003];

int main(){

    int n;
    scanf("%d", &n);

    BIT le(n), ri(n);

    for(int i=1; i<=n; i++){
        scanf("%d", &e[i]);
        ri.Update(e[i], 1);
    }

    ll ans = 0;

    for(int i=1; i<=n; i++){

       ri.Update(e[i], -1);

       ans += (le.Sum(n) - le.Sum(e[i])) * (ri.Sum(e[i]-1));

       le.Update(e[i], 1);
 
    }

    printf("%lld\n", ans);

}