随笔-141  评论-9  文章-3  trackbacks-0
 
USACO 2.1.5 Hamming Codes

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

#include <fstream>
#include <iostream>

using namespace std;

const int MAX = 0xFFF;

int N, B, D;
int mask = 0xFFFF;
int ans[MAX];
int count=0,num=0;

bool haming( int a,  int b){
    int c = mask&(a^b);
    int d=0;
    for(int i=0; i<B; ++i)
        if(c& 1<<i){
            d++;
            if(d>=D)
                return true;
        }
    return false;
}

bool check(int num){
    for(int i=0; i<count; ++i){
        if(!haming(num, ans[i]))
            return false;
    }
    return true;
}

int main(){

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

    in>>N>>B>>D;

    ans[count++]=0;
    num =1;

    while(count<N){
        if(check(num)){
            ans[count++]=num;
        }
        num++;
    }

    char *sep=" ";
    int ends=1;
    for(int i=0; i<count; ++i){
        sep=" ";
        if(i==count-1 || ends==10){
            ends=0;
            sep="\n";
        }
        out<<ans[i]<<sep;
        ends++;
    }
    return 0;
}
posted @ 2010-11-21 00:47 小阮 阅读(354) | 评论 (0) | 编辑 收藏
USACO 2.1.4 Healthy Holsteins

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

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

using namespace std;

const int MAX = 30;

int V, G; // V 需要维他命种类数, G可以喂牛的饲料种数

int need[MAX];
int kind[MAX][MAX];
int x[MAX];
int best[MAX];
int y[MAX];
int total=100000000 , num = MAX;

bool check(){
    int i,j, times=0,to=0;
    memset(y, 0, sizeof(y));
    for(i=0; i<G; ++i){
        if(x[i]){
            times++;
            for(j=0; j<V; ++j)
                y[j] += kind[i][j];
        }
    }

    for(i=0; i<V; ++i){
        if(y[i]<need[i])
            return false;
        else
            to +=y[i];
    }

    if(times<num){
        if(to<total){
            total = to;
            return true;
        }
        else 
            return false;
    }else
        return false;
}

void dfs(int t){
    if(t>=G){
        if(check()){
            num = 0;
            for(int i=0; i<G; ++i){ best[i] = x[i]; num+=best[i]; }
        }
    }else
        for(int i=0 ; i<=1; ++i){
            x[t] = i;
            dfs(t+1);
        }
}

int main(){
    int i,j;

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

    in>>V;

    for(i=0; i<V; ++i)
        in>>need[i];

    in>>G;

    for(i=0; i<G; ++i)
        for(j=0; j<V; ++j)
            in>>kind[i][j];

    dfs(0);

    char* ch=" ";
    out<<num<<ch;
    for(i=0,j=0; i<G; ++i){
        if(best[i]){
            j++;
            if(j==num) ch="";
            out<<i+1<<ch;
        }
    }
    out<<endl;
    return 0;
}
posted @ 2010-11-21 00:46 小阮 阅读(166) | 评论 (0) | 编辑 收藏
USACO 2.1.3 Sorting A Three-Valued Sequence

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

#include <fstream>
#include <iostream>
#include <algorithm>

using namespace std;

const int MAX = 1005;

int first[MAX], second[MAX];
int n;

int main(){

    int i,j, npairs=0, ntriples=0, nswap=0;

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

    in>>n;
    for(i=0; i<n; ++i){
        in>>first[i];
        second[i]=first[i];
    }

    sort(second, second+n);

    for(i=0; i<n; ++i)
        for(j=0; j<n; ++j)
            if(first[i]!=second[i] && first[j]!=second[j]
                && first[i]==second[j] && second[i]==first[j]){
                first[i]  = second[i];
                first[j] = second[j];
                npairs++;
            }

    for(i=0; i<n; ++i)
        if(first[i]!=second[i])
            ntriples++;
    
    nswap = npairs + ntriples/3 *2;

    out<<nswap<<endl;
    return 0;
}
posted @ 2010-11-21 00:45 小阮 阅读(120) | 评论 (0) | 编辑 收藏
USACO 2.1.2 Ordered Fractions

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

#include <fstream>
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstdlib>

using namespace std;

const int MAX = 165;

typedef struct Frac{
    int a,b;
    double val;

    bool operator < (const Frac &t)const{
        return val < t.val;
    }
}Frac;

int gcd(int a, int b){
    if(b==0)
        return a;
    else
        return gcd(b, a%b);
}

int n;
Frac num[MAX*MAX];

int main(){

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

    in>>n;

    int k=0;
    for(int b=1; b<=n; ++b)
        for(int a=1; a<b; ++a){
            if(!(a%2) && !(b%2))
                continue;
            if(gcd(a,b)==1){
                num[k].a=a;
                num[k].b=b;
                num[k].val=(double)a/b;
                k++;
            }
        }
            
    sort(num, num+k);

    out<<"0/1\n";
    for(int i=0; i<k; ++i)
        out<<num[i].a<<"/"<<num[i].b<<endl;
    out<<"1/1\n";
    return 0;
}
posted @ 2010-11-21 00:44 小阮 阅读(107) | 评论 (0) | 编辑 收藏
USACO 2.1.1 The Castle

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

#include <fstream>

using namespace std;

const int MAX = 55;

int t;
int g[MAX][MAX]; 
int area[3000];
bool f[MAX][MAX][5];

bool floodfill(int x, int y){
    if(g[x][y]!=-1)    return false;
    g[x][y]=t;
    area[t]++;
    if(!f[x][y][1])    floodfill(x, y-1);
    if(!f[x][y][2])    floodfill(x-1, y);
    if(!f[x][y][3])    floodfill(x, y+1);
    if(!f[x][y][4])    floodfill(x+1, y);
    return true;
}


int main(){
    int i,j,k,n,m;

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

    in>>m>>n;

    for(i=1; i<=n; ++i)
        for(j=1; j<=m; ++j){
            in>>k;
            if(k>=8) { k-=8; f[i][j][4]=true; }
            if(k>=4) { k-=4; f[i][j][3]=true; }
            if(k>=2) { k-=2; f[i][j][2]=true; }
            if(k>=1) { k-=1; f[i][j][1]=true; }
            g[i][j] = -1;
        }

    t=0;
    for(i=1; i<=n; ++i)
        for(j=1; j<=m; ++j)
            if(floodfill(i,j))
                t++;

    int max_room=0;
    for(i=0;i<=t;++i) 
        max_room= max_room>area[i]? max_room:area[i];

    out<<t<<endl;
    out<<max_room<<endl;

    int max_area=0, mx=0, my=0, x=0;
    char ch=0;
    
    for(j=1; j<=m; ++j)
        for(i=n; i>=1; i--){
            if(g[i][j]!=g[i-1][j] && i-1!=0)
                x = area[g[i][j]]+area[g[i-1][j]];
            if(x>max_area){
                max_area = x; mx = i; my = j; ch='N';
            }

            if(g[i][j]!=g[i][j+1] && j+1<=m)
                x = area[g[i][j]]+area[g[i][j+1]];
            if(x>max_area){
                max_area = x; mx = i; my = j; ch='E';
            }
        }

    out<<max_area<<endl;
    out<<mx<<" "<<my<<" "<<ch<<endl;

    return 0;
}
posted @ 2010-11-21 00:43 小阮 阅读(131) | 评论 (0) | 编辑 收藏
USACO 1.5.4 Checker Challenge

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

#include <fstream>

FILE *fi, *fo;

const int N = 20;
int n ;
int sum =0;
int a[20];
unsigned long int upperlim ;

int ps(int a) //不用 log 节省时间
{
    switch (a)
    {
    case 1:
        return 1;
    case 2:
        return 2;
    case 4:
        return 3;
    case 8:
        return 4;
    case 16:
        return 5;
    case 32:
        return 6;
    case 64:
        return 7;
    case 128:
        return 8;
    case 256:
        return 9;
    case 512:
        return 10;
    case 1024:
        return 11;
    case 2048:
        return 12;
    case 4096:
        return 13;
    }
}

void test(unsigned long int row, unsigned long int ld, unsigned long int rd, int depth){
    unsigned long int pos, p;
    if(row!=upperlim){
        pos = upperlim & ~(row|ld|rd);
            while(pos!=0){
                p = pos & (-pos);
                pos = pos-p;
                if(sum<3)
                    a[depth] = p;
                test(row+p, (ld+p)<<1, (rd+p)>>1, depth+1);
            }
    }else{
        sum++;
        if(sum<=3){
            for (int i=0;i<n-1;i++)
                fprintf(fo,"%d ",ps(a[i]));
            fprintf(fo,"%d\n",ps(a[n-1]));

        }    
    }
}

int main(void) {
    fi = fopen("checker.in", "r");
    fo = fopen("checker.out", "w");
    fscanf(fi, "%d", &n);
    upperlim = (1<<n)-1;
    test(0, 0, 0, 0);
    fprintf(fo, "%d\n", sum);
   
    return 0;
}
posted @ 2010-11-09 13:00 小阮 阅读(168) | 评论 (0) | 编辑 收藏
USACO 1.5.3 SuperPrime Rib

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

#include <fstream>
#include <math.h>

using namespace std;

int N;


int isPrime(int a){
    if(a==2)
        return 0;

    for(int i=2; i<=sqrt(a); ++i)
        if( a%i == 0)
            return 0;
    return 1;
}

void sprime(int n, int depth){
    if(depth == N){
        //cout<<n<<endl;
        printf("%d\n", n);
        return;
    }

    n *= 10;

    if(isPrime(n+1))
        sprime(n+1, depth+1);

    if(isPrime(n+3))
        sprime(n+3, depth+1);

    if(isPrime(n+7))
        sprime(n+7, depth+1);

    if(isPrime(n+9))
        sprime(n+9, depth+1);
}

int main(){

    freopen("sprime.in","r",stdin);
    freopen("sprime.out","w",stdout);

    scanf("%d\n", &N);
    //cin>>N;

    sprime(2,1);
    sprime(3,1);
    sprime(5,1);
    sprime(7,1);

    return 0;
}
posted @ 2010-11-09 12:59 小阮 阅读(167) | 评论 (0) | 编辑 收藏
USACO 1.5.2 Prime Palindromes

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

#include <fstream>
#include <iostream>
#include <algorithm>
#include <string.h>
#include <math.h>

using namespace std;

const int BASE = 10;
const int MAX = 100000;

int ans[MAX];

int isPrime(int a){
    int n = static_cast<int>(sqrt(a));
    for(int i=2; i<=n; ++i)
        if(!(a%i))
            return 0;
    return 1;
}


int getPal(int i, int j){
    /*
    if (j==1)
    {
        char a[30];
        sprintf(a,"%d",i);
        int len=strlen(a);
        for(int k=0;k<len;k++)
           a[k+len]=a[len-k-1];
        a[len*2]='\0';
        char* b;
        return atoi(a);
        //return strtol(a,&b,10);
    }
    if (j==0)
    {
        char a[30];
        sprintf(a,"%d",i);
        int len=strlen(a);
        for(int k=0;k<len;k++)
           a[k+len-1]=a[len-k-1];
        a[len*2-1]='\0';
        char* b;
        return atoi(a);
        //return strtol(a,&b,10);
    }    
*/
    
    if(j==1){
        char a[30];
        sprintf(a,"%d",i);
        int len=strlen(a);
        for(int k=0;k<len;k++)
           a[k+len]=a[len-k-1];
        a[len*2]='\0';
        char* b;
        return atoi(a);
        //return strtol(a,&b,10);
/*
        char a[30];
        sprintf(a, "%d", i);
        int len = strlen(a);
        for(int k=0; k<len; k++)
            a[k+len] = a[len-k-1]; 
        a[len*2] = '\0';
        return atoi(a);
    */    
        //char str[20];
    //    sprintf(str, "%d", i);
    //    string s(str), t(str);
        //reverse(t.begin(), t.end());
        //s.append(t);
        //return atoi(s.c_str());    
        
    }
    if(j==0){
        /*
        char a[30];
        sprintf(a,"%d",i);
        int len=strlen(a);
        for(int k=0;k<len;k++)
           a[k+len-1]=a[len-k-1];
        a[len*2-1]='\0';
        char* b;
        return atoi(a);
        //return strtol(a,&b,10);
*/
        
        char a[30];
        sprintf(a, "%d", i);
        int len = strlen(a);
        for(int k=0; k<len; k++)
            a[k+len-1] = a[len-k-1];
        a[len*2-1] = '\0';
        return atoi(a);
    
        //char str[20];
        //sprintf(str, "%d", i);
        //string s(str), t(str);
        //t = t.substr(0, t.size()-1);
        //reverse(t.begin(), t.end());
        //s.append(t);
        //return atoi(s.c_str());
        
    }
    
}


int main(){
    int i,j,a,b;
    ifstream in("pprime.in");
    ofstream out("pprime.out");

    in>>a>>b;

    int t=0;
    for(i=1; i<=9999; ++i)
        for(j=0; j<2; ++j){
            int x = getPal(i,j);
            if(isPrime(x) && x>=a && x<=b){
                ans[t++] = x;
            }
        }

    sort(ans, ans+t);

    for(i=0; i<t; ++i)
        out<<ans[i]<<endl;

    return 0;
}
posted @ 2010-11-09 12:58 小阮 阅读(169) | 评论 (0) | 编辑 收藏
USACO 1.5.1 Number Triangles


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

using namespace std;

const int N = 1005;

int a[N][N];

int max(int a, int b){
    return a>b?a:b;
}

int main(){
    int n,i,j;

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

    in>>n;

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

    for(i=n-2; i>=0; i--)
        for(j=0; j<=i; ++j)
            a[i][j] = a[i][j]+max(a[i+1][j], a[i+1][j+1]);

    out<<a[0][0]<<endl;

    return 0;
}
posted @ 2010-11-09 12:57 小阮 阅读(116) | 评论 (0) | 编辑 收藏
USACO 1.4.4 Mother's Milk


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

using namespace std;

const int MAX = 25;

typedef struct State{
    int bucket[3];
}State;

int flag[MAX][MAX][MAX];
int full_bucket[3];
int can[MAX];


State pour(State s, int from, int to){
    
    int amt = s.bucket[from];

    if(s.bucket[to]+amt>full_bucket[to])
        amt = full_bucket[to] - s.bucket[to];
    
    s.bucket[from] -= amt;
    s.bucket[to] += amt;
    return s;
}


void search(State s){

    if(flag[s.bucket[0]][s.bucket[1]][s.bucket[2]])
        return;

    flag[s.bucket[0]][s.bucket[1]][s.bucket[2]] = true;

    if(s.bucket[0] == 0 )
        can[s.bucket[2]] = true;

    for(int i=0; i<3; ++i)
        for(int j=0; j<3; ++j)
            search(pour(s,i,j));
}

int main(){
    
    ifstream in("milk3.in");
    ofstream out("milk3.out");

    in>>full_bucket[0]>>full_bucket[1]>>full_bucket[2];

    State s;
    s.bucket[0] = 0;
    s.bucket[1] = 0;
    s.bucket[2] = full_bucket[2];

    search(s);

    char* sep = "";
    for(int i=0; i<MAX; ++i)
        if(can[i]){
            out<<sep<<i;
            sep=" ";
        }

    out<<endl;

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