数据结构（栈和队列）

Posted on 2009-09-02 by

铁轨(poj 1363)

某城市有一个火车站，其中的铁路如图：

e688aae59bbe12518921101
每辆火车都从A方向驶入车站，再从B方向驶出车站，同时它的车厢可以进行某种形式的重新组合。假设从A方向驶来的火车有n节车厢（n<=1000），分别按顺序编号为：1、2…，n。假定在进入车站之前每节车厢之间都是不连着的，并且它们可以自行移动，直到处在B方向的铁轨上。另外假定车站C里可以停放任意多节的车厢。但是一旦当一节车厢进入车站C ,它就不能再回到A方向的铁轨上了，并且一旦它进入B的方向的铁轨后，它就不能再回到车站C。
负责车厢调度的工作人员需要知道能否使他以a1,a2,a2……,an的顺序从B方向驶出，请写一个程序，用来判断能否得到指定的车厢顺序。

分析：用栈模拟车站C，用x标记A方向将要驶出的车厢，用y标记B方向下一辆要驶入的车厢。
if(x等于y)
直接开过去
else if(x小于y)
 将x入栈直到x>y
else If(x大于y)
从栈里驶出，如果栈里的车厢不等于y那就表示无解

代码：

C++语言: Codee#5510

#include <iostream>
#include <stack>
using namespace std;

int main()
{
    int n,i;
    int a[1001];
    int coach;
    stack<int> s;

    while(1)
    {
        scanf("%d",&n);
        if(n==0)    break;
        while(1)
        {
            for(i=0;i<n;i++)
            {
                scanf("%d",&a[i]);
                if(a[0]==0)    break;
            }
            if(a[0]==0)    break;
            while(!s.empty())    s.pop();
            coach=1;
            for(i=0;i<n;i++)
            {
                if(a[i]==coach)
                    coach++;
                else if(a[i]>coach)
                {
                    while(a[i]>coach)
                    {
                        s.push(coach);
                        coach++;
                    }
                    coach++;
                }
                else if(a[i]<coach)
                {
                    if(a[i]!=s.top())
                    {
                        printf("No\n");
                        break;
                    }
                    s.pop();
                }
            }
            if(i>=n)
                printf("Yes\n");
        }
        printf("\n");
    }
   
    return 0;
}

小球钟——时间与运动(poj 1879)

分析（取自黑书）：模拟小球钟的运作，分钟、5分钟、小时轨道符合“后进先出”的特点，是栈。而底部的轨道符合“先进先出”的特点，构成了一个队列。我们先模拟一天的状态，将小球编号1，2，3…n，然后得到一天后新小球队列P1,P2,…Pn。我们得到一种置换F(1,2,…,n)=(P1,P2,…，Pn)。有了这个条件，对于当前处在x位置上的小球，无论小球编号多少，都知道它再过24小时应当处于位置Px，我们可以求出每一个小球回到原来位置的周期，然后求所有小球周期的最小公倍数。
代码：

C++语言: Codee#5511

#include <iostream>
using namespace std;

typedef int type;
const int Max_Size=1000;

class Queue{
private:
    type queue[Max_Size];
    int  rear, front, Size;
public:
    Queue(){
        rear = front = -1;
        Size = 0;
    }
    void enqueue( type data ) {
        rear = ( rear + 1 ) % Max_Size;
        queue[ rear ] = data;
        ++ Size;
    }
    type dequeue() {
        front = ( front + 1 ) % Max_Size;
        -- Size;
        return queue[ front ];
    }
    bool empty(){
        return !Size;
    }
    int  size(){
        return Size;
    }
};


class Stack{
private:
    type stack[Max_Size];
    int  top;
public:
    Stack(){
        top = 0;
    }
    void push( type data ){
        if ( top < Max_Size ){
            stack[ top ++ ] = data;
        }
        else{
            cout << "No Enough Space!" << endl;
        }
    }
    type pop(){
        if ( top ){
            return stack[ -- top ];
        }
        else{
            cout << "No Element Now!" << endl;
            return 0;
        }
    }
    bool empty(){
        return !top;
    }
    int  size(){
        return top;
    }
};

int gcd(int a,int b)
{
    int t,c;
    if(a==0)
        return b;
    if(b==0)
        return a;
    if(a<b)
        t=a,a=b,b=t;
    for(c=a%b;c>0;c=a%b)
    {
        a=b;b=c;
    }
    return b;
}

int main()
{
    Queue bottom;
    Stack min,fivemin,hour;
    int a,b,i,j,n;
    int pos[1001],cycle[1001];

    while(1){
        scanf("%d",&n);
        if(n==0)    break;
        while(!bottom.empty())    bottom.dequeue();
        while(!min.empty())        min.pop();
        while(!fivemin.empty())    fivemin.pop();
        while(!hour.empty())    hour.pop();

        for(i=1;i<=n;i++)    bottom.enqueue(i);
        int day=24*60;
        for(i=0;i<day;i++){
            a=bottom.dequeue();
            if(min.size()==4){
                for(j=0;j<4;j++){
                    b=min.pop();
                    bottom.enqueue(b);
                }
                if(fivemin.size()==11){
                    for(j=0;j<11;j++){
                        b=fivemin.pop();
                        bottom.enqueue(b);
                    }
                    if(hour.size()==11){
                        for(j=0;j<11;j++){
                            b=hour.pop();
                            bottom.enqueue(b);
                        }
                        bottom.enqueue(a);
                    }
                    else
                        hour.push(a);
                }
                else
                    fivemin.push(a);
            }
            else
                min.push(a);
        }
        for(i=1;i<=n;i++)
            pos[i]=bottom.dequeue();
        for(i=1;i<=n;i++)
            cycle[i]=1;
        int k;
        for(i=1;i<=n;i++){
            k=pos[i];
            while(i!=k){
                k=pos[k];
                cycle[i]++;
            }
        }
        int sum=1;
        for(i=1;i<=n;i++){
            sum=sum*cycle[i]/gcd(sum,cycle[i]);
        }
        printf("%d balls cycle after %d days.\n",n,sum);
    }
    return 0;
}

直接用STL，会比较慢，而且调试不方便，所以就自己写队列和栈。
队列的模板：
C++语言: Codee#5497

#include <iostream>
#include <iomanip>
using namespace std;

typedef int type;

const int Max_Size = 10;

class Queue{
private:
    type queue[Max_Size];
    int  rear, front, Size;
public:
    Queue(){
        rear = front = -1;
        Size = 0;
    }
    void enqueue( type data ) {
        rear = ( rear + 1 ) % Max_Size;
        queue[ rear ] = data;
        ++ Size;
    }
    type dequeue() {
        front = ( front + 1 ) % Max_Size;
        -- Size;
        return queue[ front ];
    }
    bool empty(){
        return !Size;
    }
    int  size(){
        return Size;
    }
};

int main(){
    Queue T;
    int i;
    for ( i = 1; i <= 8; ++ i ){
        T.enqueue(i);
    }
    while ( !T.empty() ){
        cout << setw(4) << T.dequeue();
    }
    cout << endl;
   
    for ( i = 9; i <= 18; ++ i ){
        T.enqueue(i);
    }
    cout << "Size = " << T.size() << endl;
    while ( !T.empty() ){
        cout << setw(4) << T.dequeue();
    }
    cout << endl;

    system("PAUSE");
    return 0;
}

栈的模板：

C++语言: Codee#5499

// Programme For ACM Lecture
// Written By Alphard
// Date : 2008.4.27

#include <iostream>
#include <iomanip>
using namespace std;

typedef int type;

const int Max_Size = 1000;

class Stack{
private:
    type stack[Max_Size];
    int  top;
public:
    Stack(){
        top = 0;
    }
    void push( type data ){
        if ( top < Max_Size ){
            stack[ top ++ ] = data;
        }
        else{
            cout << "No Enough Space!" << endl;
        }
    }
    type pop(){
        if ( top ){
            return stack[ -- top ];
        }
        else{
            cout << "No Element Now!" << endl;
        }
    }
    bool empty(){
        return !top;
    }
    int  size(){
        return top;
    }
};

int main(){
    Stack T;
    int i;
    for ( i = 1; i <= 8; ++ i ){
        T.push(i);
    }
   
    while ( !T.empty() ){
        cout << setw(4) << T.pop();
    }
    cout << endl;
   
    system("PAUSE");
    return 0;
}

求最大公约数的模板：
C++语言: Codee#5512

int gcd(int a,int b)
{
    int t,c;
    if(a==0)
        return b;
    if(b==0)
        return a;
    if(a<b)
        t=a,a=b,b=t;
    for(c=a%b;c>0;c=a%b)
    {
        a=b;b=c;
    }
    return b;
}
Posted in ACM | Tagged | Leave a comment

pku1915 Knight Moves(bfs)

Posted on 2009-08-19 by
Knight Moves
Time Limit: 1000MS   Memory Limit: 30000K
Total Submissions: 8277   Accepted: 3718

Description

Background
Mr Somurolov, fabulous chess-gamer indeed, asserts that no one else but him can move knights from one position to another so fast. Can you beat him?
The Problem
Your task is to write a program to calculate the minimum number of moves needed for a knight to reach one point from another, so that you have the chance to be faster than Somurolov.
For people not familiar with chess, the possible knight moves are shown in Figure 1.
111

Input

The input begins with the number n of scenarios on a single line by itself.
Next follow n scenarios. Each scenario consists of three lines containing integer numbers. The first line specifies the length l of a side of the chess board (4 <= l <= 300). The entire board has size l * l. The second and third line contain pair of integers {0, ..., l-1}*{0, ..., l-1} specifying the starting and ending position of the knight on the board. The integers are separated by a single blank. You can assume that the positions are valid positions on the chess board of that scenario.

Output

For each scenario of the input you have to calculate the minimal amount of knight moves which are necessary to move from the starting point to the ending point. If starting point and ending point are equal,distance is zero. The distance must be written on a single line.

Sample Input

3
8
0 0
7 0
100
0 0
30 50
10
1 1
1 1

Sample Output

5
28
0
C++语言: Codee#4809

#include <iostream>
#include <queue>
using namespace std;

int step[8][2]={{-2,1},{-2,-1},{2,-1},{2,1},\
                {-1,2},{-1,-2},{1,2},{1,-2}};
int dis[301][301];//这里用dis做标记，如果dis大于0，就说明已访问过
int n;

int BFS(int a,int b,int c,int d)
{
    int x1,x2,y1,y2;
    int i;

    memset(dis,-1,sizeof(dis));//初始化
    dis[a][b]=0;
    queue<int>q;
    q.push(a);
    q.push(b);
    while(!q.empty()){
        x1=q.front();q.pop();
        x2=q.front();q.pop();
        if(x1==c&&x2==d)
                return dis[x1][x2];
        for(i=0;i<8;i++){
            y1=x1+step[i][0];
            y2=x2+step[i][1];
            if(y1<0||y1>=n||y2<0||y2>=n||dis[y1][y2]>0)
                continue;
            dis[y1][y2]=dis[x1][x2]+1;
            q.push(y1);
            q.push(y2);
        }
    }
    return -1;
}
int main()
{
    int a,b,c,d,test;
    scanf("%d",&test);
    for(int i=0;i<test;i++){
        scanf("%d",&n);
        scanf("%d%d%d%d",&a,&b,&c,&d);
        printf("%d\n",BFS(a,b,c,d));
    }
    return 0;
}
Posted in 算法 | Tagged | Leave a comment

八皇后问题（深搜）

Posted on 2009-08-18 by

八皇后问题是一个以国际象棋为背景的问题：如何能够在 8×8 的国际象棋棋盘上放置八个皇后，使得任何一个皇后都无法直接吃掉其他的皇后？为了达到此目的，任两个皇后都不能处于同一条横行、纵行或斜线上。八皇后问题一共有 92 个互不相同的解.
1.定义问题的解空间，这个问题的解空间就是8个皇后在棋盘中的位置。
2.定义解空间的结构，可以使用8×8的数组，因为两个任意的皇后都不能在同行，我们可以用数组下标表示列，数组的值来表示皇后放的行，可简化为一个一维数组。
3.以深度优先的方式搜索解空间，并在搜索过程使用剪枝函数，根据条件：
x[i]==x[k] //判断是否处于同一行
abs(i-k)==abs(x[i]-x[k])判断是否处于同一斜线
我们容易写出剪枝函数：

C++语言: Codee#4769

bool CanPlace(int k)
{
    int i;
    for(i=1;i<k;i++)
    {
        //判断处于同一行或同一斜线
        if(x[i]==x[k]||abs(i-k)==abs(x[i]-x[k]))
            return false;
    }
    return true;
}

关键的深搜函数：
C++语言: Codee#4770

void queen(int i)
{
    int j;
    if(i>8)
    {
        print();
        count++;
        return;
    }
    for(j=1;j<=8;j++)
    {
        x[i]=j;
        if(CanPlace(i))    queen(i+1);
    }
}

完整的程序：

C++语言: Codee#4771

#include <stdio.h>
#include <math.h>

int x[10];
int count=0;//记录解的个数

bool CanPlace(int k)
{
    int i;
    for(i=1;i<k;i++)
    {
        //判断处于同一行或同一斜线
        if(x[i]==x[k]||abs(i-k)==abs(x[i]-x[k]))
            return false;
    }
    return true;
}

void print()
{
    int i;
    for(i=1;i<=8;i++)
        printf("%d ",x[i]);
    printf("\n");
}

void queen(int i)
{
    int j;
    if(i>8)
    {
        print();
        count++;
        return;
    }
    for(j=1;j<=8;j++)
    {
        x[i]=j;
        if(CanPlace(i))    queen(i+1);
    }
}

int main()
{
    queen(1);
    printf("%d\n",count);
    return 0;
}
Posted in 算法 | Tagged | Leave a comment

Crafting Winning Solutions

Posted on 2009-08-08 by
Crafting Winning Solutions

A good way to get a competitive edge is to write down a game plan for what you're going to do in a contest round. This will help you script out your actions, in terms of what to do both when things go right and when things go wrong. This way you can spend your thinking time in the round figuring out programming problems and not trying to figure out what the heck you should do next... it's sort of like precomputing your reactions to most situations.

Mental preparation is also important.

Game Plan For A Contest Round

Read through ALL the problems FIRST; sketch notes with algorithm, complexity, the numbers, data structs, tricky details, ...

  • Brainstorm many possible algorithms - then pick the stupidest that works!
  • DO THE MATH! (space & time complexity, and plug in actual expected and worst case numbers)
  • Try to break the algorithm - use special (degenerate?) test cases
  • Order the problems: shortest job first, in terms of your effort (shortest to longest: done it before, easy, unfamiliar, hard)

Coding a problem - For each, one at a time:

  • Finalize algorithm
  • Create test data for tricky cases
  • Write data structures
  • Code the input routine and test it (write extra output routines to show data?)
  • Code the output routine and test it
  • Stepwise refinement: write comments outlining the program logic
  • Fill in code and debug one section at a time
  • Get it working & verify correctness (use trivial test cases)
  • Try to break the code - use special cases for code correctness
  • Optimize progressively - only as much as needed, and keep all versions (use hard test cases to figure out actual runtime)

Time management strategy and "damage control" scenarios

Have a plan for what to do when various (foreseeable!) things go wrong; imagine problems you might have and figure out how you want to react. The central question is: "When do you spend more time debugging a program, and when do you cut your losses and move on?". Consider these issues:

  • How long have you spent debugging it already?
  • What type of bug do you seem to have?
  • Is your algorithm wrong?
  • Do you data structures need to be changed?
  • Do you have any clue about what's going wrong?
  • A short amount (20 mins) of debugging is better than switching to anything else; but you might be able to solve another from scratch in 45 mins.
  • When do you go back to a problem you've abandoned previously?
  • When do you spend more time optimizing a program, and when do you switch?
  • Consider from here out - forget prior effort, focus on the future: how can you get the most points in the next hour with what you have?

Have a checklist to use before turning in your solutions:

  • Code freeze five minutes before end of contest?
  • Turn asserts off.
  • Turn off debugging output.

Tips & Tricks

  • Brute force it when you can
  • KISS: Simple is smart!
  • Hint: focus on limits (specified in problem statement)
  • Waste memory when it makes your life easier (if you can get away with it)
  • Don't delete your extra debugging output, comment it out
  • Optimize progressively, and only as much as needed
  • Keep all working versions!
  • Code to debug:
    • whitespace is good,
    • use meaningful variable names,
    • don't reuse variables,
    • stepwise refinement,
    • COMMENT BEFORE CODE.
  • Avoid pointers if you can
  • Avoid dynamic memory like the plague: statically allocate everything.
  • Try not to use floating point; if you have to, put tolerances in everywhere (never test equality)
  • Comments on comments:
    • Not long prose, just brief notes
    • Explain high-level functionality: ++i; /* increase the value of i by */ is worse than useless
    • Explain code trickery
    • Delimit & document functional sections
    • As if to someone intelligent who knows the problem, but not the code
    • Anything you had to think about
    • Anything you looked at even once saying, "now what does that do again?"
    • Always comment order of array indices
  • Keep a log of your performance in each contest: successes, mistakes, and what you could have done better; use this to rewrite and improve your game plan!

Complexity

Basics and order notation

The fundamental basis of complexity analysis revolves around the notion of ``big oh'' notation, for instance: O(N). This means that the algorithm's execution speed or memory usage will double when the problem size doubles. An algorithm of O(N 2) will run about four times slower (or use 4x more space) when the problem size doubles. Constant-time or space algorithms are denoted O(1). This concept applies to time and space both; here we will concentrate discussion on time.

One deduces the O() run time of a program by examining its loops. The most nested (and hence slowest) loop dominates the run time and is the only one mentioned when discussing O() notation. A program with a single loop and a nested loop (presumably loops that execute N times each) is O(N 2), even though there is also a O(N) loop present.

Of course, recursion also counts as a loop and recursive programs can have orders like O(b N), O(N!), or even O(N N).

Rules of thumb

  • When analyzing an algorithm to figure out how long it might run for a given dataset, the first rule of thumb is: modern (2004) computers can deal with 100M actions per second. In a five second time limit program, about 500M actions can be handled. Really well optimized programs might be able to double or even quadruple that number. Challenging algorithms might only be able to handle half that much. Current contests usually have a time limit of 1 second for large datasets.
  • 16MB maximum memory use
  • 210 ~approx~ 10 3
  • If you have k nested loops running about N iterations each, the program has O(N k) complexity.
  • If your program is recursive with b recursive calls per level and has l levels, the program O(b l) complexity.
  • Bear in mind that there are N! permutations and 2 n subsets or combinations of N elements when dealing with those kinds of algorithms.
  • The best times for sorting N elements are O(N log N).
  • DO THE MATH! Plug in the numbers.

Examples

A single loop with N iterations is O(N):

 1  sum = 0
 2  for i = 1 to n
 3    sum = sum + i

A double nested loop is often O(N 2):

# fill array a with N elements
1 for i = 1 to n-1
2   for j = i + 1 to n
3     if (a[i] > a[j])
         swap (a[i], a[j])
Note that even though this loop executes N x (N+1) / 2 iterations of the if statement, it is O(N 2) since doubling N quadruples the execution times.

Consider this well balanced binary tree with four levels:
12
An algorithm that traverses a general binary tree will have complexity O(2 N).

Solution Paradigms

Generating vs. Filtering

Programs that generate lots of possible answers and then choose the ones that are correct (imagine an 8-queen solver) are filters. Those that hone in exactly on the correct answer without any false starts are generators. Generally, filters are easier (faster) to code and run slower. Do the math to see if a filter is good enough or if you need to try and create a generator.

Precomputation

Sometimes it is helpful to generate tables or other data structures that enable the fastest possible lookup of a result. This is called precomputation (in which one trades space for time). One might either compile precomputed data into a program, calculate it when the program starts, or just remember results as you compute them. A program that must translate letters from upper to lower case when they are in upper case can do a very fast table lookup that requires no conditionals, for example. Contest problems often use prime numbers - many times it is practical to generate a long list of primes for use elsewhere in a program.

Decomposition (The Hardest Thing At Programming Contests)

While there are fewer than 20 basic algorithms used in contest problems, the challenge of combination problems that require a combination of two algorithms for solution is daunting. Try to separate the cues from different parts of the problem so that you can combine one algorithm with a loop or with another algorithm to solve different parts of the problem independently. Note that sometimes you can use the same algorithm twice on different (independent!) parts of your data to significantly improve your running time.

Symmetries

Many problems have symmetries (e.g., distance between a pair of points is often the same either way you traverse the points). Symmetries can be 2-way, 4-way, 8-way, and more. Try to exploit symmetries to reduce execution time.

For instance, with 4-way symmetry, you solve only one fourth of the problem and then write down the four solutions that share symmetry with the single answer (look out for self-symmetric solutions which should only be output once or twice, of course).

Forward vs. Backward

Surprisingly, many contest problems work far better when solved backwards than when using a frontal attack. Be on the lookout for processing data in reverse order or building an attack that looks at the data in some order or fashion other than the obvious.

Simplification

Some problems can be rephrased into a somewhat different problem such that if you solve the new problem, you either already have or can easily find the solution to the original one; of course, you should solve the easier of the two only. Alternatively, like induction, for some problems one can make a small change to the solution of a slightly smaller problem to find the full answer.

Posted in 算法 | Leave a comment

Greedy Algorithm

Posted on 2009-08-07 by

 

Greedy Algorithm

Sample Problem: Barn Repair [1999 USACO Spring Open]

There is a long list of stalls, some of which need to be covered with boards. You can use up to N (1 <= N <= 50) boards, each of which may cover any number of consecutive stalls. Cover all the necessary stalls, while covering as few total stalls as possible.

The Idea

The basic idea behind greedy algorithms is to build large solutions up from smaller ones. Unlike other approaches, however, greedy algorithms keep only the best solution they find as they go along. Thus, for the sample problem, to build the answer for N = 5, they find the best solution for N = 4, and then alter it to get a solution for N = 5. No other solution for N = 4 is ever considered.

Greedy algorithms are fast, generally linear to quadratic and require little extra memory. Unfortunately, they usually aren't correct. But when they do work, they are often easy to implement and fast enough to execute.

Problems

There are two basic problems to greedy algorithms.

How to Build

How does one create larger solutions from smaller ones? In general, this is a function of the problem. For the sample problem, the most obvious way to go from four boards to five boards is to pick a board and remove a section, thus creating two boards from one. You should choose to remove the largest section from any board which covers only stalls which don't need covering (so as to minimize the total number of stalls covered).

To remove a section of covered stalls, take the board which spans those stalls, and make into two boards: one of which covers the stalls before the section, one of which covers the stalls after the section.

Does it work?

The real challenge for the programmer lies in the fact that greedy solutions don't always work. Even if they seem to work for the sample input, random input, and all the cases you can think of, if there's a case where it won't work, at least one (if not more!) of the judges' test cases will be of that form.

For the sample problem, to see that the greedy algorithm described above works, consider the following:

Assume that the answer doesn't contain the large gap which the algorithm removed, but does contain a gap which is smaller. By combining the two boards at the end of the smaller gap and splitting the board across the larger gap, an answer is obtained which uses as many boards as the original solution but which covers fewer stalls. This new answer is better, so therefore the assumption is wrong and we should always choose to remove the largest gap.

If the answer doesn't contain this particular gap but does contain another gap which is just as large, doing the same transformation yields an answer which uses as many boards and covers as many stalls as the other answer. This new answer is just as good as the original solution but no better, so we may choose either.

Thus, there exists an optimal answer which contains the large gap, so at each step, there is always an optimal answer which is a superset of the current state. Thus, the final answer is optimal.

Conclusions

If a greedy solution exists, use it. They are easy to code, easy to debug, run quickly, and use little memory, basically defining a good algorithm in contest terms. The only missing element from that list is correctness. If the greedy algorithm finds the correct answer, go for it, but don't get suckered into thinking the greedy solution will work for all problems.

Sample Problems

Sorting a three-valued sequence [IOI 1996]

You are given a three-valued (1, 2, or 3) sequence of length up to 1000. Find a minimum set of exchanges to put the sequence in sorted order.

Algorithm The sequence has three parts: the part which will be 1 when in sorted order, 2 when in sorted order, and 3 when in sorted order. The greedy algorithm swaps as many as possible of the 1's in the 2 part with 2's in the 1 part, as many as possible 1's in the 3 part with 3's in the 1 part, and 2's in the 3 part with 3's in the 2 part. Once none of these types remains, the remaining elements out of place need to be rotated one way or the other in sets of 3. You can optimally sort these by swapping all the 1's into place and then all the 2's into place.

Analysis: Obviously, a swap can put at most two elements in place, so all the swaps of the first type are optimal. Also, it is clear that they use different types of elements, so there is no ``interference'' between those types. This means the order does not matter. Once those swaps have been performed, the best you can do is two swaps for every three elements not in the correct location, which is what the second part will achieve (for example, all the 1's are put in place but no others; then all that remains are 2's in the 3's place and vice-versa, and which can be swapped).

Friendly Coins - A Counterexample [abridged]

Given the denominations of coins for a newly founded country, the Dairy Republic, and some monetary amount, find the smallest set of coins that sums to that amount. The Dairy Republic is guaranteed to have a 1 cent coin.

Algorithm: Take the largest coin value that isn't more than the goal and iterate on the total minus this value.

(Faulty) Analysis: Obviously, you'd never want to take a smaller coin value, as that would mean you'd have to take more coins to make up the difference, so this algorithm works.

Maybe not: Okay, the algorithm usually works. In fact, for the U.S. coin system {1, 5, 10, 25}, it always yields the optimal set. However, for other sets, like {1, 5, 8, 10} and a goal of 13, this greedy algorithm would take one 10, and then three 1's, for a total of four coins, when the two coin solution {5, 8} also exists.

Topological Sort

Given a collection of objects, along with some ordering constraints, such as "A must be before B," find an order of the objects such that all the ordering constraints hold.

Algorithm: Create a directed graph over the objects, where there is an arc from A to B if "A must be before B." Make a pass through the objects in arbitrary order. Each time you find an object with in-degree of 0, greedily place it on the end of the current ordering, delete all of its out-arcs, and recurse on its (former) children, performing the same check. If this algorithm gets through all the objects without putting every object in the ordering, there is no ordering which satisfies the constraints.

Posted in 算法 | Tagged | Leave a comment

1.3Prime Cryptarithm

Posted on 2009-08-07 by

Prime Cryptarithm
The following cryptarithm is a multiplication problem that can be solved by substituting digits from a specified set of N digits into the positions marked with *. If the set of prime digits {2,3,5,7} is selected, the cryptarithm is called a PRIME CRYPTARITHM.

      * * *
   x    * *
    -------
      * * *         <-- partial product 1
    * * *           <-- partial product 2
    -------
    * * * *

Digits can appear only in places marked by `*'. Of course, leading zeroes are not allowed.

Note that the 'partial products' are as taught in USA schools. The first partial product is the product of the final digit of the second number and the top number. The second partial product is the product of the first digit of the second number and the top number.

Write a program that will find all solutions to the cryptarithm above for any subset of digits from the set {1,2,3,4,5,6,7,8,9}.

PROGRAM NAME: crypt1

INPUT FORMAT

Line 1: N, the number of digits that will be used
Line 2: N space separated digits with which to solve the cryptarithm

SAMPLE INPUT (file crypt1.in)

5
2 3 4 6 8

OUTPUT FORMAT

A single line with the total number of unique solutions. Here is the single solution for the sample input:

      2 2 2
    x   2 2
     ------
      4 4 4
    4 4 4
  ---------
    4 8 8 4

SAMPLE OUTPUT (file crypt1.out)

1
C++语言: Codee#4277

/*
ID: fengu
PROG: crypt1
LANG: C++
*/
#include <stdio.h>
int n;
int d[10];

int belong(int b)
{
    int i;
    for(i=0;i<n;i++)
    {
        if(b==d[i])
            return 1;
    }
    return 0;
}

bool Islegal(int a)
{
    while(belong(a%10))
    {
        a/=10;
    }
    if(a==0)
        return true;
    else
        return false;
}

int main()
{
    int count=0,i,flag;
    int s1,s2;
    FILE *fin=fopen("crypt1.in","r");
    FILE *fout=fopen("crypt1.out","w");

    fscanf(fin,"%d",&n);
    for(i=0;i<n;i++)
        fscanf(fin,"%d",&d[i]);

    for(s1=111;s1<999;s1++)
    {
        for(s2=11;s2<99;s2++)
        {
            if(((s1/100)*(s2/10)+((s1/10)%10)*(s2/10)/10)>9)
                flag=0;
            if(((s1/100)*(s2%10)+((s1/10)%10)*(s2%10)/10)>9)
                flag=0;
            if(s1*s2>9999)
                flag=0;
            if(!(Islegal(s1) && Islegal(s2) && Islegal(s1*(s2/10)) && Islegal(s1*(s2%10)) && Islegal(s1*s2)))
                flag=0;
            if(flag==1)
                count++;
            flag=1;
        }
    }
    fprintf(fout,"%d\n",count);
    return 0;
}
Posted in USACO | Tagged | Leave a comment

1.3Calf Flac

Posted on 2009-08-07 by

Calf Flac
It is said that if you give an infinite number of cows an infinite number of heavy-duty laptops (with very large keys), that they will ultimately produce all the world's great palindromes. Your job will be to detect these bovine beauties.

Ignore punctuation, whitespace, numbers, and case when testing for palindromes, but keep these extra characters around so that you can print them out as the answer; just consider the letters `A-Z' and `a-z'.

Find any largest palindrome in a string no more than 20,000 characters long. The largest palindrome is guaranteed to be at most 2,000 characters long before whitespace and punctuation are removed.

PROGRAM NAME: calfflac

INPUT FORMAT

A file with no more than 20,000 characters. The file has one or more lines. No line is longer than 80 characters (not counting the newline at the end).

SAMPLE INPUT (file calfflac.in)

Confucius say: Madam, I'm Adam.

OUTPUT FORMAT

The first line of the output should be the length of the longest palindrome found. The next line or lines should be the actual text of the palindrome (without any surrounding white space or punctuation but with all other characters) printed on a line (or more than one line if newlines are included in the palindromic text). If there are multiple palindromes of longest length, output the one that appears first.

SAMPLE OUTPUT (file calfflac.out)

11
Madam, I'm Adam
C++语言: Codee#4276

/*
ID: fengu
PROG: calfflac
LANG: C++
*/
#include <iostream>
using namespace std;

typedef struct text
{
    char ch;
    int pos;
}text;

int main()
{
    char a[2000001],ch;
    text b[200001];
    int len=0,l=-1;
    int pal=1,p;
    int i,sta,end;
    FILE *fin=fopen("calfflac.in","r");
    FILE *fout=fopen("calfflac.out","w");

    while(fscanf(fin,"%c",&ch)!=EOF)
        a[len++]=ch;

    for(i=0;i<len;i++)
    {
        if(isalpha(a[i]))
        {
            b[++l].ch=toupper(a[i]);
            b[l].pos=i;
        }
    }

    for(i=0;i<=l;i++)
    {
        p=1;
        while( i-p>=0 && i+p<=l && b[i-p].ch==b[i+p].ch )    p++;
        p--;
        if(p*2+1>pal)
        {
            pal=p*2+1;
            sta=b[i-p].pos;
            end=b[i+p].pos;
        }
    }
   
    for(i=0;i<=l;i++)
    {
        p=0;
        while( i-p>=0 && i+1+p<=l && b[i-p].ch==b[i+1+p].ch )    p++;
        p--;
        if(p*2+2>pal)
        {
            pal=p*2+2;
            sta=b[i-p].pos;
            end=b[i+1+p].pos;
        }
    }

    fprintf(fout,"%d\n",pal);
    for(i=sta;i<=end;i++)
    {
        fprintf(fout,"%c",a[i]);
    }
    fprintf(fout,"\n");
    return 0;
}
Posted in USACO | Tagged | Leave a comment

1.3Barn Repair

Posted on 2009-08-07 by

Barn Repair

It was a dark and stormy night that ripped the roof and gates off the stalls that hold Farmer John's cows. Happily, many of the cows were on vacation, so the barn was not completely full.

The cows spend the night in stalls that are arranged adjacent to each other in a long line. Some stalls have cows in them; some do not. All stalls are the same width.

Farmer John must quickly erect new boards in front of the stalls, since the doors were lost. His new lumber supplier will supply him boards of any length he wishes, but the supplier can only deliver a small number of total boards. Farmer John wishes to minimize the total length of the boards he must purchase.

Given M (1 <= M <= 50), the maximum number of boards that can be purchased; S (1 <= S <= 200), the total number of stalls; C (1 <= C <= S) the number of cows in the stalls, and the C occupied stall numbers (1 <= stall_number <= S), calculate the minimum number of stalls that must be blocked in order to block all the stalls that have cows in them.

Print your answer as the total number of stalls blocked.

PROGRAM NAME: barn1

INPUT FORMAT

Line 1: M, S, and C (space separated)
Lines 2-C+1: Each line contains one integer, the number of an occupied stall.

SAMPLE INPUT (file barn1.in)

4 50 18
3
4
6
8
14
15
16
17
21
25
26
27
30
31
40
41
42
43

OUTPUT FORMAT

A single line with one integer that represents the total number of stalls blocked.

SAMPLE OUTPUT (file barn1.out)

25

[One minimum arrangement is one board covering stalls 3-8, one covering 14-21, one covering 25-31, and one covering 40-43.]

分析：从N1（一块板）到N2就是贪心的除掉空的间隔最大的那部分，再根据N2依次求出N3，等等。我设了一个数组dis[]来存储间隔，比如间隔如果是5，那么dis[5]++，之后根据板的个数，知道需要减去几个间隔，开始遍历数组,大的间隔优先减去，最后得到了总的没有覆盖的部分，总牛栏数减去这个没有覆盖的牛栏数就是答案。
C++语言: Codee#4275
/*
ID: fengu
PROG: barn1
LANG: C
*/
#include <stdio.h>
#include <memory.h>
#include <stdlib.h>

cmp(const void *va,const void *vb)
{
    return *(int*)va-*(int*)vb;
}

int main()
{
    int m,s,c;
    int cows[200],dis[201];
    int i,j,d,blocked=0;

    FILE *fin=fopen("barn1.in","r");
    FILE *fout=fopen("barn1.out","w");
    memset(dis,0,sizeof(dis));

    //输入
    fscanf(fin,"%d%d%d",&m,&s,&c);//boards,stalls,cows
    for(i=0;i<c;i++)
        fscanf(fin,"%d",&cows[i]);
    qsort(cows,c,sizeof(cows[0]),cmp);

    //把距离算好存储在dis[]
    for(i=0;i<c-1;i++)
    {
        d=cows[i+1]-cows[i]-1;
        if(d!=0)
            dis[d]++;
    }
    //间隔比板的数量少1
    for(i=0;i<m-1;i++)
        for(j=s;j>=0;j--)
        {
            if(dis[j]!=0)
            {
                dis[j]--;
                blocked+=j;
                break;
            }
        }
    blocked+=(cows[0]-1)+(s-cows[c-1]);
    fprintf(fout,"%d\n",s-blocked);

    return 0;
}

Posted in USACO | Tagged | Leave a comment

1.3Mixing Milk

Posted on 2009-08-07 by

Mixing Milk

Since milk packaging is such a low margin business, it is important to keep the price of the raw product (milk) as low as possible. Help Merry Milk Makers get the milk they need in the cheapest possible manner.

The Merry Milk Makers company has several farmers from which they may buy milk, and each one has a (potentially) different price at which they sell to the milk packing plant. Moreover, as a cow can only produce so much milk a day, the farmers only have so much milk to sell per day. Each day, Merry Milk Makers can purchase an integral amount of milk from each farmer, less than or equal to the farmer's limit.

Given the Merry Milk Makers' daily requirement of milk, along with the cost per gallon and amount of available milk for each farmer, calculate the minimum amount of money that it takes to fulfill the Merry Milk Makers' requirements.

Note: The total milk produced per day by the farmers will be sufficient to meet the demands of the Merry Milk Makers.

PROGRAM NAME: milk

INPUT FORMAT

Line 1: Two integers, N and M.
The first value, N, (0 <= N <= 2,000,000) is the amount of milk that Merry Milk Makers' want per day. The second, M, (0 <= M <= 5,000) is the number of farmers that they may buy from.
Lines 2 through M+1: The next M lines each contain two integers, Pi and Ai.
Pi (0 <= Pi <= 1,000) is price in cents that farmer i charges.
Ai (0 <= Ai <= 2,000,000) is the amount of milk that farmer i can sell to Merry Milk Makers per day.

 

SAMPLE INPUT (file milk.in)

100 5
5 20
9 40
3 10
8 80
6 30

OUTPUT FORMAT

A single line with a single integer that is the minimum price that Merry Milk Makers can get their milk at for one day.

SAMPLE OUTPUT (file milk.out)

630

分析：c语言里的快排，这里用到，qsort在库#include <stdlib.h>里，
fcmp(const void *va,const void *vb)
{
    return ((farmer*)va)->p-((farmer*)vb)->p;
}
qsort(f,nfarmer,sizeof(f[0]),fcmp);
题目不难，先把输入的牛奶按照价格排序，贪心的从价格低的开始买，直到达到需要的总量为止。
C++语言: Codee#4274
/*
ID: fengu
PROG: milk
LANG: C
*/
#include <stdio.h>
#include <stdlib.h>

typedef struct farmer
{
    int p;
    int a;
}farmer;

fcmp(const void *va,const void *vb)
{
    return ((farmer*)va)->p-((farmer*)vb)->p;
}

int main()
{
    farmer f[5000];
    int n,nfarmer,i;
    int cost=0;
    FILE *fin=fopen("milk.in","r");
    FILE *fout=fopen("milk.out","w");
    //输入并排序
    fscanf(fin,"%d%d",&n,&nfarmer);/*牛奶总量和农民个数*/
    for(i=0;i<nfarmer;i++)
    {
        fscanf(fin,"%d%d",&f[i].p,&f[i].a);
    }
    qsort(f,nfarmer,sizeof(f[0]),fcmp);

    for(i=0;i<nfarmer;i++)
    {
        if(f[i].a<n)
        {
            cost+=f[i].a*f[i].p;
            n=n-f[i].a;
        }
        else
        {
            cost+=n*f[i].p;
            n=0;
        }
    }
    fprintf(fout,"%d\n",cost);
    return 0;
}

另一种方法是设一个数组，把各个价格的牛奶数都记录在里面，用a[price]表示价格为price的牛奶数，最后遍历数组从价格小的开始直到满足需求：
usaco上的一个漂亮的代码：

C++语言: Codee#4321

#include <iostream>
#include <fstream>

#define MAXP 1000

using namespace std;

int main() {
    ifstream in("milk.in");
    ofstream out("milk.out");
   
    int N, M;
    int P[MAXP+1];
   
    in >> N >> M;
    for (int i = 0; i <= MAXP; i++) P[i]=0;
    for (int i = 0; i < M; i++) {
        int price, amt;
        in >> price >> amt;
       
         // we can add amounts that cost the same price
        // since x gallons costing c cents and
        //          y gollons costing c cents
        // is the same as
        //      x+y gallons costing c cents
        P[price] += amt;
    }
   
    // greedy choice: take as much of the item that
    // has the least price per gallon
    int res = 0;
    for (int p = 0; p<=MAXP && N>0; p++) {
        if (P[p]>0) {
            res+=p*(N<P[p]?N:P[p]);
            N-=P[p];
        }
    }
    out << res << endl;
   
    in.close();
    out.close();
   
    return 0;
}
Posted in USACO | Tagged | Leave a comment

1.2Dual Palindromes

Posted on 2009-08-07 by

Dual Palindromes
Mario Cruz (Colombia) & Hugo Rickeboer (Argentina)A number that reads the same from right to left as when read from left to right is called a palindrome. The number 12321 is a palindrome; the number 77778 is not. Of course, palindromes have neither leading nor trailing zeroes, so 0220 is not a palindrome.

The number 21 (base 10) is not palindrome in base 10, but the number 21 (base 10) is, in fact, a palindrome in base 2 (10101).

Write a program that reads two numbers (expressed in base 10):

  • N (1 <= N <= 15)
  • S (0 < S < 10000)

and then finds and prints (in base 10) the first N numbers strictly greater than S that are palindromic when written in two or more number bases (2 <= base <= 10).

Solutions to this problem do not require manipulating integers larger than the standard 32 bits.

PROGRAM NAME: dualpal

INPUT FORMAT

A single line with space separated integers N and S.

SAMPLE INPUT (file dualpal.in)

3 25

OUTPUT FORMAT

N lines, each with a base 10 number that is palindromic when expressed in at least two of the bases 2..10. The numbers should be listed in order from smallest to largest.

SAMPLE OUTPUT (file dualpal.out)

26
27
28
C++语言: Codee#4273
/*
ID: fengu
LANG: C++
TASK: dualpal
*/
#include <stdio.h>
#include <string.h>

//判断是不是回文数
int IsPal(char *s,int len)
{
    int l=0,r=len-1;
    while(l<r)
    {
        if(s[l]!=s[r])
            return 0;
        l++;r--;
    }
    return 1;
}

//求出相应的进制数
void numtrans(char *c,int n,int b)
{
    char a[30];
    char t[15]="0123456789";
    int k=0,r,l;

    while(n!=0)
    {
        a[k++]=t[n%b];
        n=n/b;
    }
    a[k]='\0';
    for(r=0,l=strlen(a)-1;l>=0;r++,l--)
    {
        c[r]=a[l];
    }
    c[r]='\0';
}

int main()
{
    int c1=0,c2=0;
    int n,s,i,j,len;
    char c[30];
    FILE *fin=fopen("dualpal.in","r");
    FILE *fout=fopen("dualpal.out","w");
    fscanf(fin,"%d%d",&n,&s);
    for(i=s+1;c1!=n;i++)
    {
        for(j=2;j<11;j++)
        {
           numtrans(c,i,j);
           len=strlen(c);
           if(IsPal(c,len))
               c2++;
        }
        if(c2>=2)
        {
            fprintf(fout,"%d\n",i);
            c1++;
        }
        c2=0;
    }
    return 0;
}

Posted in USACO | Tagged | Leave a comment