### thanhchauns2's blog

By thanhchauns2, history, 9 days ago,

Or I will shave my hair.

• +259

By thanhchauns2, history, 2 weeks ago,

I tried to add the 100s and 0s one by one, since $n$ does not exceed $10^6$, solving it by using heaps does not cost so much time. Here it is: 122955494.

Have a nice day! Please don't downvote me :(

• +17

By thanhchauns2, history, 4 weeks ago,

Hi, I'm just wonder how much time the people here need to reach CM. I have stuck with this 1700-1750 elo for 2 weeks, maybe it'll be more. Could you please share your story and your experience of how you you gone so far and achieve such high ratings? I would love to learn from any.

Thanks for reading this dumbsh*t blog.

P/s: I hope to reach CM in less than 5 months, is it possible or just illusory?

P/s 2: Sorry if this blog makes you feel inconvenient. My English is bad :(

• -25

By thanhchauns2, history, 6 weeks ago,

It's literally resubmit everyone's code. My latest submission for practice has been in queue for 30 minutes lol.

Still submitting.

• +52

By thanhchauns2, history, 6 weeks ago,

I am current looking for some Discord servers which has been built for CP community, but I haven't found any. Can anybody suggest me some? Thank you!

Sorry for my bad English T-T

P/s: I wonder why posting searching for a learning community on codeforces is badly downvoted :/ Is it a hated topic? If it is, I will remove it :(

• +22

By thanhchauns2, history, 7 weeks ago,

He told my whole family, I don't know whether to laugh or to cry :(

• +197

By thanhchauns2, history, 3 months ago,

Given a map of a dungeon, your task is to take all TWO diamonds in the dungeon.

Find the minimum number of gates you have to open to take all the diamonds.

Note: It can be more than one gate to go into the dungeon from the outside.

You can move up, down, left, right.

• The letter '.' means blank space, you can move on it

• The letter '*' means blockade, you have to go around it

• The letter '#' means there's a gate at that place, you need it opened to go through it

• The letter '\$' means the diamond.

Input format:

• First line is two number N and M — the dungeon has the size N*M. (2 ≤ N,M ≤ 100)

• N lines following, represent the map of the dungeon.

Output format:

• A single integer — the minimum number of gates you have to open.

Example input:

5 9

****#****

..#.#..

****.****

$#.#.#$

Sorry for the input, you can see read the input here : https://ideone.com/EXk0Wh

Example output:

4

Thank you guys, hope you have a great standing in the next contest.

• +7

By thanhchauns2, history, 3 months ago,

Magnus is the youngest chess grandmaster ever. He loves chess so much that he decided to decorate his home with chess pieces. To decorate his long corridor, he decided to use the knight pieces. His corridor is covered by beautiful square marble tiles of alternating colors, just like a chess board, with n rows and m columns. He will put images of knights on some (possibly none) of these tiles. Each tile will contain at most one knight.

The special thing about his arrangement is that there won’t be any pair of knights can attack each other. Two knights can attack each other if they are placed in two opposite corner cells of a 2 by 3 rectangle. In this diagram, the knight can attack any of the Xs.

Given the dimension of the long corridor, your task is to calculate how many ways Magnus can arrange his knights. Two arrangements are considered different if there exists a tile which contains a knight in one arrangement but not in the other arrangement (in other words, rotations and reflections are considered different arrangements).

Input

Each input will consist of a single test case. Note that your program may be run multiple times on different inputs. Each test case will consist of a single line with two integers n and m (1≤n≤4, 1≤m≤10^9) representing the dimensions of the carpet. There will be a single space between n and m.

Output

Output a single line with a single integer representing the number of possible arrangements, modulo (10^9+9).

Sample Input 1

1 2

Sample Output 1

4

Sample Input 2

2 2

Sample Output 2

16

Sample Input 3

3 2

Sample Output 3

36

He said I need to Divide and Conquer, however I got no idea about that.

• -31

By thanhchauns2, history, 3 months ago,

Given an array with N elements and a number P (P ≤ N). Pick randomly P elements from the array, let's call T the product of these elements. Find the largest x that T % 10^x = 0

Example:

Input

3 2

26 5 96

Output

1

Input

3 2

25 4 90

Output

2