*/ --------------------------------------------------------------------------------------
*/ 出自： 编程中国 http://www.bc-cn.net
*/ 作者： 一番宝瓶
*/ 时间： 2007-7-20 编程论坛首发
*/ 声明： 尊重作者劳动，转载请保留本段文字
*/ --------------------------------------------------------------------------------------


见于我们C++ 板块里的初学者越来越多， 感觉很多人不管是计算机专业的还算非计算机专业都对C++都很感兴趣，由于学习方式和背景不同，大家的能力也分开了层次，希望一些熟悉C++的朋友能多帮助初学者多多领悟C++的真谛.废话少说，这个帖子主要是给一些初学者介绍一下有关ACM的东东，希望能通过简单的入门，让一些新手也可以领率到正规的编程比赛的快乐。

当然不要让ACM的知名度让一些初学者不敢去尝试，我们也无需参加什么比赛，只是拿这种正规的比赛题来练练手，引导自己对C++的学习。下面介绍下一些在线的ACM OJ(ACM在线评测系统)，做做在线ACM，感觉还是不错的 ^^

UVA :http://acm.uva.es/contest/
西班牙的，号称世界第一OJ

POJ :http://acm.pku.edu.cn/JudgeOnline/contests
北京大学OJ，中国最大OJ

JOJ :http://acm.jlu.edu.cn/joj/contests.php
吉林大学OJ，题目比较简单

ZOJ :http://acm.zju.edu.cn/
浙江大学OJ，题目比较多

URAL :http://acm.timus.ru/schedule.aspx
俄罗斯的，数学味浓

SGU :http://acm.sgu.ru/contests.php
俄罗斯的，题目很少，但数学味很浓

USACO :http://ace.delos.com/contestgate
美国的，很多oier都在上面训练

SPOJ :https://www.spoj.pl/
排名方式独特，而且支持很多语言

建议有时间的朋友去国内的ACM 在线评测系统，亲切感比较强吧。再说说有关在线答题的东东，题目一般分为几种类型：DP，搜索，图论，模拟，数学，字符串处理，几何及其他等趣味题。选择了题目后，可以点submit提交你的代码，测试系统一般会回应一下几个答复：

Accepted //正确

Compiler Error //编译错误

Wrong Answer //结果错误

Presentation Error //表达格式错误

Runtime Error //运行错误

Time Limit Exceeded //超时

Memory Limit Exceeded //分配内存上限

Others (Output Too Much) //其他错误

除此之外还会给出你的程序代码的大小，运行所用时间和内存使用情况等信息。

题的内容全部为英文，但没有什么复杂的英语语法，看懂很容易，在线评测系统对输入输出的格式要求很严格，所以要特别注意input和output的要求，写完程序后用自己的IDE把题里所给的sample input测试一下结果，和给的sample output是否一致，以确保格式是否正确。

好了，相关的东西先介绍到这里，初学C++的朋友可以先做一些简单的题来接触一下ACM，下面我给了几个自己以前做过的一些题目，因为题目非常简单，希望初学者自己也能感悟一下，因为自己水平一般，还是希望一些高手不要吝啬自己的才华，把自己做过的题目与大家分享，或者帮助初学者分析，愿我们共同学好C++

一番宝瓶

2007.7.20 晨

[此贴子已经被作者于2007-7-20 11:37:45编辑过]

Given a series of integer, find the maximum number.

Input
Multi-case. The first line gives count n (n < 100) of this array. n=0 means end of input. There are one integer in the next n lines.

Output
For each case, output the maximum number in one line.

Sample Input
3
1 4 5
0
Sample Output
5

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

int main()
{
 int n;
 cin>>n;
 while (n != 0)
 {
  if (n >= 100) exit(-1);
            int *a = new int[n];
  for (int i=0; i<n; ++i)
   cin>>a[i];
  cout<<*max_element(a,a+n)<<endl;
  delete []a;
  cin>>n;
 }
 return 0;
}

In this problem you are to generate a triangular wave form according to a specified pair of Amplitude and Frequency.

Input and Output
The input will contain two integers, each on a separate line. The first integer is the Amplitude; the second integer is the Frequency.

For the output of your program, you will be printing wave forms each separated by a blank line. The total number of wave forms equals the Frequency, and the horizontal ``height'' of each wave equals the Amplitude. The Amplitude will never be greater than nine.

The waveform itself should be filled with integers on each line which indicate the ``height'' of that line.

NOTE: There is a blank line after each separate waveform, excluding the last one.

Sample Input

3
2

Sample Output

1
22
333
22
1

1
22
333
22
1

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

int main()
{
 int n, m;
    cin>>n>>m;
    while(m-->0)
 {
      for(int i=-n+1; i<n; ++i, cout<<endl)
      for(int k=0; k<n-abs(i); cout<<n-abs(i), k++);
      if( m>0 ) cout<<endl;
 }
    return 0;
}

Given a positive integer, tell whether it is equal to the sum of four consecutive integers.

Input
A positive integer(<231), each case will be on a separate line. A zero (0) denotes the end of input.

Output
The phrase “ is not the sum of four consecutive integers.” or the phrase “ is the sum of four consecutive integers.”, where is the number in question.

Example
In this example, 2 = -1 + 0 + 1 + 2, and 82 = 19 + 20 + 21 + 22. 5 and 41 are not of the correct form.

Input
2
5
41
82
0

Output

2 is the sum of four consecutive integers.
5 is not the sum of four consecutive integers.
41 is not the sum of four consecutive integers.
82 is the sum of four consecutive integers.

程序代码：

#include <iostream>
using namespace std;

inline bool sure(int n);
int main()
{
int i, n, a[40];
for(i =0, n=0;; ++i, ++n)
{
  cin>>a[i];
  if( a[i] == 0) break;
}
for(i=0; i<n; ++i)
{ if(sure(a[i])) cout<<a[i]<<\" is the sum of four consecutive integers.\n\";
  else cout<<a[i]<<\" is not the sum of four consecutive integers.\n\";
}
return 0;
}
inline bool sure(int n)
{
int sum = 0, num = 0;
for(int i=-n; i<n+4; ++i)
{   
  if( n != sum ) 
  { 
    num++;
    if(num-->4) sum+=4;
    else sum+=i;
  }
         else 
      return true;
}
return false;
}

[此贴子已经被作者于2007-7-21 17:31:28编辑过]

Zorro is ready to modernize -- he is tired of hand drawing his giant "Z", and would like to add an educational element. So he wants you to write a program to draw a Z using the lower-case letters of the alphabet in order. If you run out of letters, just continue by following z with a.

Input
A positive integer(<=500) denoting the number of characters across the top of the Z. An input of 0 will indicate that Zorro is done.

Output
The Z, drawn in lowercase alphabetic characters. Each Z should be separated from the previous Z by at least one blank line.

Sample Input
3
30
0

Sample Output

abc
d //d在中间，格式没弄好
efg

abcdefghijklmnopqrstuvwxyzabcd
e
f
g
h
i
j
k
l
m
n
o
p
q
r
s
t
u
v
w
x
y
z
a
b
c
d
e
f
ghijklmnopqrstuvwxyzabcdefghij
Hint:
Blank line is used between two Zorros, so there are no extra blank line after last Zorro.

程序代码：

#include <iostream>
#include <string>

using namespace std;
string alpha(\"abcdefghijklmnopqrstuvwxyz\");
void printZ(int n);
int main()
{
int i, n, a[10];
for(i=0, n=0;; ++i, ++n)
{
  cin>>a[i];
  if(a[i]==0) break;
  if(a[i] > 500) exit(-1);
}
for(i=0; i<n; ++i)
{   if(i>0) cout<<endl;
  printZ(a[i]);
}
return 0;
}
void printZ(int n)
{
int i, num=1;
for(i=0; num <= n; ++i)
{
  if(i==26) i=0;
  cout<<alpha[i];
  num+=1;
}
cout<<endl;
for(int j=0; j<n-2; ++j, cout<<endl)
{
  if(i==26) i=0;
  for(int k=0; k<n-j-2; cout<<' ', ++k);
  cout<<alpha[i++];
}
for(num=1; num <= n; num++)
{
  if(i==26) i=0;
  cout<<alpha[i++];
}
cout<<endl;
}

[此贴子已经被作者于2007-7-20 11:35:19编辑过]

Draw a diamond shape with character '*'.

Input
There are several lines in the input, each line is a integer N(N<100), N is zero means the end of input.

Output
For each line of input, draw a diamond whose width is N like sample. Notice there is no unnecessary spaces after '*' in the same line.

Output a blank line after each case.

Sample Input

3
0
Sample Output

　　＊
　＊＊＊
＊＊＊＊＊
　＊＊＊
　　＊

程序代码：

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

inline void printch(int n);
int main()
{
int n, a[1000], i=0;
while(cin>>n)
    {
if(n == 0) break;
a[i++] = n;
}
for(int j=0; j<i; cout<<endl, ++j) printch(a[j]);
return 0;
}
inline void printch(int n)
{
for(int i=-n+1; i<n; ++i, cout<<endl)
{
  for(int j=0; j<abs(i); cout<<' ', ++j);
     for(int k=0; k<2*n-2*abs(i)-1; cout<<'*', k++);
}
}

[此贴子已经被野比于2007-7-21 0:23:26编辑过]

Consider a scenario where you are asked to calculate a function Answer(x, y), with x and y both integers in the range [1, N], 1 <= N <= 50000. If you know Answer(x, y), then you can easily derive Answer(k*x, k*y) for any integer k. In this situation you want to know how many values of Answer(x, y) you need to precalculate. The function Answer is not symmetric.

For example, if N = 4, you need to precalculate 11 values: Answer(1, 1), Answer(1, 2), Answer(2, 1), Answer(1, 3), Answer(2, 3), Answer(3, 2), Answer(3, 1), Answer(1, 4), Answer(3, 4), Answer(4, 3) and Answer(4, 1).

Input
Each line will has a positive integer N.

Output
Only one integer that is how many values of Answer(x, y) you need to precalculate.

Sample Input
4
Sample Output
11

程序代码：

#include <iostream>
using namespace std;
#define min(x, y) ((x)>(y)?(x):(y))

bool gcm(int a, int b);
int main()
{
int N;
while (cin>>N)
{
int count = 0;
if (N<1 || N>50000) exit(-1);
for (int i=1; i<=N; ++i)
{
 for (int j=1;j<=N; ++j)
 {
    if( gcm(i, j) ) continue;
    else count++;
 }
}
cout<<count++<<endl;
}
return 0;
}
bool gcm(int a, int b)
{
for (int i=2; i<=min(a,b); ++i)
   if ( a%i==0 && b%i==0 ) return true;
return false;
}

Given a character string, determine if it is a palindrome. A palindrome is a word or phrase that reads the same forwards and backwards, like mom or noon. For our purposes, palindromes are case insensitive, so Bob and Anna are palindromes. Also, we are only concerned with alphabetic characters, so punctuation and other non-alphabetic characters may be ignored.

Input
A positive integer denoting the number of cases. Each case will consist of a string of characters, including blanks and non-alphabetic characters. Each case will be on a separate line.

Output
The sentence “<string> is a palindrome.” if the word is a palindrome, or the sentence “<string> is not a palindrome.” if it is not, where <string> is the input string.

Sample Input
5
Allen Alda
asdffdsa
Race car
Go hang a salami, I'm a lasagna hog!
Hanna

Sample Output

Allen Alda is not a palindrome.
asdffdsa is a palindrome.
Race car is a palindrome.
Go hang a salami, I'm a lasagna hog! is a palindrome.
Hanna is not a palindrome.

程序代码：

 
#include <iostream>
#include <string>
#include <cctype>
using namespace std;

int main()
{
 int n, count=0;
 cin>>n;
 cin.clear(ios::goodbit);
 string *s = new string[n];
    for(int i=0; i<n; ++i)  getline(cin,s[i]);
 for(int j=0; j<n; ++j, count=0)
 {
  string temp=\"\";
  for(int k=0; k<s[j].size(); ++k)
  {
    if(isalpha(s[j].at(k)))
           temp+=tolower(s[j].at(k));
  }
  for(int m=0; m<temp.size()/2; ++m)
      ( temp[m]==temp[temp.size()-m-1] ) ? count++ : count--;
  if(count==temp.size()/2 || temp.size() == 1) cout<<s[j]<<\" is a palindrome\n\";
  else cout<<s[j]<<\" is not a palindrome\n\";
 }
 delete []s;
 return 0;
}

[此贴子已经被作者于2007-7-20 12:38:19编辑过]

umm, smart and detailed analysis ... ,GO ON.

For Example, when N = 2 and M = 3, there are 6 squares size of 1 * 1 and 2 squares size of 2 * 2 in the chessboard, so the answer is 8.
Input
There are several lines in the input, each line consist of two positive integers N and M (1 <= N <= 100, 1 <= M <= 100) except the last line which N = 0 and M = 0 implying the end of the input and you should not process it.
Output
Please output the number of the squares for each chessboard in a single line.

Sample Input
1 1
2 3
3 3
0 0

Sample Output
1
8
14

程序代码：

#include <iostream>
using namespace std;
#define max(x, y) ((x)>(y)?(x):(y))
int num(int, int);

int main()
{
 int N, M, ar[50];
 int i=0;
 while( cin>>N>>M )
 {
  if( N<0|| N>100 || M<0 || M>100 ) exit(-1);
  ar[i]=N;
  ar[i+1]=M;
  if(ar[i]==0 && ar[i+1]==0 ) break;
  i+=2;
 }
 for(int j=0; ar[j]!=0 && ar[j+1]!=0; j+=2, cout<<endl)
  cout<<num(ar[j], ar[j+1]);
 return 0;
}
int num(int n, int m)
{
int sum = 0;
for(int i=2; i<=max(n, m); ++i)
if( n >= i && m >= i)
{
 if( n*m ==i*i ) sum += 1;
 else 
 sum += ( m-i+1 )*( n-i+1 );
}
return sum+n*m;
}

[此贴子已经被作者于2007-7-21 15:41:13编辑过]