Tổng hợp những bài toán duyệt hay trong các kỳ thi lập trình - VN Spoj LTTK Education xin giới thiệu với bạn đọc Tổng hợp những bài toán duyệt hay trong các kỳ thi lập trình - VN Spoj để bạn đọc tham khảo học tập những điều bổ ích mà tài liệu này mang lại nhé! Chúc các em học tập thật tốt và mang lại nhiều kết quả khả quan cho bản thân nhé! ✪ ✪ ✪ ✪ ✪ Link tải tài liệu: LINK TẢI TÀI LIỆU Spoiler: Read me CÁC BÀI TOÁN DUYỆT 1. Robot quét vôi. Có 9 căn phòng (đánh số từ 1 đến 9) đã được quét vôi với màu trắng, xanh hoặc vàng. Có 9 robot (đánh số từ 1 đến 9) phụ trách việc quét vôi. Mỗi robot chỉ quét một số phòng nhất định. Việc quét vôi được thực hiện nhờ một chương trình cài sẵn theo qui tắc: Nếu phòng đang có màu trắng thì quét màu xanh Nếu phòng đang có màu xanh thì quét màu vàng Nếu phòng đang có màu vàng thì quét màu trắng Cần phải gọi lần lượt một số các robot ra quét vôi (mỗi lần một robot, một robot có thể gọi nhiều lần và có thể có robot không được gọi. Robot được gọi sẽ quét vôi tất cả các phòng mà nó phụ trách) để cuối cùng các phòng đều có màu trắng. Yêu cầu: Hãy tìm một phương án như vậy sao cho số lần gọi robot là ít nhất. Giả thiết rằng lượng vôi cho mỗi lượt quét đối với các phòng là như nhau. Input 9 dòng đầu: dòng thứ i mô tả một danh sách các phòng do robot i phụ trách việc quét vôi. Mỗi dòng là một chuỗi các chữ số từ 1..9 biểu diễn các số hiệu của các phòng, các chữ số viết sát nhau. Dòng cuối mô tả mầu vôi ban đầu của các phòng. Dòng gồm 9 ký tự viết sát nhau gồm toàn các chữ cái T (trắng), X (xanh), V(vàng) biểu diễn mầu ban đầu của 9 căn phòng theo trật tự số hiệu của chúng. Output gồm một dòng Nếu không có phương án thì in ra số 0 Trái lại thì in ra dãy thứ tự các robot được gọi (số hiệu các robot được viết sát nhau và in ra kết quả có thứ tự từ điển bé nhất) Example Input: 159 123 357 147 5 369 456 789 258 XVXVXVTXT Output: 2255799 Hướng dẫn: Chú ý rằng, sau 3 lần quét vôi thì màu của một căn phòng trở lại như cũ. Bởi vậy, việc sử dụng một robot ≥ 3 lần là không tối ưu. Ta có thể giải bài toán bằng cách sinh dãy tam phân độ dài 9, mỗi giá trị a chính là số lần gọi robot i. 2. DÃY ABC Cho trước một số nguyên dương N (N 100), hãy tìm một xâu chỉ gồm các ký tự A, B, C thoả mãn 3 điều kiện: - Có độ dài N - Hai đoạn con bất kỳ liền nhau đều khác nhau (đoạn con là một dãy ký tự liên tiếp của xâu) - Có ít ký tự C nhất. Hướng dẫn: Nếu dãy X1X2…Xn thoả mãn 2 đoạn con bất kỳ liền nhau đều khác nhau, thì trong 4 ký tự liên tiếp bất kỳ bao giờ cũng phải có 1 ký tự "C". Như vậy với một dãy con gồm k ký tự liên tiếp của dãy X thì số ký tự C trong dãy con đó bắt buộc phải k div 4. Tại bước thử chọn Xi, nếu ta đã có Ti ký tự "C" trong đoạn đã chọn từ X1 đến Xi, thì cho dù các bước đệ quy tiếp sau làm tốt như thế nào chăng nữa, số ký tự "C" sẽ phải chọn thêm bao giờ cũng (n - i) div 4. Tức là nếu theo phương án chọn Xi như thế này thì số ký tự "C" trong dãy kết quả (khi chọn đến Xn) cho dù có làm tốt đến đâu cũng Ti + (n - i) div 4. Ta dùng con số này để đánh giá nhánh cận, nếu nó nhiều hơn số ký tự "C" trong “Cấu hình tối ưu” thì chắc chắn có làm tiếp cũng chỉ được một cấu hình tồi tệ hơn, ta bỏ qua ngay cách chọn này và thử phương án khác. Các bạn tham khảo Code: program ABC_STRING; const InputFile = 'ABC.INP'; OutputFile = 'ABC.OUT'; max = 100; var N, MinC: Integer; X, Best: array[1..max] of 'A'..'C'; T: array[0..max] of Integer; f: Text; function Same(i, l: Integer): Boolean; var j, k: Integer; begin j := i - l; for k := 0 to l - 1 do if X[i - k] <> X[j - k] then begin Same := False; Exit; end; Same := True; end; function Check(i: Integer): Boolean; var l: Integer; begin for l := 1 to i div 2 do if Same(i, l) then begin Check := False; Exit; end; Check := True; end; procedure KeepResult; begin MinC := T[N]; Best := X; end; procedure Try(i: Integer); var j: 'A'..'C'; begin for j := 'A' to 'C' do begin X := j; if Check(i) then begin if j = 'C' then T := T[i - 1] + 1 else T := T[i - 1]; if T + (N - i) div 4 < MinC then if i = N then KeepResult else Try(i + 1); end; end; end; procedure PrintResult; var i: Integer; begin for i := 1 to N do Write(f, Best); WriteLn(f); WriteLn(f, '"C" Letter Count : ', MinC); end; begin Assign(f, InputFile); Reset(f); ReadLn(f, N); Close(f); Assign(f, OutputFile); Rewrite(f); T[0] := 0; MinC := N; Try(1); PrintResult; Close(f); end. 3. BÀI TOÁN NGƯỜI DU LỊCH Cho n thành phố đánh số từ 1 đến n và m tuyến đường giao thông hai chiều giữa chúng, mạng lưới giao thông này được cho bởi bảng C cấp nxn, ở đây Cij = Cji = Chi phí đi đoạn đường trực tiếp từ thành phố i đến thành phố j. Giả thiết rằng Cii = 0 với i, Cij = + nếu không có đường trực tiếp từ thành phố i đến thành phố j. Một người du lịch xuất phát từ thành phố 1, muốn đi thăm tất cả các thành phố còn lại mỗi thành phố đúng 1 lần và cuối cùng quay lại thành phố 1. Hãy chỉ ra cho người đó hành trình với chi phí ít nhất. Bài toán đó gọi là bài toán người du lịch hay bài toán hành trình của một thương gia (Traveling Salesman) Hướng dẫn: Hành trình cần tìm có dạng (x1 = 1, x2, …, xn, xn+1 = 1) ở đây giữa xi và xi+1: hai thành phố liên tiếp trong hành trình phải có đường đi trực tiếp (Cij + ) và ngoại trừ thành phố 1, không thành phố nào được lặp lại hai lần. Có nghĩa là dãy (x1, x2, …, xn) lập thành 1 hoán vị của (1, 2, …, n). Duyệt quay lui: x2 có thể chọn một trong các thành phố mà x1 có đường đi tới (trực tiếp), với mỗi cách thử chọn x2 như vậy thì x3 có thể chọn một trong các thành phố mà x2 có đường đi tới (ngoài x1). Tổng quát: xi có thể chọn 1 trong các thành phố chưa đi qua mà từ xi-1 có đường đi trực tiếp tới (1 i n). Nhánh cận: Khởi tạo cấu hình BestConfig có chi phí = + . Với mỗi bước thử chọn xi xem chi phí đường đi cho tới lúc đó có < Chi phí của cấu hình BestConfig?, nếu không nhỏ hơn thì thử giá trị khác ngay bởi có đi tiếp cũng chỉ tốn thêm. Khi thử được một giá trị xn ta kiểm tra xem xn có đường đi trực tiếp về 1 không ? Nếu có đánh giá chi phí đi từ thành phố 1 đến thành phố xn cộng với chi phí từ xn đi trực tiếp về 1, nếu nhỏ hơn chi phí của đường đi BestConfig thì cập nhật lại BestConfig bằng cách đi mới. Sau thủ tục tìm kiếm quay lui mà chi phí của BestConfig vẫn bằng + thì có nghĩa là nó không tìm thấy một hành trình nào thoả mãn điều kiện đề bài để cập nhật BestConfig, bài toán không có lời giải, còn nếu chi phí của BestConfig < + thì in ra cấu hình BestConfig - đó là hành trình ít tốn kém nhất tìm được Input: file văn bản TOURISM.INP Dòng 1: Chứa số thành phố n (1 n 20) và số tuyến đường m trong mạng lưới giao thông m dòng tiếp theo, mỗi dòng ghi số hiệu hai thành phố có đường đi trực tiếp và chi phí đi trên quãng đường đó (chi phí này là số nguyên dương 100) Output: file văn bản TOURISM.OUT, ghi hành trình tìm được. Theo LTTK Education
