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. Tiếp tục đọc

Advertisements
Đăng tải tại Bài tập, Lập trình C++ / Pascal, Spoj, Thuật toán, Trie | Bạn nghĩ gì về bài viết này?

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ừ w1, w2, …, wn sao cho với mọi 1 ≤ i < n, từ wi là tiền tố của từ wi+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={s1, s2, …, sm}. 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ừ). Tiếp tục đọc

Đăng tải tại Bài tập, Lập trình C++ / Pascal, Spoj, Thuật toán, Trie | Bạn nghĩ gì về bài viết này?

SPOJ – ACM – ACMNB

SPOJ – ACM

Đề bài :

Đề thi ACM năm nay gồm có 2n bài đánh số t 1 ti 2n. Bng k năng thiết kế thut toán siêu vit, ch vài giây sau khi đọc đề, PHUONGHD đã có lời gii cho c 2n bài. Vấn đề còn lại là phân công hai người lp trình bi PHUONGHD không quen vi th ngôn ng lp trình mới được đưa vào sử dng ti cuthi.

Do rt hiu hai lp trình viên Tí và Tèo trong đội, PHUONGHD biết rng bài th i nếu giao cho Tí làm sẽ mt ai giây, cũng bài đó nếu giao cho Tèo s mt bi giây để hoàn thành.

Nhim v cbn là hãy giúp PHUONGHD phân công cho hai lp trình viên, mỗi người làm đúng i bài sao cho tng thi gian lp trình cả 2n bài là ít nht.

D liu: Vào t file văn bản ACM.INP

      Dòng 1 cha s nguyên dương n <= 4*1e5

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

Tiếp tục đọc

Đăng tải tại Bài tập, Bài tập, Lập trình C++ / Pascal, Sắp xếp, Spoj, Thuật toán | Bạn nghĩ gì về bài viết này?

SPOJ – Chuỗi ốc – BEADSNB

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

Ban đầu từ chuỗi rỗng, không có v c; khi gp mt v c mi, có th lấy để xâu vào một trong hai đầu ca chui hoc hoc bỏ đi không lấy; cui cùng nhận được mt chui v c mà tính t đầu chuỗi đến cui chui, các v c có kích thước tăng dần và gm càng nhiu v c càng tt.

Yêu cu: 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 nht và xâu chuỗi để được chui gm nhiu v c nht.

Tiếp tục đọc

Đăng tải tại Bài tập, Bài tập, Lập trình C++ / Pascal, Quy hoạch động, Spoj, Thuật toán | Bạn nghĩ gì về bài viết này?

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

Tiếp tục đọc

Đăng tải tại Bài tập, Bài tập, Bài tập, Binary Indexed Tree, Cây khung, Codeforces, Lập trình C++ / Pascal, Quy hoạch động, Đồ thị | Bạn nghĩ gì về bài viết này?

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ử AL, AL+1, …, AR theo thứ tự tăng dần.

Tiếp tục đọc

Đăng tải tại Bài tập, Bài tập, Bài tập, Binary Search, Lập trình C++ / Pascal, Segment Tree, Spoj, Thuật toán | Bạn nghĩ gì về bài viết này?

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. Tiếp tục đọc

Đăng tải tại Bài tập, Lập trình C++ / Pascal, Spoj, Thuật toán | Bạn nghĩ gì về bài viết này?

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 !) Tiếp tục đọc

Đăng tải tại Bài tập, Lập trình C++ / Pascal, Spoj, Thuật toán | Bạn nghĩ gì về bài viết này?

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

Tiếp tục đọc

Đăng tải tại Bài tập, Binary Search Tree (BST), Lập trình C++ / Pascal, Spoj, Thuật toán | Bạn nghĩ gì về bài viết này?

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.

Tiếp tục đọc

Đăng tải tại Bài tập, Bài tập, Binary Indexed Tree, Lập trình C++ / Pascal, Spoj, Thuật toán | Bạn nghĩ gì về bài viết này?