Exercise Solutions in Chapter 3 of Introduction to Algorithmic Competition (2nd Edition)

"Introduction to Algorithmic Competition Classics" exercise source Github open source: https://github.com/RyanHe123/Classic-Introduction-to-Algorithmic-Competition
The problem-solving in this article is done by myself. If there are mistakes or improvements, please put them in the comments section. Thank you.

Problem 3-1 score (ACM/ICPC Seoul 2005, UVa 1585)

Give a string composed of O and X (length 1 - 80), statistical score. The score of each O is the number of consecutive O, and the score of X is 0. For example, OOOXXOXXOO scored 1+2+0+0+1+0+0+1+1+2+3.

#include<stdio.h>
int main()
{
	int n;
	scanf("%d", &n);
	int i = 0;
	getchar();
	for (; i < n; i++)
	{
		char ch; int sum = 0;
		int state = 0;
		while ((ch = getchar()) !='\n')
		{
			if (ch == 'O')
			{
				state++;
				sum += state;
			}
			else
			{
				state = 0;
			}
		}
		printf("%d\n", sum);
	}
}

Exercise 3-2 Molecular Weight (ACM/ICPC Seoul 2007, UVa 1586)

The molecular formula of a substance (without parentheses) is given to calculate its molecular weight. The formula in this question contains only four kinds of atoms, namely C, H, O and N, with atomic weights of 12.01, 1.008, 16.00 and 14.01 (g/mol). For example, the molecular weight of C6H5OH is 94.108 g/mol.

#include<stdio.h>
#include<ctype.h>
#include<string.h>
char s[90];
int main()
{
	int n;
	scanf("%d",&n);
	int i=0;
	for(;i<n;i++)
	{
		double atom;
		int count=1;
		scanf("%s",s);
		int j;
		double sum=0;
		for(j=0;j<strlen(s);j++)
		{
			switch(s[j])
			{
				case 'C':atom=12.01;break;
				case 'H':atom=1.008;break;
				case 'O':atom=16.00;break;
				case 'N':atom=14.01;break;
			}
			if(isdigit(s[j+1])!=0)
				count=s[++j];
			while(isdigit(s[j+1])!=0)
				count=count*10+s[++j];
			sum+=count*atom;
		}
		printf("%.3f\n",sum);
	}
}

Exercise 3-3 Number Number (ACM/ICPC Danang 2007, UVa1225)

Write the first n (n < 10000) integers together in sequence: 123456789101112. Number one, number 0 - 9, how many times each occurs (output 10 integers, 0, 1, respectively)............................................. 9 times of occurrence.

#include<stdio.h>
#include<math.h> 
int main()
{
	int t;
	scanf("%d", &t);
	int i;
	for (i = 0; i < t; i++)
	{
		int a[10] = { 0 };
		int n;
		scanf("%d", &n);
		int j;
		for (j = 1; j <= n; j++)
		{
			int num = j;
			while (num != 0)
			{
				a[num % 10]++;
				num /= 10;
			}
		}
		for (j = 0; j < 9; j++)
			printf("%d ", a[j]);
		printf("%d\n", a[9]);
	}
}	

Exercise 3-4 Cycle Series (UVa 455)

If a string can be repeated many times by a string of length k, it is said that the string has a period of K. For example, abcabcabcabc takes three cycles (note that it also takes six and twelve cycles).
Input a string with a length not exceeding 80 and output its minimum cycle.

#include<stdio.h>
#include<string.h>
int main()
{
	int n;
	scanf("%d",&n);
	int i;
	for(i=0;i<n;i++)
	{
		char s[100];
		scanf("%s",s);
		int t;
		for(t=1;t<=strlen(s);t++)
		{
			//Initially ignoring that the end is not the end of the full cycle 
			if(strlen(s)%t!=0)
				continue;
			int j=0,state=1;
			for(;j<strlen(s);j++)
			{
				if(s[j]!=s[j%t])
				{
					state=0;
					break;
				}
			}
			if(state==1)
				{
					if(i!=0)printf("\n");
				printf("%d\n",t);break;
				}
		}
	}
}

Exercise 3-5 Puzzles (ACM/ICPC World Finals 1993, UVa227)

There is a 5*5 network, just one cell is empty, and the other cells have a letter, a total of four instructions, A,B,L,R, respectively, to move adjacent subtitles around the top and bottom of the space into the space. Input initial network and instruction sequence (end at 0), output instruction after the completion of the network, if there are illegal instructions, should output, "This puzzle has no final configuration."

//There are many pits in the output format of this question, PE countless times. 
#include<stdio.h>
int main()
{
	 //Input Matrix
	int kase=1,state;
	int i,j;
	for(;;)
	{
	state=1;
	int x,y;
	char p[5][6],ch;
	for(i=0;i<5;i++)
	{
		fgets(p[i],7,stdin);
		if(p[0][0]=='Z'&&p[0][1]=='\n')
			return 0;
 	}
 	//Search for space position 
	for(i=0;i<5;i++)
	{
		for(j=0;j<5;j++)
		{
			if(p[i][j]==' ')
			{x=i;y=j;}
		}
	} 	
 	while((ch=getchar())!='0')
 	{
 		switch(ch)
 		{
 			case'A':if(x==0)state=0;
			 else{p[x][y]=p[x-1][y];p[x-1][y]=' ';x--;}break;	//Boundary Judgment and Mobility
 			case'B':if(x==4)state=0;
			 else{p[x][y]=p[x+1][y];p[x+1][y]=' ';x++;}break;
 			case'L':if(y==0)state=0;
			 else{p[x][y]=p[x][y-1];p[x][y-1]=' ';y--;}break;
 			case'R':if(y==4)state=0;
			 else{p[x][y]=p[x][y+1];p[x][y+1]=' ';y++;}break;
		}
	}
	//output 
	if(kase!=1)
	printf("\n");
	printf("Puzzle #%d:\n",kase++);
	if(state==0)
	printf("This puzzle has no final configuration.\n");
	else
	{
	for(i=0;i<5;i++)
	{
		for(j=0;j<5;j++)
		{
			printf("%c",p[i][j]);
			if(j!=4)printf(" "); 
		}
		printf("\n");
	} 	
	}
	 getchar();
	}
}

Question 3-6 Answers to Crossword Puzzles (ACM/ICPC World Finals 1994, UVa232)

Enter a grid for column c of row r, and the'*'is used to represent the'*'. Each white space is filled with a letter. If there is no white cell in the adjacent position on the left or the adjacent position on the top of a white cell (it may be a black cell, or it may be out of the grid boundary), then the white cell is called a starting lattice. First, all the starting cells are numbered 1, 2, 3 from top to bottom, left to right.

#include<stdio.h>
int main()
{
	int a,b;
	int kase=1;
	while(scanf("%d",&a)&&a!=0)
	{
		scanf("%d",&b);
		if(kase!=1)
		printf("\n"); 
		char p[a][b+1];int n[a][b];
		int i,j;
		getchar();//The \n generated by swallowing input a and b with this line 
		for(i=0;i<a;i++)
			for(j=0;j<b;j++)n[i][j]=0;//Initialize 0 for n arrays 
		//Read determinant
		for(i=0;i<a;i++)
			fgets(p[i],b+2,stdin);
		//Marked Initial Lattice
		int count=1;
		for(i=0;i<b;i++)
		if(p[0][i]!='*')n[0][i]=count++;		//Mark the first line 
		for(i=1;i<a;i++)
		{
			if(p[i][0]!='*')n[i][0]=count++;
			for(j=1;j<b;j++)
			if((p[i][j-1]=='*'||p[i-1][j]=='*')&&p[i][j]!='*') n[i][j]=count++;
		}
		/*for(i=0;i<a;i++)
		for(j=0;j<b;j++)
		{
			printf("%d ",n[i][j]);d
			if(j==b-1)printf("\n");
		}*/
		//Look for qualified words 
		printf("puzzle #%d:\nAcross\n",kase++);
		//transverse 
		for(i=0;i<a;i++)
		for(j=0;j<b;j++)
		{
			if(j==0&&p[i][0]!='*')
			{
				printf("%3d.",n[i][0]);
				while(p[i][j]!='*'&&j<b)
				putchar(p[i][j++]);
				printf("\n");
			}
			while(p[i][j]=='*'&&j<b){
				j++;
			}
			if(j>=b)break;
			printf("%3d.",n[i][j]);
			while(p[i][j]!='*'&&j<b)
				putchar(p[i][j++]);
				printf("\n");
		 } 
		//Longitudinal or horizontal search, more complex than horizontal search 
		printf("Down\n");
		int temp; 
		for(i=0;i<a;i++)
		for(j=0;j<b;j++)
		{
			if(i==0&&p[0][j]!='*')
			{
				printf("%3d.",n[0][j]);
				temp=i;
				while(p[temp][j]!='*'&&temp<a)
				putchar(p[temp++][j]);
				printf("\n");
			}
			if(i>0&&p[i][j]!='*'&&p[i-1][j]=='*')
			{
				printf("%3d.",n[i][j]);
				temp=i;
				while(p[temp][j]!='*'&&temp<a)
				putchar(p[temp++][j]);
				printf("\n");
			}

		 } 
		 
	} 
	
 } 

Exercise 3-7 DNA Sequence (ACM/ICPC Seoul 2006, UVa1368)

Input m DNA sequences with length of n, find a DNA sequence, and the total Hamming distance to the ordered sequence is as small as possible. The Hamming distance of two equal-length strings is equal to the number of different positions of the characters. For example, the Hamming distance of ACGT and GCGA is 2 (the left number is 1 and 4 characters are different).
Input integers m and N (4 < m < 50, 4 < n < 1000), and m DNA sequences of length n (containing only letters A, C, G, T), output to m sequences of Hamming distance and minimum DNA sequence and corresponding distance. If there are multiple solutions, the minimum dictionary order solution is required. For example, for the following five DNA sequences, the optimal solution is TAAGATAC.
TATGATAC
TAAGCTAC
AAAGATCC
TGAGATAC
TAAGATGT

#include<stdio.h>
int main()
{
	int n;
	scanf("%d", &n);
	int t;
	for (t = 0; t < n; t++)
	{
		int m, n;
		scanf("%d %d", &m, &n);
		char s[50][1100];
		int i,j;
		for (j = 0; j < m; j++)
			scanf("%s", s[j]);
		//Read strings, two-dimensional arrays 
		
		int sum = 0;
		for (j = 0; j < n; j++)
		{
			int a[4] = { 0 };
			for (i = 0; i < m; i++)
			{
				
				//Number of occurrences of bit-by-bit reads 
				switch (s[i][j])
				{
				case'A':a[0]++; break;
				case'C':a[1]++; break;
				case'G':a[2]++; break;
				case'T':a[3]++; break;
				}
			}
			int max = 0, index = 0;
			int z;
			//Find the letters that appear most frequently 
			for (z = 0; z < 4; z++){
				if(a[z]==max)
				{
					if(z<index)
					index=z;
				}
				if (a[z] > max)
				{
					index=z;
					max = a[z];  // If the number of occurrences is the same, the output dictionary order is small. 
				}
			}
			sum += m - max;	
			switch (index)
			{
			case 0:putchar('A'); break;
			case 1:putchar('C'); break;
			case 2:putchar('G'); break;
			case 3:putchar('T'); break;
			}
		}
		printf("\n%d\n", sum);
	}

}

Exercise 3-8 Cyclic Decimals (ACM/ICPC World Finals 1990, UVa202)

Input integers a and b a greater than or equal to 0 is less than or equal to 3000,b greater than or equal to 1 is less than or equal to 3000, output a/b of the circular decimal representation and the length of the circular section. If the cycle period is more than 50, only 50 bits are displayed, and then all of them are used. Express

#include<stdio.h>
#include<string.h>
struct combine
{
	int x, y;
};// Record divisors and residuals 
combine c[2000] = { 0 }; int yu[3000] = { 0 };//Record the remainder. The array must be open outside main, or something will go wrong. 
int main()
{
	int a, b;
	while (EOF != scanf("%d", &a))
	{
		scanf("%d", &b);
		int n = a;
		int d = a / b;
		c[0].y = a % b;
		yu[a%b]++;
		a = a % b * 10;
		int i;
		for (i = 1;; i++)//When there is the same remainder, stop the loop 
		{
			c[i].x = a / b; c[i].y = a % b;
			if (yu[a%b] == 1)
				break;
			else
				yu[a%b]++;
			a = a % b * 10;
		}
		int j, l;
		for (j = 0;; j++)//Find the location where the same residue occurred the previous time 
		{
			if (c[j].y == a % b)
			{
				l = i - j;
				break;
			}
		}
			printf("%d/%d = %d.", n, b, d);
			int t;
			for (t = 1; t <= j; t++)
				printf("%d", c[t].x);
			printf("(");
			for (; t <= i; t++)
			{
				if (t == 51)
				{
					printf("..."); break;
				}
				printf("%d", c[t].x);
			}
			printf(")\n   %d = number of digits in repeating cycle\n\n",l);//The output format of this question is very ambiguous. It needs to add a blank line between each output. 
		memset(c, 0, sizeof(c));
		memset(yu, 0, sizeof(yu));
	}
}

Exercise 3-9 Subsequence (UVa10340)

Enter two strings S and t to determine whether 0 or more characters can be deleted from t (other characters in the same order) and get the string s.
For example, abcde can get bce, but can not get dc.

#include<stdio.h>
#include<string.h>
//String must be larger, just start small, RE 
char s[1000000],t[1000000];
int main()
{
	//Read strings
	while((s[0]=getchar())!=EOF)
	{
		int i=1;
		while((s[i]=getchar())!=' ')
			i++;
		s[i]='\0';
		i=0;
		while((t[i]=getchar())!='\n')
			i++;
		int index=0; 
		for(i=0;i<strlen(t);i++)
	{
		if(s[index]==t[i])
			index++;
		
	}
		if(index==strlen(s))
		printf("Yes\n");
		else
		printf("No\n");
		//Initialize arrays to prevent the last experiment from affecting the next one 
		memset(s,0,sizeof(s));
		memset(t,0,sizeof(t));
	 } 
}

Exercise 3-10 boxes (ACM/ICPC NEERC 2004, UVa1587)

Multi-instance testing. Given the length and width of six rectangles, judge whether these six faces can be enclosed in a cube. If they can be enclosed, output "POSSIBLE" (excluding quotation marks), otherwise output "IMPOSSIBLE" (excluding quotation marks), each output occupies one line.

struct rectangle
{
	int x, y;
};
void internal_swap(struct rectangle &r1)
{
	if (r1.x > r1.y)
	{
		int temp;
		temp = r1.x;
		r1.x = r1.y;
		r1.y = temp;
	}
}
void external_swap(rectangle &r1, rectangle &r2)
{
	if (r1.x > r2.x)
	{
		rectangle temp;
		temp = r1;
		r1 = r2;
		r2 = temp;
	}
	if (r1.x == r2.x&&r1.y > r2.y)
	{
		rectangle temp;
		temp = r1;
		r1 = r2;
		r2 = temp;
	}
}
#include<stdio.h>
int main()
{
	rectangle rec[6];
	while (scanf("%d %d", &rec[0].x,&rec[0].y)!=EOF)
	{
		internal_swap(rec[0]);
		int i;
		for (i = 1; i < 6; i++)
		{
			scanf("%d %d", &rec[i].x,&rec[i].y);
			internal_swap(rec[i]);
		}
		int j;
		for (i = 0; i < 5; i++)
		{
			for (j = 0; j < 5 - i; j++)
			{
				external_swap(rec[j], rec[j + 1]);
			}
		}
		int state = 1;
		for (i = 0; i < 6; i += 2)
		{
			if (rec[i].x != rec[i + 1].x || rec[i].y != rec[i + 1].y)
				state = 0;
		}
		if (rec[0].x != rec[2].x || rec[0].y != rec[4].x || rec[2].y != rec[4].y)
			state = 0;
		if (state == 1)
			printf("POSSIBLE\n");
		else
			printf("IMPOSSIBLE\n");
	}
}

Exercise 3-11 Changing Low Grade Devices (ACM/ICPC NEERC 2006, UVa1588)

//a and b try to insert in the front, compare the minimum length of the two directions, and output the minimum length.
#include<stdio.h>
#include<string.h> 
int main()
{
	char a[200], b[200];
	while (EOF != scanf("%s", a))
	{
		scanf("%s", b);
		int la = strlen(a), lb = strlen(b), s1, s2, s;
		int i, j; int state_2 = 0;
		//a before 
		for (i = 0; i < la; i++)
		{
			int state = 1;
			for (j = 0; j < lb; j++)
			{
				if (a[i + j] + b[j] - '0' - '0' > 3)
				{
					state = 0;
					break;
				}
			}
			if (state == 1) {
				//Output the longest one up and down
				state_2 = 1;
				s1 =( (i + lb)>la? (i + lb):la); break;
			}
			if (state_2 == 0)
				s1 = la + lb;
		}
		state_2 = 0;
		//b before 
		for (i = 0; i < lb); i++)
		{
			int state = 1;
			for (j = 0; j < la; j++)
			{
				if (b[i + j] + a[j] - '0' - '0' > 3)
				{
					state = 0;
					break;
				}
			}
			if (state == 1)
			{
				state_2 = 1;
				s2 = ((i + la) > lb ? (i + la) : lb);
				break;
			}
			if (state_2 == 0)
			{
				s2 = la + lb;
			}
		}
		if (s1 > s2)s = s2;
		else s = s1;
		printf("%d\n", s);
		memset(a, 0, sizeof(a));
		memset(b, 0, sizeof(b));
	}
	return 0;
}

Exercise 3-12 Floating Points (UVa11809)

I haven't come up with this question for a long time (it's too much for me), so I found the solution of God on the Internet and posted it here. Links: https://blog.csdn.net/crazysillynerd/article/details/43339157

//Non-original, link: https://blog.csdn.net/crazysillynerd/article/details/43339157 
#include <iostream>
#include <sstream>
#include <string>
#include <cmath>
 
using namespace std;
 
int main() {
    double M[20][40];
    long long E[20][40];
 
    // charge by the meter
    for(int i = 0; i <= 9; ++i) for(int j = 1; j <= 30; ++j) {
        double m = 1 - pow(2, -1 - i), e = pow(2, j) - 1;
        double t = log10(m) + e * log10(2);
        E[i][j] = t, M[i][j] = pow(10, t - E[i][j]);
    }
 
    // Input and output results
    string in;
    while(cin >> in && in != "0e0") {
        // Processing input
        for(string::iterator i = in.begin(); i != in.end(); ++i) if(*i == 'e') *i = ' ';
        istringstream ss(in);
        double A; int B;
        ss >> A >> B;
        while(A < 1) A *= 10, B -= 1;
        // Look for answers in a typed list
        for(int i = 0; i <= 9; ++i) for(int j = 1; j <= 30; ++j) {
            if(B == E[i][j] && (fabs(A - M[i][j]) < 1e-4 || fabs(A / 10 - M[i][j]) < 1e-4)) {
                cout << i << ' ' << j << endl;
                break;
            }
        }
    }
}

Tags: network github less

Posted on Sun, 08 Sep 2019 05:54:27 -0700 by Bjom