# 2020-2-11 freshman competition

### Question E: find the number that meets the condition

Time limit: 1 Sec memory limit: 128 MB
[Submission] [state]

Title Description

Input N (N < = 32767), output the integer (including N) within N, so that the sum of its numbers is 15, and output 8 numbers per line. The output field width is 6.

input

Only one integer N is included.

output

Number of eligible.

sample input Copy

```200
```

sample output Copy

```    69    78    87    96   159   168   177   186
195```

The problem is very simple. But pay attention to the output format, and the proposal understanding

I write others as% 15 = = 0;

I am drunk.

```//First error code
#include <bits/stdc++.h>
using namespace std;
const int mod=2e5+5;
typedef long long ll;
int A;
int main()
{
int n,cnt=0;
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
int sum=0,m=i;
while(m)
{
sum+=m%10;
m/=10;
}
if(sum%15==0)///They say that sum=15.... this is the wrong point
{
if(cnt%8==0&&cnt)printf("\n");
printf("%6d",i);
cnt++;

}

}
return 0;
}```

```#include <bits/stdc++.h>
using namespace std;
const int mod=2e5+5;
typedef long long ll;
int A;
int main()
{
int n,cnt=0;
scanf("%d",&n);
for(int i=69;i<=n;i++)
{
//int sum=0;
if((i%10+i/10%10+i/100%10+i/1000%10+i/10000%10)==15)
{
if(cnt%8==0&&cnt)printf("\n");
printf("%6d",i);
cnt++;
}

}
return 0;
}```

### Problem B: [divide and conquer] solution of one variable cubic equation

Time limit: 1 Sec memory limit: 128 MB
[Submission] [state]

Title Description

It can be seen as a univariate cubic equation, such as ax3+bx2+cx+d=0. The coefficients (a, b, c, d) of each item in the equation are given, and it is agreed that there are three different real roots (the range of roots is between - 100 and 100) in the equation, and the absolute value of the difference between roots is > = 1. Three real roots are required.

input

Four real numbers: a, b, c, d

output

Output the three real roots in the same line from small to large (spaces are left between roots), and accurate to 2 decimal places

sample input Copy

`1 -5 -4 20`

sample output Copy

```-2.00 2.00 5.00
```

Tips

Data size and engagement
|a|，|b|，|c|，|d|<=10

Although I don't know what divide and conquer means, isn't this enumeration accurate to the decimal????

```#include <bits/stdc++.h>
using namespace std;
const int mod=2e5+5;
typedef long long ll;
int A;
int main()
{
double a,b,c,d;
int cnt=0;
scanf("%lf%lf%lf%lf",&a,&b,&c,&d);
for(double i=-100;i<=100;)
{
if(cnt==3) break;
double sum=a*i*i*i+b*i*i+c*i+d;
if(fabs(sum)<0.000001)
{
cnt++;
printf("%0.2lf ",i);
}

i+=0.01;
}
return 0;
}```

### Problem C: Division of [dynamic programming] number

Time limit: 1 Sec memory limit: 256 MB
[Submission] [state]

Title Description

The rewards of actively exploring space are great, because scientists in the magic world later discovered that their planet would be wiped out by extraterrestrial meteorites or other unexpected events every 150 million years or so by excavating prehistoric civilization sites. The dinosaurs that dominated the planet for more than 100 million years died out as a result. Only an enterprising and innovative cosmic civilization can avoid this "natural punishment". Now, the zenith man launched a large-scale meteorite attack on the magic world. The space defense system of the magic world responded in time, dividing the defense Energy N into k parts to deal with K meteorites. It is known that each part cannot be empty (or it will be hit by meteorites), and any two parts cannot be the same (regardless of the order). For example: n=7, k=3, the following three classifications are considered the same: 1, 1, 5; 1, 5, 1; 5, 1, 1. Ask how many different divisions there are.

input

n，k (6<n≤200，2≤k≤6)

output

An integer, that is, a different division.

sample input Copy

`7 3`

sample output Copy

`4`

I don't know what happened to me. Basically, all the recent dynamic planning is done by using dfs......

```​#include <bits/stdc++.h>
using namespace std;
const int mod=2e5+5;
typedef long long ll;
int cnt=0;
int n,kk;
void dfs(int last,int k,int rest)//In order to avoid repetition, I adopt the idea of A1 < = A2 < = A3 < = A4
//Last is the last obtained length of, rest is the remaining length, always keep rest > = last
{
for(int i=last;i<=rest;i++)
{
if(k==kk-1)
{
if(rest>=last)
cnt++;
break;
}
else{
if(i<=rest-i)
dfs(i,k+1,rest-i);
}
}

}
int main()
{
scanf("%d %d",&n,&kk);
dfs(1,0,n);
printf("%d",cnt);
return 0;
}​```

### Question F: find the longest well ordered string

Time limit: 1 Sec memory limit: 128 MB
[Submission] [state]

Title Description

We call similar strings like "ABC" or "ACEG" as well as "ACB" or "ACCD" or "AGCD" as well as "ABC" or "ACEG" (because they are arranged in ASCII code).
Write a program to find out the longest well ordered string in the typed string and output its length.

input

A string of characters (length ≤ 255).

output

Only one line, the length of the longest well ordered string.

sample input Copy

```23423555423567
```

sample output Copy

5

This is a kind of length to find the longest monotone (Generalized Monotone)

```//I've done similar problems before. This is equivalent to finding the longest monotone sequence...
#include <bits/stdc++.h>
using namespace std;
const int mod=2e5+5;
typedef long long ll;
int A;
int main()
{
char str;
scanf("%s",str);
int len=strlen(str),ans=0;
for(int i=1;i<len;i++)
{
if(str[i]>str[i-1]) A[i]=A[i-1]+1;
ans=max(ans,A[i]);
}
printf("%d",ans+1);
return 0;
}```

### Question G: data access arrangement

Time limit: 1 Sec memory limit: 128 MB
[Submission] [state]

Title Description

Take 1 to N consecutive numbers (1 ≤ n ≤ 9) to form all possible n digits that are not repeated for each number, and number them from small to large. When a number M is entered, the N digits corresponding to the number can be printed out. For example, when n = 3, all three digits that can be composed are: Then, when input number M = 2, output 132.

input

It includes two numbers: positive integer N (1 < = N < = 9) and positive integer M (1 < = M < = 362880).

output

There is only one line, that is, the N digits corresponding to the entered number M.

sample input Copy

```3 2
```

sample output Copy

### But I've been stuck for a long time and have another point. Pay attention to my code comments and know that I've been thinking for a long time....

```​
#include <bits/stdc++.h>
using namespace std;
const int mod=2e5+5;
typedef long long ll;
int vis,A;
int n,k,cnt;
void dfs(int num)
{
if(num==n+1)
{
cnt++;
}
if(cnt==k)
{
for(int i=1;i<=n;i++)
printf("%d",A[i]);
}
else if(cnt<k)
{
for(int i=1; i<=n; i++)
{
if(vis[i])
continue;
else
{
A[num]=i;
vis[i]=1;
dfs(num+1);
if(cnt<k)vis[i]=0;///////////////Critical
}
}
}

}
int main()
{

scanf("%d%d",&n,&k);
dfs(1);

return 0;
}​```

### Question I: base conversion

Time limit: 1 Sec memory limit: 128 MB
[Submission] [state]

Title Description

Lele is learning to convert base numbers, but he is always confused about whether he is doing it right. Please make a program to realize the data conversion between two different base numbers and help him test it.

input

There are three lines in total. The first line is a positive integer, which represents the base n(2 ≤ n ≤ 16) of the number to be converted. The second line is an n-base number. If n > 10, the capital letters A-F are used to represent the numbers 10-15. The decimal value corresponding to the n-base number does not exceed 1000000000. The third line is also a positive integer, which represents the base m(2 ≤ m ≤ 16) of the number after conversion.

output

Only one line, including a positive integer, represents the m-ary number after conversion.

sample input Copy

```16
FF
2```

sample output Copy

`11111111`

Well, I admit that I'm not very proficient in the conversion of base system, but I did a good job in finding the loopholes in this problem, and the data design was ingenious

12 ABA 10

And then I output sum, and then I compare the answers, and I know that there is no revese

```Please treat yourself AC Mark the topic of the. Note that each person can only mark it once! Don't mark what you don't know, the malicious reporter will recycle the account!!!
?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include <bits/stdc++.h>
using namespace std;
const int mod=2e5+5;
typedef long long ll;
char s="0123456789ABCDEF";
vector<char> A;
int main()
{
int n;
char str;
int m;
scanf("%d",&n);
scanf("%s",str);
scanf("%d",&m);
int len=strlen(str);
ll sum=0,k=1;
for(int i=len-1;i>=0;i--)
{
int num=0;
if(str[i]<='9') num=str[i]-'0';
else num=str[i]-'A'+10;
sum+=num*k;////////
k*=n;////////////
}
//printf("%lld\n",sum);
while(sum)
{
int p=sum%m;
A.push_back(s[p]);
sum/=m;
}
reverse(A.begin(),A.end());//////////It's important. It's been a long time
for(int i=0;i<A.size();i++)
{
printf("%c",A[i]);
}
return 0;
}```

### Question H: minimum number of moves

Time limit: 1 Sec memory limit: 128 MB
[Submission] [state]

Title Description

There are n piles of candy (2 ≤ n ≤ 200), arranged in a row, numbered 1, 2 N.
It is known that each pile of candy has a certain number of pieces, and the sum of the pieces is a multiple of n. Move any candy in each pile so that the number of each pile is the same and the number of moves is the least.
Move rule:
Each time you can move any number of candy, the first pile can move to the second pile, the second pile can move to the first or third pile,...... Pile n can only move to pile n-1.
For example, when n=4:
Reactor No. 1 2 3 4
Number 9 8 17 6
There are many ways to move, one of which is:
① Pile 3 moves 4 to pile 4, becoming: 9.8.13.10
② The third pile moves three to the second pile, becoming: 9 11 10 10
③ Pile 2 moves one to pile 1, becoming: 10 10 10 10
After three moves, each pile becomes 10.

input

There are two lines.
The first line is an integer n.
The second line is n integers separated by spaces.

output

An integer representing the minimum number of moves.

sample input Copy

```4
9　8　17　6
```

sample output Copy

`3`

That is, greedy, find the average, anyway, he can only move on the two adjacent sides (except for the special case of head and tail);;;;;

```#include <bits/stdc++.h>
using namespace std;
const int mod=2e5+5;
typedef long long ll;
int A;
int main()
{
int n,cnt=0;
ll sum=0;
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d",A+i);
sum+=A[i];
}
//printf("%lld\n",sum);
int anv=sum/n;
for(int i=1;i<n;i++)
{
if(A[i]<anv)
{
cnt++;
A[i+1]-=(anv-A[i]);
}
if(A[i]>anv)
{
cnt++;
A[i+1]+=(A[i]-anv);
}
}
printf("%d",cnt);
return 0;
}```  Published 24 original articles, won praise 1, visited 623

Tags: REST Programming ascii

Posted on Tue, 11 Feb 2020 07:03:01 -0800 by thor erik