CHEFSTEP - July Lunchtime 2020 Division 2

Link đề bài trên Codechef

Tóm tắt đề bài: Chef chỉ đi được những quãng đường lớn hơn hoặc bằng và chia hết cho độ dài một bước chân của Chef. VD: mỗi bước của Chef dài 5 đơn vị, khi đó Chef chỉ đi được các quãng đường 5, 10, 15 (còn nữa) đơn vị và không đi được các quãng đường 4, 6, 9, 11, 12 (còn nữa) đơn vị.

Hướng dẫn: Duyệt, những số chia hết và lớn hơn hoặc bằng K thì output 1, còn lại output 0.

Link code mẫu (C++).

Happy coding!

A. Common Subsequence - Codeforces Round #658 (Div. 2)

Link đề bài

Tóm tắt đề bài: Cho 2 mảng A và B. Tìm một dãy con chung (khác rỗng) của A và B sao cho dãy con này có ít phần tử nhất.

Một cách diễn đạt khác: Vì dãy con có ít phần tử nhất mà không rỗng của A và B có 1 phần tử nên bài toán này thực chất là đi tìm 1 phần tử chung của 2 dãy A và B, không quan trọng thứ tự xuất hiện của phần tử chung đó.

Hướng giải: Có nhiều cách khác nhau để cài thuật giải, chung quy vẫn là tìm một phần tử xuất hiện trong cả 2 dãy A và B. Nói chung là cài kiểu gì (miễn đừng điên quá) cũng AC.

Code mẫu mình để ở đây.

Mình càng ngày càng bận, từ bài tập trên lớp đến đồ án, đôi khi là mấy cái dự án con con để thỏa mãn cái nhu cầu của bản thân. Nên mình sẽ không dịch bài nữa, chỉ tóm tắt lại thôi nhé. 

1385B - Codeforces Round #656 (Div. 3)

Link đề bài trên Codeforces.

Tóm tắt: bạn được cho một mảng có kích thước 2*n. In ra màn hình mảng kích thước n gồm các phần tử của mảng 2n bên trên sao cho mỗi phần tử chỉ xuất hiện 1 lần theo đúng thứ tự trong mảng 2n bên trên.

Ví dụ:

Input:

5

2

1 1 2 2

4

1 3 1 4 3 4 2 2

5

1 2 1 2 3 4 3 5 4 5

3

1 2 3 1 2 3

4

2 3 2 4 1 3 4 1

Output:

1 2 

1 3 4 2 

1 2 3 4 5 

1 2 3 

2 3 4 1 

Giải thích:

Ở bộ test đầu: [1, 1, 2, 2] có 2 phần tử khác nhau là 1 và 2, theo đúng thứ tự xuất hiện trong mảng đầu sẽ là [1, 2]

Ở bộ test thứ 2: [1, 3, 1, 4, 3, 4, 2, 2] có 4 phần tử khác nhau là [1, 2, 3, 4], theo đúng thứ tự xuất hiện trong mảng đầu sẽ là [1, 3, 4, 2].

Hướng dẫn giải:

Bài này chỉ duyệt mảng đơn giản. Sử dụng unordered_set, set hay map để lưu các giá trị đã xuất hiện trong mảng. Cuối cùng chỉ cần một mảng lưu lại các phần tử này theo đúng thứ tự xuất hiện của chúng là ổn.

Link code mẫu

FACEFRND - Friends of Friends

Link đề bài trên SPOJ

Đề bài:

Bob hay lên mạng xã hội chơi và giờ Bob đang thắc mắc: không biết khai niệm "Bạn của Bạn (Friends of Friends)" trong mạng xã hội đó là sao? Nếu $X$ là bạn của Bob, $Y$ là bạn của $X$ nhưng $Y$ không phải là bạn của Bob thì $Y$ là một người "Bạn của Bạn" của Bob. Bạn được yêu cầu tìm số lượng người "Bạn của Bạn" của Bob. (Mỗi người trong mạng xã hội đó được định danh bằng một ID 4 chữ số).

Input:

Dòng đầu tiên chứa một số nguyên $N\ (1 \leq N \leq 1000)$ là số lượng người trong danh sách bạn bè của Bob. Tiếp sau đó là $N$ dòng:

• Đầu mỗi dòng là ID người bạn của Bob.
• Tiếp sau đó là số nguyên $M\ (1 \leq M \leq 100)$ là số lượng người trong danh sách bạn bè của người đó.
• Tiếp sau đó là $M$ ID lần lượt là ID của từng người bạn (ngoại trừ Bob).

Output:

In ra một số nguyên duy nhất - số lượng người "Bạn của Bạn" của Bob.

Ví dụ:

Input:

$3$
$2334$ $5$ $1256$ $4323$ $7687$ $3244$ $5678$
$1256$ $2$ $2334$ $7687$
$4323$ $5$ $2334$ $5678$ $6547$ $9766$ $9543$

Output:

$6$

Hướng dẫn giải

Từ ví dụ bên trên, ta có thể chỉ ra được những người "Bạn của Bạn" trong ví dụ là $3244, 5678, 6547, 7687, 9543$ và $9766$. Tổng quát về cách giải: ta ghi những ID là bạn của Bob (ID đầu tiên mỗi dòng) vào 1 mảng, ghi những ID còn lại vào một mảng. Nếu ID trong mảng bạn Bob tồn tại trong mảng còn lại thì ID đó không được tính là "Bạn của Bạn".

Bài này tiện nhất là dùng STL set vì tìm kiếm sẽ nhanh hơn, kiểu dữ liệu cũng nên để là string thay vì int vì ID vẫn có thể có số 0 ở đầu. Code mẫu mình để ở đây.

Chốt:

Happy coding!