SPOJ – Tin mật – SEC

SPOJ – Tin mật – SEC

(Admin viết)

Tóm đề : Cho m xâu ban đầu và n xâu truy vấn. Với mỗi xâu truy vấn x hỏi xem có bao nhiêu xâu y trong m xâu ban đầu thỏa : x có thể là tiền tố của y hoặc y là tiền tố của x.

SPOJ – Chuỗi từ – CHAIN2

SPOJ – Chuỗi từ – CHAIN2

Chuỗi từ có độ dài n là một dãy các từ w₁, w₂, …, w_n sao cho với mọi 1 ≤ i < n, từ w_i là tiền tố của từ w_i+1.

Nhắc lại từ u có độ dài k là tiền tố của từ v có độ dài l nếu l > k và các ký tự đầu tiên của v trùng với từ u.

Cho tập hợp các từ S={s₁, s₂, …, s_m}. Tìm chuỗi từ dài nhất có thể xây dựng được bằng cách dùng các từ trong tập hợp S (có thể không sử dụng hết các từ).

SPOJ – ACM – ACMNB

SPOJ – ACM

Đề bài :

Đề thi ACM năm nay gồm có 2n bài đánh số từ 1 tới 2n. Bằng kỹ năng thiết kế thuật toán siêu việt, chỉ vài giây sau khi đọc đề, PHUONGHD đã có lời giải cho cả 2n bài. Vấn đề còn lại là phân công hai người lập trình bởi PHUONGHD không quen với thứ ngôn ngữ lập trình mới được đưa vào sử dụng tại cuộc thi.

Do rất hiểu hai lập trình viên Tí và Tèo trong đội, PHUONGHD biết rằng bài thứ i nếu giao cho Tí làm sẽ mất ai giây, cũng bài đó nếu giao cho Tèo sẽ mất bi giây để hoàn thành.

Nhiệm vụ của bạn là hãy giúp PHUONGHD phân công cho hai lập trình viên, mỗi người làm đúng i bài sao cho tổng thời gian lập trình cả 2n bài là ít nhất.

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

      Dòng 1 chứa số nguyên dương n <= 4*1e5

      2n dòng tiếp theo, dòng thứ i chứa hai số nguyên dương ai, bi

SPOJ – Chuỗi ốc – BEADSNB

http://vn.spoj.com/problems/BEADSNB/

Ban đầu từ chuỗi rỗng, không có vỏ ốc; khi gặp một vỏ ốc mới, có thể lấy để xâu vào một trong hai đầu của chuỗi hoặc 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 chuỗi đế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 a1, a2, …, an là kích thước dãy ốc lần lượt gặp. hãy tìm cách nhặt và xâu chuỗi để được chuỗi gồm nhiều vỏ ốc nhất.

Codeforces – Tutorial For Contest Nowruz challenge

Link để đăng kí và đọc đề và làm : Link  –  Đề bài 

Tutorial : 

PROBLEM A : Hamro and array

Bài này chỉ dùng hai mảng F[0][i] và F[1][i] tương ứng là tổng các số từ 1->i với vị trí là chẵn, lẻ. Khi đó dựa vào vị trí của l là chẵn hay lẻ để tính tổng cần tìm

My submission

SPOJ – Phần tử thứ K – YPKTH

SPOJ – Phần tử thứ K – YPKTH

Cho dãy số A có N phần tử nguyên phân biệt.

Cho Q truy vấn, mỗi truy vấn có dạng: L R K

Yêu cầu: mỗi truy vấn xuất ra phần tử lớn thứ K sau khi sắp xếp các phần tử A_L, A_L+1, …, A_R theo thứ tự tăng dần.

SPOJ – Cuộc đấu cân não – NCOB

SPOJ –  Cuộc đấu cân não – NCOB

Người hành tinh BrainPower vừa mời Nuga tham dự một cuộc thi đấu thú vị. Đó là giải “Cờ Chạy” liên hành tinh.

“Cờ Chạy” là thể loại cờ do Co & Da – người hành tinh BP đưa ra vào năm 3101. Mỗi ván có 2 người chơi, luân phiên nhau thực hiện nước đi của mình, bốc thăm để chọn người chơi trước. Bàn cờ là một dãy N ô vuông, đánh số từ 1 đến N từ trái sang phải, và chỉ có 2 quân cờ duy nhất, ban đầu được đặt ở 2 ô vuông do 2 người chơi tự do lựa chọn (hai ô vuông này có thể trùng nhau). Giả sử 2 quân cờ đang ở 2 ô vuông có chỉ số là X và Y ( X ≤ Y). Người chơi thực hiện nước đi bằng cách di chuyển quân cờ ở vị trí Y đi K ô về bên trái, sao cho K phải là một bội số dương của X, và quân cờ vẫn ở trên bàn cờ. Nói cách khác, vị trí mới của quân cờ Y là Y’ = Y – K, Y’ ≥ 1. Trò chơi kết thúc khi không thể thực hiện được nước đi nào nữa. Và người không thực hiện được nước đi của mình là người thua cuộc.

SPOJ – Time Travel – TTRAVEL

SPOJ – Time Travel –  TTRAVEL

Farmer John (FJ) vừa mua đuợc một cái cỗ máy thời gian. FJ có thể tiến tới một thời gian nào đó trong tuơng lai bằng cách cứ cho thời gian trôi (không thể sử dụng máy thời gian vì tuơng lai chưa định sẵn/bị đảo lộn) hoặc quay trở lại mốc thời gian nào đó trong quá khứ.

FJ  muốn đạt đuợc sản luợng nhiều nhất có thể . Vì thế anh ấy đã thống kê , ghi lại sản lụơng những con bò cung cấp trong quá trình nuôi hoặc sau khi có một truy vấn hành động nào đó làm tác động đến đàn bò. FJ chỉ quan tâm đến chỉ số ID của con bò mà anh ấy nuôi trong thời gian ngắn nhất . Hãy viết chuơng trình xác định và in ra các số ID ấy sau mỗi truy vấn hành động (hoặc in ra -1 nếu FJ chẳng còn con bò nào !)

SPOJ – Tập hợp động – CPPSET (cơ bản về set)

SPOJ – Tập hợp động – CPPSET (cơ bản về set)

Cho một tập hợp S các số nguyên, bạn hãy lập trình thực hiện các thao tác sau:

• ADD x: thêm số x vào tập S
• DELETE x: xóa số x khỏi tập S
• MININUM: tìm số nhỏ nhất trong tập S
• MAXIMUM: tìm số lớn nhất trong tập S
• SUCC x: tìm số nhỏ nhất lớn hơn x trong tập S
• SUCC_2 x: tìm số nhỏ nhất và không nhỏ hơn x trong tập S
• PRED x: tìm số lớn nhất nhỏ hơn x trong tập S
• PRED_2 x: tìm số lớn nhất không vượt quá x trong tập S

SPOJ – Dãy số may mắn – NKLUCK

SPOJ – Dãy số may mắn – NKLUCK

Cho mảng n số, vị trí trung vị của đoạn i..j là vị trí thứ m/2+1 với m là chiều dài của dãy i..j và dãy i..j đã sort tăng. Đếm số bộ i,j thỏa vị trí trung vị == k cho trước

Dữ liệu vào

• Dòng đầu chứa số nguyên dương n và số nguyên X.
• n dòng tiếp theo mỗi dòng chứa giá trị của số được ghi trên mẫu giấy thứ i.