SDUT 2022 summer team contest 6th（for 21）

A - Secrete Master Plan

Master Mind KongMing gave Fei Zhang a secrete master plan stashed in a pocket. The plan instructs how to deploy soldiers on the four corners of the city wall. Unfortunately, when Fei opened the pocket he found there are only four numbers written in dots on a piece of sheet. The numbers form 2×22×2 matrix, but Fei didn't know the correct direction to hold the sheet. What a pity!

Given two secrete master plans. The first one is the master's original plan. The second one is the plan opened by Fei. As KongMing had many pockets to hand out, he might give Fei the wrong pocket. Determine if Fei receives the right pocket.

Input

The first line of the input gives the number of test cases, T(1≤T≤10^4)T(1≤T≤104). TT test cases follow. Each test case contains 4 lines. Each line contains two integers a_{i0}ai0​ and a_{i1}ai1​ (1≤a_{i0},a_{i1}≤1001≤ai0​,ai1​≤100). The first two lines stands for the original plan, the 3_{rd}3rd​ and 4_{th}4th​ line stands for the plan Fei opened.

Output

For each test case, output one line containing "Case #x: y", where x is the test case number
(starting from 1) and yy is either "POSSIBLE" or "IMPOSSIBLE" (quotes for clarity).

Sample

4 1 2 3 4 1 2 3 4 1 2 3 4 3 1 4 2 1 2 3 4 3 2 4 1 1 2 3 4 4 3 2 1

Case #1: POSSIBLE Case #2: POSSIBLE Case #3: IMPOSSIBLE Case #4: POSSIBLE

/*Where there is light, in my heart.*/
/*SUMMER_TRAINING*/
#include 
#include 
#include 
#include 
#include 
using namespace std;
//
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define INF 0x3f3f3f
#define ll long long
#define INF 0x3f3f3f3f
#define mem(a,b) memset(a,b,sizeof(a))
#define unmap(a,b) unordered_map
#define unset(a) unordered_set
#define F first
#define S second
#define pb push_back
#define rep(i, a, b) for (int i = (a); i <= (b); ++i)
#define _rep(i, a, b) for (int i = (a); i >= (b); --i)
#define mode 1e4+7
#define pi acos(-1)
#define U_queue priority_queue,greater >
typedef double db;
typedef pair<int,int> PII;
typedef pair PLL;
typedef vector<int> vi;
const int N = 5010;
//====================================================//
int num;
void solve(){
     num++;
     int a,b,c,d;
     cin>>a>>b>>c>>d;
     int e,f,g,h;
     cin>>e>>f>>g>>h;
     if(e==a&&f==b&&g==c&&h==d)
          printf("Case #%d: POSSIBLE\n",num);
     else if(e==c&&f==a&&g==d&&h==b)
          printf("Case #%d: POSSIBLE\n",num);
     else if(e==d&&f==c&&g==b&&h==a)
          printf("Case #%d: POSSIBLE\n",num);
     else if(e==b&&f==d&&g==a&&h==c)
          printf("Case #%d: POSSIBLE\n",num);
     else
         printf("Case #%d: IMPOSSIBLE\n",num);
}
signed main(){
     int t;
     scanf("%d",&t);
     
     while(t--){
     //for(int i=2;i<=t;i++){
          solve();
     }
}
 
//made by melody 20220806

G - Ancient Go

Yu Zhou likes to play Go with Su Lu. From the historical research, we found that there are much difference on the rules between ancient go and modern go.

Here is the rules for ancient go they were playing:

\cdot⋅The game is played on a 8×88×8 cell board, the chess can be put on the intersection of the board lines, so there are 9×99×9 different positions to put the chess.
\cdot⋅Yu Zhou always takes the black and Su Lu the white. They put the chess onto the game board alternately.
\cdot⋅The chess of the same color makes connected components(connected by the board lines), for each of the components, if it's not connected with any of the empty cells, this component dies and will be removed from the game board.
\cdot⋅When one of the player makes his move, check the opponent's components first. After removing the dead opponent's components, check with the player's components and remove the dead components.
One day, Yu Zhou was playing ancient go with Su Lu at home. It's Yu Zhou's move now. But they had to go for an emergency military action. Little Qiao looked at the game board and would like to know whether Yu Zhou has a move to kill at least one of Su Lu's chess.

Input

The first line of the input gives the number of test cases, T(1≤T≤100)T(1≤T≤100). TT test cases follow. Test cases are separated by an empty line. Each test case consist of 9 lines represent the game board. Each line consists of 9 characters. Each character represents a cell on the game board. '.'′.′ represents an empty cell. 'x'′x′ represents a cell with black chess which owned by Yu Zhou. 'o'′o′ represents a cell with white chess which owned by Su Lu.

Output

For each test case, output one line containing Case #x: y, where xx is the test case number (starting from 1) and yy is Can kill in one move!!! if Yu Zhou has a move to kill at least one of Su Lu's components. Can not kill in one move!!! otherwise.

Sample

2 .......xo ......... ......... ..x...... .xox....x .o.o...xo ..o...... .....xxxo ....xooo. ......ox. .......o. ...o..... ..o.o.... ...o..... ......... .......o. ...x..... ........o

Case #1: Can kill in one move!!! Case #2: Can not kill in one move!!!

Hint

In the first test case, Yu Zhou has 4 different ways to kill Su Lu's component.

In the second test case, there is no way to kill Su Lu's component.

固定的88地图 直接暴力

/*Where there is light, in my heart.*/
/*SUMMER_TRAINING*/
#include 
#include 
#include 
#include 
#include 
using namespace std;
//
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define ll long long
#define INF 0x3f3f3f3f
#define mem(a,b) memset(a,b,sizeof(a))
#define unmap(a,b) unordered_map
#define unset(a) unordered_set
#define F first
#define S second
#define pb push_back
#define rep(i, a, b) for (int i = (a); i <= (b); ++i)
#define _rep(i, a, b) for (int i = (a); i >= (b); --i)
#define mode 1e4+7
#define pi acos(-1)
#define U_queue priority_queue,greater >
typedef double db;
typedef pair<int,int> PII;
typedef pair PLL;
typedef vector<int> vi;
const int N = 1e3+5;
const int mod=1e9+7;
//====================================================//
int num;
char a[10][10];
bool st[10][10];
int fx[]={0,0,1,-1};
int fy[]={1,-1,0,0};
 
bool check(int x,int y){
     if(x>0&&x<=9&&y>0&&y<=9&&st[x][y]==false) return true;
     return false;
}
int dfs(int x,int y){
     st[x][y]=1;
     int X=0,Y=0;
     int sum=0;
     for(int i=0;i<4;i++){
          X=x+fx[i];  
          Y=y+fy[i];
          if(check(X,Y)){
               if(a[X][Y]=='.'){
                    st[X][Y]=1;
                    sum++;
               }
               else if(a[X][Y]=='x') continue;
               else if(a[X][Y]=='o'){
                    sum+=dfs(X,Y);
               }
          }
     }
     return sum;
}
void solve(){
     num++;
     for(int i=1;i<=9;i++)
     for(int j=1;j<=9;j++)
     cin>>a[i][j];
     bool flag=false;
     for(int i=1;i<=9;i++)
     for(int j=1;j<=9;j++){
          if(a[i][j]=='o'){
               mem(st,0);
               int t=dfs(i,j);
               if(t==1){
                    flag=true;
                    break;
               }
          }
     }
     if(flag)
     printf("Case #%d: Can kill in one move!!!\n",num);
     else
     printf("Case #%d: Can not kill in one move!!!\n",num);
}
signed main(){
     int t;
     scanf("%d",&t);
     num=0;
     while(t--){
     //for(int i=1;i<=t;i++){
          solve();
     }
}
 
//made by melody 20220806

H - Sudoku

Yi Sima was one of the best counselors of Cao Cao. He likes to play a funny game himself. It looks like the modern Sudoku, but smaller.

Actually, Yi Sima was playing it different. First of all, he tried to generate a 4×44×4 board with every row contains 1 to 4, every column contains 1 to 4. Also he made sure that if we cut the board into four 2×22×2 pieces, every piece contains 1 to 4.

Then, he removed several numbers from the board and gave it to another guy to recover it. As other counselors are not as smart as Yi Sima, Yi Sima always made sure that the board only has one way to recover.

Actually, you are seeing this because you've passed through to the Three-Kingdom Age. You can recover the board to make Yi Sima happy and be promoted. Go and do it!!!

Input

The first line of the input gives the number of test cases, T(1≤T≤100)T(1≤T≤100). TT test cases follow. Each test case starts with an empty line followed by 4 lines. Each line consist of 4 characters. Each character represents the number in the corresponding cell (one of '1', '2', '3', '4'). '*' represents that number was removed by Yi Sima.

It's guaranteed that there will be exactly one way to recover the board.

Output

For each test case, output one line containing Case #x:, where xx is the test case number (starting from 1). Then output 4 lines with 4 characters each. indicate the recovered board.

Sample

3 **** 2341 4123 3214 *243 *312 *421 *134 *41* **3* 2*41 4*2*

Case #1: 1432 2341 4123 3214 Case #2: 1243 4312 3421 2134 Case #3: 3412 1234 2341 4123

 dfs

#include 
using namespace std;
 
const int N = 10;
int mp[N][N];
char s[N];
int vis[N][N];
int stx[N][N],sty[N][N];
int flag;
 
bool judge(int x,int y,int a)
{
    if(x>=1&&x<=2)
    {
        if(y>=1&&y<=2)
        {
            if(mp[1][1]==a||mp[1][2]==a||mp[2][1]==a||mp[2][2]==a)
                return false;
        }
        else if(mp[1][3]==a||mp[1][4]==a||mp[2][3]==a||mp[2][4]==a)
        {
            return false;
        }
    }
    else
    {
        if(y>=1&&y<=2)
        {
            if(mp[3][1]==a||mp[3][2]==a||mp[4][1]==a||mp[4][2]==a)
                return false;
        }
        else if(mp[3][3]==a||mp[3][4]==a||mp[4][3]==a||mp[4][4]==a)
            return false;
    }
    return true;
}
void dfs(int x,int y)
{
    if(flag)return ;
    else if(y>4)
    {
        for(int i=1; i<=4; i++)
        {
            for(int j=1; j<=4; j++)
            {
                printf("%d",mp[i][j]);
            }
            printf("\n");
        }
        flag=1;
        return ;
    }
    else if(x>4)dfs(1,y+1);
    else if(!mp[x][y])
    {
        for(int i=1; i<=4; ++i)
        {
            if(!stx[x][i]&&!sty[y][i]&&judge(x,y,i))
            {
                stx[x][i]=sty[y][i]=1;
                mp[x][y]=i;
                dfs(x+1,y);
                mp[x][y]=0;
                stx[x][i]=sty[y][i]=0;
            }
        }
    }
    else dfs(x+1,y);
}
int main()
{
    int t,i,j,k=1;
    scanf("%d",&t);
    while(t--)
    {
        memset(stx,0,sizeof(stx));
        memset(sty,0,sizeof(sty));
        for(i=1; i<=4; i++)
        {
            scanf("%s",s);
            for(j=0; j<4; j++)
            {
                if(s[j]=='*')
                {
                    mp[i][j+1]=0;
                }
                else
                {
                    mp[i][j+1]=s[j]-'0';
                    stx[i][mp[i][j+1]]=1;
                    sty[j+1][mp[i][j+1]]=1;
                }
            }
        }
        flag=0;
        printf("Case #%d:\n",k++);
        dfs(1,1);
    }
    return 0;
}

L - Huatuo's Medicine

Huatuo was a famous doctor. He use identical bottles to carry the medicine. There are different types of medicine. Huatuo put medicines into the bottles and chain these bottles together.

However, there was a critical problem. When Huatuo arrived the patient's home, he took the chain out of his bag, and he could not recognize which bottle contains which type of medicine, but he remembers the order of the bottles on the chain.

Huatuo has his own solution to resolve this problem. When he need to bring 2 types of medicines, E.g. AA and BB, he will put AA into one bottle and put BB into two bottles. Then he will chain the bottles in the order of '-B-A-B-'′−B−A−B−′. In this way, when he arrived the patient's home, he knew that the bottle in the middle is medicine AA and the bottle on two sides are medicine BB.

Now you need to help Huatuo to work out what's the minimal number of bottles needed if he want to bring NN types of medicine.

Input

The first line of the input gives the number of test cases, T(1≤T≤100)T(1≤T≤100). TT lines follow. Each line consist of one integer N(1≤N≤100)N(1≤N≤100), the number of types of the medicine.

Output

For each test case, output one line containing Case #x: y, where xx is the test case number (starting from 1) and yy is the minimal number of bottles Huatuo needed.

Sample

1 2

Case #1: 3

/*Where there is light, in my heart.*/
/*SUMMER_TRAINING*/
#include 
#include 
#include 
#include 
#include 
using namespace std;
//
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define INF 0x3f3f3f
#define ll long long
#define INF 0x3f3f3f3f
#define mem(a,b) memset(a,b,sizeof(a))
#define unmap(a,b) unordered_map
#define unset(a) unordered_set
#define F first
#define S second
#define pb push_back
#define rep(i, a, b) for (int i = (a); i <= (b); ++i)
#define _rep(i, a, b) for (int i = (a); i >= (b); --i)
#define mode 1e4+7
#define pi acos(-1)
#define U_queue priority_queue,greater >
typedef double db;
typedef pair<int,int> PII;
typedef pair PLL;
typedef vector<int> vi;
const int N = 5010;
//====================================================//
signed main(){
     int t;
     scanf("%d",&t);
     //while(t--){
     for(int i=1;i<=t;i++){
         int n;
     cin>>n;
     int res=2*n-1;
     printf("Case #%d: %d\n",i,res);
     }
}
 
//made by melody 202208

D - Pick The Sticks

The story happened long long ago. One day, Cao Cao made a special order called "Chicken Rib" to his army. No one got his point and all became very panic. However, Cao Cao himself felt very proud of his interesting idea and enjoyed it.

Xiu Yang, one of the cleverest counselors of Cao Cao, understood the command Rather than keep it to himself, he told the point to the whole army. Cao Cao got very angry at his cleverness and would like to punish Xiu Yang. But how can you punish someone because he's clever? By looking at the chicken rib, he finally got a new idea to punish Xiu Yang.

He told Xiu Yang that as his reward of encrypting the special order, he could take as many gold sticks as possible from his desk. But he could only use one stick as the container.

Formally, we can treat the container stick as an LL length segment. And the gold sticks as segments too. There were many gold sticks with different length a_{i}ai​ and value v_{i}vi​. Xiu Yang needed to put these gold segments onto the container segment. No gold segment was allowed to be overlapped. Luckily, Xiu Yang came up with a good idea. On the two sides of the container, he could make part of the gold sticks outside the container as long as the center of the gravity of each gold stick was still within the container. This could help him get more valuable gold sticks.

As a result, Xiu Yang took too many gold sticks which made Cao Cao much more angry. Cao Cao killed Xiu Yang before he made himself home. So no one knows how many gold sticks Xiu Yang made it in the container.

Can you help solve the mystery by finding out what's the maximum value of the gold sticks Xiu Yang could have taken?

Input

The first line of the input gives the number of test cases, T(1≤T≤100)T(1≤T≤100). TT test cases follow. Each test case start with two integers, N(1≤N≤1000)N(1≤N≤1000) and L(1≤L≤2000)L(1≤L≤2000), represents the number of gold sticks and the length of the container stick. NN lines follow. Each line consist of two integers, a_{i}(1≤a_{i}≤2000)ai​(1≤ai​≤2000) and v_{i}(1≤v_{i}≤10^{9})vi​(1≤vi​≤109), represents the length and the value of the i_{th}ith​ gold stick.

Output

For each test case, output one line containing Case #x: y, where xx is the test case number (starting from 1) and yy is the maximum value of the gold sticks Xiu Yang could have taken.

Sample

4 3 7 4 1 2 1 8 1 3 7 4 2 2 1 8 4 3 5 4 1 2 2 8 9 1 1 10 3

Case #1: 2 Case #2: 6 Case #3: 11 Case #4: 3

Hint

In the third case, assume the container is lay on x-axis from 0 to 5. Xiu Yang could put the second gold stick center at 0 and put the third gold stick center at 5,
so none of them will drop and he can get total 2+9=11 value.

In the fourth case, Xiu Yang could just put the only gold stick center on any position of [0,1], and he can get the value of 3.

/*Where there is light, in my heart.*/
/*SUMMER_TRAINING*/
#include 
#include 
#include 
#include 
#include 
using namespace std;
//
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define ll long long
#define INF 0x3f3f3f3f
#define mem(a,b) memset(a,b,sizeof(a))
#define unmap(a,b) unordered_map
#define unset(a) unordered_set
#define F first
#define S second
#define pb push_back
#define rep(i, a, b) for (int i = (a); i <= (b); ++i)
#define _rep(i, a, b) for (int i = (a); i >= (b); --i)
#define mode 1e4+7
#define pi acos(-1)
#define U_queue priority_queue,greater >
typedef double db;
typedef pair<int,int> PII;
typedef pair PLL;
typedef vector<int> vi;
const int N = 1e4+5;
const int mod=1e9+7;
//====================================================//
int num;
struct node{
     int w;
     ll v;
}a[N];
void solve(){
     num++;
     int n,m;
     cin>>n>>m;
     m*=2;
     ll Max=0;
     for(int i=0;i
          cin>>a[i].w>>a[i].v;
          a[i].w*=2;
          if(a[i].w>=2*m){
               Max=max(Max,a[i].v);
          }
     }
     ll dp[N][3];
     mem(dp,0);
     for(int i=0;i
          if(a[i].w>=2*m) continue;
          for(int j=m;j>=0;j--){
               for(int k=0;k<3;k++){
                    if(j-a[i].w>=0){
                         dp[j][k]=max(dp[j][k],dp[j-a[i].w][k]+a[i].v);
                    }
                    if(k&&a[i].w<=2*j){
                         dp[j][k]=max(dp[j][k],dp[j-a[i].w/2][k-1]+a[i].v);
                    }
               }
          }
     }
     ll ans=max(dp[m][0],dp[m][1]);
     ans=max(ans,dp[m][2]);
     printf("Case #%d: %lld\n",num,max(ans,Max));
}
signed main(){
     int t;
     scanf("%d",&t);
     num=0;
     while(t--){
     //for(int i=1;i<=t;i++){
          solve();
     }
}
 
//made by melody 20220806