CHUỖI ỐC

Nguồn: PreVOI

Biển Đà Nẵng được nhiều du khách biết đến như một trong những điểm nghỉ ngơi lý tưởng và được tạp chí Forbes (Mỹ) bình chọn là một trong những bãi biển đẹp nhất thế giới. Các bãi tắm có độ dốc lớn, nước trong xanh thích hợp cho những du khách muốn thưởng thức những loại hình dịch vụ giải trí nghỉ dưỡng câu cá, lướt ván, lặn, ngắm san hô…

Trong một đợt đi du lịch ở Đà Nẵng, sáng sớm DONG3D thường đi dạo dọc bờ biển và nhặt những vỏ ốc rồi xâu chúng lại thành một chuỗi. Nguyên tắc tạo chuỗi ốc của DONG3D như sau: ban đầu chuỗi ốc rỗng, không có vỏ ốc, khi gặp một vỏ ốc mới có thể lấy để xâu vào 1 trong hai đầu của chuỗi hoặc bỏ đi không lấy, cuối cùng nhận được một chuỗi vỏ ốc mà tính từ đầu đến cuối chuỗi các vỏ ốc có kích thước tăng dần và gồm càng nhiều vỏ ốc càng tốt.

Yêu cầu: cho trước dãy a₁, a₂,…,a_N là kích thước các vỏ ốc mà DONG3D lần lượt gặp khi đi dọc bờ biển, hãy tìm cách nhặt và xâu chuỗi để được nhiều vỏ ốc nhất.

Dữ liệu vào: từ tệp văn bản BEADS.INP

+ Dòng đầu tiên ghi số nguyên dương N≤10⁵

+ Dòng thứ 2 chứa N số nguyen dương a₁, a₂,…,a_N ("i:a_i≤10⁹)

Dữ liệu ra: ghi vào tệp văn bản BEADS.OUT một số nguyên duy nhất là số lượng vỏ ốc trong chuỗi tạo được.

Ví dụ:

BEADS.INP	BEADS.OUT
5 4 4 5 3 1	4

TEST - SOLUTION

QUAN HỆ HỌ HÀNG

DÂY DẪN

TÌM CHỮ SỐ

Xét biểu diễn thập phân của phân số a/b. Biểu diễn này có thể là một số thập phân hữu hạn hoặc một số thập phân vô hạn tuần hoàn. Nếu phân số có thể biểu diễn bởi một số thập phân hữu hạn, ta có thể viết thêm một dãy vô hạn các chữ số 0 vào sau chữ số cuối cùng sau dấu chấm thập phân và coi đó cũng là một số thập phân vô hạn tuần hoàn. Ví dụ:

Yêu cầu: Sau khi đánh số từ 1 trở đi, từ trái qua phải các chữ số đứng sau dấu “,” trong biểu diễn thập phân của a/b, hãy xác định chữ số thứ k.

Ví dụ:

+ Với a=100, b=8, k=2, chữ số đứng thứ 2 sau dấu thập phân của giá trị 100/8  là chữ số 0

+ Với a=99, b=140, k=12, chữ số đứng thứ 12 sau dấu chấm thập phân giá trị 99/140 là chữ số 2

Dữ liệu: Vào từ tệp văn bản DIGIT.INP gồm 1 dòng chứa 3 số nguyên dương a, b, k<= 10^18 cách nhau ít nhất một ký tự trắng.

Kết quả: Ghi ra tệp văn bản DIGIT.OUT một số nguyên duy nhất là giá trị chữ số tìm được

Ví dụ:

DIGIT.INP	DIGIT.OUT
100 8 1	5
17 3 10	6
99 140 12	2

VẼ LẠC ĐÀ

Nguồn: http://codeforces.com/contest/14/problem/E

(Đóng góp của Đinh Nguyên Khôi)

 Bob rất là thích vẽ lạc đà với 1 cái bưới, 2 cái bướu, rồi 3 cái bướu, vâng vâng...... Nó vẽ lạc đà bằng cách nối các điểm trên mặt phẳng tọa độ lại với nhau. Bây giờ, thằng bé đang vẽ những con lạ đà mà với t cục bướu, đại diện chúng bằng nhiều "bộ đường thẳng". Mỗi "bộ đường thẳng" bao gồm n điểm (x₁; y₁) , (x₂ ; y₂) , .... , (x_n ; y_n). Đỉnh đầu tiên sẽ có hoành độ là x₁ = 1, tiếp theo là điểm có hoành độ là x₂ = 2 Còn những tung độ yi thì có thể tùy ý, nhưng phải theo một số quy định sau đây :

+ Có đúng t cục bướu. Mà nó nằm ở một số vị trí j sao cho y[j - 1] < y[j] > y[j + 1]

+ Có đúng t - 1 vị trí j sao cho: y[j - 1] > y[j] < y[j + 1]

+ Không được tồn tại một đoạn thẳng nào song song với trục Ox

+ Các giá trị y[i] phải nằm trong đoạn [1 ; 4]

Để vẽ những con lạc đà này với t cục bướu, Bob cần phải mua vở, nhưng nó không biết cần bao nhiêu trang giấy để vẽ. Output là số lượng những "bộ đường thẳng" khác nhau mà có thể vẽ với t cục bướu và n điểm.

Input: Gồm 2 số n và t (1 <= n <= 20, 1 <= t <= 10)

Output: Gồm 1 số nguyên duy nhất là số cách có thể.

Ví dụ:

INPUT	OUTPUT
6 1	6

6 bộ có thể vẽ là :

123421 ; 123431 ; 123432 ; 124321 ; 134321 ; 234321.

GRID GAME

Nguồn: https://uva.onlinejudge.org

(Đóng góp của Đinh Nguyên Khôi)

Alice và Bob cả hai đều có kẹo nhiều ơi là nhiều ! Nhưng mà tụi nó muốn ăn. Cho nên hai đứa nó quyết định chơi một trò chơi theo lượt như sau:

Tụi nó sẽ điền vào một cái bảng M có kích thước N x N với những số nguyên bất kỳ. Alice sẽ bắt đầu trò chơi bằng cách kẻ ngang những một hàng i mà nó chưa kẻ. Bây giờ tới lượt của Bob, nó phải kẻ dọc cột j mà trước đó nó chưa kẻ. Sau khi lượt của Bob kết thúc, Alice sẽ lấy được số kẹo mà giao ở cột i và hàng j là M(i, j). Nếu như M(i, j) < 0, tức là điều này đồng nghĩa với việc Alice sẽ phải đưa cho Bob M(i, j) viên kẹo. Trò chơi sẽ kết thúc khi toàn bộ các cột và hàng đều được kẻ rồi. (Xem hình để biết thêm chi tiết).

Nhiệm vụ của bạn rất là đơn giản thôi ! Hãy tính xem Alice có thể lấy được nhiều nhất là bao nhiêu viên kẹo, hay nói cách khác, là tính xem Bob lấy được ít nhất bao nhiêu viên. Giả sử hai người này đều chơi tối ưu.

Input: Dòng đầu là số nguyên t (1 <= t <= 20), là số test case trong một test. 
Mỗi test case sẽ bắt đầu bởi một số nguyên N (1≤N≤ 8), là kích thước của cái bảng. 
N dòng sau, mỗi dòng có N số nguyên. Số nguyên thứ j trên dòng thứ i là M(i , j).

Output: Gồm t dòng, dòng thứ i tương ứng với test case thứ i, chỉ in ra một số nguyên duy nhất là số lượng kẹo nhiều nhất mà Alice có thể ăn được.

Ví dụ:

INPUT	OUTPUT
3 2 10 10 -5 -5 2 10 10 -5 -5 2 10 -5 -5 10	5 5 -10

HỆ THỐNG ĐIỆN

Nhận được sự đầu tư lớn của một tập đoàn nước ngoài, đất nước Omega dự định xây dựng k  nhà máy thủy điện tại k địa điểm khác nhau để cung cấp điện cho n thành phố. Các nhà máy thủy điện được đánh số thứ tự từ 1 đến k, chi phí xây dựng cho nhà máy thủy điện thứ i là w_i. Tuy nhiên họ cần phải tính toán để chi phí xây dựng và lắp đặt hệ thống điện lưới quốc gia là ít nhất.

Hệ thống điện lưới được mô tả như một bản đồ được chia thành các ô vuông đơn vị mà tọa độ đỉnh của các ô vuông là một cặp số nguyên (x,y) cho biết hoành độ và tung độ của nó. Các nhà máy thủy điện và các thành phố đều nằm trên đỉnh của ô vuông đơn vị. Chi phí lắp đặt đường dây điện giữa hai điểm (u, v) và (s, t) được tính bằng giá trị |u-s|+|v-t|

Hãy tính toán chi phí ít nhất để xây dựng hệ thống điện cho đất nước Omega sao cho tất cả các thành phố đều có điện biết rằng thành phố có điện khi có đường dây điện đến ít nhất một thành phố có điện khác hoặc có đường dây điện nối trực tiếp nhà máy thủy điện.

Lưu ý: không cần thiết phải xây dựng hết k  nhà máy thủy điện

Dữ liệu: Vào từ tệp văn bản ELECTRIC.INP

+ Dòng đầu tiên gồm 2 số nguyên dương k và n lần lượt là số lượng các nhà máy thủy điện và số lượng thành phố.

+ K dòng tiếp theo dòng thứ i (i=1..k) gồm 3 số nguyên x_i , y_i, w_i cho biết nhà máy thủy điện thứ i nằm ở tọa độ (x_i, y_i) và chi phí xây dựng là w_i

+ N dòng tiếp theo mỗi dòng thứ j (j=1..n) chứa 2 số nguyên u_j, v_j cho biết hoành độ và tung độ của thành phố thứ j.

Dữ liệu ra: ghi vào tệp văn bản ELECTRIC.OUT một số nguyên cho biết chi phí ít nhất để xây dựng hệ thống điện lưới cho nước Omega.

Giới hạn:

+ 1≤n≤200

+ 1≤k≤n

+ Tọa độ của các thành phố và nhà máy thủy điện có trị tuyệt đối ≤10⁶

+ 1≤w_i≤10⁶

Các số trên một dòng của Input cách nhau ít nhất 1 ký tự trắng.

Ví dụ:

ELECTRIC.INP	ELECTRIC.OUT
3 7 1 1 10 4 7 20 9 3 15 1 6 2 3 5 1 5 5 7 3 8 1 8 7	37