Educational Codeforces Round 82 (Rated for Div. 2)(A~D)

아휴, 아쉽다. D문제를 풀 수 있을 것 같은데, 아쉽게도 시간이 부족해서... 역시 교육장에서는 교육을... 일단 3개의 문제부터 풀고 나머지는 천천히 보충하자.
A. Erasing Zeroes
A는 더 이상 할 말이 없다. 가장 왼쪽과 가장 오른쪽의 위치를 통계해서 중간에 0이 얼마나 있는지 보면 된다.

#include
using namespace std;
typedef long long ll;
const int maxn=100010,mod=1e9+7;
int main()
{
	int t;  cin>>t;
	while(t--)
	{
		string s;   cin>>s;
		int res=0,l=-1,r=0,num=0;
		for(int i=0;i<s.size();i++)
		{
			if(s[i]=='1')
			{
			  num++;
			  if(l==-1) l=i;
			  r=i;
			}
		}
		if(num==0) 
            cout<<0<<endl;
		else
			cout<<r-l+1-num<<endl;
	}	
	return 0;
}

B. National Project
B는 정말 그 구덩이가 있어요. 문제면에서 온전한 길을 닦는다고... 온전한 길을 닦는다고... 사고방식은 코드를 직접 보세요!그래도 쉬워요.

#include
using namespace std;
typedef long long ll;
int main()
{
	ll t; cin>>t;
	while(t--)
    {
		ll n,g,b;   cin>>n>>g>>b;
		ll tmp=(n+1)/2;
		if(tmp<=g)  //      g     n  
			cout<<n<<endl;
		else
		{
			ll num=tmp/g;
			ll ans;
			if(tmp%g==0)    0    num-1      g 
				ans=(num-1)*(g+b)+g;
			else
				ans=(num)*(g+b)+tmp%g;    0   num          
			cout<<max(ans,n)<<endl;
		}
	}
	return 0;
}

C. Perfect Keyboard
사실 蒟蒻이 생각한 것은 쌍방향 체인 시계였는데 잊어버렸어요. 2333, 수조로 쓸 수밖에 없었어요...수동으로 이 문제를 시뮬레이션해 보면 규칙이 하나 있는데, 그는 매번 어떤 수의 좌우로 이동해야만 한다.이 예와 같다.z를 먼저 놓고 x!=z, 그래서 x는 z 오른쪽에 놓고 다음 z를 본다. 현재 위치-1의 그 자모와 같기 때문에 현재 위치-1을 직접 양보하고 새로운 위치를 추가하지 않아도 된다. 이런 식으로 추측한다. (현재 위치가 ans라고 가정하면) 매번 ans,ans-1,ans+1을 판단한다.같으면 현재 위치를++, –, 또는 변하지 않게 합니다.

#include
using namespace std;
typedef long long ll;
char str[205],ans[105];
bool vis[105];

int main()
{
	int T;  scanf("%d",&T);
	while (T--)
	{
		scanf("%s",str+1);
		int n=strlen(str+1),l=27,r=27,now=27,flag=0;
		ans[l]=str[1];
		memset(vis,0,sizeof(vis));
		vis[str[1]-'a']=1;
		for (int i=2;i<=n;i++)
		{
			if (now>l&&ans[now-1]==str[i])
                now--;
			else if (now<r&&ans[now+1]==str[i])
                now++;
			else if (now==l&&!vis[str[i]-'a'])
                ans[--l]=str[i],now--,vis[str[i]-'a']=1;
			else if (now==r&&!vis[str[i]-'a'])
                ans[++r]=str[i],now++,vis[str[i]-'a']=1;
			else
			{
			    flag=1;
                break;
            }
		}
		if (flag)
            puts("NO");
		else
		{
			puts("YES");
			for (int i=l;i<=r;i++)
                putchar(ans[i]);
			for (int i=0;i<26;i++)
				if (!vis[i]) putchar(i+'a');
			puts("");
		}
	}
	return 0;
}

위에는 큰 놈의 코드인데 이해가 안 되면 고구마 코드를 볼 수 있는데 정말 꺼내기가 쑥스러워서...

#include
using namespace std;
typedef long long ll;
const ll mod = 1e9+7;
const int N = 2e5+5;
int a[600];
int b[60];

int main()
{
	ll t;cin>>t;
	while(t--)
    {
        memset(a,-1,sizeof a);
        memset(b,-1,sizeof b);
        string s;cin>>s;
        a[300]=s[0]-'a';
        int x=300;
        int flag=1;
        for(int i=1;i<s.size();i++)   //                
        {
            if((s[i]-'a')!=a[x-1]&&(s[i]-'a')!=a[x+1]&&(s[i]-'a')!=a[x])
            {
                if(a[x+1]!=-1&&a[x-1]!=-1)
                {
                    flag=0;
                    break;
                }
                if(a[x+1]==-1)
                {
                    x++;
                    a[x]=s[i]-'a';
                }
                if(a[x-1]==-1)
                {
                    x--;
                    a[x]=s[i]-'a';
                }

            }
            else if((s[i]-'a')==a[x-1])
                x--;
            else if((s[i]-'a')==a[x+1])
                x++;
        }
        if(!flag)
            cout<<"NO"<<endl;
        else
        {
            set<int> st;
            for(int i=0;i<600;i++)    //          
            {
                if(a[i]!=-1)
                {
                    if(st.count(a[i]))
                        flag=0;
                    else
                        st.insert(a[i]);
                }
            }
            if(!flag)
                cout<<"NO"<<endl;
            else
            {
                cout<<"YES"<<endl;
                for(int i=0;i<600;i++)//               ，         
                {
                    if(a[i]!=-1)
                    {
                       cout<<char(a[i]+'a');
                       b[a[i]]=1;

                    }
                }
                for(int i=0;i<26;i++)
                    if(b[i]==-1)
                        cout<<char(i+'a');
                cout<<endl;
            }
        }

    }

	return 0;
}

D. Fill The Bag
어머님, 정말 첫인상 2진법이에요. 계속 2진법으로 생각하다가... 쓸 수도 있지만 정말 욕심보다는 편해요. 코드를 직접 보세요. 생각이 한눈에 보여요.

#include 
using namespace std;
typedef long long ll;

int main()
{
	int t;cin>>t;
	while (t--)
    {
        ll s,n,m,x,ans;
		cin>>n>>m;
		s=ans=0;
		multiset<ll,greater<ll>> f;
		while (m--)
        {
            cin>>x;
            s+=x;
            f.insert(x);
        }
		if (s<n)//    n ，     ...
            cout<<"-1"<<endl;
		else
		{
			while(n)
			{
				m=*f.begin();
				f.erase(f.begin());
				if(m<=n)  //m<=n    ，    
				{
				    n-=m;
				    s-=m;
				}
				else if(s-m<n)  //  m   
                {
                    ans++;
                    f.insert(m/2);
                    f.insert(m/2);
                }
				else  //   m>n&&s-m>n，       m    
                    s-=m;
			}
			cout<<ans<<endl;
		}
	}
}

E는 DP가 나올 것 같아서 보충을 하자...FG는 그만두고 계속 목숨을 부지하자...
E. Erase Subsequences
귀신이 나올 뻔했어. 점심 내내 큰 WA가 마지막이 아니었어. 하마터면 내가 믿을 뻔했어...