hoahonggai

Bài1:Thang máy.
Trong 1 tòa nhà , người ta xây dựng hệ thống thang máy gồm K thang máy hoạt động theo một quy trình rất đặc biệt. Mỗi thang máy chỉ để đi lại giữa hai tầng nhất định mà không dừng ở giữa chừng. Khi bắt đầu giờ làm việc, toàn bộ K thang máy đều ở tầng thấp hơn. Các thang máy sẽ di chuyển lên xuống liên tục. Để đi lại giữa hai tầng liên tiếp, mỗi thang máy cần 5 giây. Vì vậy, để đi từ tầng X đến tầng Y, thang máy cần |Y – X| × 5 giây. Ai cũng nói rằng thời gian đứng trong thang máy là tạo cảm giác mệt mỏi nhất, hơn cả thời gian chờ đợi hay chuyển thang máy.
Người sống trong ngôi nhà muốn đi từ tầng 1 lên tầng N thật nhanh và không phải ở lâu trong thang máy. Bạn hãy tìm ra một cách đi để thời gian phải ở trong thang máy là ít nhất.
Dữ liệu vào file LIFT.INP
• Dòng thứ nhất ghi 2 số N và K (N ≤ 5000, K ≤ 10000).
• Dòng thứ U trong K dòng tiếp theo, mỗi dòng ghi hai số P và Q là hai tầng được nối trực tiếp bằng thang máy thứ U.
Dữ liệu ra file LIFT.OUT
• Dòng thứ nhất ghi thời gian nhanh nhất để lên tầng N.
• Dòng thứ hai ghi số M là số lần đi thang máy mà bạn cần.
• Dòng thứ ba ghi M số lần lượt là số hiệu của thang máy mà bạn sử dụng.

Bài 2: .
Cho n thành phố, được đánh số từ 1..n; và r con đường đi qua các thành phố đó. Hãy tìm con đường ngắn nhất đi từ thành phố 1 đến thành phố n.

INPUT gồm:
- Dòng 1: số thành phố (n<=100)
- Dòng 2: số con đưởng (r<=10000) .
- r dòng tiếp theo gồm các số
d:thành phố đầu
c:thành phố cuối
l:độ dài đoạn đường nối từ thành phố d tới c
OUTPUT gồm: độ dài đoạn đường ngắn nhất từ 1->n

Bài 3:Hướng dẫn viên du lịch
Ông G. là một hướng dẫn viên du lịch. Công việc của ông ta là hướng dẫn một vài “tua” du lịch từ thành phố này đến thành phố khác. Trên các thành phố này, có một vài con đường hai chiều được nối giữa chúng. Mỗi cặp thành phố có đường kết nối đều có dịch vụ xe buýt chỉ chạy giữa hai thành phố này và chạy theo đường nối trực tiếp giữa chúng. Mỗi dịch vụ xe buýt đều có một giới hạn lớn nhất lượng khách mà xe buýt có thể trở được. Ông G có một tấm bản đồ chỉ các thành phố và những con đường nối giữa chúng. Ngoài ra, ông ta cũng có thông tin về mỗi dịch vụ xe buýt giữa các thành phố. Ông hiểu rằng ông không thể đưa tất cả các khách du lịch đến thành phố thăm quan trong cùng một chuyến đi.
Lấy ví dụ: Về bản đồ gồm 7 thành phố, mỗi cạnh được nối giữa các thành phố biểu thị những con đường và các số viết trên mỗi cạnh cho biết cho biết giới hạn hành khách của dịch vụ xe buýt chạy trên tuyến đường đó.

Bây giờ, nếu ông G muốn đưa 99 khách du lịch từ thành phố 1 đến thành phố 7. Ông ta sẽ phải yêu cầu ít nhất là 5 chuyến đi, và lộ trình ông ta nên đi là 1 – 2 – 4 – 7.
Nhưng, Ông G. nhận thấy là thật khó để tìm ra tất cả lộ trình tốt nhất để sao cho ông ta có thể đưa tất cả khách du lịch đến thành phố thăm quan với số chuyến đi là nhỏ nhất. Do vậy mà ông ta cần sự trợ giúp của các bạn.
Dữ liệu: Vào từ file Tourist.inp
- Tệp Tourist.inp sẽ chứa một hay nhiều trường hợp test.
- Dòng đầu tiên trong mỗi trường hợp test chứa hai số nguyên N (N ≤ 100) và R mô tả lần lượt số thành phố và số đường đi giữa các thành phố.
- R dòng tiếp theo, mỗi dòng chứa 3 số nguyên: C1, C2, P. C1, C2 mô tả lộ trình đường đi từ thành phố C1 đến thành phố C2 và P (P > 1) là giới hạn lớn nhất có thể phục vụ của dịch vụ xe buýt giữa hai thành phố.
Các thành phố được đánh dấu bằng một số nguyên từ 1 đến N. Dòng thứ (R+1) chứa ba số nguyên S, D, T mô tả lần lượt thành phố khởi hành, thành phố cần đến và số khách du lịch được phục vụ.
Kết quả: Đưa ra file Tourist.out
Ghi ra số lộ trình nhỏ nhất cần phải đi qua các thành phố thỏa mãn yêu cầu đề bài.
Ví dụ:
Tourist.inp
7 10
1 2 30
1 3 15
1 4 10
2 4 25
2 5 60
3 4 40
3 6 20
4 7 35
5 7 20
6 7 30
1 7 99
0 0
Tourist.out
5

Bài 4: Ông Ngâu, Bà Ngâu.
Hẳn các bạn đã biết ngày "ông Ngâu bà Ngâu" hàng năm, đó là một ngày đầy mưa và nước mắt. Tuy nhiên, một ngày trước đó, nhà Trời cho phép 2 "ông bà" được đoàn tụ. Trong vũ trụ vùng thiên hà nơi ông Ngâu bà Ngâu ngự trị có N hành tinh đánh số từ 1 đến N, ông ở hành tinh Adam (có số hiệu là S) và bà ở hành tinh Eva (có số hiệu là T). Họ cần tìm đến gặp nhau.
N hành tinh được nối với nhau bởi một hệ thống cầu vồng. Hai hành tinh bất kỳ chỉ có thể không có hoặc duy nhất một cầu vồng (hai chiều) nối giữa chúng. Họ luôn đi tới mục tiêu theo con đường ngắn nhất. Họ đi với tốc độ không đổi và nhanh hơn tốc độ ánh sáng. Điểm gặp mặt của họ chỉ có thể là tại một hành tinh thứ 3 nào đó.
Yêu cầu: Hãy tìm một hành tinh sao cho ông Ngâu và bà Ngâu cùng đến đó một lúc và thời gian đến là sớm nhất. Biết rằng, hai ngưười có thể cùng đi qua một hành tinh nếu như họ đến hành tinh đó vào những thời điểm khác nhau.

Dữ liệu Trong file văn bản ONBANGAU.INP gồm
Dòng đầu là 4 số N M S T (N ≤ 100, 1 ≤ S ≠ T ≤ N), M là số cầu vồng. M dòng tiếp, mỗi dòng gồm hai số I J L thể hiện có cầu vồng nối giữa hai hành tinh I , J và cầu vồng đó có độ dài là L (1 ≤ I ≠ J ≤ N, 0 < L ≤ 200).
Kết quả Ra file văn bản ONBANGAU.OUT, do tính chất cầu vồng, mỗi năm một khác, nên nếu như không tồn tại hành tinh nào thoả mãn yêu cầu thì ghi ra một dòng chữ CRY. Nếu có nhiều hành tinh thoả mãn thì ghi ra hành tinh có chỉ số nhỏ nhất.

giangmeo

mấy bài này bạn phải dùng đến thuật toán heap Dijkstra nhưng hơi bị phức tạp đấy

thienthan

Bài hơi dài chưa đọc hết sao lấy bản khi nào rồi đọc.
Bài này cùng lắm vét cạn thôi code vài trăm dòng là cùng.

Quên bạn muốn code bằng gì?
Em đang học C++ cứ code bằng nó luyện tập đã.

Voldark

Mấy bài này bạn muốn giải bằng Pascal hay C++ vậy??? Khó thật đấy... Cỡ đề thi Quốc gia chứ chẳng chơi. Tuy nhiên thực sự là mông lung sao ấy... Đề bài ra có vẻ rất thiếu rõ ràng! Cụ thể là tìm con đường ngắn nhất từ thành phố 1 tới thành phố n, tìm làm sao??? Hay là các thang máy, đi kiểu gì cà? Mỗi thang chỉ đi được từ tầng này tới tầng kia, nhưng k0 biết tầng nào tới tầng nào thì sao mà chọn?

hoahonggai

Mình đang học Pascal. Mọi người giải hộ nhanh với.

giangmeo

bài thứ nhất ấy dùng Dijkstra kết hợp với thuật nén bit ấy.
bài hai thì dùng Dijkstra thôi chứ cần gì đâu.
bài 3 có lẻ dùng luồng cực đại ấy
bài 4 Dijkstra
chúc may mắn

hoahonggai

lập trình hộ cái.biết là dùng dịkstra rồi nhung vẫn ko lập trình được

giangmeo

kiên nhẩn chứ cái quan trọng của lập trình là kinh nghiệm bạn ah