# La Salle Pui China programming challenge 2017

### Article directory

Topic connection: https://codeforces.com/group/EdIaLnPMK4/contest/101522

### G.Gravitational Tetris

**Question meaning: * * similar to Tetris, 10 columns. Given the number of remaining blocks in each column (< 12), each row can be eliminated by using 8 blocks of different shapes

Output the total number of blocks needed, and the model and location of each line (the column at the lower left corner of the block placement location)

Solution: because it can be eliminated, each model is composed of 4 blocks, 10 columns, and only need to output any scheme, only need to consider one elimination row number that can meet all possible situations at least. Therefore, it can be assumed that 40 rows can be paved (> = 24 and can be paved through the combination of 1, 2, 3 and 4; by using model AG, the first 9 columns can be paved with 40 rows, a[i]+4A+3G=40, and the satisfied group A,G is enough, then a[i+1]+=G;(G is L-shaped)

The number of squares in the last column (divided by 4 redundant 2 or divided by 4) is discussed by classification. 38 grids (divided by 4 redundant 2) or 40 grids are paved with AG. For the former, use 1 E (in column 9) and 2 B (in column 1 and 5).

Record the total number of uses, and store the use model and location

```#include<bits/stdc++.h>
using namespace std;
int a[10],b,c,cnt=0;
vector<char>s;
vector<int>v;
int main(){
for(int i=0;i<10;i++){
scanf("%d",&a[i]);
}
for(int i=0;i<9;i++){//40 rows in the first 9 trains
b=(40-a[i])/4;
for(int j=b;j>=0;j--){
if((40-a[i]-j*4)%3==0){
c=(40-a[i]-j*4)/3;
b=j;
break;
}
}
a[i+1]+=c;
a[i]+=4*b+c*3;
for(int j=1;j<=b;j++){
s.push_back('A');
v.push_back(i+1);
}
for(int j=1;j<=c;j++){
s.push_back('G');
v.push_back(i+1);
}
cnt+=c+b;
}
if(a[9]%4==0){//Column 10 discussed separately
for(int i=1;i<=(40-a[9])/4;i++){
s.push_back('A');
v.push_back(10);
cnt++;
}
}else if(a[9]%4==2){
for(int i=1;i<=(38-a[9])/4;i++){
s.push_back('A');
v.push_back(10);
cnt++;
}
s.push_back('E');
v.push_back(9);
s.push_back('B');
v.push_back(1);
s.push_back('B');
v.push_back(5);
cnt+=3;
}
cout<<cnt<<endl;
for(int i=0;i<s.size();i++){
cout<<s[i]<<" "<<v[i]<<endl;
}
}
```

### H.Hit!

Given the center coordinates and radius of two circles, output any point, which is in the common part of two circles

**Solution: * * two circles are known,
(x−x1)2+(y−y1)2=r12，，(x−x2)2+(y−y2)2=r22 (x-x_1 )^2+(y-y_1 )^2=r_1^2，，(x-x_2 )^2+(y-y_2 )^2=r_2^2 (x−x1​)2+(y−y1​)2=r12​，，(x−x2​)2+(y−y2​)2=r22​
The two circle formula subtracts a straight line (common chord or tangent line) so that the point where it intersects the connecting center line is P (in the common part where the two circles intersect)
O1P = λ PO2 (here is the length, λ > 0), O ﹣ 1 p = λ Po ﹣ 2 (here is the length, λ > 0), O1 P = λ PO2 (here is the length, λ > 0),

Where λ = ∣ ((x1 − x1)2+(y1 − y2)2+(r12 − r22))/((x1 − x2)2+(y − y2)2 − (r12 − r22)) ∣ Where λ = | ((x | 1-x | ^ 2 + (Y | - y 〝 2) ^ 2 + (R 〝 1-y 〝 2)) / ((x 〝 1-x 〝 2) ^ 2 + (Y-Y 〝 2) ^ 2 - (R 〝 1-2-r 〝2))| Where λ = ∣ ((x1 − x1) 2+(y1 − y2) 2+(r12 − r22)) / ((x1 − x2) 2+(y − y2) 2 − (r12 − r22)) ∣

Then take the center line as the hypotenuse, parallel to the triangle of the right angle side of the x,y axis, and get the horizontal and vertical coordinates of the point through the proportion line segment

In particular, when λ = r1/r2, the two circles are tangent, at this time, the coordinate of point P
p((x1r1+x2r1)/(r1+r2),(y1r2+y2r1)/(r1+r2)) p((x_1 r_1+x_2 r_1)/(r_1+r_2 ),(y_1 r_2+y_2 r_1)/(r_1+r_2 )) p((x1​r1​+x2​r1​)/(r1​+r2​),(y1​r2​+y2​r1​)/(r1​+r2​))
(the coordinate formula substituting the tangent condition is in line with all the points passing. For the sake of safety, the general coordinate formula can be obtained through the proportional line segment.)

```#include<bits/stdc++.h>
using namespace std;
int xa,ya,ra,xb,yb,rb;
int main(){
cin>>xa>>ya>>ra>>xb>>yb>>rb;
double r=ra+rb;
printf("%.6lf %.6lf",(double)(xa*rb+xb*ra)/r,(double)(ya*rb+yb*ra)/r);
}
```

### I. Inverted Signs

**Meaning: * * a series of numbers. The chaos index is defined as the sum of the difference between two adjacent numbers. Change the symbols of consecutive digits to minimize the chaos index and find the minimum value

Obviously, if H[l] is changed The sign of H[r], only the two terms of | H[l]-H[l-1] | and | H[r+1]-H[r] |, can change the chaos index

The size of the change is|H[i]+H[i-1]|-|H[i]-H[i-1]|

Traverse to find out all the items with negative changes (reduce the chaos number), select the two items with the most negative changes, and consider the special case

```#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1000005;
ll n,h[maxn],sum=0;
vector<ll>v;
int main() {
scanf("%lld",&n);
scanf("%lld",&h[1]);
for(ll i=2; i<=n; i++) {
scanf("%lld",&h[i]);
sum+=abs(h[i]-h[i-1]);
int t=abs(h[i-1]+h[i])-abs(h[i]-h[i-1]);
if(t<0)  v.push_back(t);//Negative changed item
}
int len=v.size();
if(len==0) return cout<<sum,0;
sort(v.begin(),v.end());
if(len==1) return cout<<sum+v[0],0;
if(len>1) return cout<<sum+v[0]+v[1],0;
}
```

### J . Juicy Candies

**Question meaning: * * find the string with the smallest dictionary order in all strings composed of B 'B', R 'R' and S' S' (different requirements for adjacent letters). No: None

**Question solution: * * definition dp [i] [b] [r] [s] represents the number of strings with B 'B', R 'R', s' s', I representing prefixes beginning with letters (i=0 represents B, 1 represents R, 2 represents s)

Obviously DP [0] [1] [0] [0] = DP [1] [0] [1] [0] = DP [2] [0] [0] [0] [1] = 1 has a state transition equation

When i=0: dp[i] [b] [r] [s]=dp [1] [b-1] [r] [s]+dp [2] [b-1] [r] [s]

When i=1: dp[i] [b] [r] [s]=dp [0] [b] [r-1] [s]+dp [2] [b] [r-1] [s]

When i=2: dp[i] [b] [r] [s]=dp [0] [b] [r] [s-1]+dp [1] [b] [r] [s-1]

Does not exist when DP [0] [b] [R] [S] + DP [1] [b] [R] [S] + DP [2] [b] [R] [S] < K

To find a string, follow the following:

(1): b<B&c!='B'&dp[0] [B-b] [R-r] [S-s]>=K, +'B',K-=dp[0] [B-b] [R-r] [S-s] ,Go to (4)

(2): r<R&c!='R'&dp[1] [B-b] [R-r] [S-s]>=K, +'R',K-=dp[1] [B-b] [R-r] [S-s] Go to (4)

(3): s<S&c!='S'&dp[2] [B-b] [R-r] [S-s]>=K, +'S', K-=dp[2] [B-b] [R-r] [S-s]

(4) : update the values of b,r,s,c

```#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll maxn=1e18+5;
ll B,R,S,K;
ll dp[3][205][205][205];//dp[i][b][r][s] number of strings prefixed with B, R, s, I
string str;
int main(){
scanf("%lld%lld%lld%lld",&B,&R,&S,&K);
dp[0][1][0][0]=dp[1][0][1][0]=dp[2][0][0][1]=1;
for(int a=0;a<=B;a++){
for(int b=0;b<=R;b++){
for(int c=0;c<=S;c++){
for(int i=0;i<3;i++){//state transition
if(a&&i==0) dp[i][a][b][c]+=dp[1][a-1][b][c]+dp[2][a-1][b][c];
if(b&&i==1) dp[i][a][b][c]+=dp[0][a][b-1][c]+dp[2][a][b-1][c];
if(c&&i==2) dp[i][a][b][c]+=dp[0][a][b][c-1]+dp[1][a][b][c-1];
if(dp[i][a][b][c]>=K) dp[i][a][b][c]=maxn;
}
}
}
}
if(dp[0][B][R][S]+dp[1][B][R][S]+dp[2][B][R][S]<K) return cout<<"None",0;//The string with the smallest dictionary order k does not exist
ll p=-1,b=B,r=R,s=S;
for(int i=1;i<=B+R+S;i++){
for(int j=0;j<3;j++){
if(j!=p){
if(dp[j][b][r][s]>=K){
if(b&&j==0){
b--;
str.push_back('B');
}else if(r&&j==1){
r--;
str.push_back('R');
}else if(s&&j==2){
s--;
str.push_back('S');
}
p=j;
break;
}else K-=dp[j][b][r][s];
}
}
}
cout<<str;
return 0;
}
```

### K .Knights

**Question meaning: * * N*M rectangle, all the squares in the same row or in the same row that have been occupied will be occupied. To occupy all the squares on the basis of a given occupied grid, you need to send a knight to occupy at least how many squares;

**Solution: * * 4 corners must be occupied by knights alone. At the same time, 4 corners are occupied. The whole rectangle is also occupied, so at least 4 corners are needed

Consider special case 1 * 1: at least one; one row or one column: at least two others: four; deduct the given angle

```#include<bits/stdc++.h>
using namespace std;
int n,m,k,x,y,cnt=0;
int main(){
scanf("%d%d%d",&n,&m,&k);
for(int i=1;i<=k;i++){
scanf("%d%d",&x,&y);
if(x==1&&y==1) cnt++;
else if(x==1&&y==m) cnt++;
else if(x==n&&y==1) cnt++;
else if(x==n&&y==m) cnt++;
}
if(n==1&&m==1) return cout<<1-cnt,0;
if(n==1||m==1) return cout<<2-cnt,0;
return cout<<4-cnt,0;
}
```

### L .Let Me Count The Ways

Meaning: given two rows, n columns and m columns (n > = m), put n+m numbers into this m+n grid, so that the numbers are not repeated, the number in front of each row is larger than the number in the back, the number in the first row of each column is larger than the number in the second row,,, there are several ways to put them. Take mold for 1e9+7

Answer: select n numbers C (m+n,n) according to the size of the first row, and subtract the number C (n+m,n+1) that does not conform to the size rule of the column;

That is, c (M + N, n) - c (n + m, N + 1)

Here we use the fast power inverse element, Lucas theorem. There are problems

```#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int p=1e9+7;
ll n,m;
ll quick_mod(ll a, ll b) {
ll ans = 1;
a %= p;
while(b) {
if(b & 1) {
ans = ans * a % p;
b--;
}
b >>= 1;
a = a * a % p;
}
return ans;
}
ll C(ll n, ll m) {
if(m > n) return 0;
ll ans = 1;
for(int i=1; i<=m; i++) {
ll a = (n + i - m) % p;
ll b = i % p;
ans = ans * (a * quick_mod(b, p-2) % p) % p;
}
return ans;
}
ll Lucas(ll n, ll m) {
if(m == 0) return 1;
return C(n % p, m % p) * Lucas(n / p, m / p) % p;
}
int main() {
scanf("%lld%lld", &n, &m);
printf("%lld", Lucas(m+n,n)-Lucas(m+n,n+1));
return 0;
}

```
```ll b = i % p;
ans = ans * (a * quick_mod(b, p-2) % p) % p;
}
return ans;
```

}
ll Lucas(ll n, ll m) {
if(m == 0) return 1;
return C(n % p, m % p) * Lucas(n / p, m / p) % p;
}
int main() {
scanf("%lld%lld", &n, &m);
printf("%lld", Lucas(m+n,n)-Lucas(m+n,n+1));
return 0;
}

Published 3 original articles, praised 0 and visited 96

Tags: Programming

Posted on Thu, 30 Jan 2020 23:21:12 -0800 by gintjack