[usaco] Chapter1-Getting started(Section 1.3)

 

/*
    ID:bbezxcy1
    PROG: milk
    LANG: C++
*/
#include<cstring>
#include<algorithm>
#include<cstdio>
#include<iostream>
using namespace std;

class fuck{
	public:
		int val,num;
}sum[10000];
bool cmp(fuck a,fuck b){
	if(a.val<b.val){
		return 1;
	}
	return 0;
}
int main(){
	int need,loc,n,i,j,a,b,c,ans;
    freopen("milk.in","r",stdin );
    freopen("milk.out","w",stdout );
	while(scanf("%d%d",&need,&n)!=EOF){
		ans=0;
	    for(i=0;i<n;i++){
			scanf("%d%d",&sum[i].val,&sum[i].num);
		}
		sort(sum,sum+n,cmp);
		loc=0;
		while(need!=0){
			if(need-sum[loc].num>0){
				need-=sum[loc].num;
				ans+=sum[loc].num*sum[loc].val;
				loc++;
			}
			else{
				ans+=need*sum[loc].val;
				break;
			}
		}
		printf("%d\n",ans);
	}
	return 0;
}

 

/*
    ID:bbezxcy1
    PROG: barn1
    LANG: C++
*/
#include<iostream>
#include<cstring>
#include<fstream>
#include<cstdio>
#include <algorithm>
using namespace std;
const int nMax=1000;
int dis[nMax],pos[nMax];
int main(){
    int m,s,c,i,j,a,b,n,ans;
    freopen ( "barn1.in", "r", stdin );
    freopen ( "barn1.out", "w", stdout );
    while(scanf("%d%d%d",&m,&s,&c)!=EOF){
        for(i=0;i<c;i++){
            scanf("%d",&pos[i]);
        }
        if(m>=c){
            cout<<c<<endl;
            continue;
        }
        sort(pos,pos+c);
        ans=pos[c-1]-pos[0];
        for(i=0;i<c-1;i++){
            dis[i]=pos[i+1]-pos[i];
        }
        sort(dis,dis+c-1);
        b=m;
        m--;
        a=c-2;
        while(m--&&a>=0){
            ans-=dis[a];
//            cout<<"dis"<<dis[a];
//            cout<<" ans"<<ans<<endl;
            a--;
        }
        cout<<ans+b<<endl;
    }
    return 0;
}

  /*

    ID: bbezxcy1
    PROG: calfflac
    LANG: C++
*/
#include<iostream>
#include<cstring>
#include<fstream>
#include<cstdio>
using namespace std;
const int nMax=200000;
int p[nMax];
char str1[nMax];
void build(char *str,int len) {  //abc-->@#a#b#c#
    int i=0,j;
    str1[0]='@';//开始加入另特殊字符
    str1[1]='#';
    j=2;
    for(i=0;i<len;i++ ){//在每个字符两边都插入一个特殊字符
        str1[j++]=str[i];
        str1[j++]='#';
    }
    str1[j]='\0';
}

int ps;
int manacher(){
    int idd,mxx=0,maxx=0,record;
    memset(p,0,sizeof(p));
    for(int i=strlen(str1);i>=0;i--){
        if( mxx>i )
            p[i]=min(mxx-i, p[2*idd-i]);
        else p[i]=1;
        while(str1[i+p[i]]==str1[i-p[i]])
            p[i]++;

        if( i+p[i]>mxx ){
            mxx=i+p[i];
            idd=i;
        }

        if( p[i]>maxx){
            maxx=p[i]-1;//P[id］-1就是该回文子串在原串中的长度
            record=i;
            ps=record;
        }
    }
    return maxx;
}
int main(){
    char c;
    int len,a,b,n,i;
    int pos[nMax];
    char str[nMax],abc[nMax];
    len=n=0;
    freopen ( "calfflac.in", "r", stdin );
    freopen ( "calfflac.out", "w", stdout );
//    cin>>str;
//    cout<<str<<endl;
    while(scanf("%c",&c)!=EOF){
        str[len]=c;
        if((c>='a'&&c<='z')||(c>='A'&&c<='Z')){
            if(c>='a'&&c<='z'){
                abc[n]=c;
            }
            else{
                abc[n]=c+'a'-'A';
            }
            pos[n]=len;
            n++;
        }
        len++;
    }
    abc[n]='\0';
    //cout<<endl<<abc<<endl;
    build(abc,n);
    a=manacher();   //回文串长度
    cout<<a<<endl;
  //  cout<<ps<<"ps"<<endl;
    if(ps%2==1){
        ps=ps/2-1;
      //  cout<<ps<<endl;
        for(i=pos[ps-a/2+1];i<=pos[ps+a/2];i++){
            cout<<str[i];
        }cout<<endl;
    }
    else{
        ps=ps/2-1;
     //   cout<<ps<<endl;
        for(i=pos[ps-a/2];i<=pos[ps+a/2];i++){
            cout<<str[i];
        }cout<<endl;
    }

    return 0;
}

  /*

    ID:bbezxcy1
    PROG: crypt1
    LANG: C++
*/
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
int num[30],tmp[30];
int ans,n;
bool shit[30];
bool innum(int a){
	int i,j,b,c;
	while(a){
		b=a%10;
		a/=10;
		if(shit[b]!=1){
			return 0;
		}
	}
	return 1;
}
bool check(){
	int a=tmp[0]*100+tmp[1]*10+tmp[2];
	int b=tmp[3]*10+tmp[4];
	int c=tmp[3]*a;
	int d=tmp[4]*a;
	int e=c+10*d;
	if(c<100||c>=1000||d<100||d>=1000){
		return 0;
	}
	if(e<1000||e>=10000){
		return 0;
	}
	if(innum(c)&&innum(d)&&innum(e)){
		return 1;
	}
	return 0;
}
void dfs(int dep){
    if(dep==5){
		if(check()){
//		    for(int i=0;i<5;i++)
//		    {
//		        cout<<tmp[i]<<" ";
//		    }cout<<endl;
			ans++;
		}
		return;
	}
	for(int i=0;i<n;i++){
		tmp[dep]=num[i];
		dfs(dep+1);
	}
}
int main(){
	int i,j,a,b,c;
    freopen("crypt1.in","r",stdin );
    freopen("crypt1.out","w",stdout );
	while(scanf("%d",&n)!=EOF){
		memset(shit,0,sizeof(shit));
		for(i=0;i<n;i++){
			scanf("%d",&num[i]);
			shit[num[i]]=1;
		}
		ans=0;
		dfs(0);
		printf("%d\n",ans);
	}
	return 0;
}