# Educational Codeforces Round 109 (Rated for Div. 2) (A, B, D)

A. Potion-making

Solution idea: for a mathematical thinking problem, we abstract the description of the problem into w/(e+w)=k/100, because the input of k can be regarded as a known quantity. What we need to find is e+w, and then we move the formula to e+w=w*100/k. now the only unknown quantity of this formula becomes W. we just need to enumerate w so that this formula can be divided, Finally, we can output the enumerated W

The ac code is attached below

```#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <string>
#include <cstring>
#include <queue>
#include <set>
#include <map>
#include <vector>
#define dbg(a)  cout<<#a<<" : "<<a<<endl;
#define IOS ios_base::sync_with_stdio(false); cin.tie(NULL);
#define PAUSE   system("pause")
#define sd(a)       scanf("%d",&a)
#define sll(a)      scanf("%lld",&a)
#define sdd(a,b)    scanf("%d%d",&a,&b)
#define sddd(a,b,c) scanf("%d%d%d",&a,&b,&c)
#define sf(a)       scanf("%lf",&a)
#define sff(a,b)    scanf("%lf%lf",&a,&b)
#define sfff(a,b,c) scanf("%lf%lf%lf",&a,&b,&c)
using namespace std;
typedef long long ll;
const int maxn=100005;
int t,n,ans;
int main()
{
sd(t);
while(t--)
{
sd(n);
for(int i=1;i<=100;i++)
{
if(100*i%n==0){
printf("%d\n",100*i/n);
break;
}
}
}
//PAUSE;
return 0;
}```

B. Permutation Sort

Solution idea: this topic is to give you n numbers, which are composed of 1~n. you can reorder any interval, but this interval cannot be 1-n. finally, ask you how many times at least you can sort these n numbers into ascending order of 1~n. This is a greedy topic, which can be divided into the following four situations

If there is an increasing order, we do not need to operate the output 0

If the first number is 1, we only need to operate the interval [2~n]. One operation can turn the sequence into incremental order. Similarly, this is the case when the nth number is n

If the first number is not 1 or the nth number is not n, we only need to use one operation to put the nth number at the position of N, or put the first number at 1 to form the above situation. This is that the whole sequence can be incremented and orderly in one operation. In this case, a total of two operations are required, Of course, there is a special case in this case, which is the following

If the first number is n and the last number is 1, such as the sequence is 5 2 3 4 1, we can't move 1 to the first position or n to the nth position after one operation, so we need two operations to form the second case, so this special case requires three operations in total

The ac code is attached below

```#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <string>
#include <cstring>
#include <queue>
#include <set>
#include <map>
#include <vector>
#define dbg(a)  cout<<#a<<" : "<<a<<endl;
#define IOS ios_base::sync_with_stdio(false); cin.tie(NULL);
#define PAUSE   system("pause")
#define sd(a)       scanf("%d",&a)
#define sll(a)      scanf("%lld",&a)
#define sdd(a,b)    scanf("%d%d",&a,&b)
#define sddd(a,b,c) scanf("%d%d%d",&a,&b,&c)
#define sf(a)       scanf("%lf",&a)
#define sff(a,b)    scanf("%lf%lf",&a,&b)
#define sfff(a,b,c) scanf("%lf%lf%lf",&a,&b,&c)
using namespace std;
typedef long long ll;
const int maxn=55;
int t,n;
int a[maxn];
int main()
{
sd(t);
while(t--)
{
int ans=0;
sd(n);
for(int i=1;i<=n;i++)
{
sd(a[i]);
}
int flag=0;
for(int i=1;i<=n;i++)
if(a[i]!=i){
flag=1;
break;
}
if(!flag) printf("0\n");
else if(a[1]==1||a[n]==n)
printf("1\n");
else if(a[1]==n&&a[n]==1)
printf("3\n");
else    printf("2\n");
}
//PAUSE;
return 0;
}```

The idea of solving C problem is not very difficult. I think it's OK to use a monotonous stack for maintenance, but I met many detailed problems in the implementation. The amount of code is a little large, and I won't make up if the code doesn't come out

D. Armchairs

```#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <string>
#include <cstring>
#include <queue>
#include <set>
#include <map>
#include <vector>
#define dbg(a)  cout<<#a<<" : "<<a<<endl;
#define IOS ios_base::sync_with_stdio(false); cin.tie(NULL);
#define PAUSE   system("pause")
#define sd(a)       scanf("%d",&a)
#define sll(a)      scanf("%lld",&a)
#define sdd(a,b)    scanf("%d%d",&a,&b)
#define sddd(a,b,c) scanf("%d%d%d",&a,&b,&c)
#define sf(a)       scanf("%lf",&a)
#define sff(a,b)    scanf("%lf%lf",&a,&b)
#define sfff(a,b,c) scanf("%lf%lf%lf",&a,&b,&c)
using namespace std;
typedef long long ll;
const double eps = 1e-10;
const double pi = acos(-1.0);
const int maxn = 5010;
int n;
int x[maxn];
int a[maxn],b[maxn];
ll dp[maxn][maxn];
ll minx[maxn][maxn];
int main()
{
sd(n);
for(int i = 1; i <= n; i++){
sd(x[i]);
if(x[i]) a[++a[0]] = i;
else b[++b[0]] = i;
}
sort(a+1,a+a[0]+1);
sort(b+1,b+b[0]+1);
for(int i = 1; i <= a[0]; i++){
for(int j = i; j <= b[0]; j++){
dp[i][j] = minx[i-1][j-1] + (ll)abs(a[i]-b[j]);
if(j == i) minx[i][j] = dp[i][j];
else minx[i][j] = min(minx[i][j-1],dp[i][j]);
}
}
ll ans = 1145141919810;
for(int i = 1; i <= n; i++) if(dp[a[0]][i]) ans = min(ans,dp[a[0]][i]);
if(ans == 1145141919810) ans = 0;
printf("%lld\n",ans);
//PAUSE;
return 0;
}
```

Keywords: cf

Added by meehal on Fri, 11 Feb 2022 17:38:27 +0200