第二回练习
题目
1.计数器
**********************************************************************源程序名: count.???(C,CPP) *
*可执行文件名: count.exe *
*输入文件名: count.in *
*输出文件名: count.out *
*********************************************************************
【问题描述】
一本书的页数为N，页码从1开始编起，请你求出全部页码中，用了多少个0,1,2,3,……,9，其中一个页码不含多余的0，如N = 1234时第5页不是0005，只是5。
【输入】
一个正整数N(1<=N<=10^9)，表示总的页数。
【输出】
共十行，第K行为数字K-1的个数。
【样例】
count.in
11
count.out
1
4
1
1
1
1
1
1
1
1
代码：
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
using namespace std;
#define INF 1e9
#define MIN(x,y) (x<y?x:y)
long long a[10];
void count(long long n){
long long current, last, tmp = n;
int factor = 1;
int len = 0;
int i;
while(tmp){
current = n/factor%10;
last = n%factor;
for(i=0; i<=9; ++i){
a[i] += len*current*factor/10;
}
for(i=0; i<current; ++i){
a[i] += factor;
}
a[current] += last+1;
a[0] -= factor; //减去多余的0
factor *= 10;
len++;
tmp /= 10;
}
}
int main(){
long long n;
scanf("%I64d", &n);
memset(a, 0, sizeof(a));
count(n);
for(int i=0; i<10; ++i)
printf("%I64d\n", a[i]);
return 0;
}
2.排队接水
**********************************************************************源程序名: water.???(C,CPP) *
*可执行文件名: water.exe *
*输入文件名: water.in *
*输出文件名: water.out *
*********************************************************************
【问题描述】
有N个人在一个水龙头前排队接水，假如每个人接水的时间为Ti，请编程找出这N个人排队的一种顺序，使得N个人的平均等待时间最小。
【输入】
输入文件一共两行，第一行为N；第二行分别表示第1个人到第N个人每人的接水时间T1,T2,……Tn，每个数据之间有一个空格。
【输出】
输出文件有两行，第一行为一种排队顺序，即1到N的一种排列（有多种最优解时输出字典序最小的序列）；第二行为这种排列方案下的平均等待时间（输出结果精确到小数点后两位，四舍五入）。
【样例】
water.in
10
56 12 1 99 1000 234 33 55 99 812
water.out
3 2 7 8 1 4 9 6 10 5
291.90
代码：
#include <cstdio>
#include <cstdlib>
#include <iostream>
using namespace std;
struct Tnode{
double time;
int label;
}node[1010];
int cmp(const void *a, const void *b){
struct Tnode e1 = *(struct Tnode *)a;
struct Tnode e2 = *(struct Tnode *)b;
if(e1.time==e2.time) return e1.label - e2.label;
return e1.time - e2.time;
}
int main(){
int i, j;
int n;
scanf("%d", &n);
for(i=0; i<n; ++i){
scanf("%lf", &node[i].time);
node[i].label = i+1;
}
qsort(node, n, sizeof(struct Tnode), cmp);
double sum = 0;
for(i=0; i<n; ++i){
sum += node[i].time*(n-i-1);
printf("%d ", node[i].label);
}
printf("\n%0.2lf\n", sum/(n*1.0));
return 0;
}
3.最多因子数
**********************************************************************源程序名: divisors.???(C,CPP) *
*可执行文件名: divisors.exe *
*输入文件名: divisors.in *
*输出文件名: divisors.out *
*********************************************************************
【问题描述】
数学家门喜欢各种类型的有奇怪特性的数。例如，他们认为945是一个有趣的数，因为它是第一个所有约数之和大于本身的奇数。
为了帮助他们寻找有趣的数，你将写一个程序扫描一定范围内的数，并确定在此范围内约数个数最多的那个数。当范围很大时，我们可能会得到多个答案，此时要将他们都输出来。
【输入】
只有一行，给出扫描的范围，由下界L和上界U确定，满足2<=L<=U<=4 000。
【输出】
对于给定的范围，输出该范围内约数最多的数。若有多个，则按升序输出这些数，每个数之间用一个空格隔开。
【样例】
divisors.in
1000 2000
divisors.out
1680
代码：
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
using namespace std;
#define INF 1e9
#define MAX(x,y) (x>y?x:y)
#define MIN(x,y) (x<y?x:y)
#define SWAP(x,y) {(x)=(x)^(y);(y)=(x)^(y);(x)=(x)^(y);}
int data[4010];
int main(){
int i, j;
memset(data, 0, sizeof(data));
for(i=2; i<4000; ++i){
for(j=1; j<=4000; ++j){
if(j%i==0) data[j]++;
}
}
int imax;
int m, n;
scanf("%d%d", &m, &n);
imax= n;
for(i=m; i<n; ++i)
if(data[imax]<data[i]) imax = i;
bool flag = false;
for(i=m; i<=n; ++i){
if(data[imax] == data[i]){
if(flag) printf(" ");
flag = true;
printf("%d", i);
}
}
return 0;
}
4.黑白棋游戏
**********************************************************************源程序名: game.???(C,CPP) *
*可执行文件名: game.exe *
*输入文件名: game.in *
*输出文件名: game.out *
*********************************************************************
【问题描述】
黑白棋游戏的棋盘由一个4*4方格阵列构成。棋盘的每一个方格中放有1枚棋子，共有8枚白色棋子和8枚黑色棋子。这16枚棋子的每一种放置方案都构成一个游戏状态。在棋盘上拥有1条公共边的2个方格称为相邻方格。一个方格最多可有4个相邻方格。在玩黑白棋游戏时，每一步可将任何2个相邻方格中棋子互换位置。对于给定的初始游戏状态和目标游戏状态，编程计算从初始游戏状态变化到目标游戏状态的最短着棋步数。
【输入】
输入文件共有8行。前四行是初始游戏状态，后四行目标游戏状态。每行4个数分别表示该行放置的棋子颜色。“0”表示白棋；“1”表示黑棋。
【输出】
输出文件是最少着棋步数N。
【样例】
game.in
1 1 1 1
0 0 0 0
1 1 1 0
0 0 1 0
1 0 1 0
0 1 0 1
1 0 1 0
0 1 0 1
game.out
4
代码：
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
using namespace std;
#define INF 1e9
#define MIN(x,y) (x<y?x:y)
#define SWAP(x,y) {(x)=(x)^(y);(y)=(x)^(y);(x)=(x)^(y);}
bool visit[16][16][16][16];
int end[4];
int start[4];
int queue[16*16*16*16][5];
void swap_row(int &m, int &n, int pos){
int first[4], second[4];
for(int i=0; i<4; ++i){
first[4-i-1] = m%2;
m /= 2;
}
for(int i=0; i<4; ++i){
second[4-i-1] = n%2;
n /= 2;
}
swap(first[pos], second[pos]);
for(int i=0; i<4; ++i)
m = m*2 + first[i];
for(int i=0; i<4; ++i)
n = n*2 + second[i];
}
void swap_col(int &m, int pos){
int first[4];
for(int i=0; i<4; ++i){
first[3-i] = m%2;
m /= 2;
}
SWAP(first[pos], first[pos+1]);
for(int i=0; i<4; ++i)
m = m*2 + first[i];
}
bool judge(int m){
for(int i=0; i<4; ++i)
if(queue[m][i] != end[i]){
return false;
}
return true;
}
void print(int now){
static int key = 1;
printf("Key:%d Start..\n", key);
key++;
int first[4][4];
int i, j, tmp;
for(i=0; i<4; i++){
tmp = queue[now][i];
for(j=0; j<4; j++){
first[i][3-j] = tmp%2;
tmp /= 2;
}
}
for(i=0; i<4; i++){
for(j=0; j<4; ++j){
printf("%d ", first[i][j]);
}
printf("\n");
}
printf("END....\n\n");
}
int main(){
int i, j;
memset(start, 0, sizeof(start));
memset(end, 0, sizeof(end));
memset(visit, false, sizeof(visit));
int s[4][4];
int e[4][4];
for(i=0; i<4; ++i){
for(j=0; j<4; ++j){
scanf("%d", &s[i][j]);
start[i] = start[i]*2+s[i][j];
}
// printf("%d\n", start[i]);
}
for(i=0; i<4; ++i){
for(j=0; j<4; ++j){
scanf("%d", &e[i][j]);
end[i] = end[i]*2 + e[i][j];
}
// printf("%d\n", end[i]);
}
visit[start[0]][start[1]][start[2]][start[3]] = true;
for(i=0; i<4; ++i)
queue[0][i] = start[i];
queue[0][4] = 0;
int head =0, tail = 1;
// print(head);
// printf("HELLO \n\n\n");
while(tail>head){
if(judge(head)){
printf("%d\n", queue[head][4]);
break;
}
for(i=0; i<3; ++i){
for(j=0; j<4; ++j){
swap_row(queue[head][i], queue[head][i+1], j);
if(!visit[queue[head][0]][queue[head][1]][queue[head][2]][queue[head][3]]){
visit[queue[head][0]][queue[head][1]][queue[head][2]][queue[head][3]] = true;
for(int k=0; k<4; ++k)
queue[tail][k] = queue[head][k];
queue[tail][4] = queue[head][4]+1;
// print(tail);
//getchar();
tail++;
}
swap_row(queue[head][i], queue[head][i+1], j);
}
}
for(i=0; i<4; ++i){
for(j=0; j<3; ++j){
swap_col(queue[head][i], j);
if(!visit[queue[head][0]][queue[head][1]][queue[head][2]][queue[head][3]]){
visit[queue[head][0]][queue[head][1]][queue[head][2]][queue[head][3]] = true;
for(int k=0; k<4; ++k)
queue[tail][k] = queue[head][k];
queue[tail][4] = queue[head][4]+1;
tail++;
}
swap_col(queue[head][i], j);
}
}
head++;
}
//printf("%d", queue[head][4]);
return 0;
}