アルゴリズムコンテスト入門経典第4章【uvaoj練習問題（一）】

13406 ワード

テーマ集
http://uva.onlinejudge.org/index.php?option=com_オンラインjudge&Itemid=8&category=94
uva 10055
http://uva.onlinejudge.org/index.php?option=com_オンラインjudge&Itemid=8&category=94&page=show_problem&problem=996
「 The se two number s in each line denotes the number of solidiers in hashmat's army and his opponent's army or vice versa.」
vice versaというテーマに気づいたら大丈夫です。英語の読解力があります。

#include <stdio.h>

int
main(void)
{
	long long a, b;

	while (scanf("%lld %lld", &a, &b) != EOF) {
		printf("%lld
", a>b ? a-b : b-a);
	}
	return 0;
}

uva 10071
http://uva.onlinejudge.org/index.php?option=com_オンラインjudge&Itemid=8&category=94&page=show_problem&problem=1012

#include <stdio.h>

int
main(void)
{
	int v, t;

	while (scanf("%d %d", &v, &t) != EOF)
		printf("%d
", v*t*2);
	return 0;
}

uva 100300
http://uva.onlinejudge.org/index.php?option=com_オンラインjudge&Itemid=8&category=94&page=show_problem&problem=1241
題意によって（a/b）＊b＊cの過程がありますので、a*cと書きます。

#include <stdio.h>

int
main(void)
{
	int tc, x, a, b, c;
	int permium;

	scanf("%d", &tc);
	while (tc--) {
		scanf("%d", &x);
		permium = 0;
		while (x--) {
			scanf("%d %d %d", &a, &b, &c);
			permium += a*c;
		}
		printf("%d
", permium);
	}
	return 0;
}

uva 458
http://uva.onlinejudge.org/index.php?option=com_オンラインjudge&Itemid=8&category=94&page=show_problem&problem=399
つまり、改行以外の文字は相対的に並進して出力します。

#include <stdio.h>

int
main(void)
{
	int c;

	while ((c = getchar()) != EOF)
		putchar(c == '
' ? '
' : c-('1'-'*'));
	return 0;
}

uva 494
http://uva.onlinejudge.org/index.php?option=com_オンラインjudge&Itemid=8&category=94&page=show_problem&problem=435
ctype.hで書いたプログラムは可読性がいいですよ。
fgetsの使い方に注意して、回車符があったら読み取りを停止し、回車符を読み込んでください。このgdbは確認できます。EOFに会ったらNULLに戻ります。
strの値はstr[0]に等しいが、この二つのものは結果が違っている。strは配列全体を含む長いブロックであり、str[0]は要素の単位ブロックであり、sizedキーワードは単位ブロック数であると考えられる。

#include <stdio.h>
#include <ctype.h>
#define N 10000
char str[N];

int
main(void)
{
	char *p = NULL;
	int count;
	
	while (fgets(str, sizeof (str), stdin) != NULL) {
		count = 0;
		for (p = str; *p != '
'; p++) {
			if (isalpha(*p) && !isalpha(*(p+1)))
				count++;
		}
		printf("%d
", count);
	}
	return 0;
}

uva 414
http://uva.onlinejudge.org/index.php?option=com_オンラインjudge&Itemid=8&category=94&page=show_problem&problem=355
この英語は読みにくいです。何回見てやっと分かります。つまり、両方の図形（「X」からなります。）が出会ったりつながったりした時、空白の文字はどれぐらい残っていますか？
一番最初に出会った行または複数行が必ずあるという考えです。これらの行の空白の数は一番少ないです。行列の空白の数を求めて、行数*を引いて、すべての行の空白の数の配列を昇順に並べた後のspacenum[0]が答えです。
注意例は'B'が''に代わるので、テスト時は'B'に変更し、提出時は''に戻ります。

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define X 30
#define Y 15

/*
       ：memset(spacenum, 0, sizeof (int));
                 ，               0
      sizeof            
 fgets    ex.sizoef (str)
 memset    ex. sizeof (str)
 qsort    ex.sizeof (int)
 */

char str[Y][X];
int spacenum[Y];

int
cmp(const void *a, const void *b)
{
	return *(int *)a - *(int *)b;
}

int
main(void)
{
	int row;
	int i, j;
	int sum;
	
	while (scanf("%d%*c", &row)) {
		if (row == 0)
			break;
		sum = 0;
		memset(spacenum, 0, sizeof(spacenum));
		for (i = 0; i != row; i++) {
			fgets(str[i], sizeof (str[i]), stdin);
			for (j = 0; str[i][j] != '
'; j++) {
				if (str[i][j] == ' ') {
					spacenum[i]++;
				}
			}
			sum += spacenum[i];
		}
		qsort(spacenum, row, sizeof (int), cmp);
		printf("%d
", sum - row*spacenum[0]);
	}
	return 0;
}

ウバ490
http://uva.onlinejudge.org/index.php?option=com_オンラインjudge&Itemid=8&category=94&page=show_problem&problem=431
この問題ははっきり言っていませんが、実は何行かの文字列を入力して空白文字列の文字行列にして、右回りの文字列を入力する最小行列です。
構造体を使ってもいいです。二次元配列を使ってもいいです。構造体は見たところ分かりやすいですが、くどいです。

#include <stdio.h>
#define N 110

typedef struct node {
	char str[N];
}node;

node a[N];
char *p[N];

int
main(void)
{
	int i = 0, j;		
	while (fgets(a[i].str, sizeof (a[i].str), stdin) != NULL) {
		i++;
	}
	for (j = 0; j != i; j++) {
		p[j] = a[i-1-j].str;
	}
	while (1) {
		for (j = 0; j != i; j++) {
			if (*p[j] == '
')
				printf(" ");
			else
				printf("%c", *p[j]++);
		}
		for (j = 0; j != i; j++) {
			if (*p[j] != '
')
				break;
		}
		printf("
");
		if (j == i)
			break;
	}
	return 0;
}

uva 445
http://uva.onlinejudge.org/index.php?option=com_オンラインjudge&Itemid=8&category=94&page=show_problem&problem=386
条件によって出力されますが、数字は常に重畳されています。この数字は後ろの文字（アルファベットセットに「*」）を出力する回数を意味します。また入力が'b'なら出力'に対応します。

#include <stdio.h>
#include <ctype.h>
#define N 150

char str[N];

int
main(void)
{
	char *p = NULL;
	int times;
	int i;
	
	while (fgets(str, sizeof (str), stdin) != NULL) {
		times = 0;
		for (p = str; *p != '
'; p++) {
			if (isdigit(*p)) {
				times += *p - '0';
			}
			if (isalpha(*p) || '*' == *p) {
				for (i = 0; i != times; i++)
					printf("%c", *p == 'b' ? ' ' : *p);
				times = 0;
			}
			if ('!' == *p)
				printf("
");
		}
		printf("
");
	}
	return 0;
}

uva 488
http://uva.onlinejudge.org/index.php?option=com_オンラインjudge&Itemid=8&category=94&page=show_problem&problem=429
この問題坑のところは最後の組のテストデータの最後の波だけが空行を出力する必要がないです。例えば、全部で3組のテストデータ、第2グループのデータは4波を出力します。第4波も空行を出力します。

#include <stdio.h>

int
main(void)
{
	int tc;
	int a, f;
	int i, j;
	int tmp;

	scanf("%d", &tc);
	while (tc--) {
		scanf("%d %d", &a, &f);
		while (f--) {
			for (i = 1; i != 2*a; i++) {
				tmp = i > a ? 2*a-i : i;
				for (j = 0; j != tmp; j++) {
					printf("%d", tmp);
				}
				printf("
");
			}
			if (!(0 == tc && 0 == f)) //Notice!!!
				printf("
");
		}
	}
	return 0;
}

uva 489
http://uva.onlinejudge.org/index.php?option=com_オンラインjudge&Itemid=8&category=94&page=show_problem&problem=430
ばかX方法でACを一回使いました。いい方法で第二段コードを見ます。
この問題はやはり論理を試験しました。論理をきちんと整理しさえすれば、間違いはありません。
馬鹿Xの方法は当てた文字を所与の文字の中で探して、見つけました。しかも以前に当てたことがないので、勝利のパラメータは1をプラスします。もし探し終わったら、まだ見つけられませんでした。失敗のパラメータは1を加えます。

#include <stdio.h>
#include <string.h>
#define N 200
#define M 27
char s_str[N];
char g_str[N];

typedef struct node {
	char alpha;
	int isexist;
	int isguessed;
}node;

node list[M];

void
guess(int key, int *w, int *l)
{
	int i;

	for (i = 0; i != M; i++) {
		if (list[i].isexist && list[i].alpha == key && !list[i].isguessed) {
			(*w)++;
			list[i].isguessed = 1;
			break;
		}
	}
	if (i == M) {
		(*l)++;
	}
}

int
main(void)
{
	int round;
	int i;
	char *p, *q;
	int win_c, lose_c;
	int count;

	while (scanf("%d", &round)) {
		if (-1 == round)
			return 0;
		scanf("%s %s", s_str, g_str);
		count = 0;
		win_c = 0;
		lose_c = 0;
		
		for (i = 0; i != M; i++) {
			list[i].alpha = 'a'+i;
			list[i].isexist = 0;
			list[i].isguessed = 0;
		}
		
		for (p = s_str; *p != '\0'; p++) {
			for (i = 0; i != M; i++) {
				if (*p == list[i].alpha && !list[i].isexist) {
					list[i].isexist = 1;
					count++;
				}
			}
		}
		
		for (q = g_str; *q != '\0'; q++) {
			guess(*q, &win_c, &lose_c);
			if (win_c == count) {
				printf("Round %d
", round);
				printf("You win.
");
				break;
			}
			if (lose_c == 7) {
				printf("Round %d
", round);
				printf("You lose.
");
				break;
			}
		}
		if (*q == '\0') {
			printf("Round %d
", round);
			printf("You chickened out.
");
		}
	}
	return 0;
}

良い方法は、
与えられた文字列の異なる文字を格納する新しい文字列Sを直接作成し、異なる文字数を統計しました。
そして当てられた文字列の中では、重複した文字は削除しますが、重複している部分の文字が当たっていれば、勝利要素は増加しません。当て間違えたら、失敗要素は増加します。
したがって、当てられた文字列の中で二つの部分に分けて、重複しない部分、重複した部分、繰り返してSを検索して、失敗要素+1が見つからないです。繰り返しないで勝利の要素+1を探し当てて、さもなくば失敗の要素+1；
uva 694
http://uva.onlinejudge.org/index.php?option=com_オンラインjudge&Itemid=8&category=94&page=show_problem&problem=635
なぜaをlong long long intタイプにしましたか？a保証はint範囲ですが、3*a＋1のプロセスがあり、これはオーバーフローを引き起こす可能性があります。ですから、どれだけ多くても、思い切ってlong long intを採用します。
【罠】このようなデータが演算中に溢れるのは非常に怖いです。例えば、前の二点検索では、mid=(a+b)/2は、パラメータがオーバーフローしないことを保証しますが、a+bはオーバーフローします。

#include <stdio.h>

int
main(void)
{
	long long a, save_a;
	int	lim, count;
	int tc = 0;
	
	while (scanf("%lld %d", &a, &lim)) {
		if (-1 == a && -1 == lim)
			break;
		save_a = a;
		count = 1;
		while (a != 1) {
			if (a % 2 == 0) {
				a = a/2;
			}
			else {
				a = 3*a+1;
			}
			if (a > lim)
				break;
			count++;
		}
		printf("Case %d: ", ++tc);
		printf("A = %lld, limit = %d, number of terms = %d
", save_a, lim, count);
	}
	return 0;
}

uva 457
http://uva.onlinejudge.org/index.php?option=com_オンラインjudge&Itemid=8&category=94&page=show_problem&problem=398
この問題は英語の読解力をテストします。卵が痛くてたまらないです。提出する人が少ない理由は英語が読めないからです。
いくつかの用語を勉強しましょう。
culture dish培養皿
population density群密度/濃度？
タイトルの意味は：
一日目以降の培養皿の中で【菌体濃度】：PD=DNA[S]は、Sは前日の現在の培養皿のPDと直接隣接するトレーニング皿のPDの3つに等しい。
そして一番右（左）側の右（左）隣の培養皿（存在しない）のPD=0を規定しています。
このため出力される行列は、列が1～40からなります。

#include <stdio.h>
#include <string.h>
#define X 50
#define Y 60
#define N 10

int DNA[N];
char PD[Y][X];

int
main(void)
{
	int tc;
	int i, j;

	scanf("%d", &tc);
	while (tc--) {
		for (i = 0; i != N; i++) {
			scanf("%d", &DNA[i]);
		}
		memset(PD, 0, sizeof (PD));
		PD[0][20] = 1;
		for (i = 0; i != 50; i++) {
			for (j = 1; j != 41; j++) {
				PD[i+1][j] = DNA[ PD[i][j]+PD[i][j-1]+PD[i][j+1] ];
				switch(PD[i][j]) {
				case 0:
					printf(" ");
					break;
				case 1:
					printf(".");
					break;
				case 2:
					printf("x");
					break;
				case 3:
					printf("W");
					break;
				}
			}
			printf("
");
		}
		if (tc != 0) {
			printf("
");
		}
	}
	return 0;
}

入力
1
0 1 2 0 1 3 3 3 3 0
出力

                   .                    
                  ...                   
                 .x x.                  
                .  .  .                 
               .........                
              .x       x.               
             .  x     x  .              
            ...xxx   xxx...             
           .x .WW.x x.WW. x.            
          .   .xxW . Wxx.   .           
         ... . WxW...WxW . ...          
        .x xx..WWWW WWWW..xx x.         
       .  ..W.Wx  WWW  xW.W..  .        
      ....xWWxWWx W W xWWxWWx....       
     .x  .WWWWWWWW W WWWWWWWW.  x.      
    .  x..x      WW WW      x..x  .     
   ...x .. x     WWWWW     x .. x...    
  .x .  xx xx    W   W    xx xx  . x.   
 .   ..x.....x           x.....x..   .  
... .x...   . x         x .   ...x. ... 
x xx .. x. .. xx       xx .. .x .. xx x.
x... xx   xxx ..x     x.. xxx   xx ...  
 . x ..x x.W. x. x   x .x .W.x x.. x x. 
.. x x. . WW.    xx xx    .WW . .x x.  .
xx x.  x..Wx..  x.....x  ..xW..x  .  ...
...  .x .WWW.x.x .   . x.x.WWW. x....x x
x x..   .x xW.W  .. ..  W.Wx x.  .  . .x
x. .x. .  .WWx. .xxxxx. .xWW.  ......x  
  x . x....xWW x WWWWW x WWx...x    . x 
 xx .  .  .WWWWxWW   WWxWWWW. . x  .. xx
x.. .......x  WWWW   WWWW  x.x. xx.xx ..
 .xxx     . x W  W   W  W x W.  .WWW. xx
. WW.x   .. xW           WxW.....x x. ..
..WxW x .xx WW           WWWW   . .  xxx
xWWWWWx  W.WWW           W  W  ..x..x.W.
WW   WWx .xx W                .x.....WW.
WW   WWW  W.W                . ..   Wxx.
WW   W W  .x.               ..xxx.  WxW 
WW    W  . . .             .x.WWW . WWW 
WW      ..x.x..           . .Wx W...W W 
WW     .x..W..x.         ..x.WWW.W W.W  
WW    . ..WWW.. .       .x..Wx xx.W.x.  
WW   ..xxWx xWxx..     . ..WWW..WWWW. . 
WW  .x.WxxW.WxxW.x.   ..xxWx xWWx  x.x..
WW . .WWxxWxWxxWW. . .x.WxxW.WWWWxx W..x
WW..x.xWxxxWxxxWx.x.x .WWxxWxx  Wx.W.W. 
WxW..WWxxWxxxWxxWW.W  .xWxxxx.x WWWWxW..
WWWWWxWxxxxWxxxxWxx. . WxxWWWW WW  WWWWx
W   WWxxWWxxxWWxxxW x..WxxW  WWWW  W  WW
    WWxxWWxWxWWxWxWW .WWxxW  W  W     WW

この効果はとても綺麗です。Wは濃度が一番強くて、x回のを表します。最小です。細菌はこのDNAを備え、シャーレの中で50日間の変化がはっきりと見られます。
【結び目】
1、memset（）は使いやすく、多次元配列（実際には本当の多次元がない）を含み、sizeofキーワードは空間ブロック数を求める。
2、ライブラリ関数と述語関数を多用する。プログラム可読性は、プログラム論理が明確で、注釈文が多く、ライブラリ関数と述語関数が合理的に使用されることを含む。
3、qsort()に含まれるパラメータは、並べられる要素の数とsizofが取るユニットの要素が占める空間の大きさ(バイト数)と、例えばsizeof(int)と、sort（）はsort（a，a+n）です。
4、fgets()とscanf()が文字の文を読み込む違いは、前者が文字＋';です。後者は本当の文字列です。
5、【罠】＋*演算途中にデータが溢れ出す。したがって、式の演算順序を変えたり、データタイプを変えたりします。
6、【罠】どこで改行が必要ですか？題意をはっきり読む多くの文字を出力する時は必ずコピーを使って手で打つのではなく、そうでないとWAが崩れてしまいます。
7、自分の慣習の論理形式によって歩く。たとえば、二つの集合を表す。反対の状況を取れば、直接にその条件の前で非を取る。

hdu 4576 Robot

チケット予約システムのaction要求