随笔-141  评论-9  文章-3  trackbacks-0
 
USACO 1.4.3 Arithmetic Progressions


/*
ID: lorelei3
TASK: ariprog
LANG: C++
*/

#include <vector>
#include <algorithm>
#include <functional>
#include <cstdlib>
#include <iostream>
#include <fstream>

using namespace std;

const int N = 300000;

bool    flag[N]; 
bool    none_find =true;
int        array[N];

int main(){
    int i,j,num,n,m, def;

    ifstream in("ariprog.in");
    ofstream out("ariprog.out");

    in>>n>>m;

    num=0;
    for(i=0;i<=m;++i)
        for(j=0;j<=m;++j){
            if(!flag[i*i+j*j]){
                array[num++] = i*i+j*j;
            }
            flag[i*i+j*j] = true;
        }

    sort(array, array+num);

    //a+(n-1)*b <= m*m+m*m
    bool is;
    int p,c;
    int max = 2*m*m;
    int def_max = max/(n-1);

    for(def=1; def<=def_max; def++){
        for(p=0; array[p]<=(max-((n-1)*def)); p++){
            is = true;
            for(c=(n-1); c>=0; c--){
                if(!flag[array[p]+c*def]){
                    is =false;
                    break;
                }
            }
            if(is){
                none_find = false;
                out<<array[p]<<" "<<def<<endl;
            }
        }
    }

    if(none_find)
        out<<"NONE"<<endl;

    return 0;
}
posted @ 2010-11-09 12:54 小阮 阅读(123) | 评论 (0) | 编辑 收藏
USACO 1.4.2 The Clocks

/*
ID: lorelei3
TASK: clocks
LANG: C++
*/
#include <iostream>
#include <fstream>

using namespace std;

char *movestr[] ={"abde","abc","bcef","adg","bdefh","cfi","degh","ghi","efhi"};

int movedist[9][9];
int clocks[9];
int move[9];
int bestmove[9];
int nbestmove;


void mkmove(){
    int i;
    char *p;

    for(i=0; i<9; ++i)
        for(p=movestr[i]; *p; p++)
            movedist[i][*p-'a']=3;
}

void solve(int k){
    int i,j,n,rep;

    if(k==9){
        for(j=0; j<9; ++j)
            if(clocks[j]%12!=0)
                return;
        n=0;
        for(j=0; j<9; ++j)
            n+=move[j];

        if(nbestmove==0 || n<nbestmove){
            nbestmove = n;
            for(j=0; j<9; ++j)
                bestmove[j] = move[j];
        }
        return;
    }

    for(rep=3; rep>=0; --rep){

        for(i=0; i<rep; ++i)
            for(j=0; j<9; ++j)
                clocks[j] += movedist[k][j];

        move[k]=rep;
        solve(k+1);

        for(i=0; i<rep; ++i)
            for(j=0; j<9; ++j)
                clocks[j] -= movedist[k][j];
    }
}

int main(){
    char *ch="";
    int i,j;
    ifstream in("clocks.in");
    ofstream out("clocks.out");

    for(i=0;i<9;i++)
        in>>clocks[i];

    mkmove();

    solve(0);

    for(i=0; i<9; ++i)
        for(j=0; j<bestmove[i]; ++j){
            out<<ch<<i+1;
            ch=" ";
        }
    out<<endl;

    return 0;
}
posted @ 2010-11-09 12:53 小阮 阅读(196) | 评论 (0) | 编辑 收藏
USACO 1.4.1 Packing Rectangles
     摘要: 这题看了答案.. /**//*ID: lorelei3TASK: packrecLANG: C++*/#include <fstream>#include <algorithm>#include <iostream>using namespace std;const in...  阅读全文
posted @ 2010-11-09 12:52 小阮 阅读(595) | 评论 (0) | 编辑 收藏
USACO 1.3.4 Prime Cryptarithm

这个代码好烂。。

/*
ID: lorelei3
TASK: crypt1
LANG: C++
*/

#include <fstream>
#include <stdlib.h>
#include <stdio.h>
#include <string.h>

using namespace std;

const int N = 10;

int s[N];
bool f[N];


int main(){
    int a,b,c,d,e,i,n,ans=0;
    int ai[3], bi[3], res[4];
    ifstream in("crypt1.in");
    ofstream out("crypt1.out");
    memset(f, false, sizeof(f));

    in>>n;
    for(i=0; i<n; ++i){
        in>>s[i];
        f[s[i]] = true;
    }

    
    for(a=0; a<n; ++a)
        for(b=0; b<n; ++b)
            for(c=0; c<n; ++c)
                for(d=0; d<n; ++d){
                    if(s[a]*s[d]>10)
                        continue;
                    for(e=0; e<n; ++e){
                        memset(ai, 0, sizeof(a));
                        memset(bi, 0, sizeof(b));
                        memset(res, 0, sizeof(res));

                        int cc =0, bb=0;
                        
                        bb = (s[c]*s[e])%10;
                        cc = (s[c]*s[e])/10;

                        ai[0] = bb;

                        bb = (s[b]*s[e]+cc)%10;
                        cc = (s[b]*s[e]+cc)/10;

                        ai[1] = bb;
                        ai[2] = (s[a]*s[e]+cc);

                        if(!(f[ai[0]] && f[ai[1]] && f[ai[2]]))
                            continue;

                        if(ai[2]>10)
                            continue;

                        bb = (s[c]*s[d])%10;
                        cc = (s[c]*s[d])/10;

                        bi[0] = bb;

                        bb = (s[b]*s[d]+cc)%10;
                        cc = (s[b]*s[d]+cc)/10;

                        bi[1] = bb;
                        bi[2] = (s[a]*s[d]+cc);

                        if(!(f[bi[0]] && f[bi[1]] && f[bi[2]]))
                            continue;

                        if(bi[2]>10)
                            continue;
                        

                        res[0]=ai[0];
                        
                        cc=0;
                        bb=(ai[1]+bi[0]+cc)%10;
                        cc=(ai[1]+bi[0]+cc)/10;
                        res[1]=bb;

                        bb=(ai[2]+bi[1]+cc)%10;
                        cc=(ai[2]+bi[1]+cc)/10;
                        res[2]=bb;

                        res[3]=bi[2]+cc;

                        if(res[3]>10)
                            continue;
                        else{
                            if(f[res[0]]&&f[res[1]]&&f[res[2]]&&f[res[3]]){
                                ans++;
                            }
                        }
                    }
                }


    out<<ans<<endl;
    return 0;
}
posted @ 2010-11-09 01:02 小阮 阅读(144) | 评论 (0) | 编辑 收藏
USACO 1.3.3 Calf Flac

/*
ID: lorelei3
TASK: calfflac
LANG: C++
*/

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>
#include <ctype.h>


const int N = 21000;

char fulltext[N];
char text[N];

int pallen,b;

int findpal(){
    char *p, *fwd, *bkwd, *etext = text+strlen(text);
    int tmp;

    for(p=text; *p; ++p){
        for(fwd=p,bkwd=p; fwd<etext && bkwd>=text && *fwd==*bkwd; fwd++, bkwd--);
        bkwd++;
        tmp=fwd-bkwd;
        if(tmp>pallen){
            pallen=tmp;
            b=bkwd-text;
        }

        for(fwd=p,bkwd=p+1; fwd<etext && bkwd>=text && *fwd==*bkwd; fwd++, bkwd--);
        bkwd++;
        tmp=fwd-bkwd;
        if(tmp>pallen){
            pallen=tmp;
            b=bkwd-text;
        }
    }
    return 0;
}

int main(){
    int i;
    char *p, *q, ch;

    FILE *fin, *fout;
    fin = fopen("calfflac.in", "r");
    fout = fopen("calfflac.out", "w");

    p=fulltext;
    q=text;
    while((ch = getc(fin)) != EOF) {
        if(isalpha(ch))
            *q++ = tolower(ch);
        *p++ = ch;
    }

    *p = '\0';
    *q = '\0';

        
    findpal();

    fprintf(fout, "%d\n", pallen);

    for(i=0, p=fulltext; *p; ++p)
        if(isalpha(*p))
            if(i++==b)
                break;

    for(i=0; i<pallen && *p; ++p){
        fputc(*p, fout);
        if(isalpha(*p))
            i++;
    }
    fprintf(fout, "\n");

    return 0;
}
posted @ 2010-11-09 01:01 小阮 阅读(163) | 评论 (0) | 编辑 收藏
USACO 1.3.2 Barn Repair

/*
ID: lorelei3
TASK: barn1
LANG: C++
*/

#include <fstream>
#include <algorithm>

using namespace std;

const int MAX = 200;

int a[MAX], b[MAX];

int main(){
    int i, j, m, s, c, t;
    ifstream in("barn1.in");
    ofstream out("barn1.out");

    in>>m>>s>>c;

    for(i=0; i<c; ++i)
        in>>a[i];

    sort(a, a+c);

    t=a[c-1]-a[0]+1;

    for(i=0; i<c-1;++i)
        b[i]=a[i+1]-a[i]-1;

    sort(b, b+c-1);

    for(i=c-2, j=1; i>=0&&j<m; i--,j++)
        t-=b[i];

    out<<t<<endl;

    return 0;
}
posted @ 2010-11-09 01:00 小阮 阅读(148) | 评论 (0) | 编辑 收藏
USACO 1.3.1 Mixing Milk

/*
ID: lorelei3
PROG: milk
LANG: C++
*/

#include <fstream>
#include <algorithm>

using namespace std;

const int MAX = 5005;

typedef struct Cow{
    int price;
    int amount;
    bool operator< (const Cow& c) const{
        return price < c.price;
    }
}Cow, *pCow;

Cow cows[MAX];

int total,n;

int main(){
    int i, cost=0;
    ifstream in("milk.in");
    ofstream out("milk.out");

    in>>total>>n;

    for(i=0; i<n; ++i){
        in>>cows[i].price>>cows[i].amount;
    }

    sort(cows, cows+n);

    i=0;
    while(total-cows[i].amount>0){
        total -= cows[i].amount;
        cost += cows[i].amount * cows[i].price;
        i++;
    }

    cost += cows[i].price*total;

    out<<cost<<endl;

    return 0;
}
posted @ 2010-11-09 00:59 小阮 阅读(120) | 评论 (0) | 编辑 收藏
USACO 1.2.5 Dual Palindromes


/*
ID: lorelei3
PROG: dualpal
LANG: C++
*/

#include <fstream>

using namespace std;

int IsDual(int num, int base){
    int s[100];
    int i,j = 0;
    while(num!=0){
        s[j] = num%base;
        num /= base;
        j++;
    }

    for(i=0,j--; i<j; ++i,--j)
        if(s[i]!=s[j])
            return 0;
    return 1;
}


int IsDoubleDual(int S){
    for(int i=2, j=0; i<=10; ++i){
        if(IsDual(S, i)){
            j++;
            if(j==2)
                return 1;
        }
    }
    return 0;
}

int main(){
    int n,N,S;
    ifstream in("dualpal.in");
    ofstream out("dualpal.out");

    in>>N>>S;

    n=0;
    
    while(n<N){
        S++;
        if(IsDoubleDual(S)){
            n++;
            out<<S<<endl;
        }
    }

    return 0;
}
posted @ 2010-11-09 00:56 小阮 阅读(119) | 评论 (0) | 编辑 收藏
USACO 1.2.4 Palindromic Squares
先进制转换，再判断是不是回文。

/*
ID: lorelei3
PROG: palsquare
LANG: C++
*/

#include <fstream>
#include <iostream>

using namespace std;


void transform(int s, int b, char* k){
    int j=0;
    char t[]="0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ";
    while(s!=0){
        k[j] = t[s%b];
        s = s/b;
        ++j;
    }
    k[j]='\0';
    
    char* a;
    for(a=k+j-1; k<a; a--,k++){
        char ch = *a;
        *a = *k;
        *k = ch;
    }
}

int isPal(char* s){
    int len = 0;
    char* r = s;
    while(*r!='\0'){
        len++;
        r++;
    }
    char* t;
    for(t=s+len-1; s<t; s++,t--)
        if(*s!=*t)
            return 0;
    return 1;
}

int main(){
    int b;
    char k[100];
    char a[100];
    ifstream in("palsquare.in");
    ofstream out("palsquare.out");

    in>>b;

    for(int i=1; i<=300; i++){
        transform(i*i, b, k);
        if(isPal(k)){
            transform(i,b,a);
            out<<a<<" "<<k<<endl;
        }
    }
    return 0;
}
posted @ 2010-11-09 00:54 小阮 阅读(144) | 评论 (0) | 编辑 收藏
USACO 1.2.3 Name That Number


/*
ID: lorelei3
PROG: namenum
LANG: C++
*/

#include <fstream>
#include <string>

using namespace std;

const char code[26] = {'2','2','2','3','3','3','4','4','4','5','5','5','6','6','6','7','0','7','7','8','8','8','9','9','9','0'};

int main(){
    bool flag = false;
    string digits, b, s;

    ifstream in1("namenum.in");
    ifstream in2("dict.txt");
    ofstream out("namenum.out");

    in1>>digits;

    while(in2>>s){
        if(code[s[0]-'A'] != digits[0])
            continue;
        
        int len = s.length();
        b = s;
        for(int i=0; i<len; ++i){
            b[i] = code[s[i]-'A'];
        }
        
        if(b == digits){
            flag = true;
            out<<s<<endl;
        }

    }
    if(!flag)
        out<<"NONE"<<endl;

    return 0;
}
posted @ 2010-11-09 00:46 小阮 阅读(147) | 评论 (0) | 编辑 收藏
仅列出标题
共14页: First 6 7 8 9 10 11 12 13 14 
Powered by: 博客园 模板提供：沪江博客 Copyright ©2024 小阮