LINK TẢI LUẬN VĂN MIỄN PHÍ CHO AE KET-NOI
Tin học đầu tiên được tổ chức tại thành phố Pravetz, Bulgaria từ ngày 16 đến ngày 19 tháng 5 năm 1989
Bài toán 1
Cho trước 2*N hộp nằm cạnh nhau trên cùng một hàng với N <= 5. Trong đó có hai hộp liền nhau trống rỗng, các hộp còn lại chứa N-1 vật "A" và N-1 vật "B".
Ví dụ, với N = 5 ta có như sau:
Quy tắc trao đổi: Chuyển các vật trong hai hộp liền nhau chứa đồ vật sang hai hộp rỗng, giữ nguyên vị trí các hộp.
Yêu cầu
Tìm cách hoán chuyển sao cho tất cả các hộp chứa vật A nằm bên trái các hộp chứa vật B, không cần biết các hộp rỗng nằm ở đâu.
Bài toán đặt ra
Hãy viết chương trình:
1. Xây dựng mô hình hoán chuyển các hộp với số hộp và trạng thái ban đầu của các hộp được nhập từ bàn phím. Mỗi hoán chuyển được nhập bằng số (thuộc từ 1 đến N-1) của hai hộp liền nhau đầu tiên sẽ được đổi chỗ cho các hộp rỗng. Chương trình phải tìm và báo cáo trạng thái các hộp sau khi hoán chuyển.
2. Cho trước hiện trạng các hộp, tìm ít nhất một cách hoán chuyển đạt mục tiêu cuối cùng của bài toán. Chương trình phải báo cáo cả trạng thái ban đầu và trạng thái hiện tại sau mỗi bước hoán chuyển.
3. Tìm những cách hoán chuyển để số hộp bị di chuyển ít nhất và vẫn đạt được mục đích.
Bài toán 2
Các tầng trong một tòa nhà được đánh số tuần tự từ 0, 1, 2, ..., N (N<=15). Trong tòa nhà có tất cả K (1<=K<=4) thang máy. Thang máy được điều khiển từ một trung tâm và chỉ chấp nhận hai lệnh được nhập vào bằng cách bấm nút. Các nút ngoài thang máy (một nút ra lệnh lên và một nút ra lệnh xuống) có ở tất cả các tầng. Các nút trong (ra lệnh đến một tầng cụ thể) có trong mỗi thang máy.
Hãy viết chương trình mô phỏng quá trình điều khiển thang máy với các lệnh sau:
1. Trong tòa nhà có một thang máy (K=1) và mỗi lần nó chỉ chấp nhận một lệnh.
Các lệnh khác chỉ được chấp nhận khi lệnh trước đó được hoàn thành.
2. Trong tòa nhà có nhiều thang máy (K>=1). Mỗi thang máy chỉ chấp nhận lệnh từ nút trong nếu không có lệnh nào đang được xử lý. Thiết bị điều khiển có thể nhận nhiều lệnh cùng lúc. Các lệnh trong luôn được thang máy thực hiện mỗi khi ra lệnh. Thiết bị điều khiển sẽ chọn chiếc thang máy đang rỗi phù hợp nhất để thực hiện lệnh ngoài.
3. Xét trường hợp tương tự trong yêu cầu 2 với điều kiện các thang máy số chẵn chỉ có thể dừng ở các tầng số chẵn và các thang máy số lẻ chỉ dừng ở các tầng số lẻ. Tất cả các thang máy đều có thể dừng ở tầng 0.
4. Xét trường hợp trong yêu cầu 3 và giả sử tại mỗi thang máy có nhiều lệnh đang đợi thực hiện. Tất cả các lệnh trong đều được chấp nhận dù cho thang máy có rỗi hay không.
Gợi ý:
Tất cả các thang máy đều đồng bộ và tại một điểm thời gian, các thang máy đều ở các tầng cho trước nào đó.
Trong một khoảng thời gian tiếp theo, một thang máy có thể đi lên đi xuống hay ở nguyên tầng cũ.
Các lệnh có thể nhập vào bất cứ lúc nào, các lệnh có định dạng sau:
a, Lệnh ngoài -;
b, Lệnh trong -
Tại mỗi thời điểm có thể nhập nhiều lệnh hay không nhập lệnh nào.
Tại mỗi thời điểm chương trình báo vị trí của mỗi chiếc thang máy.
Thang máy đủ lớn và không bị quá tải.
Chương trình phải điều khiển thang máy sao cho tối ưu nhất.
Bài toán 3
Cho trước một nhóm N người. Mỗi người là bạn của hơn [N/2] người còn lại và là kẻ thù
của không quá K người. Một người có một cuốn sách mà tất cả mọi người đều muốn đọc và thảo luận với một số người khác.
Hãy viết chương trình:
1. Tìm cách truyền tay nhau cuốn sách sao cho tất cả mọi người đều được đọc nó một lần và chuyển nó cho bạn mình và cuối cùng cuốn sách về tay người chủ.
2. Chia nhóm người thành S tổ để thảo luận về cuốn sách. Mỗi người phải có không quá P kẻ thù trong cùng tổ.
Giả sử S*P >= K.
Bài toán 4
Xét đoạn văn bản được soạn thảo bằng các ký tự viết hoa /A-Z/ và 8 ký tự . , + - : / ? !
Đoạn văn bản đó được gửi qua kênh giao tiếp dưới dạng chuỗi byte. Số ký tự 1 trong mỗi byte phải là số chẵn.
1. Đưa ra cách mã hóa các ký tự trên bằng các chuỗi nhị phân sao cho cách mã hóa rõ ràng và số bit được gửi qua kênh giao tiếp là ít nhất.
2. Hãy viết chương trình:
2.1. Cho trước đoạn văn bản, hãy in ra đoạn văn bản dưới dạng một chuỗi các số thập lục phân.
2.2. Cho trước đoạn văn bản đã mã hóa nhận được, hãy giải mã và hiển thị đoạn văn bản lên màn hình.
Bài toán 5
Xét một hình phẳng gồm n đỉnh, mỗi đỉnh đều bậc 3.
Ví dụ:
Để các đỉnh X,Y và Z liền kề đỉnh T. Ta nói Y là đỉnh lân cận trái và Z là đỉnh lân cận phải của T tính theo X, nếu góc XTZ nhỏ hơn góc XTY.
Ví dụ, E là đỉnh lân cận phải và G là đỉnh lân cận trái của H tính theo A vì góc
AHE nhỏ hơn góc AHG.
Hãy viết chương trình:
1. Nhập tọa độ của các đỉnh và các cạnh của hình phẳng, hãy vẽ hình đó lên màn hình
theo một tỷ lệ phù hợp. Các cạnh được biểu diễn bằng các đoạn thẳng.
2. Cho trước một cặp đỉnh X0 và X1 và một chuỗi các ký tự L và R. Hãy tìm một đường đi X0X1X2...Xn trên hình đó sao cho:
- X0 và X1 là hai đỉnh bắt đầu;
- Xi+1 là đỉnh lân cận trái hay đỉnh lân cận phải của Xi tính theo Xi-1 tuỳ theo
ký tự thứ (i-2) trong chuỗi điều khiển là L và R.
Ví dụ:
Đường đi tìm được trong ví dụ trên với A và H là các đỉnh bắt đầu và chuỗi LRRLLR là AHGFEDCB.
3. Vẽ đường đi trong yêu cầu 2 lên màn hình.
4. Dùng một đỉnh bắt đầu và một đỉnh kết thúc, hãy vẽ một đường đi qua số đỉnh ít nhất, vẽ đường đi đó lên màn hình và báo cáo các đỉnh bắt đầu cùng chuỗi điều khiển tạo ra đường đi như trong yêu cầu 2.
Bài toán 6
Cho trước một đa giác có 20 cạnh. Các cạnh được đánh số từ 1 đến 20. Hãy tìm đường đi trên hình đa giác 20 cạnh sao cho chỉ đến mỗi cạnh duy nhất 1 lần. Đường đi giá trị C được định nghĩa là tích vô hướng:
trong đó fi là số cạnh đi qua ở bước thứ i.
Chỉ có thể đi từ cạnh này sang cạnh khác nếu hai cạnh đó nằm lân cận.
A. Hai cạnh lân cận nhau nếu có một đỉnh chung;
B. Hai cạnh lân cận nhau nếu có một đỉnh chung hay có một điểm chung.
Hãy tìm các đường đi có giá trị nhỏ nhất cho ví dụ trên.
Chú ý:
Vì tính phức tạp về thời gian và không gian của thuật toán nên bạn không cần tìm kết quả chính xác mà chỉ cần đưa ra một kết quả tương đối.
The 15th International Olympiad in Informatics Held in Kenosha, Wisconsin, United States of America, 2003.
Đề thi IOI 2003 - Trail Maintenance
Bài toán: Duy trì đường mòn (Trail Maintenance)
Những con bò của bác nông dân Jonh muốn được tự do đi lại giữa N (1≤N≤200) cánh đồng (đánh số 1..N) của trang trại, mặc dù giữa các cánh đồng bị ngăn cách bởi những rừng cây. Các con bò muốn sử dụng những tuyến đường mòn nối liền các cặp cánh đồng để đi. Bò có thể di chuyển trên các con đường theo cả hai chiều.
Các con bò không tự làm được đường, thay vào đó, chúng sử dụng đường đi của động vật hoang dã mà chúng phát hiện ra. Hàng tuần, các con bò cần lựa chọn một số hay tất cả các tuyến đường chúng biết để duy trì.
Đầu mỗi tuần, các con bò lại phát hiện thêm một đường đi mới của động vật hoang dã. Chúng phải quyết định tập hợp các con đường mà chúng phải duy trì sao cho trong tuần đó chúng có thể đi lại từ cánh đồng này tới cánh đồng khác một cách bất kỳ. Bò chỉ có thể sử dụng các con đường mà hiện chúng đang duy trì khi di chuyển.
Các con bò luôn mong muốn tổng chiều dài các đường mòn phải duy trì là nhỏ nhất. Bò có thể chọn duy trì bất kỳ con đường nào trong số chúng biết, dù cho đường đi đó có được duy trì ở tuần trước hay không.
Đường đi của động vật hoang dã (kể cả khi được duy trì) không bao giờ thẳng. Hai tuyến đường nối cùng một cặp cánh đồng có thể có chiều dài khác nhau. Các tuyến đường cũng có thể cắt nhau, tuy nhiên, bò không thay đổi đường đi trừ khi chúng ở trên cánh đồng.
Cứ vào đầu tuần, các con bò sẽ cho bạn biết đường đi mới của động vật hoang dã mà chúng vừa phát hiện được. Chương trình của bạn phải chỉ ra tổng ngắn nhất chiều dài các con đường mà bò cần duy trì để trong tuần đó, chúng có thể đi đến mọi cánh đồng, tất nhiên, nếu tồn tại các tuyến đường như vậy.
Input: Standard input
Dòng đầu tiên của tệp input bao gồm hai số nguyên, cách nhau bởi dấu trắng, N và W, trong đó W là số tuần mà chương trình cần tính toán. (1≤W≤6000)
Với mỗi tuần, đọc một dòng chứa thông tin về đường đi của động vật hoang dã được phát hiện. Dòng này chứa 3 số nguyên, cách nhau bởi dấu trắng, bao gồm: số hiệu các cánh đồng hai đầu đường đi và chiều dài con đường (1..10000). Số hiệu cánh đồng hai đầu tuyến đường luôn khác nhau.
Output: Standard output
Ngay sau khi biết thông tin về đường đi của động vật hoang dã mới được phát hiện, chương trình của bạn cần đưa ra một dòng trên đó bao gồm tổng chiều dài ngắn nhất của các con đường mà bò phải duy trì. Nếu không tồn tại các đường đi cho phép bò di chuyển đến mọi cánh đồng, đưa ra số -1.
Chương trình của bạn phải kết thúc ngay sau khi xử lý tuần cuối cùng.
Ví dụ:
Do Drive thay đổi chính sách, nên một số link cũ yêu cầu duyệt download. các bạn chỉ cần làm theo hướng dẫn.
Password giải nén nếu cần: ket-noi.com | Bấm trực tiếp vào Link để tải:
Tin học đầu tiên được tổ chức tại thành phố Pravetz, Bulgaria từ ngày 16 đến ngày 19 tháng 5 năm 1989
Bài toán 1
Cho trước 2*N hộp nằm cạnh nhau trên cùng một hàng với N <= 5. Trong đó có hai hộp liền nhau trống rỗng, các hộp còn lại chứa N-1 vật "A" và N-1 vật "B".
Ví dụ, với N = 5 ta có như sau:
Quy tắc trao đổi: Chuyển các vật trong hai hộp liền nhau chứa đồ vật sang hai hộp rỗng, giữ nguyên vị trí các hộp.
Yêu cầu
Tìm cách hoán chuyển sao cho tất cả các hộp chứa vật A nằm bên trái các hộp chứa vật B, không cần biết các hộp rỗng nằm ở đâu.
Bài toán đặt ra
Hãy viết chương trình:
1. Xây dựng mô hình hoán chuyển các hộp với số hộp và trạng thái ban đầu của các hộp được nhập từ bàn phím. Mỗi hoán chuyển được nhập bằng số (thuộc từ 1 đến N-1) của hai hộp liền nhau đầu tiên sẽ được đổi chỗ cho các hộp rỗng. Chương trình phải tìm và báo cáo trạng thái các hộp sau khi hoán chuyển.
2. Cho trước hiện trạng các hộp, tìm ít nhất một cách hoán chuyển đạt mục tiêu cuối cùng của bài toán. Chương trình phải báo cáo cả trạng thái ban đầu và trạng thái hiện tại sau mỗi bước hoán chuyển.
3. Tìm những cách hoán chuyển để số hộp bị di chuyển ít nhất và vẫn đạt được mục đích.
Bài toán 2
Các tầng trong một tòa nhà được đánh số tuần tự từ 0, 1, 2, ..., N (N<=15). Trong tòa nhà có tất cả K (1<=K<=4) thang máy. Thang máy được điều khiển từ một trung tâm và chỉ chấp nhận hai lệnh được nhập vào bằng cách bấm nút. Các nút ngoài thang máy (một nút ra lệnh lên và một nút ra lệnh xuống) có ở tất cả các tầng. Các nút trong (ra lệnh đến một tầng cụ thể) có trong mỗi thang máy.
Hãy viết chương trình mô phỏng quá trình điều khiển thang máy với các lệnh sau:
1. Trong tòa nhà có một thang máy (K=1) và mỗi lần nó chỉ chấp nhận một lệnh.
Các lệnh khác chỉ được chấp nhận khi lệnh trước đó được hoàn thành.
2. Trong tòa nhà có nhiều thang máy (K>=1). Mỗi thang máy chỉ chấp nhận lệnh từ nút trong nếu không có lệnh nào đang được xử lý. Thiết bị điều khiển có thể nhận nhiều lệnh cùng lúc. Các lệnh trong luôn được thang máy thực hiện mỗi khi ra lệnh. Thiết bị điều khiển sẽ chọn chiếc thang máy đang rỗi phù hợp nhất để thực hiện lệnh ngoài.
3. Xét trường hợp tương tự trong yêu cầu 2 với điều kiện các thang máy số chẵn chỉ có thể dừng ở các tầng số chẵn và các thang máy số lẻ chỉ dừng ở các tầng số lẻ. Tất cả các thang máy đều có thể dừng ở tầng 0.
4. Xét trường hợp trong yêu cầu 3 và giả sử tại mỗi thang máy có nhiều lệnh đang đợi thực hiện. Tất cả các lệnh trong đều được chấp nhận dù cho thang máy có rỗi hay không.
Gợi ý:
Tất cả các thang máy đều đồng bộ và tại một điểm thời gian, các thang máy đều ở các tầng cho trước nào đó.
Trong một khoảng thời gian tiếp theo, một thang máy có thể đi lên đi xuống hay ở nguyên tầng cũ.
Các lệnh có thể nhập vào bất cứ lúc nào, các lệnh có định dạng sau:
a, Lệnh ngoài -
b, Lệnh trong -
Tại mỗi thời điểm có thể nhập nhiều lệnh hay không nhập lệnh nào.
Tại mỗi thời điểm chương trình báo vị trí của mỗi chiếc thang máy.
Thang máy đủ lớn và không bị quá tải.
Chương trình phải điều khiển thang máy sao cho tối ưu nhất.
Bài toán 3
Cho trước một nhóm N người. Mỗi người là bạn của hơn [N/2] người còn lại và là kẻ thù
của không quá K người. Một người có một cuốn sách mà tất cả mọi người đều muốn đọc và thảo luận với một số người khác.
Hãy viết chương trình:
1. Tìm cách truyền tay nhau cuốn sách sao cho tất cả mọi người đều được đọc nó một lần và chuyển nó cho bạn mình và cuối cùng cuốn sách về tay người chủ.
2. Chia nhóm người thành S tổ để thảo luận về cuốn sách. Mỗi người phải có không quá P kẻ thù trong cùng tổ.
Giả sử S*P >= K.
Bài toán 4
Xét đoạn văn bản được soạn thảo bằng các ký tự viết hoa /A-Z/ và 8 ký tự . , + - : / ? !
Đoạn văn bản đó được gửi qua kênh giao tiếp dưới dạng chuỗi byte. Số ký tự 1 trong mỗi byte phải là số chẵn.
1. Đưa ra cách mã hóa các ký tự trên bằng các chuỗi nhị phân sao cho cách mã hóa rõ ràng và số bit được gửi qua kênh giao tiếp là ít nhất.
2. Hãy viết chương trình:
2.1. Cho trước đoạn văn bản, hãy in ra đoạn văn bản dưới dạng một chuỗi các số thập lục phân.
2.2. Cho trước đoạn văn bản đã mã hóa nhận được, hãy giải mã và hiển thị đoạn văn bản lên màn hình.
Bài toán 5
Xét một hình phẳng gồm n đỉnh, mỗi đỉnh đều bậc 3.
Ví dụ:
Để các đỉnh X,Y và Z liền kề đỉnh T. Ta nói Y là đỉnh lân cận trái và Z là đỉnh lân cận phải của T tính theo X, nếu góc XTZ nhỏ hơn góc XTY.
Ví dụ, E là đỉnh lân cận phải và G là đỉnh lân cận trái của H tính theo A vì góc
AHE nhỏ hơn góc AHG.
Hãy viết chương trình:
1. Nhập tọa độ của các đỉnh và các cạnh của hình phẳng, hãy vẽ hình đó lên màn hình
theo một tỷ lệ phù hợp. Các cạnh được biểu diễn bằng các đoạn thẳng.
2. Cho trước một cặp đỉnh X0 và X1 và một chuỗi các ký tự L và R. Hãy tìm một đường đi X0X1X2...Xn trên hình đó sao cho:
- X0 và X1 là hai đỉnh bắt đầu;
- Xi+1 là đỉnh lân cận trái hay đỉnh lân cận phải của Xi tính theo Xi-1 tuỳ theo
ký tự thứ (i-2) trong chuỗi điều khiển là L và R.
Ví dụ:
Đường đi tìm được trong ví dụ trên với A và H là các đỉnh bắt đầu và chuỗi LRRLLR là AHGFEDCB.
3. Vẽ đường đi trong yêu cầu 2 lên màn hình.
4. Dùng một đỉnh bắt đầu và một đỉnh kết thúc, hãy vẽ một đường đi qua số đỉnh ít nhất, vẽ đường đi đó lên màn hình và báo cáo các đỉnh bắt đầu cùng chuỗi điều khiển tạo ra đường đi như trong yêu cầu 2.
Bài toán 6
Cho trước một đa giác có 20 cạnh. Các cạnh được đánh số từ 1 đến 20. Hãy tìm đường đi trên hình đa giác 20 cạnh sao cho chỉ đến mỗi cạnh duy nhất 1 lần. Đường đi giá trị C được định nghĩa là tích vô hướng:
trong đó fi là số cạnh đi qua ở bước thứ i.
Chỉ có thể đi từ cạnh này sang cạnh khác nếu hai cạnh đó nằm lân cận.
A. Hai cạnh lân cận nhau nếu có một đỉnh chung;
B. Hai cạnh lân cận nhau nếu có một đỉnh chung hay có một điểm chung.
Hãy tìm các đường đi có giá trị nhỏ nhất cho ví dụ trên.
Chú ý:
Vì tính phức tạp về thời gian và không gian của thuật toán nên bạn không cần tìm kết quả chính xác mà chỉ cần đưa ra một kết quả tương đối.
The 15th International Olympiad in Informatics Held in Kenosha, Wisconsin, United States of America, 2003.
Đề thi IOI 2003 - Trail Maintenance
Bài toán: Duy trì đường mòn (Trail Maintenance)
Những con bò của bác nông dân Jonh muốn được tự do đi lại giữa N (1≤N≤200) cánh đồng (đánh số 1..N) của trang trại, mặc dù giữa các cánh đồng bị ngăn cách bởi những rừng cây. Các con bò muốn sử dụng những tuyến đường mòn nối liền các cặp cánh đồng để đi. Bò có thể di chuyển trên các con đường theo cả hai chiều.
Các con bò không tự làm được đường, thay vào đó, chúng sử dụng đường đi của động vật hoang dã mà chúng phát hiện ra. Hàng tuần, các con bò cần lựa chọn một số hay tất cả các tuyến đường chúng biết để duy trì.
Đầu mỗi tuần, các con bò lại phát hiện thêm một đường đi mới của động vật hoang dã. Chúng phải quyết định tập hợp các con đường mà chúng phải duy trì sao cho trong tuần đó chúng có thể đi lại từ cánh đồng này tới cánh đồng khác một cách bất kỳ. Bò chỉ có thể sử dụng các con đường mà hiện chúng đang duy trì khi di chuyển.
Các con bò luôn mong muốn tổng chiều dài các đường mòn phải duy trì là nhỏ nhất. Bò có thể chọn duy trì bất kỳ con đường nào trong số chúng biết, dù cho đường đi đó có được duy trì ở tuần trước hay không.
Đường đi của động vật hoang dã (kể cả khi được duy trì) không bao giờ thẳng. Hai tuyến đường nối cùng một cặp cánh đồng có thể có chiều dài khác nhau. Các tuyến đường cũng có thể cắt nhau, tuy nhiên, bò không thay đổi đường đi trừ khi chúng ở trên cánh đồng.
Cứ vào đầu tuần, các con bò sẽ cho bạn biết đường đi mới của động vật hoang dã mà chúng vừa phát hiện được. Chương trình của bạn phải chỉ ra tổng ngắn nhất chiều dài các con đường mà bò cần duy trì để trong tuần đó, chúng có thể đi đến mọi cánh đồng, tất nhiên, nếu tồn tại các tuyến đường như vậy.
Input: Standard input
Dòng đầu tiên của tệp input bao gồm hai số nguyên, cách nhau bởi dấu trắng, N và W, trong đó W là số tuần mà chương trình cần tính toán. (1≤W≤6000)
Với mỗi tuần, đọc một dòng chứa thông tin về đường đi của động vật hoang dã được phát hiện. Dòng này chứa 3 số nguyên, cách nhau bởi dấu trắng, bao gồm: số hiệu các cánh đồng hai đầu đường đi và chiều dài con đường (1..10000). Số hiệu cánh đồng hai đầu tuyến đường luôn khác nhau.
Output: Standard output
Ngay sau khi biết thông tin về đường đi của động vật hoang dã mới được phát hiện, chương trình của bạn cần đưa ra một dòng trên đó bao gồm tổng chiều dài ngắn nhất của các con đường mà bò phải duy trì. Nếu không tồn tại các đường đi cho phép bò di chuyển đến mọi cánh đồng, đưa ra số -1.
Chương trình của bạn phải kết thúc ngay sau khi xử lý tuần cuối cùng.
Ví dụ:
Do Drive thay đổi chính sách, nên một số link cũ yêu cầu duyệt download. các bạn chỉ cần làm theo hướng dẫn.
Password giải nén nếu cần: ket-noi.com | Bấm trực tiếp vào Link để tải:
You must be registered for see links