JOI 2012/2013 - Vòng chung kết

Mỗi năm, trong lễ hội văn hóa của trường trung học JOI, hành lang đều được trang trí bằng đèn. Dãy đèn gồm \(N\) bóng, xếp trên một hàng từ phía tây sang phía đông của hành lang. Mỗi bóng đèn ở một trong hai trạng thái: sáng hoặc tắt.

Trong kho của trường có một chiếc máy điều khiển bóng đèn đã lâu không được sử dụng. Khi chọn một đoạn gồm các bóng đèn liên tiếp trong dãy, máy sẽ tắt tất cả bóng đang sáng trong đoạn đó và bật tất cả bóng đang tắt trong đoạn đó. Tuy nhiên, vì đã cũ nên máy chỉ có thể sử dụng một lần.

Các học sinh thích những đoạn mà bóng sáng và bóng tắt nằm xen kẽ nhau; ta gọi một đoạn như vậy là đoạn xen kẽ. Vì thế, các bạn quyết định sử dụng máy một lần nếu cần, để tạo ra dãy đèn có chứa một đoạn xen kẽ dài nhất có thể.

Yêu cầu

Cho thông tin về dãy đèn, hãy viết chương trình tìm độ dài lớn nhất của một đoạn xen kẽ có thể xuất hiện trong dãy sau khi sử dụng máy nhiều nhất một lần.

Dữ liệu vào

Đọc dữ liệu từ đầu vào chuẩn theo định dạng sau:

• Dòng đầu tiên chứa số nguyên \(N\).
• Dòng thứ hai chứa \(N\) số, mỗi số là \(0\) hoặc \(1\), cách nhau bởi dấu cách. Số thứ \(i\) từ trái sang (\(1\le i\le N\)) mô tả trạng thái của bóng thứ \(i\) tính từ phía tây trước khi sử dụng máy: \(1\) là sáng, \(0\) là tắt.

Dữ liệu ra

Ghi ra đầu ra chuẩn một dòng chứa một số nguyên là độ dài lớn nhất của một đoạn xen kẽ có thể xuất hiện trong dãy đèn thu được.

Ràng buộc

• \(2\le N\le100000\).

Phân nhóm

• \(20\%\) số điểm dành cho các dữ liệu thỏa mãn \(N\le500\).
• \(40\%\) số điểm dành cho các dữ liệu thỏa mãn \(N\le2000\).

10
1 1 0 0 1 0 1 1 1 0

7

Đây là ví dụ đã được giải thích trong phần minh họa của đề bài.

10
1 0 0 0 0 1 0 1 0 1

8

Chỉ đổi trạng thái bóng thứ \(4\) tính từ phía tây sẽ tạo ra một đoạn xen kẽ có độ dài lớn nhất là \(8\).

5
1 1 0 1 1

5

Đổi trạng thái các bóng từ vị trí thứ \(2\) đến vị trí thứ \(4\) tính từ phía tây sẽ tạo ra một đoạn xen kẽ gồm toàn bộ các bóng đèn.

3
0 1 0

3

Lưu ý rằng có những trường hợp không cần sử dụng máy.

Nước IOI vừa xây dựng một tuyến đường sắt mới. Mỗi đoàn tàu chạy trên đường sắt của nước IOI được tạo thành bằng cách nối các toa tàu. Có hai loại toa, I và O; hai toa chỉ có thể nối với nhau nếu khác loại. Ngoài ra, để bố trí buồng lái, cả hai toa ở hai đầu đoàn tàu đều phải thuộc loại I.

Một đoàn tàu được biểu diễn bằng xâu tạo bởi các chữ cái chỉ loại toa theo đúng thứ tự, và độ dài của đoàn tàu là độ dài xâu đó. Chẳng hạn, nối các toa theo thứ tự IOIOI tạo thành một đoàn tàu dài \(5\); một toa I đứng riêng cũng là đoàn tàu dài \(1\). Các cách xếp OIOI hoặc IOOI không tạo thành đoàn tàu hợp lệ.

Một số toa tàu đang được cất trong hai nhà chứa toa. Trong mỗi nhà chứa, các toa nằm trên một hàng. Để ghép đoàn tàu, người ta lấy các toa ra khỏi nhà chứa và nối chúng ở phía trước các nhà chứa. Chỉ có thể lấy ra toa gần cửa vào nhất của một nhà chứa, nhưng được tự do chọn nhà chứa để lấy toa ở mỗi lần.

Trước khi bắt đầu ghép đoàn tàu, có thể lấy tùy ý bao nhiêu toa ra khỏi các nhà chứa và chuyển chúng sang một đường ray chờ riêng. Một khi đã chuyển sang đường ray chờ, toa đó không thể được dùng để ghép đoàn tàu nữa. Khi đã bắt đầu ghép đoàn tàu, cho đến lúc ghép xong, không được chuyển toa từ nhà chứa sang đường ray chờ.

Không nhất thiết phải dùng hết các toa trong nhà chứa. Nói cách khác, sau khi ghép xong, có thể vẫn còn các toa chưa được dùng trong nhà chứa.

Dự kiến có rất nhiều người đi đường sắt tại nước IOI, nên người ta muốn ghép một đoàn tàu dài nhất có thể.

Yêu cầu

Cho thông tin các toa trong hai nhà chứa, hãy viết chương trình tìm độ dài lớn nhất của đoàn tàu có thể ghép được.

Các toa trong hai nhà chứa lần lượt được mô tả bằng xâu \(S\) dài \(M\) và xâu \(T\) dài \(N\), chỉ gồm các ký tự I, O. Mỗi ký tự biểu diễn một toa có loại tương ứng. Ký tự đầu tiên là toa gần cửa vào nhất; ký tự cuối cùng là toa nằm sâu nhất trong nhà chứa.

Dữ liệu vào

Đọc dữ liệu từ đầu vào chuẩn theo định dạng sau:

• Dòng đầu tiên chứa hai số nguyên \(M,N\), cách nhau bởi dấu cách.
• Dòng thứ hai chứa xâu \(S\).
• Dòng thứ ba chứa xâu \(T\).

Dữ liệu ra

Ghi ra đầu ra chuẩn một dòng chứa một số nguyên là độ dài lớn nhất của đoàn tàu có thể ghép được. Nếu không thể ghép được đoàn tàu nào, in ra \(0\).

Ràng buộc

• \(1\le M\le2000\).
• \(1\le N\le2000\).
• \(S\) có độ dài \(M\) và \(T\) có độ dài \(N\); cả hai xâu chỉ gồm các ký tự I, O.

Phân nhóm

• \(20\%\) số điểm dành cho các dữ liệu thỏa mãn \(M\le10\) và \(N\le10\).
• \(50\%\) số điểm dành cho các dữ liệu thỏa mãn \(M\le50\) và \(N\le50\).

5 5
OIOOI
OOIOI

7

Gọi hai nhà chứa được mô tả bởi \(S\) và \(T\) lần lượt là nhà chứa \(S\) và nhà chứa \(T\). Chẳng hạn, chuyển toa đầu tiên của nhà chứa \(S\) và hai toa đầu tiên của nhà chứa \(T\) sang đường ray chờ, rồi lấy toa lần lượt từ các nhà chứa \(S,S,T,S,S,T,T\). Ta ghép được đoàn tàu IOIOIOI dài \(7\).

Cũng có thể chuyển toa đầu tiên của nhà chứa \(S\) và hai toa đầu tiên của nhà chứa \(T\) sang đường ray chờ, rồi lấy toa theo thứ tự các nhà chứa \(T,T,S,S,T,S,S\) để ghép một đoàn tàu dài \(7\). Không thể ghép đoàn tàu dài hơn, nên in ra \(7\).

5 9
IIIII
IIIIIIIII

1

Lưu ý rằng một toa I đứng riêng cũng thỏa mãn điều kiện của một đoàn tàu.

Bạn đã đi lạc vào một dinh thự lớn. Dinh thự gồm các căn phòng hình vuông xếp thành lưới theo các hướng đông, tây, nam, bắc, với \(M\) cột theo hướng đông–tây và \(N\) hàng theo hướng nam–bắc, tổng cộng \(M\times N\) phòng. Phòng ở cột thứ \(x\) tính từ phía tây (\(1\le x\le M\)) và hàng thứ \(y\) tính từ phía nam (\(1\le y\le N\)) được ký hiệu là \((x,y)\).

Hai phòng kề nhau theo một trong bốn hướng được nối bằng một cánh cửa ở chính giữa bức tường chung. Mỗi cửa hoặc đóng và không thể đi qua, hoặc mở và có thể đi qua. Khi cửa mở, đi từ tâm phòng này đến tâm phòng kia mất \(1\) phút. Ngoài ra, ở tâm một số phòng có công tắc; nếu nhấn giữ công tắc trong \(1\) phút, trạng thái đóng/mở của tất cả cửa trong dinh thự sẽ đảo ngược.

Hiện tại, mọi cửa nối hai phòng kề nhau theo hướng đông–tây đều đóng, còn mọi cửa nối hai phòng kề nhau theo hướng nam–bắc đều mở. Bạn đang ở tâm phòng \((1,1)\) và muốn đến tâm phòng \((M,N)\) trong thời gian ngắn nhất.

Yêu cầu

Cho kích thước dinh thự \(M,N\) và vị trí của \(K\) phòng có công tắc là \((X_1,Y_1),(X_2,Y_2),\ldots,(X_K,Y_K)\), hãy viết chương trình tính số phút ít nhất cần thiết để đi từ tâm phòng \((1,1)\) đến tâm phòng \((M,N)\), bắt đầu với các cửa đông–tây đóng và các cửa nam–bắc mở. Nếu không thể đến phòng \((M,N)\), hãy báo điều đó.

Dữ liệu vào

Đọc dữ liệu từ đầu vào chuẩn theo định dạng sau:

• Dòng đầu tiên chứa ba số nguyên \(M,N,K\), cách nhau bởi dấu cách. \(M\) là số phòng theo hướng đông–tây, \(N\) là số phòng theo hướng nam–bắc, \(K\) là số phòng có công tắc.
• Dòng thứ \(i\) trong \(K\) dòng tiếp theo (\(1\le i\le K\)) chứa hai số nguyên \(X_i,Y_i\), cách nhau bởi dấu cách, cho biết có công tắc ở tâm phòng \((X_i,Y_i)\).

Các cặp \((X_1,Y_1),(X_2,Y_2),\ldots,(X_K,Y_K)\) đôi một khác nhau.

Dữ liệu ra

Ghi ra đầu ra chuẩn một dòng chứa một số nguyên là thời gian di chuyển ngắn nhất, tính bằng phút. Nếu không thể đến phòng \((M,N)\), in ra số nguyên \(-1\).

Ràng buộc

• \(2\le M\le100000\).
• \(2\le N\le100000\).
• \(1\le K\le200000\).
• \(1\le X_i\le M\) (\(1\le i\le K\)).
• \(1\le Y_i\le N\) (\(1\le i\le K\)).

Phân nhóm

• \(20\%\) số điểm dành cho các dữ liệu thỏa mãn \(M\le1000\) và \(N\le1000\).
• \(30\%\) số điểm dành cho các dữ liệu thỏa mãn \(K\le2000\).
• \(50\%\) số điểm dành cho các dữ liệu thỏa mãn ít nhất một trong hai điều kiện trên. Không có dữ liệu chấm nào đồng thời thỏa mãn cả hai điều kiện.

3 2 1
1 2

4

Có thể đi từ tâm phòng \((1,1)\) đến tâm phòng \((3,2)\) trong \(4\) phút bằng các hành động sau, và đây là thời gian ngắn nhất:

1. Đi đến tâm phòng \((1,2)\).
2. Nhấn công tắc ở tâm phòng \((1,2)\).
3. Đi đến tâm phòng \((2,2)\).
4. Đi đến tâm phòng \((3,2)\).

3 2 1
2 1

-1

Trong ví dụ này, bạn không thể đến phòng \((3,2)\).

8 9 15
3 1
3 2
3 7
3 8
1 1
4 5
4 3
5 6
5 8
6 3
6 2
7 5
8 9
8 6
8 5

25

Trạng thái ban đầu của dinh thự trong ví dụ này được minh họa bên dưới. Lưu ý rằng tâm phòng \((1,1)\) hoặc phòng \((M,N)\) cũng có thể có công tắc.

Tháp JOIOI là một trò chơi dành cho một người, sử dụng các đĩa.

Mỗi đĩa mang một trong ba chữ cái J, O, I. Đường kính của các đĩa đôi một khác nhau. Khi bắt đầu trò chơi, các đĩa được xếp chồng lên nhau, từ dưới lên trên theo thứ tự đường kính giảm dần.

Bạn muốn dùng các đĩa này để tạo ra nhiều tháp JOIOI nhỏ nhất có thể. Một tháp JOIOI nhỏ gồm \(3\) đĩa mà khi đọc các chữ cái theo thứ tự đường kính tăng dần, ta được JOI hoặc IOI. Không được sử dụng cùng một đĩa từ hai lần trở lên.

Yêu cầu

Các chữ cái trên những đĩa đã cho, đọc theo thứ tự đường kính tăng dần, được biểu diễn bằng xâu \(S\) có độ dài \(N\). Hãy viết chương trình tính số tháp JOIOI nhỏ nhiều nhất có thể tạo ra từ các đĩa này.

Dữ liệu vào

Đọc dữ liệu từ đầu vào chuẩn theo định dạng sau:

• Dòng đầu tiên chứa số nguyên \(N\), là độ dài của xâu \(S\).
• Dòng thứ hai chứa xâu \(S\).

Dữ liệu ra

Ghi ra đầu ra chuẩn một dòng chứa một số nguyên là số tháp JOIOI nhỏ nhiều nhất có thể tạo ra.

Ràng buộc

• \(1\le N\le1000000\).
• \(S\) có độ dài \(N\) và chỉ gồm các ký tự J, O, I.

Phân nhóm

• \(10\%\) số điểm dành cho các dữ liệu thỏa mãn \(N\le15\).
• \(30\%\) số điểm dành cho các dữ liệu thỏa mãn \(N\le50\).
• \(50\%\) số điểm dành cho các dữ liệu thỏa mãn \(N\le3000\).

6
JOIIOI

2

JOIIOI chứa một dãy con JOI và một dãy con IOI, nên có thể tạo ra hai tháp JOIOI nhỏ.

5
JOIOI

1

Xâu chứa cả dãy con JOI lẫn dãy con IOI, nhưng không thể lấy đồng thời cả hai vì không được dùng một ký tự từ hai lần trở lên.

6
JOIOII

2

15
JJOIIOOJOJIOIIO

4

Sắp xếp nổi bọt là một thuật toán sắp xếp dãy. Giả sử ta muốn sắp xếp dãy số \(A\) có độ dài \(N\) theo thứ tự tăng dần. Thuật toán xét các cặp số kề nhau theo thứ tự từ đầu dãy; nếu một cặp đang sai thứ tự thì đổi chỗ hai số đó. Cụ thể, trong một lượt duyệt, lần lượt với \(i=1,2,\ldots,N-1\), nếu \(A_i>A_{i+1}\) thì đổi chỗ hai số này. Ta biết rằng lặp lại lượt duyệt đó \(N-1\) lần sẽ sắp xếp được dãy theo thứ tự tăng dần.

Số lần đổi chỗ của sắp xếp nổi bọt đối với dãy \(A\) là số lần hai số nguyên được đổi chỗ khi áp dụng thuật toán trên cho \(A\). Các thuật toán và cách cài đặt được gọi là sắp xếp nổi bọt có thể khác nhau đôi chút về thứ tự, phạm vi vòng lặp hoặc điều kiện kết thúc. Tuy nhiên, khi áp dụng cho cùng một dãy, số lần đổi chỗ không thay đổi bởi những khác biệt này.

Chẳng hạn, hàm C dưới đây sắp xếp mảng số nguyên a có độ dài n bằng sắp xếp nổi bọt:

void bubble_sort(int *a, int n) {
  int i, j;
  for (i = 0; i < n - 1; ++i) {
    for (j = 0; j < n - 1; ++j) {
      if (a[j] > a[j + 1]) {
        /* Ba dòng sau tương ứng với một lần đổi chỗ hai số nguyên. */
        int x = a[j];
        a[j] = a[j + 1];
        a[j + 1] = x;
      }
    }
  }
}

Yêu cầu

Cho dãy số \(A\) có độ dài \(N\). Ta tạo dãy \(A'\) bằng cách chọn hai số nguyên ở các vị trí tùy ý trong \(A\) và đổi chỗ chúng đúng một lần. Hãy viết chương trình tìm số lần đổi chỗ nhỏ nhất của sắp xếp nổi bọt đối với dãy \(A'\). Lưu ý rằng hai số được đổi chỗ ban đầu không nhất thiết phải kề nhau.

Dữ liệu vào

Đọc dữ liệu từ đầu vào chuẩn theo định dạng sau:

• Dòng đầu tiên chứa số nguyên \(N\), là độ dài của dãy \(A\).
• Dòng thứ \(i\) trong \(N\) dòng tiếp theo (\(1\le i\le N\)) chứa số nguyên \(A_i\), là số thứ \(i\) của dãy \(A\).

Dữ liệu ra

Ghi ra đầu ra chuẩn một dòng chứa một số nguyên là số lần đổi chỗ nhỏ nhất của sắp xếp nổi bọt đối với dãy \(A'\).

Ràng buộc

• \(1\le N\le100000\).
• \(1\le A_i\le1000000000\) (\(1\le i\le N\)).

Phân nhóm

• \(10\%\) số điểm dành cho các dữ liệu thỏa mãn \(N\le1000\) và \(A_i\ne A_j\) với mọi \(1\le i<j\le N\).
• \(30\%\) số điểm dành cho các dữ liệu thỏa mãn \(N\le5000\) và \(A_i\ne A_j\) với mọi \(1\le i<j\le N\).
• \(80\%\) số điểm dành cho các dữ liệu thỏa mãn \(A_i\ne A_j\) với mọi \(1\le i<j\le N\).

5
10
3
6
8
1

0

Đổi chỗ số \(10\) ở đầu dãy \(A\) và số \(1\) ở cuối dãy. Khi đó \(A'\) đã được sắp xếp, nên số lần đổi chỗ của sắp xếp nổi bọt bằng \(0\).

5
3
1
7
9
5

2

Đổi chỗ số \(7\) ở vị trí thứ \(3\) của \(A\) và số \(5\) ở cuối dãy, ta được \(A'=(3,1,5,9,7)\). Số lần đổi chỗ của sắp xếp nổi bọt đối với \(A'\) là \(2\).

3
1
2
3

1

Ngay cả khi dãy \(A\) đã được sắp xếp từ đầu, vẫn phải thực hiện một lần đổi chỗ để tạo ra dãy \(A'\).