Knight Moves

---

Time limit: 1 Seconds   Memory limit: 32768K  
Total Submit: 1163   Accepted Submit: 635  

---

A friend of you is doing research on the Traveling Knight Problem (TKP) where you are to find the shortest closed tour of knight moves that visits each square of a given set of n squares on a chessboard exactly once. He thinks that the most difficult part of the problem is determining the smallest number of knight moves between two given squares and that, once you have accomplished this, finding the tour would be easy.
Of course you know that it is vice versa. So you offer him to write a program that solves the "difficult" part.

Your job is to write a program that takes two squares a and b as input and then determines the number of knight moves on a shortest route from a to b.

Input Specification

The input file will contain one or more test cases. Each test case consists of one line containing two squares separated by one space. A square is a string consisting of a letter (a-h) representing the column and a digit (1-8) representing the row on the chessboard.

Output Specification

For each test case, print one line saying "To get from xx to yy takes n knight moves.".

Sample Input

e2 e4
a1 b2
b2 c3
a1 h8
a1 h7
h8 a1
b1 c3
f6 f6

Sample Output

To get from e2 to e4 takes 2 knight moves.
To get from a1 to b2 takes 4 knight moves.
To get from b2 to c3 takes 2 knight moves.
To get from a1 to h8 takes 6 knight moves.
To get from a1 to h7 takes 5 knight moves.
To get from h8 to a1 takes 6 knight moves.
To get from b1 to c3 takes 1 knight moves.
To get from f6 to f6 takes 0 knight moves.

---

问跳马步到定点的最小步数。可以判重BFS，也可以用公式。
#include <iostream>
#include <string>
using namespace std;

int minKightStep(int a, int b){ //a >= 0 && b >= 0
 if(a > b) swap(a, b);
 if(a == 0){
  if(b == 0) return 0;
  if(b == 1) return 3;
  if(b == 2) return 2;
  if(b == 6) return 4;
 }
 if(a == 1 && b == 4) return 3;
 if(a == 2 && b == 2) return 4;

 int u = min(min((a+b) / 3, (2*a+b) / 4) , (a+2*b) / 4);
 return a+b-2*u;

}

int main()
{
 string s1,s2;
 int ax,ay,bx,by;

 while(cin >> s1 >> s2)
 {
  if ( s1 == s2 )
  {
   cout << "To get from " << s1 << " to " << s2 << " takes 0 knight moves.";
   continue;
  }

  ax = s1[0]-'a';
  ay = s1[1]-'1';
  bx = s2[0]-'a';
  by = s2[1]-'1';

  cout << minKightStep(ax*8+ay,bx*8+by) << endl;
 }

}

Web Navigation

---

Time limit: 1 Seconds   Memory limit: 32768K  
Total Submit: 1815   Accepted Submit: 618  

---

Standard web browsers contain features to move backward and forward among the pages recently visited. One way to implement these features is to use two stacks to keep track of the pages that can be reached by moving backward and forward. In this problem, you are asked to implement this.

The following commands need to be supported:

BACK: Push the current page on the top of the forward stack. Pop the page from the top of the backward stack, making it the new current page. If the backward stack is empty, the command is ignored.

FORWARD: Push the current page on the top of the backward stack. Pop the page from the top of the forward stack, making it the new current page. If the forward stack is empty, the command is ignored.

VISIT <url>: Push the current page on the top of the backward stack, and make the URL specified the new current page. The forward stack is emptied.

QUIT: Quit the browser.

Assume that the browser initially loads the web page at the URL http://www.acm.org/

This problem contains multiple test cases!

The first line of a multiple input is an integer N, then a blank line followed by N input blocks. Each input block is in the format indicated in the problem description. There is a blank line between input blocks.

The output format consists of N output blocks. There is a blank line between output blocks.

Input

Input is a sequence of commands. The command keywords BACK, FORWARD, VISIT, and QUIT are all in uppercase. URLs have no whitespace and have at most 70 characters. You may assume that no problem instance requires more than 100 elements in each stack at any time. The end of input is indicated by the QUIT command.

Output

For each command other than QUIT, print the URL of the current page after the command is executed if the command is not ignored. Otherwise, print "Ignored". The output for each command should be printed on its own line. No output is produced for the QUIT command.

Sample Input

1

VISIT http://acm.ashland.edu/
VISIT http://acm.baylor.edu/acmicpc/
BACK
BACK
BACK
FORWARD
VISIT http://www.ibm.com/
BACK
BACK
FORWARD
FORWARD
FORWARD
QUIT

Sample Output

http://acm.ashland.edu/
http://acm.baylor.edu/acmicpc/
http://acm.ashland.edu/
http://www.acm.org/
Ignored
http://acm.ashland.edu/
http://www.ibm.com/
http://acm.ashland.edu/
http://www.acm.org/
http://acm.ashland.edu/
http://www.ibm.com/
Ignored

---

Problem Source: East Central North America 2001

模拟上网浏览的秒杀题。
#include <iostream>
#include <stack>
#include<vector>

#include <string>
using namespace std;

vector<string> vs;
vector<int> ord;

stack<string> s1;
stack<string> s2;
int main()
{

 int d;
 cin >> d;
 for(int i  =0;i < d;i++)
 {
  while(!s1.empty())
   s1.pop();
  s1.push("http://www.acm.org/");
  while(!s2.empty() )
   s2.pop();
        string s;

  while( cin >> s )
  {
   if ( s == "QUIT")
    break;
   if ( s == "VISIT")
   {
    cin >> s;
    s1.push(s);
    cout << s << endl;
    while(!s2.empty())
     s2.pop();
   }
   if ( s == "BACK")
   {
    if ( s1.size() == 1 )
     cout << "Ignored" << endl;
    else
    {
     s2.push(s1.top());
     s1.pop();
     cout << s1.top() << endl;

    }
   }
   if ( s == "FORWARD")
   {
    if (s2.empty() )
     cout << "Ignored" << endl;
    else
    {
     cout << s2.top() << endl;
     s1.push(s2.top());
     s2.pop();    
    }
   }
   
  }
  if ( i != d-1 ) cout << endl;
 }
 
 return 0;
}

A New Growth Industry

---

Time limit: 1 Seconds   Memory limit: 32768K  
Total Submit: 867   Accepted Submit: 292  

---

A biologist experimenting with DNA modification of bacteria has found a way to make bacterial colonies sensitive to the
surrounding population density. By changing the DNA, he is able to “program” the bacteria to respond to the varying densities in their immediate neighborhood.

The culture dish is a square, divided into 400 smaller squares (20x20). Population in each small square is measured on a four point scale (from 0 to 3). The DNA information is represented as an array D, indexed from 0 to 15, of integer values and is interpreted as follows:

In any given culture dish square, let K be the sum of that square's density and the densities of the four squares immediately to the left, right, above and below that square (squares outside the dish are considered to have density 0). Then, by the next day, that dish square's density will change by D[K] (which may be a positive, negative, or zero value). The total density cannot, however, exceed 3 nor drop below 0.

Now, clearly, some DNA programs cause all the bacteria to die off (e.g., [-3, -3, …, -3]). Others result in immediate population explosions (e.g., [3,3,3, …, 3]), and others are just plain boring (e.g., [0, 0, … 0]). The biologist is interested in how some of the less obvious DNA programs might behave.

Write a program to simulate the culture growth, reading in the number of days to be simulated, the DNA rules, and the initial population densities of the dish.


Input Format:

Input to this program consists of three parts:

1. The first line will contain a single integer denoting the number of days to be simulated.

2. The second line will contain the DNA rule D as 16 integer values, ordered from D[0] to D[15], separated from one another by one or more blanks. Each integer will be in the range -3…3, inclusive.

3. The remaining twenty lines of input will describe the initial population density in the culture dish. Each line describes one row of squares in the culture dish, and will contain 20 integers in the range 0…3, separated from one another by 1 or more blanks.

Output Format:

The program will produce exactly 20 lines of output, describing the population densities in the culture dish at the end of the simulation. Each line represents a row of squares in the culture dish, and will consist of 20 characters, plus the usual end-of-line terminator.

Each character will represent the population density at a single dish square, as follows:

No other characters may appear in the output.

This problem contains multiple test cases!

The first line of a multiple input is an integer N, then a blank line followed by N input blocks. Each input block is in the format indicated in the problem description. There is a blank line between input blocks.

The output format consists of N output blocks. There is a blank line between output blocks.

Sample Input:

1

2
0 1 1 1 2 1 0 -1 -1 -1 -2 -2 -3 -3 -3 -3
3 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 3 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

Sample Output:

##!.................
#!..................
!...................
....................
....................
....................
....................
.........!..........
........!#!.........
.......!#X#!........
........!#!.........
.........!..........
....................
....................
....................
....................
....................
....................
....................
....................

---

Problem Source: Mid-Atlantic USA 2001

扩散算法。。
#include<cstdio>
#include<cstdlib>
#include<string>
#include<cmath>

int Day, D[16], Square[20][20];
int Square2[20][20];
char *Sign = ".!X#";

int Run ()
{
 int i, j, k, m;
 for (i = 0; i < Day; i ++)
 {
  for (j = 0; j < 20; j ++)
   for (k = 0; k < 20; k ++)
   {
    m = Square[j][k];
    if (j - 1 >= 0)
     m += Square[j - 1][k];
    if (j + 1 < 20)
     m += Square[j + 1][k];
    if (k - 1 >= 0)
     m += Square[j][k - 1];
    if (k + 1 < 20)
     m += Square[j][k + 1];

    Square2[j][k] = Square[j][k] + D[m];
    if (Square2[j][k] > 3)
     Square2[j][k] = 3;
    if (Square2[j][k] < 0)
     Square2[j][k] = 0;
   }

   memcpy (Square, Square2, sizeof(Square[0][0]) * 20 * 20);
 }

 for (i = 0; i < 20; i ++)
 {
  for (j = 0; j < 20; j ++)
   printf ("%c", Sign[Square2[i][j]]);
  printf ("\n");
 }

 return 0;
}

int main()
{

 int j, k, t, aa = 1;
 scanf( "%d", &t);
 while (t --) {
  if (aa) aa = 0; else printf("\n");
  scanf ( "%d", &Day);
  for (j = 0; j < 16; j ++)
   scanf ( "%d", &D[j]);
  for (j = 0; j < 20; j ++)
   for (k = 0; k < 20; k ++)
    scanf ( "%d", &Square[j][k]);
  Run ();
 }

 return 0;
}

 

Count the Colors

---

Time limit: 1 Seconds   Memory limit: 32768K  
Total Submit: 975   Accepted Submit: 305  

---

Painting some colored segments on a line, some previously painted segments may be covered by some the subsequent ones.

Your task is counting the segments of different colors you can see at last.

Input

The first line of each data set contains exactly one integer n, 1 <= n <= 8000, equal to the number of colored segments.

Each of the following n lines consists of exactly 3 nonnegative integers separated by single spaces:

x1 x2 c

x1 and x2 indicate the left endpoint and right endpoint of the segment, c indicates the color of the segment.

All the numbers are in the range [0, 8000], and they are all integers.

Input may contain several data set, process to the end of file.

Output

Each line of the output should contain a color index that can be seen from the top, following the count of the segments of this color, they should be printed according to the color index.

If some color can't be seen, you shouldn't print it.

Print a blank line after every dataset.

Sample Input

5
0 4 4
0 3 1
3 4 2
0 2 2
0 2 3
4
0 1 1
3 4 1
1 3 2
1 3 1
6
0 1 0
1 2 1
2 3 1
1 2 0
2 3 0
1 2 1

Sample Output

1 1
2 1
3 1

1 1

0 2
1 1

Author: Standlove

---

Problem Source: ZOJ Monthly, May 2003

#include <cstdio>
#include <map>
using namespace std;

int seg[9000];
map<int,int> mm;
int main()
{
 int d;
 while( scanf("%d",&d) != EOF )
 {
  mm.clear();
  for( int i =0 ;i < 9000;i++)
  {
   seg[i] = -1;
  }
  int x,y,c;
  int posmax = -10000;
  for( int i = 0;i  < d;i++)
  {
   scanf("%d%d%d",&x,&y,&c);
   if ( posmax < y ) posmax  = y;
   for( int j = x;j<y;j++)
   {
    seg[j] = c;
   }
  }

  int justc =-1;
  for( int i = 0;i < posmax;i++ )
  {
   if ( seg[i] == justc ) continue;
   else
   {
    justc = seg[i];
    if (justc == -1 ) continue;
    if ( mm.find(justc) != mm.end())
     mm[justc]++;
    else
     mm[justc] = 1;
   }
  }

  map<int,int>::iterator iter = mm.begin();
  for (int i =0 ;i< mm.size();i++)
  {
   printf("%d %d\n", iter->first ,iter->second);
   iter++;
  }
  printf("\n");
 
 }

 return 0;
}

Multiplication Puzzle

---

Time limit: 1 Seconds   Memory limit: 32768K  
Total Submit: 538   Accepted Submit: 231  

---

The multiplication puzzle is played with a row of cards, each containing a single positive integer. During the move player takes one card out of the row and scores the number of points equal to the product of the number on the card taken and the numbers on the cards on the left and on the right of it. It is not allowed to take out the first and the last card in the row. After the final move, only two cards are left in the row.

The goal is to take cards in such order as to minimize the total number of scored points.

For example, if cards in the row contain numbers 10 1 50 20 5, player might take a card with 1, then 20 and 50, scoring
10*1*50 + 50*20*5 + 10*50*5 = 500+5000+2500 = 8000

If he would take the cards in the opposite order, i.e. 50, then 20, then 1, the score would be
1*50*20 + 1*20*5 + 10*1*5 = 1000+100+50 = 1150.

Input

The first line of the input file contains the number of cards N (3 <= N <= 100). The second line contains N integers in the range from 1 to 100, separated by spaces.

Process to the end of file.

Output

Output file must contain a single integer - the minimal score.

Sample Input

6
10 1 50 50 20 5

Sample Output

3650

 

---

Problem Source: Northeastern Europe 2001, Far-Eastern Subregion

虽然是最简单的二维dp，还是要彩票哥一再指点和沈老师的标程才能理解。。没办法，太弱~~><~~
此二维dp的基本思想是二分。状态值等于左右子串状态值与本次提取值的和。

#include <iostream>
using namespace std;

 

long N;
long a[110], score[110][110];

int main()
{
 while( cin >> N )
 {
  for(int i = 0 ;i < N;i++)
  {
   cin >> a[i];
   score[i][i] = 0;
  }

  long temp;
    long j;
  for( int d = 2;d < N;d++)
  {
   for( int i = 0 ;i < N-d;i++)
   {
    score[i][j=i+d] = 2000000000;
    for(int k=i;k < j;k++)
    {
     temp =  score[i][k] + score[k][j] + a[i]*a[j]*a[k];
     if ( temp  < score[i][j]  )
      score[i][j] = temp;
    }
   }
  }

  cout << score[0][N-1] << endl;
 }
}