Description

There is a kind of bacterium(細菌) and its life is 3 week.

At end of first week, it divides into 2 bacteria.

At end of second week, it divides into 2 bacteria again.

At third week, it does nothing and die.

For example, we have one bacterium at first week.

At begin of 5^th week, there are total 10 bacteria.

Now, give you week W. You should tell me how many bacterium at begin of W^th week.

Input

One integer, week W.

1<= W <=40

Output

How much bacterium at begin of W^th week.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Simulate the process of arithmetics(四則運算) in form of prefix notation and calculate the answer.

The characteristic of prefix notation is that operators always precede their operands rather than between then. For example, we see an equation '1 + 2' in conventional infix notation . In prefix notation the expression becomes '+ 1 2'. Another example is (3 - 6) * 2. In prefix notation it becomes ' * - 3 6 2'.

Input

An equation in prefix notation.

Operands are integers in the range between 0 and 9.

There are four operators in this problem: addition('+'), subtraction('-'), multiplication('*'), and division('/').

At the end of an equation there is a '=' symbol. 

No blank space between elements.

No calculate errors(for example, 5/0) will happen.

The length of equations (includes '=') is less than 40.

Output

Show the answer of equation

Note that the answer may be a decimal number, so you are asked to use '%.3f' to show the answer, or you'll get WA even if your answer is correct.

No new line character at the end. 

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

In computer science, we can use a fixed format to represent an arithmetic.

Now, I give you a fixed format with 5 fields, op, rd, rs ,rt and imm.

The op means what operator will be done and there are 5 kinds of op, PLUS, MINUS, SWAP, SET and ANSWER.

The rd means where the operate result will be put.

The rs means where is the operand 1 and the rt mean where is the operand 2.

The imm means the constant.

PLUS and MINUS operator’s operand are variables.

The result of MINUS is always positive number.

The constant of SET is always positive number.

For example, the format (PLUS C A B -) means C is A plus B. Because we do not need constant, we give imm a -.

Format (SET B - - 200) means B is been set to 200.

Format (ANSWER - - - -) means print result.

Now, there are 5 integer array and each length is 2000000 and each integer represents a digit ( 0 ~ 9).

In addition, there are some arithmetic you need to complete. 

#include 
#include 
#include 

#define	OP_ANSWER	0
#define OP_PLUS		1
#define OP_MINUS	2
#define	OP_SWAP		3
#define OP_SET		4

#define LEN		2000000

int *A, *B, *C, *D, *E;

int op_translation(char *s){
	if(!strcmp(s, "PLUS"))
		return OP_PLUS;
	else if(!strcmp(s, "MINUS"))
		return OP_MINUS;
	else if(!strcmp(s, "SWAP"))
		return OP_SWAP;
	else if(!strcmp(s, "SET"))
		return OP_SET;
	else if(!strcmp(s, "ANSWER"))
		return OP_ANSWER;
	else
		return -1;
}

int** operand_translation(char *rx){
	switch(*rx){
		case 'A':	return &A;
		case 'B':	return &B;
		case 'C':	return &C;
		case 'D':	return &D;
		case 'E':	return &E;
		default:	return NULL;
	}
}

void alu_plus(int *rd, int *rs, int *rt){
/***
Big number operation of plus:
rd = rs + rt
***/

/// add your code here

}

void alu_minus(int *rd, int *rs, int *rt){
/***
Big number operation of minus:
rd = rs - rt
***/

/// add your code here

}

void alu_set(int *rd, char *imm){
/***
Big number operation of set:
rd = imm
***/

/// add your code here

}

void alu_swap(int **rd, int **rs){
/***
Big number operation of swap:
rd <=> rs
***/

/// add your code here

}

void alu_answer_print(char *s){
	int i, flag, *a=*operand_translation(s);

	flag = 0;
	printf("%s: ",s);
	for(i=LEN-1; i>=0; i--){
		if(flag || *(a+i)>0){
			printf("%d", *(a+i));
			flag=1;
		}
	}
	if(!flag)
		printf("0\n");
	else
		printf("\n");
}

void alu_answer(){
	alu_answer_print("A");
	alu_answer_print("B");
	alu_answer_print("C");
	alu_answer_print("D");
	alu_answer_print("E");
}

void initial(){

	A = (int*)malloc(sizeof(int)*LEN);
	B = (int*)malloc(sizeof(int)*LEN);
	C = (int*)malloc(sizeof(int)*LEN);
	D = (int*)malloc(sizeof(int)*LEN);
	E = (int*)malloc(sizeof(int)*LEN);

	memset(A, 0, sizeof(int)*LEN);
	memset(B, 0, sizeof(int)*LEN);
	memset(C, 0, sizeof(int)*LEN);
	memset(D, 0, sizeof(int)*LEN);
	memset(E, 0, sizeof(int)*LEN);
}

void destroy(){
	free(A);
	free(B);
	free(C);
	free(D);
	free(E);
}

int main(){
	char op[8]; /// operator
	char rd[4]; /// destination
	char rs[4]; /// source 1
	char rt[4]; /// source 2
	char imm[LEN]; /// immediate

	int **prd; /// pointer rd
	int **prs; /// pointer rs
	int **prt; /// pointer rt

	initial();

	while(scanf("%s %s %s %s %s", op, rd, rs, rt, imm)==5){
		prd = operand_translation(rd);
		prs = operand_translation(rs);
		prt = operand_translation(rt);

		switch(op_translation(op)){
		case OP_MINUS	: alu_minus	(*prd, *prs, *prt);	break;
		case OP_PLUS	: alu_plus	(*prd, *prs, *prt);	break;
		case OP_SET	: alu_set	(*prd,  imm	 );	break;
		case OP_SWAP	: alu_swap	( prd,  prs	 );	break;
		case OP_ANSWER	: alu_answer();				break;
		}
	}
	
	destroy();
	
	return 0;
}

Input

Many groups of arithmetic command with above format and rules.

Output

5 variable.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

An nxn square matrix A is called invertible or non-singular if there exists a matrix B such that AB = BA = I_n. If B exists, it is unique and is called the inverse matrix of A, denoted A⁻¹. In this problem, you are given a 3x3 matrix A, and supposed to calculate A⁻¹.

For example, for

Note that the denominator should be positive and each element should be expressed in simplest terms.

 The formulation of inverse matrices: 

The following is an excerpt of incomplete code:

#include

int a[3][3]={0},nu[3][3]={0},de[3][3]={0},div[3][3]={0};
//a[3][3] is input, nu[3][3] is the numerator of output, de[3][3] is the denominator of input, div[3][3] is gcd of nu[3][3] and de[3][3]
int i,j,det=0;
void show();
void simple();
int gcd(int x,int y);

int main(void)
{
    for(i=0;i<3;i++){
        for(j=0;j<3;j++){
            scanf("%d",&a[i][j]);
        }
    }

    /* your code */

    simple();
    show();

    return 0;
}

void show(){
    for(i=0;i<3;i++){
        for(j=0;j<3;j++)
            printf("%4d",nu[i][j]/div[i][j]);
        printf("\n --- --- ---\n");
        for(j=0;j<3;j++)
            printf("%4d",de[i][j]/div[i][j]);
        printf("\n\n");
    }
}

void simple(){
    for(i=0;i<3;i++){
        for(j=0;j<3;j++){
            if(nu[i][j]!=0)
                if(de[i][j]>0)
                    div[i][j]=gcd(abs(nu[i][j]),abs(de[i][j]));
                else
                    div[i][j]=-gcd(abs(nu[i][j]),abs(de[i][j]));
            else{
                de[i][j]=0;
                div[i][j]=1;
            }
        }
    }
}

int gcd(int x,int y){
    if(x%y==0) return y;
    else return gcd(y,x%y);
}

Input

A 3x3 matrix A.

Output

The inverse matrix of A, denoted A⁻¹.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Observe the following instructions to solve a simple problem.

1.          Input a sequence A, and then arrange the sequence number from large to small in order to get the new sequence B.

2.          Do in the same way by step 1, but this time arrange the sequence A from small to large in order to get another sequence C.

3.          Calculate the difference of B and C, that is, B-C.

4.          Use B-C in step 3 as a new sequence A and repeat the above steps 1 to 3.

5.          The repetitions end when a difference has been observed in the previous operations.

6.          Finally you need to print the times that step 3 is executed.

Note: the input won’t be 0.

Example:

For the sequence A=3412, the sequence B from large to small is 4321. Besides, the sequence C from small to large is 1234.
Then follow the above instructions, we have 4321 - 1234 = 3087, 8730 - 378 = 8352, 8532 - 2358 = 6174, 7641 - 1467 = 6174.
In this case, you should print the number 4.

For another sequence A=12345, the sequence B from large to small is 54321. Besides, the sequence C from small to large is 12345. 
Then follow the above instructions, we have 54321 - 12345 = 41976, 97641 - 14679 = 82962, 98622 - 22689 = 75933, 97533 - 33579 = 63954, 96543 - 34569 = 61974, 97641 - 14769 = 82962.
In this case, you should print the number 6.

Input

The input sequence contains no more than six digits.

Output

The times that step 3 is executed.

Note that there is a newline character at the end of the output.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

There are two polynomial equations f(x) and g(x).

 f(x)=(a_m x^m+a_(m-1) x^(m-1)+⋯+a₁ x¹+a₀ x⁰)ⁿ

g(x)=c_p x^p+c_(p-1) x^(p-1)+⋯+c₁ x¹+c₀ x⁰

,where n,m,p∈N,0≤p<100.

In this problem, we define g(x) as the expand form of f(x). For example, if f(x)=(x+3)², then g(x)= x²+6x+9.

Note that all the coefficients are integers.

Input

m

a_m a_(m-1)  … a₁ a₀ 

n

Output

c_p c_(p-1)  … c₁ c₀

Note that you need to use “%5d” to print answer and there is a new line at the end.  

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

In this problem we consider the simplified version of game Reversi.
The simple Reversi is a strategy board game played on an 8x8 board. There are 64 identical disks, which are light on one side and dark on the other.
Given an initial play and a sequence of moves, your job is to output the final play.
The rules are the following:
1. Dark and light play in turns.
2. When a disk is placed and is faced up light(resp. dark), all of the dark(resp. light) disks between light disks are then turned over to become dark(resp. light).
3. ‘L’(resp. ‘D’) is shown when the disk is faced up light(resp. dark). The ‘-‘ is shown when there is no disk on the position.

Note that every move of the testcases is a valid move, that is, the following two conditions will not happen:
1. A disk is placed on a disk.
2. The disk placed did not turn over some disks.

You may use the following piece of code:

#include 

#define B_SIZE 8

char board[B_SIZE][B_SIZE];

void read_board(){
    int i, j;

    for(i = 0; i < B_SIZE; i++){
        for(j = 0; j < B_SIZE; j++){
            scanf(" %c", &board[i][j]);
        }
    }
}

void print_board(){
    int i, j;

    for(i = 0; i < B_SIZE; i++){
        for(j = 0; j < B_SIZE; j++){
            printf(" %c", board[i][j]);
        }
        printf("\n");
    }
}

int main()
{
    int N;

    read_board();
    scanf("%d", &N);

    /* your code here */

    print_board();
    printf("%d\n", N);

    return 0;
}

Input

The map
N moves
(dark/light row column) of move 1
(dark/light row column) of move 2
…
(dark/light row column) of move N
 

Output

The final map.
Each entry of the map is printed by ‘ %c’, and there is a newline character at the end of the map.
 

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

The scenario: You are a police officer and there are some bad guys hiding behind the blocks.

Given a map represented as a two-dimensional array, the bad guys are hiding at the top row of the map. From the second row to the bottom, there are several blocks. You are at the bottom row of the map. You have to use your gun to destroy the blocks in front of you so that you can defeat the bad guys.

Every bad guy or block has a vitality level. When you fire at a block, the vitality level of it is decreased by 1; if the vitality level of a block becomes 0, it is destroyed. Similarly, when you fire at a bad guy, his vitality level is decreased by 1. If his vitality level is 0, he is defeated.

The following image shows the situation at certain moment.

Input

The first line contains two numbers I and J, which denote the size of the place (I for rows and J for columns, 3 <= I, J <= 5). 

The next line contains J numbers, which indicate the vitality levels of the bad guys at the corresponding columns. If the number is 0, it means that at that column there is no bad guy.

The following I-1 lines indicate the existence of blocks from row 2 to row I. Each line contains J numbers corresponding to the J columns. If the number is larger than 0, it means that there is a block at that column. Note that there is no block at row I, which means that all the J numbers for row I are 0.

The value of vitality level is between 1 and 9.

The final line gives a sequence of instructions telling that, at which column you should fire. The end of the instructions is marked as 'e'.

For example, if the instructions are "1 2 1 e", you should fire at the first column, then the second column, and then the first column again. The length of sequence is less than 10.

Output

Show the final configuration of the map after the instructions are done, using the same form as the input.

That means every integer in the map is printed by "%2d". Remember to print a newline character '\n' at the end of each row.

Sample Input  Download

Sample Output  Download

Tags

Discuss