Algorithm Design and Analysis Experiment 1

Generate nonvoid proper subsets

描述

Given a set, generate all of its nonvoid proper subsets in ascending order.

输入

Each test case starts with 2 <= N <= 9, which is the number of elements in a set. The next line will have N integers 1 <= ai <= 9, representing the value of each element in the set in ascending order. The input is terminated at the end of the file (EOF).

输出

For each test case, you must print all the nonvoid proper subsets of the input set in ascending order. Afer each test case you must print a blank line.

输入样例 1

输出样例 1

#include <stdio.h>
#include <string.h>
#include<iostream>
using namespace std;

int num = 0;            //存储集合中的元素个数
int *arr2 = NULL;   //存储元素排列的数组
int arr1[100];

void opt(int length)    //输出指定长度的元素 
{
    for(int i = 0;i < length; i++){
    	
        cout<<arr1[arr2[i]];
    }
    cout<<endl;
}
//递归组合集合中指定长度的真子集 
void travel(int len, int currLen, int position)
{
    if(currLen == len){
        opt(len);                     
        return;                                
    }
    while(position != num){
        arr2[currLen] = position;               //记录当前位置
        travel(len, currLen + 1, ++position);   //继续递归产生下一个位置
    }
}
int main(){
	int N,i;
	while(cin>>N){
	  for(i=0;i<N;i++)
	  	cin>>arr1[i];
	num = i;   
	arr2 = (int *)malloc(sizeof(int) * num);          
    int j;                                      
    for(j = 1;j < num; j++)
        travel(j, 0, 0);      
		cout<<endl;                             //递归遍历子集 
    } 
    return 0;
}

Simple Count

描述

Count how many numbers do not contain 4 or 7 in the N numbers from 1 to N.

输入

Each test case starts with 1 <= N <= 1,000,000. The input is terminated by the end of file (EOF).

输出

For each test case, print how many numbers from 1 to N do not contain 4 or 7.

输入样例 1

5
10
20

输出样例 1

4
8
16

#include<iostream> 
using namespace std;

bool check(int x){
	while(x){
		if(x%10 == 4|| x%10==7){
		   return true;	  
	    }
	    x = x/10;
	}
	return false;
}


int countNum(int m){
	int result = 0;
	for(int i =1;i<=m;i++){
		result += check(i)?1:0;
	}
    int total = m-result;
	cout<<total<<endl;
}

int main(){
	int n;
	while(scanf("%d",&n)!=EOF){ 
	    if((1<=n)&&(n<=1000000))
	   	   countNum(n);	   
	}
	return 0;
}

Line up in the canteen

描述

One day, there is a kind of new delicious food from one of the windows in the canteen. All students want to have a taste. Therefore, they all go to this window to line up and form a sequence. We need to simplify this sequence. For example, if a sequence is 12221133345678899, we can simplify it as 1213456789.

输入

Each test case contains a sequence. There are only numbers and letters in the sequence. The max length of the sequence is 100. The input is terminated by the end of file (EOF).

输出

For each test case, you must print the simplyfied sequence in one line.

输入样例 1

12221133345678899
aabbccddeeffgg

输出样例 1

1213456789
abcdefg

#include<iostream> 
#include<bits/stdc++.h>

using namespace std;

int main(){
	string str1,str2;
	while(cin>>str1){
		int len1 = str1.length();
		int i=j=0;	
		for( i =0 ; i < len1; i ++){
			if(str1[i+1] != str1[i]) {
				str2[j] = str1[i];
				j++;}
		}
		
		for(int m= 0; m< j ; m++)
			cout<<str2[m];
		cout<<endl;
	}
	return 0;
}

Removing the Wall

描述

There is a wall in Tom's garden, which is builded by N different bricks. Bricks may have different height, but their width are the same. For example, when N is 7, and H=[1,2,6,1,1,7,1], this wall will be look like:

One day, Tom bought a new car and he wants to park it in his garden. So he needs to remove some parts of the wall. In order to reduce the cost, the sum of height of the removing part should be as low as possible.

输入

Each test case starts with two integers N, K (1<=N<=1*10^3，1<=K<=N). n means this wall is builded by N different bricks, and K means the width of the car. The next line will be n integers H1,H2,..,Hn(1<=Hi<=100), representing the height of the N bricks. The input will be terminated at the end of file (EOF).

输出

For each test case, you must print an integer M which means removing from the Mth brick. If there is more than one position, print the most left one.

输入样例 1

7 3
1 2 6 1 1 7 1

输出样例 1

提示

In the sample, the sum of the numbers of the 3rd, 4th, 5th bricks is 8, which is the lowest, so the wall should be removed from the 3rd position.

#include<bits/stdc++.h>
#include<iostream>
using namespace std;

int main(){
	int len,num,count;
	while(cin>>num>>len){
		vector<int> a(num);
		for(int i =0;i<num;i++)
			cin>>a[i];
	count = num-len+1;
	long sum;
	int loc;
    long MIN = 50000;
	for(int i =0;i<count;i++){
		   sum = 0;
		for(int j = i;j<i+len;j++)
		  sum +=a[j];
		if(sum <MIN){
		  MIN = sum;
		  loc = i+1;}
      }
	cout<<loc<<endl;
    }
	return 0;
}

A dice game

描述

One day, boy A and girl B are playing a dice game. First, they write a number between 1~6 in a piece of paper, and then roll the dice. The one whose number is closer to the number of the dice will win this game. For example, A wins if |a-x|<|b-x|. And |a-x|=|b-x| means a draw.

输入

Each test case cantains two integers a and b, representing the numbers guessed by boy A and girl B respectively. The input is terminated in the end of file (EOF).

输出

For each test case, you must print the numbers of the cases of "A wins", "draw" and "B wins".

输入样例 1

2 5

输出样例 1

3 0 3

输入样例 2

2 4

输出样例 2

2 1 3

#include<iostream>
using namespace std;

int main(){
	int boy,girl;
	int Bscore,Gscore,Equal;
	while(cin>>boy>>girl){
	Bscore = 0,Gscore = 0,Equal = 0;
		for(int i =1;i <=6;i++){
			if(abs(boy-i) == abs(girl-i)) Equal++;
			else if(abs(boy-i) < abs(girl-i)) Bscore++;
			else Gscore++;
			//cout<<i<<" "<<Bscore<<" "<<Equal<<" "<<Gscore<<endl;
		}
		cout<<Bscore<<" "<<Equal<<" "<<Gscore<<endl;
	}
}

Don't touch my cake！

描述

A boy bought N different cakes someday. They were arranged randomly in a line given by permutation P=[p1, p1, ..., pn], where pi denotes the unique label of a cake. To play a game, his mother sorted some subsegment of permutation P from position L to position R, that is, [L, R].

After every such sorting, the boy would be wondering if the X-th cake is still in its original position. In other words, was px changed?

After every such sorting, cakes were returned to their initial positions, so you can assume that all the sortings are independent of each other.

输入

The first line contains two space-separated integers N, M (1 ≤ N, M ≤ 1000) — the length of permutation and the number of sortings.

The second line contains n space-separated integers p1, p2, ..., pn (1 ≤ pi ≤ n) — permutation P. Note that all elements in the permutation are different.

Each of the next M lines contains three space-separated integers Li, Ri, Xi (1 ≤ Li ≤ Xi ≤ Ri ≤ n) — the left and right borders of the subsegment and the position which is interesting to the boy in the i-th sorting.

The input is terminated at the end of the file (EOF).

输出

For each sorting, print "Yes" if the cake at position X was not changed, or "No" otherwise.

输入样例 1

输出样例 1

Yes
No
Yes
Yes
No

输入样例 2

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

输出样例 2

Yes
No
Yes
No
Yes

提示

Explanation of first test case:

[1, 2, 3, 4, 5] — permutation after sorting, the 3-rd element is not changed, so answer is "Yes".
[3, 4, 5, 2, 1] — permutation after sorting, the 1-st element is changed, so answer is "No".
[5, 2, 3, 4, 1] — permutation after sorting, the 3-rd element is not changed, so answer is "Yes".
[5, 4, 3, 2, 1] — permutation after sorting, the 4-th element is not changed, so answer is "Yes".

[5, 1, 2, 3, 4] — permutation after sorting, the 3-rd element is changed, so answer is "No".

	int right = r-1;
	for(i=left;i<right;i++){
		int k = i;
		for(int j =i+1; j<=right;j++){
			if(a[j]<a[k]) k = j;
		}
		if(k!=i){
			int temp = a[i];
			a[i]  = a[k];
			a[k] = temp;
		}
	}	
}

bool check(int a[],int l, int r, int x){
	    for(int i = 0;i<N;i++)
	       arr2[i] = a[i];
        sort(a,l,r);
        int loc = x-1;
        if(arr2[loc] == a[loc]){
           	for(int i = 0;i<N;i++)
	         arr1[i] = arr2[i];
	      return true;
        	
	    }
	    else {
	    	for(int i = 0;i<N;i++)
	         arr1[i] = arr2[i];
	         return false;	    	
		}     
}


int main(){
	int m;
	while(cin>>N>>m){
		for(int i=0;i<N;i++)
			cin>>arr1[i];
	int l,r,x;
    for(int i =0; i<m ;i++){
    	cin>>l>>r>>x;
		bool result = check(arr1,l,r,x);
		if(result)
		  cout<<"Yes"<<endl;
		else
		  cout<<"No"<<endl;
	}
  }
    return 0;
}

Tom palindrome number

描述

Tom is studing math these days. If there is a number X, whose binary form and decimal form are all palindrome numbers, Tom names it "Tom palindrome number". And Tom wants to know how many "Tom palindrome number" there are between N and M ? (1001,66,64446 are all palindrome number)

输入

Each test case starts with two integer N and M (1<=N<=M<=1000000).

输出

For each test case, you must print all Tom palindrome numbers between N and M, one line for each. After each test case you must print a blank line. And print nothing if there isn't any "Tom palindrome number" between N and M.

输入样例 1

输出样例 1

#include<iostream>
using namespace std;

int judge(int i, int x) {
    int res = i, t = 0;
    while (i) {
        t = t * x + i % x;
        i /= x;
    }
    return t == res;
}

int main() {
    int m,n;
    while(cin>>m>>n){
    for (int i=m; i <=n; i++) {
        if (judge(i,10) && judge(i,2)) {
            cout << i <<endl;
        }
   }
   cout<<endl;
    }
    return 0;
}

Unova

描述

In mythology, Unova was created by uniting the warring peoples of the land leaded by twin heroes. They used a single dragon more than 2500 years ago. The brothers started to argue over their beliefs; the elder brother sought truth and the younger brother sought ideals. Different people have different ideas on many things. If there are N people and N different views on one thing. How many situations could be possible if everyone holds a different view?

输入

Each test case contains an integer N (N < 10), which is the number of people and views. Inputs will be terminated at the end of file (EOF).

输出

For each test case, you must print all the situations in lexicographical order. There should be a blank line after each answer.

输入样例 1

1
2
3

输出样例 1

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

int A[11];  // n<10

void print_permutation(int n, int* A, int cur) {
  if(cur == n) { // terminate recursion
    for(int i = 0; i < n; i++) printf("%d", A[i]);
    printf("\n");
  } else for(int i = 1; i <= n; i++) { // try to assign A[cur] with i
    int ok = 1;
    for(int j = 0; j < cur; j++)
      if(A[j] == i) ok = 0; // i is already used in A[0]~A[cur-1]
    if(ok) {
      A[cur] = i;
      print_permutation(n, A, cur+1); // recursion
    }
  }
}

int main() {
  int n;
  while(cin>>n){
  print_permutation(n, A, 0); 
   printf("\n");
   }
  return 0;
}

更多推荐

Algorithm Design and Analysis Experiment 1