Previous: Xiao Tang began to brush the real title of the 2014 fifth C / C + + group B Blue Bridge Cup
Next: in the liver, in the liver
preface
Winter vacation must kill them!!!
1, Gauss diary
Title Description:
The great mathematician Gauss has a good habit: keep a diary anyway. There is a difference in his diary. He never indicates the date, but uses an integer instead, such as 4210. Later, people know that the integer is the date, which means that the day is the day after Gauss was born. This may also be a good habit. It reminds the owner all the time: how much time can be wasted when the day passes?
Gauss was born on April 30, 1777. In the diary of an important theorem discovered by Gauss, 5343 is marked, so it can be calculated that the day is December 15, 1791. The day Gauss received his doctorate is marked 8113 in his diary. Please calculate the date Gauss received his doctorate.
The format for submitting answers is yyyy MM DD, for example: March 21, 1980
Analysis:
Hey hey, this topic is proper simulation calculation. We will add it day by day, and then when this day is equal to 8113, we will quit
Title Code:
#include <stdio.h>
void riqi(int n)
{
int year=1777;
int yue=4;
int day=30;
for(int i=1;i<=n;i++)
{
day++;
if(yue==4||yue==6||yue==9||yue==4||yue==11)
{
if(day>30)
{
day=1;
yue++;
}
}
else if(yue==1||yue==3||yue==5||yue==7||yue==8||yue==10||yue==12)
{
if(day>31)
{
day=1;
yue++;
}
}
else if((year%400==0)||(year%4==0)&&(year%100!=0)&&(yue==2))
{
if(day>29)
{
day=1;
yue++;
}
}
else
{
if(day>28)
{
day=1;
yue++;
}
}
if(yue>12)
{
yue=1;
year++;
}
}
printf("%d-%d-%d",year,yue,day-1);
}
int main()
{
int n;
scanf("%d",&n);//Input 8113
riqi(n);
return 0;
}
Operation results:
1799-7-16
2, Sloppy formula
Title Description:
Xiao Ming is an acute child. When he was in primary school, he often copied the questions written by the teacher on the blackboard wrong.
Once, the teacher's question was: 36 x 495 =?
He copied it: 396 x 45 =?
But the result is very dramatic. His answer is actually right!!
Because 36 * 495 = 396 * 45 = 17820
There may be many such coincidences, such as 27 * 594 = 297 * 54
Suppose a b c d e represents 5 different numbers from 1 to 9 (note that they are different numbers and do not contain 0)
How many formulas can satisfy the form such as: ab * cde = adb * ce?
Please make use of the advantages of computers to find all the possibilities and answer the types of different formulas.
The formulas satisfying the commutative law of multiplication are of different kinds, so the answer must be an even number.
Analysis:
Hey, hey, direct violence untie, 5-layer for loop
Title Code:
#include <stdio.h>
#include <iostream>
int main()
{
int sum=0;
int temp=0;
int count=0;
for(int i1=1;i1<=9;i1++)//a
{
for(int i2=1;i2<=9;i2++)//b
{
if(i1!=i2)
for(int i3=1;i3<=9;i3++)//c
{
if(i3!=i1&&i3!=i2)
for(int i4=1;i4<=9;i4++)//d
{
if(i4!=i3&&i4!=i2&&i4!=i1)
for(int i5=1;i5<=9;i5++)//e
{
if(i5!=i4&&i5!=i3&&i5!=i2&&i5!=i1)
{
sum=(i1*10+i2)*(i3*100+i4*10+i5);
temp=(i1*100+i4*10+i2)*(i3*10+i5);
if(sum==temp)
{
printf("%d*%d=%d*%d\n",i1*10+i2,i3*100+i4*10+i5,i1*100+i2*10+i4,i3*10+i5);
count++;
}
}
}
}
}
}
}
printf("%d",count);
}
Operation results:
142
3, 39th step
Title Description:
Xiao Ming just finished watching the movie "the 39th step". When he left the cinema, he counted the steps in front of the auditorium. It happened to be 39 steps! Standing in front of the steps, he suddenly thought of another question:
If I can only take one or two steps in each step, I will take the left foot first, then turn left and right, and the last step is the right foot, that is to say, I have to take an even number of steps. So, how many different methods are there after 39 steps?
Please make use of the advantages of computer to help Xiao Ming find the answer. The required submission is an integer.
Analysis:
Harm, isn't this our old recursion
The recursive exit is exactly equal to 39 and just the right foot
Title Code:
#include <stdio.h>
//1 for left foot and 0 for right foot
int taijie(int n,int jio,int &count)
{
if(n>39)
{
return 0;
}
if(n==39&&jio==0)
{
count++;
}
else if(jio==1)
{
taijie(n+1,0,count);
taijie(n+2,0,count);
}
else if(jio==0)
{
taijie(n+1,1,count);
taijie(n+2,1,count);
}
}
int main()
{
int count=0;
taijie(0,0,count);
printf("%d\n",count);
}
Operation results:
51167078
4, Golden continued fraction
Title Description:
The golden section number 0.61803... Is an irrational number. This constant is very important and will appear in many engineering problems. Sometimes you need to get this number very accurate.
For some precision engineering, the accuracy of constants is very important. Perhaps you have heard of the Hubble Space Telescope. After its first launch, it found a manual processing error. For such a behemoth, in fact, it is only a mistake that the mirror is many times thinner than the hair, but it has become "myopia"!
To get back to business, how can we get the golden section number as accurate as possible? There are many ways.
The simpler one is to use continued fraction:
The more "layers" calculated by this continued fraction, the closer its value is to the golden section. Please make use of this feature to find a sufficiently accurate value of the golden section number, which is required to be rounded to 100 decimal places.
The value of 3 digits after the decimal point is 0.618
The value of 4 digits after the decimal point is 0.6180
The value of 5 digits after the decimal point is 0.61803
The value of 7 digits after the decimal point is 0.6180340
(note the 0 in the tail, which cannot be ignored)
Your task is to write the golden section value accurate to 100 decimal places. Note: the mantissa is rounded off! If the mantissa is 0, keep it! Obviously, the answer is a decimal with 100 digits after the decimal point.
Analysis:
Our words are equivalent to a 1 / 2, 2 / 3, 3 / 5. Is it a Fibonacci sequence? Then we just need to simulate and calculate the value of Fibonacci sequence, divide the previous one by the latter one, and then count one output
Title Code:
#include<iostream>
using namespace std;
long long ans[100] = {0,1,1,2};
int main()
{
for( int i = 3; i < 90; i++ )
ans[i] = ans[i-1] + ans[i-2];
long long x = ans[81], y = ans[82];
for( int i = 0; i < 100; i++ )
{
cout << x/y;
x = (x%y)*10;//One by one input
}
return 0;
}
Operation results:
0618033988749894848204586834365637806199342618022749702241907684204945739336382682315131422629959486
5, Prefix judgment
Title Description:
The following code determines the need_ Whether the string pointed to by start is haystack_ The prefix of the string pointed to by start. If not, NULL will be returned. For example, "abcd1234" contains the prefix "abc".
char *prefix(char *haystack_start,char *needle_start)
{
char *haystack=haystack_start;
char *needle=needle_start;
while(*haystack&&*needle)
{
if(_____________________) return NULL; //Fill in the blanks
}
if(*needle) return NULL;
return haystack_start;
}
Analysis:
Hey, hey, are you familiar with this topic? In fact, the comparison process is that the pointers on both sides are + 1 at the same time to see if they are the same. If they are the same, we will jump to the next one. If they are different, we will also skip to know that one side is empty.
Title Code:
*(haystack++)!=*(needle++)
6, Three part sorting
Title Description:
There are many classical algorithms for general sorting, such as quick sorting, Hill sorting and so on. However, in practical application, there are often some special requirements more or less. We don't need to apply those classical algorithms. We can establish a better solution according to the actual situation.
For example, sort the numbers in an integer array: make negative numbers close to the left, positive numbers close to the right, and 0 in the middle. The characteristic of the problem of attention is that order is not required in the negative number region and the positive number region. You can use this feature to end the battle by one linear scan!
The following procedure achieves this goal. Where x points to the integer array to be sorted, and len is the length of the array.
#include <stdio.h>
void sort3p(int *x,int len)
{
int p=0;
int left=0;
int right=len-1;
int t;
while(p<=right)
{
if(x[p]<0)
{
t=x[left]; x[left]=x[p]; x[p]=t; left++; p++;
}
else if(x[p]>0)
{
t=x[right]; x[right]=x[p]; x[p]=t; right--;
}
else
{
_______________________//Fill in the blanks
}
}
}
Analysis:
Uh huh, Xiao Tang likes to do this kind of topic best. His every step is actually a hint to us. According to the meaning of the topic, he divides the less than 0 and greater than 0 on both sides, and then he writes them for us. Then the last else is when we are equal to 0. Let's refer to the previous value to see if it's directly out, However, it should be noted that this position can only be filled in. After we fill in it, we should write it together in + +
Title Code:
x[p++]=0
7, Wrong note
Title Description:
A secret related unit has issued a certain bill and wants to recover it all at the end of the year. Each bill has a unique ID number. The ID numbers of all bills throughout the year are continuous, but the starting number of ID is randomly selected. Due to the negligence of the staff, an error occurred when entering the ID number, resulting in a broken ID and a duplicate ID. Your task is to find out the ID of the broken number and the ID of the duplicate number through programming, assuming that the broken number cannot occur in the maximum and minimu m n umbers. The program is required to first input an integer n (n < 100) to represent the number of subsequent data lines, and then read in N lines of data. The data length of each line is different. It is several (no more than 100) positive integers (no more than 100000) separated by spaces, and each integer represents an ID number. The program is required to output 1 line, including two integers m and N, separated by spaces, where M represents the hyphen ID and N represents the duplicate ID.
For example, user input:
2
5 6 8 11 9
10 12 9
Program output:
7 9
Another example is user input:
6
164 178 108 109 180 155 141 159 104 182 179 118 137 184 115 124 125 129 168 196
172 189 127 107 112 192 103 131 133 169 158
128 102 110 148 139 157 140 195 197
185 152 135 106 123 173 122 136 174 191 145 116 151 143 175 120 161 134 162 190
149 138 142 146 199 126 165 156 153 193 144 166 170 121 171 132 101 194 187 188
113 130 176 154 177 120 117 150 114 183 186 181 100 163 160 167 147 198 111 119
Program output:
105 120
Analysis:
Hei hei, Xiao Tang's method for this topic is to find our maximum value first, because our broken number cannot occur in the maximum and minimum numbers, so we can start from the maximum number, reduce it later, and then count the number of times this number appears in him
Title Code:
#include <stdio.h>
#include <string.h>
int a[100]={0};
int xunzhao(int shu,int a[],int temp)
{
int count=0;
for(int i=0;i<temp;i++)
{
if(shu==a[i])
count++;
}
return count;
}
int main()
{
int temp=0;
int n=0;
int max=-1;
char c;
scanf("%d",&n);
while(n>0)
{
scanf("%d",&a[temp]);
temp++;
c=getchar();
if(c!=' ')
{
n--;
}
}//input data
for(int i=0;i<temp;i++)//Find maximum
{
if(max<a[i])
max=a[i];
}
for(int i=0;i<temp;i++)
{
if(xunzhao(max,a,temp)==0)//max is the number we are looking for, and the return value is the number of times this number appears
{
printf("%d\n",max);
}
if(xunzhao(max,a,temp)==2)
{
printf("%d\n",max);
}
max=max-1;
}
}
Operation results:
[[input sample] 2 5 6 8 11 9 10 12 9 [Output example] 7 9 [[input sample] 6 164 178 108 109 180 155 141 159 104 182 179 118 137 184 115 124 125 129 168 196 172 189 127 107 112 192 103 131 133 169 158 128 102 110 148 139 157 140 195 197 185 152 135 106 123 173 122 136 174 191 145 116 151 143 175 120 161 134 162 190 149 138 142 146 199 126 165 156 153 193 144 166 170 121 171 132 101 194 187 188 113 130 176 154 177 120 117 150 114 183 186 181 100 163 160 167 147 198 111 119 [Output example] 105 120
8, Flip a coin
Title Description:
Problem description
Xiao Ming is playing a coin flipping game.
There are some coins in a row on the table. We use * for the front and o for the back (lowercase letters, not zero).
For example, it may be: **oo***oooo If you flip the two coins on the left at the same time, it becomes: oooo***oooo
Now Xiao Ming's question is: if you know the initial state and the target state to be achieved, you can only flip two adjacent coins at the same time, how many times should you flip at least for a specific situation?
We agree that flipping two adjacent coins is called one-step operation, so the requirements are:
Input format
Two lines of equal length strings represent the initial state and the target state to be achieved respectively. Length of each line < 1000
Output format
An integer representing the minimum number of operation steps.
For example, user input: ********** o****o**** The program should output: 5 User input, for example: *o**o***o*** *o***o**o*** The program should output: 1
Analysis:
Every time it's different, we must turn two coins, so we'll turn it until it's the same
Title Code:
#include<stdio.h>
#include<string.h>
void flips(char *c)
{
if(*c=='*')
*c='o';
else
*c='*';
}
int main()
{
char conis1[1001];
char conis2[1001];
scanf("%s",conis1);
scanf("%s",conis2);
int step=0;
for(int i=0;i<strlen(conis1);i++)
{
if(conis1[i]!=conis2[i])
{
if(conis1[i]=='*')
{
conis1[i]='o';
flips(&conis1[i+1]);
}
else
{
conis1[i]='*';
flips(&conis1[i+1]);
}
step++;
}
}
printf("%d",step);
return 0;
}
Operation results:
[[input sample] ********** o****o**** [Output example] 5 [[input sample] *o**o***o*** *o***o**o*** [Output example] 1
9, Band fraction
Title Description:
100 can be expressed in the form of fraction: 100 = 3 + 69258 / 714, or 100 = 82 + 3546 / 197. Note that in the form of fraction, the numbers 1 ~ 9 appear respectively and only once (excluding 0). Like this band fraction, 100 has 11 representations.
Title Requirements: read a positive integer N (N < 1000 * 1000) from the standard input, and the program outputs the number to form all kinds of numbers represented by fractions without repetition and omission with numbers 1 ~ 9. Note: it is not required to output each representation. Only the number of representations is counted!
Analysis:
Like this topic, hey hey, sometimes our full permutation, let's simulate one by one. The full permutation is directly over, and then we do a small treatment here, that is
100=82+3546/197
100 *197=82 *197+3456
Title Code:
#include <iostream>
#include <algorithm>
#include <stdio.h>
using namespace std;
int n; //Number of goals given by the topic
int num[9]={1,2,3,4,5,6,7,8,9};
int cnt; //Count, the last output result
//Calculate the number of segments in the num array
int calc(int l, int r){
int res = 0;
for(int i = l; i <= r; i++)
res = res * 10 + num[i];
return res;
}
void f(int n){
while(next_permutation(num,num+9)){
for(int i=0;i<7;i++){
for(int j=i+1;j<8;j++){
int a = calc(0,i);
int b = calc(i+1,j);
int c = calc(j+1,8);
if(a * c + b == c * n)
cnt++;
}
}
}
}
int main(){
int n=0;
scanf("%d", &n);
f(n);
printf("%d\n", cnt);
return 0;
}
Operation results:
[[input sample] 100 [Output example] 11 [[input sample] 105 [Output example] 6
10, Consecutive interval number
Title Description:
Xiao Ming has been thinking about such a strange and interesting question these days:
How many consecutive intervals are there in a full permutation of 1~N? The definition of the serial interval here is:
If all the elements in the interval [L, R] (i.e. the L-th to r-th elements of this arrangement) can get a "continuous" sequence with a length of R-L+1 after incremental sorting, it is called this interval serial interval.
When N is very small, Xiao Ming can quickly calculate the answer, but when N becomes large, the problem is not so simple. Now Xiao Ming needs your help.
Input format:
The first line is a positive integer n (1 < = n < = 50000), indicating the scale of the full arrangement.
The second line is N different numbers PI (1 < = Pi < = N), indicating a full arrangement of these N numbers.
Output format:
Output an integer representing the number of different consecutive intervals.
In the first use case, the concatenation intervals are: [1,1], [1,2], [1,3], [1,4], [2,2], [3,3], [4,4]
In the second use case, the serial number intervals are: [1,1], [1,2], [1,3], [1,4], [1,5], [2,2], [3,3], [4,4], [5,5]
Analysis:
Xiao Tang looked at this topic at first and referred to the code of this treasure
Reference code
Title Code:
#include<iostream>
using namespace std;
int main(){
int n = 0;
cin>>n;
int data[n] = {0};
for(int i=0;i<n;i++){
scanf("%d",&data[i]);
}
int ans = 0;
for(int i=0;i<n;i++){
int max = data[i];
int min = data[i];
for(int j=i;j<n;j++){
if(data[j]>max) max = data[j];
if(data[j]<min) min = data[j];
if(max-min == j-i){
ans++;
}
}
}
cout<<ans<<endl;
return 0;
}
Operation results:
[[input sample] 4 3 2 4 1 [Output example] 7 [[input sample] 5 3 4 2 5 1 [Output example] 9
Previous: Xiao Tang began to brush the real title of the 2014 fifth C / C + + group B Blue Bridge Cup
Next: in the liver, in the liver