Luogu Problem Set

Luogu.com is a collaboration of all interesting and challenging Computer Science problems from contests or Olympics.

In order to enrich the problem set and satisfy the needs of CS lovers and geeks, from then on, I will post the English version of all the problems on it, each of which is strictly labeled as the original.

For convenience and submitting format, I will prepare $\geq 10$ random inputs in the pastebin, once you have completed your program, you can test each of them to get an individual output, then you should submit the final answer based on the outputs (e.g. the sum of all the outputs).

Requirments:

Generally, the running time should be less than $1 s$ for all given inputs. Although I've no methods to test the running time, the size of the input should help.
You can use any programming language as you want.
Your algorithm should be always correct for all the circumstances.

Welcome to challenge the problem set :)

#ComputerScience

Easy Math Editor

This discussion board is a place to discuss our Daily Challenges and the math and science related to those challenges. Explanations are more than just a solution — they should explain the steps and thinking strategies that you used to obtain the solution. Comments should further the discussion of math and science.

When posting on Brilliant:

Use the emojis to react to an explanation, whether you're congratulating a job well done , or just really confused .
Ask specific questions about the challenge or the steps in somebody's explanation. Well-posed questions can add a lot to the discussion, but posting "I don't understand!" doesn't help anyone.
Try to contribute something new to the discussion, whether it is an extension, generalization or other idea related to the challenge.
Stay on topic — we're all here to learn more about math and science, not to hear about your favorite get-rich-quick scheme or current world events.

Markdown	Appears as
`italics` or `_italics_`	italics
`bold` or `__bold__`	bold
- bulleted - list	bulleted list
1. numbered 2. list	numbered list
Note: you must add a full line of space before and after lists for them to show up correctly
paragraph 1 paragraph 2	paragraph 1 paragraph 2
`[example link](https://brilliant.org)`	example link
`> This is a quote`	This is a quote
# I indented these lines # 4 spaces, and now they show # up as a code block. print "hello world"	# I indented these lines # 4 spaces, and now they show # up as a code block. print "hello world"

Math	Appears as
Remember to wrap math in `$` ... `$` or `\[` ... `\]` to ensure proper formatting.
`2 \times 3`	$2 \times 3$
`2^{34}`	$2^{34}$
`a_{i-1}`	$a_{i-1}$
`\frac{2}{3}`	$\frac{2}{3}$
`\sqrt{2}`	$\sqrt{2}$
`\sum_{i=1}^3`	$\sum_{i=1}^3$
`\sin \theta`	$\sin \theta$
`\boxed{123}`	$\boxed{123}$

Comments

Luogu P1004 - Square access

As shown above, the image shows a $N \times N$ square, and some of them have treasures. The number denotes the value of treasures.

A thief wants to get as many treasures as possible, in order not to be caught by police, he can only start from the square of the upper left corner $A$ , move rightwards and downwards without backing, to the square of lower right corner $B$ . Along the way on each trial, he can take away the treasure of the squares. Unfortunately, he only has two trials, that is, he will go from $A$ to $B$ twice. Notice that on the second chance, the treasures taken away on the first chance can't be taken again.

Given the size of the square, $N$ and the distribution of the values of treasures, find the maximum revenue the thief can get.

How to submit:

The pastebin below has $10$ inputs. Each input has the format:

A number $N (1 \leq N \leq 50)$ , the size of the square.
$N \times N$ numbers, the distribution of the values of treasures.

You should output: A number $M$ , the maximum revenue the thief can get.

Then submit the sum of all the outputs.

Inputs are here

Alice Smith - 11 months, 1 week ago

what is meant by trials does he go from A to B twice.

Sahil Goyat - 11 months, 1 week ago

Yes, exactly. The thief will go from A to B twice. Notice that on the second chance, the treasures taken away on the first chance can't be taken again.

Alice Smith - 11 months, 1 week ago

@Alice Smith – thanks

Sahil Goyat - 11 months, 1 week ago

//use search
//this is a long version using DFS.
//time needed:time needed to search through all the possibilities*steps(less than 50), obviously less than 10^12
#include<stdio.h>
#include<stdlib.h>

int book[2][51][51];//register paths 1 and 2 for x=1,2, 3 dimensional 
int k,n,x=0,y=0;
int next[2][2]={{0,1},
                    {1,0}};//right & down
int copy[51][51]; //we don’t want to edit matrix a,so we make a copy
int max=0;

void dfs(int x, int y, int step)//next step, used in DFS command
{
    while(x!=size||y!=size)          
            for(k=0;k<=1;k++)//tries route
            {
            x+=next[k][0];
            y+=next[k][1]; 
            //check boundary 
            if(x<1||x>size||y<1||y>size)
                continue;
            if(book[n][x][y]=0)
            {
                book[n][x][y]=1;//register
                value+=copy[x][y];//take treasure
                copy[x][y]=0;//treasure taken 
                dfs(x,y,step+1);
                book[n][x][y]=0;
        }
}

void DFS(int a[51][51])//Depth First Search, finds every possible route
{

    int l,m;
    for(k=1,k<=size,k++)
        for(l=1,l<=size,l++)
            copy[k][l]=a[k][l];

    int value;//total value of treasure in one route
    //check if arrived at B
    if(x==y==size)
    {
        //update max
        if(value>max)
            max=value;
        return;
    }

    for(n=1;n<=2;n++)
        for(k=0;k<=1;k++)//tries route
        {
            x+=next[k][0];
            y+=next[k][1]; 
            //check boundary 
            if(x<1||x>size||y<1||y>size)
                continue;
            if(book[n][x][y]=0)
            {
                book[n][x][y]=1;//register
                value+=copy[x][y];//take treasure
                copy[x][y]=0;//treasure taken 
                dfs(x,y,step+1);
                book[n][x][y]=0;
        }
    }
    return;
}

int main
{
    int size, a[51][51]//size,square;
    int i,j;

    scanf(“%d”,&size);
    for(i=1;i<=size;i++)
        for(j=1;j<=size;j++)
            scanf(“%d”,&a[i][j]);//initialise square

    book[1][0][0]=1;
    book[2][0][0]=1;
    DFS(a[51][51]);
    return 0;
}

Jeff Giff - 11 months, 1 week ago

Run time: $O(f(n))$ , when a computer runs $10^{12}$ times per sec

Jeff Giff - 11 months, 1 week ago

@Jeff Giff – Please complete the program and then post your solution:)

Alice Smith - 11 months, 1 week ago

@Alice Smith – I’m trying :D

Jeff Giff - 11 months, 1 week ago

@Alice Smith – But it would be IMPOSSIBLE to run the code, since I can’t use PC :/

Jeff Giff - 11 months, 1 week ago

@Alice Smith , please run the code above with inputs
$3$
$0 3 3$
$3 3 3$
$3 3 0$
and
$2$
$0 0$
$2 0$
Then tell me the inputs if you have time! Thank you! :)

Jeff Giff - 11 months, 1 week ago

Worst case time complexity: 50 times the $1249/1250^{th}$ term of the $2500^{th}$ row of the pascal triangle

Jeff Giff - 11 months, 1 week ago

@Vinayak Srivastava , here’s something you can try :)

Jeff Giff - 11 months, 1 week ago

@Razing Thunder

Sahil Goyat - 11 months, 1 week ago

@Sahil Goyat – yes Mr. C2

Razing Thunder - 11 months, 1 week ago

@Razing Thunder – try these questions

Sahil Goyat - 11 months, 1 week ago

//this is an updated version using BFS
struct node
{
    int x,y;//co-ords
    int step;//‘step’ in BFS
    int value;//treasure value
};

int main
{
    struct node que[2501]//50^2expansions
    int x,y,i,j,size,a[51][51];
}

Jeff Giff - 11 months, 1 week ago

Luogu P1005 - Matrix fetching game

Alice wants to play a matrix fetching game on a $n \times m$ matrix, where the elements of the matrix $a_{ij}$ are all non-negative integers. The rules of the game are as follows:

Alice has $m$ round of fetching.
For each fetching, she needs to take away one element from each row of the matrix.
Each element taken at a time can only be the first or last one of the row.
After each fetching, she will get a score. The score is the sum of all scores earned from fetching each row. The scores earned from each row is equal to $e \cdot 2^i$ , where $e$ is the value of the element taken, and $i$ is the $i \th$ round of fetching (labeled from $1$ to $m$ ).
After $m$ rounds, all of the elements of the matrix will be taken, and the score earned from each fetching will be added to get the final score.

Your goal is to find the optimal strategy for Alice to get maximum final score possible.

How to submit:

The pastebin below has $10$ inputs. Each input has the format:

Two numbers $n,m$ , the number of rows and columns of the matrix.
$n \times m$ numbers, the values of each element of the matrix.

You should output: A number $M$ , the maximum final score Alice can get.

Then submit the sum of all of the outputs.

Input restrictions:

Input $1 \sim 6$ : $1 \leq n,m \leq 30$ .

Input $7 \sim 10$ : $1 \leq n,m \leq 80$ .

Inputs are here

Alice Smith - 11 months, 1 week ago

The logic is to choose the smallest ${e_m}$ possible for each fetch, leaving the larger ones for the next. A for—if-else loop in python should do. Time complexity $O(2mn)$ .
Note that we can’t use C because it’s int is limited as $\pm 2^{31}$ , but the total points are way larger.

Jeff Giff - 11 months, 1 week ago

Luogu P1008 - Triple hit

This problem has no inputs, and both mental calculation or programming are acceptable.

If $1,2,\cdots,9$ were split into $3$ disjoint groups and we use them to make three $3$ -digit numbers $x,y,z$ , such that $x:y:z=1:2:3$ , then find all possible triples for $(x,y,z)$ .

How to submit:

Find all possible triples for $(x,y,z)$ , and submit $\displaystyle \sum (x+2y+4z)$ .

Alice Smith - 11 months ago

are the groups disjoint and also does x,y,z all belong to each group or can two belong to the same.

Sahil Goyat - 11 months ago

Yes, they are disjoint.

Alice Smith - 11 months ago

Luogu P1006 - Passing notes

Alice and Bob are good friends and classmates, they always talk about endless topics together. In a quality development activity, the classmates were arranged to make a matrix with $m$ rows and $n$ columns, and Alice and Bob were arranged at both ends of the diagonal of the matrix, so they could not talk directly. Fortunately, they can communicate by passing notes. The note will be passed to each other through many classmates. Alice sits in the upper left corner of the matrix with coordinates $(1,1)$ , and Bob sits in the lower right corner of the matrix with coordinates $(m,n)$ . The note passed from Alice to Bob can only be passed down or to the right, and the note passed from Bob to Alice can only be passed up or to the left.

During the activity, Alice hoped to pass a note to Bob, and also hoped that Bob would reply to her. Every classmate in the class can help them, but only once. That is to say, if the person helped when Alice handed the note to Bob, he would not help when Bob handed it to Alice, and vice versa.

There is one more thing that needs to be paid attention to. Each student in the class is willing to help with a high or low degree of goodwill (note: the degree of kindness of Alice and Bob is not defined, use 0 when entering), which is an integer between $[0,100]$ , and the larger the number, the more kind the student is. Alice and Bob hope to find as many kind students as possible to help pass the note, that is, to find two back and forth transmission paths, so that the sum of the degree of goodwill of the students on these two paths is maximized.

Now, please help Alice and Bob find such two paths.

How to submit:

The pastebin below has $10$ inputs. Each input has the format:

Two numbers $m,n$ , the number of rows and columns of the matrix.
The next $m$ rows are an $m \times n$ matrix. The integer in the $i \th$ row and $j \th$ column of the matrix represents the degree of goodwill of the students sitting in the $i \th$ row and $j \th$ column. The $n$ integers on each line are separated by spaces.

The output is an integer, which represents the* maximum* value of the sum of the degree of goodwill of the students who participated in passing the note on two roads back and forth.

Then submit the sum of all of the outputs.

Input restrictions:

Input $1 \sim 3$ : $1 \leq n,m \leq 10$ .

Input $4 \sim 10$ : $1 \leq n,m \leq 50$ .

Inputs are here

Note: This problem is very similar to Luogu P1004 - Square access, except that the two paths can't cross each other.

Alice Smith - 11 months ago

Luogu P1007 - Single-plank Bridge

The war has entered a critical time. You are the leader of the transport team, leading the transport force to deliver supplies to the front. The transportation task is as boring as a problem. You want to find some excitement, so you order your soldiers to admire the scenery on a log bridge in front, and you stay under the bridge to admire the soldiers. The soldiers were very angry because the single-plank bridge was very narrow and could only accommodate one person. If there are two people walking towards each other on the bridge to meet, then the two of them will not be able to bypass each other, and only one person can turn back and get off the bridge and let the other person pass first. However, multiple people can stay in the same location at the same time.

Suddenly, you received a message from the command center that enemy bombers are flying towards the single-plank bridge where you are! To be safe, your troops must withdraw the log bridge. The length of the single-plank bridge is $L$ , and soldiers can only stay where the coordinates are integers. The speed of all soldiers is $1$ , but a soldier arrives at a position with coordinates $0$ or $L+1$ at a certain moment, and he leaves the single-plank bridge.

Each soldier has an initial facing direction, they will walk in this direction at a constant speed, and will not change direction by themselves. However, if two soldiers meet face to face, they cannot pass each other, so they turn around and continue walking. It doesn't take any time to turn around.

Because of the previous anger, you can no longer control your soldiers. Even, you don't even know the direction each soldier is facing initially. Therefore, you want to know how long it takes at least for your troops to evacuate the log bridge. In addition, the headquarters is also arranging to stop the enemy's attack, so you also need to know how long it takes at most for your troops to evacuate the log bridge.

How to submit:

The pastebin below has $10$ inputs. Each input has the format:

Line 1: An integer $L$ , the length of the log bridge, where the coordinates are $1,2,\cdots,L$ .
Line 2: An integer $N$ , the number of soldiers.
Line 3: $N$ integers, the initial coordinates for each soldier.

Output: Two integers $L, R$ . $L$ is the minimum time it takes for your troops to evacuate the log bridge, $R$ is the maximum time it takes for your troops to evacuate the log bridge.

Then submit the sum of $2R-L$ of each output.

Inputs are here

Input restrictions:

No two soldiers are on the same coordinate initially.
$N \leq L \leq 5000$ .

Alice Smith - 11 months ago

Math	Appears as
Remember to wrap math in `\(` ... `\)` or `\[` ... `\]` to ensure proper formatting.
`2 \times 3`	$2 \times 3$
`2^{34}`	$2^{34}$
`a_{i-1}`	$a_{i-1}$
`\frac{2}{3}`	$\frac{2}{3}$
`\sqrt{2}`	$\sqrt{2}$
`\sum_{i=1}^3`	$\sum_{i=1}^3$
`\sin \theta`	$\sin \theta$
`\boxed{123}`	$\boxed{123}$