정보 창의력 대회 문제 풀이.

망해버렸다.
총 8문제로 2문제씩 small,large로 되어 있다.

 Prob No. 0681 : 최대약수구간 (Large) [CH02.2.Algorithm(Design)]
http://koistudy.net/?mid=prob_page&NO=1665

이런 야비한 방법도 통과할 수 있다는 걸 깨달았다.

#include <bits/stdc++.h>
int mx,i,n,ans,a[50]={0,1,2,6,12,24,48,60,120,180,240,360,720,840,1260,1680,2520,5040,7560,10080,15120,20160,25200,27720,45360,50400,55440,83160,110880,166320,221760,277200,332640,498960,554400,665280,720720,1081080,1441440,2162160,2882880,3603600,4324320,6486480,7207200,8648640};
int main()
{
    scanf("%d",&n);
    for(i=1;i<=45;i++)
        if(n>=a[i])
            mx=a[i];
    printf("%d",n-mx+1);
}

Prob No. 0686 : 24시간 마법진 (Large) [CH02.4.Algorithm(Design)]
http://koistudy.net/?mid=prob_page&NO=1670
걍 nC4 구하라는 문제

#include <bits/stdc++.h>
typedef long long int ll;
using namespace std;
map<ll,ll> M;
map<ll,ll> ::iterator it;
ll mod=1000000007,sum=1;
ll n,i,j,v;
int main()
{
    scanf("%lld",&n);
    if(n==1)
        printf("0");
    else if(n==3){
        printf("0");
    }
    else{
        for(i=n-3;i<=n;i++){
            v=i;
            for(j=2;j*j<=v;j++){
                while(v%j==0){
                    M[j]++;
                    v/=j;
                }
            }
            if(v!=1)
                M[v]++;
        }
        for(i=1;i<=4;i++){
            v=i;
            for(j=2;j*j<=v;j++){
                while(v%j==0){
                    M[j]--;
                    v/=j;
                }
            }
            if(v!=1)
                M[v]--;
        }
        for(it=M.begin();it!=M.end();it++){
            for(i=1;i<=it->second;i++){
                sum=(sum*(it->first))%mod;
            }
        }
        printf("%lld",(sum*24)%mod);
    }
}
nC4 이거보다 쉽게 구할 수 있으면 댓글 좀 주세요 ㅠㅠ.

Prob No. 0684 : 1, 2, 3 Game (Large) [CH02.4.Algorithm(Design)]
http://koistudy.net/?mid=prob_page&NO=1668
이것도 못풀었는데 걍 n부터 bfs했더니 끝났다.
#include <bits/stdc++.h>
using namespace std;
map<int,int> M;
map<int,int>::iterator it;
queue<int> Q;
int n;
int main()
{
    scanf("%d",&n);
    Q.push(n);
    Q.push(0);
    M[n]=0;
    while(!Q.empty())
    {
        int x,y;
        x=Q.front();Q.pop();
        y=Q.front();Q.pop();
     //   printf("%d %d\n",x,y);
        if(x==1){
            printf("%d",y);
            break;
        }
        if(x%3==0 && x/3>=1){
            it=M.find(x/3);
            if(it==M.end()){
            Q.push(x/3);
            Q.push(y+1);
            M[x/3]=y+1;
            }
        }
        if(x%2==0 && x/2>=1){
            it=M.find(x/2);
            if(it==M.end()){
            Q.push(x/2);
            Q.push(y+1);
           // printf("->%d %d\n",y,x);
            M[x/2]=y+1;
            }
        }
        if(x-1>=1){
            it=M.find(x-1);
            if(it==M.end()){
            Q.push(x-1);
            Q.push(y+1);
            M[x-1]=y+1;
            }
        }
    }
}

나머지 한 문제는 쉽다.