Skip to content
Narrow screen resolution Wide screen resolution Auto adjust screen size Increase font size Decrease font size Default font size default color grey color
         
 | 
VNOI - Olympic tin học Việt Nam

Điểm tin VOJ

Số thành viên:6040
Số bài tập:1001
Số bài nộp:722923
Bài nộp hôm nay:0

Top 10 thành viên xuất sắc

HạngThành viênĐiểm
1mr_invincible587.9
2white_cobra418.6
3hieult403.4
4phaleq384.0
5vodanh9x368.2
6con_nha_ngheo352.0
7flash_mt350.2
8darksabers349.8
9yenthanh132345.3
10rockman9x_94343.1
So sánh mã (Comparing code) In E-mail
(3 votes)
Người viết: Ngô Minh Đức   
21/04/2008
Bài Comparing code (So sánh mã)
Công ty Racine Business Networks (RBN) kiện công ty Heuristic Algorithm Languages (HAL) ra toà vì cho rằng HAL đã lấy mã nguồn của RBN UNIXTM để sử dụng cho hệ điều hành mã nguồn mở HALnix.
RBN và HAL đều cùng sử dụng một ngôn ngữ lập trình với mỗi lệnh trên một dòng theo dạng: STOREA = STOREB + STOREC. Trong đó STOREA, STOREB, và STOREC là các tên biến. Cụ thể, tên biến thứ nhất bắt đầu ở cột thứ nhất và được theo sau bởi một dấu cách, dấu bằng, dấu cách, tên biến thứ hai, dấu cách, dấu cộng, dấu cách, tên biến thứ ba. Một tên biến có thể xuất hiện nhiều lần trên một dòng. Tên biến được tạo thành từ 1 đến 8 ký tự hoa trong bảng mã ASCII (′A′…′Z′).
RBN cho rằng HAL đã sao chép các dòng lệnh liên tiếp trực tiếp từ mã nguồn của RBN, chỉ thực hiện một số thay đổi nhỏ.
− Theo RBN, HAL đã thay đổi một số tên biến để che dấu hành vi phạm tội của mình. HAL lấy một loạt các dòng lệnh từ chương trình của RBN và với mỗi tên biến, thay đổi mọi sự xuất hiện của tên biến đó thành tên biến mới, mặc dầu tên biến mới có thể trùng tên biến cũ. Tất nhiên, không có hai biến được đổi thành cùng một tên mới.
− RBN cũng cho rằng HAL có thể thay đổi thứ tự vế phải của một số dòng lệnh:
STOREA = STOREB + STOREC có thể được đổi thành STOREA = STOREC + STOREB.
− RBN cho rằng HAL không thay đổi thứ tự các dòng lệnh từ mã nguồn của RBN.
Cho các mã nguồn chương trình của RBN và HAL, tìm các lệnh liên tiếp dài nhất từ chương trình của HAL mà có thể được tạo thành từ các lệnh chương trình của RBN bằng các cách thay đổi như trên. Chú ý rằng chuỗi các lệnh từ hai chương trình không phải bắt đầu tại cùng một dòng trong cả hai file.
Input: code.inp
− Dòng đầu tiên của file INPUT bao gồm hai số nguyên R and H (1 ≤ R ≤ 1000; 1 ≤ H ≤ 1000) phân tách nhau bởi dấu cách. R là số dòng lệnh trong chương trình nguồn của RBN. H là số dòng lệnh trong chương trình nguồn của chưong trình HAL.
− R dòng tiếp theo là mã nguồn chương trình của RBN.
− H dòng tiếp theo là mã nguồn chương trình của HAL.
Output: code.out
Tệp OUTPUT bao gồm một dòng với một số nguyên là số dòng lệnh liên tiếp dài nhất mà HAL có thể đã sao chép của RBN và sửa đổi.
Ví dụ:
CODE.INP.
4 3
RA = RB + RC
RC = D + RE
RF = RF + RJ
RE = RF + RF
HD = HE + HF
HM = HN + D
HN = HA + HB
CODE.OUT.
2
Dòng từ 1 − 2 của chương trình RBN giống dòng 2-3 của chương trình HAL, nếu việc thay đổi các tên biến được thực hiện như sau đối với chương trình của RBN: RA → HM, RB → D, RC → HN, D → HA, RE → HB. Không có sự tương ứng với nhiều hơn hoặc bằng ba dòng lệnh liên tiếp.
Hạn chế: Thời gian chạy chương trình là 2 giây. Bộ nhớ 64 MB.
Cho điểm:
Bạn sẽ nhận được điểm tối đa cho mỗi bộ test nếu chương trình của bạn đưa ra được đúng tệp CODE.OUT.
 
< Trước   Tiếp >