CCF-CSP Questions (six)

Algorithms change the world. The importance of algorithms is self-evident to a programmer, so the practice of some algorithms is indispensable. Next, I will share some algorithmic problems.

Question

question

Analysis

Arrays or stacks can be used to store data, multiply and divide first, convert all operations into additions, and then add.

Solution

Here is the solution to this problem.The following are two solutions, the result is 100 points.

Program

Method One

//
//  main.cpp
//  IN
//
//  Created by gang du on 2019/6/15.
//  Copyright © 2019 gang du. All rights reserved.
//

/**
 * six states
 * state 0 : 2 -> missing 0, 1, 3
 * state 1 : 2, 0 -> missing 1, 3
 * state 2 : 2, 3 -> missing 0, 1
 * state 3 : 2, 0, 1 -> missing 3
 * state 4 : 2, 0, 3 -> missing 1
 * state 4 : 2, 3, 0, 1 -> all used
 */
 
#include<iostream>
#include<memory.h>
using namespace std;

#define MOD 1000000007

int main(){
	long long status[1001][6];
	int n,i;
	memset(status,0,sizeof(status));
	cin>>n;
	for(i=1;i<=n;i++){
		status[i][0]=1%MOD;
		status[i][1]=(status[i-1][0]+status[i-1][1]*2)%MOD;
		status[i][2]=(status[i-1][0]+status[i-1][2])%MOD;
		status[i][3]=(status[i-1][1]+status[i-1][3]*2)%MOD;
		status[i][4]=(status[i-1][1]+status[i-1][2]+status[i-1][4]*2)%MOD;
		status[i][5]=(status[i-1][3]+status[i-1][4]+status[i-1][5]*2)%MOD;
	}
	cout<<status[n][5]<<endl;
	return 0;
}

Remarks

This program is written in C++ and uses standard input and output functions.

If you like this blog or find it useful for you, you are welcome to comment on it. You are also welcome to share this blog, so that more people can participate in it. If the images used in the blog infringe your copyright, please contact the author to delete them. Thank you !

...

00:00

This is the fourth question of CCF-CSP in December 2013.