GHÉP SỐ LỚN – NUMCON – SPOJ | LÀM HẾT MÌNH

ĐỀ BÀI :

GHÉP SỐ LỚN  – NUMCON – SPOJ

Vaxia đã viết được một số lớn trên một cuộn giấy dài và muốn khoe với anh trai Petia về thành quả vừa đạt được. Tuy nhiên,  khi Vaxia vừa ra khỏi phòng để gọi anh trai thì cô em Kachia chạy vào phòng và xé rách cuộn giấy thành một số mảnh. Kết quả là trên mỗi mảnh có một hoặc vài kí số theo thứ tự đã viết.

Bây giờ Vaxia không thể nhớ chính xác mình đã viết số gì. Vaxia chỉ nhớ rằng đó là một số rất lớn.

Để làm hài lòng cậu em trai, Petia quyết định truy tìm  số nào là lớn nhất mà Vaxia đã có thể viết lên cuộn giây trước khi bị xé. Bạn hãy giúp Petia làm việc này.

Dữ liệu vào:

Ghi một hoặc nhiều dòng. Mỗi dòng ghi một dãy kí số. Số dòng không vượt quá 100. Mỗi dòng ghi từ 1 đến 100 kí số. Bảo đảm rằng có ít nhất một dòng mà kí số đầu tiên khác 0.

Dữ liệu ra

Ghi ra số lớn nhất đã có thể viết trên cuộn giấy trước khi bị xé rách.

Ví dụ

Input :

2 20 004 66

Output :

66220004

THUẬT TOÁN:

Bài này dùng tư tưởng sort lại dãy các số đề cho sao cho khi ghép hai số kề nhau trong dãy luôn là lớn nhất hay tối ưu, tức là khi printf ra dãy thì luôn đảm bảo dãy “trùm” nhất.

Do không quá 100 số nên bài toán trở nên tầm thường chỉ cần O(N^2) là được

Xin hỏi : Mình mới bắt đầu học về C++ nên chưa biết cách nhập hết file (EOF trong C++) (nhập xâu). Nếu có bạn nào am hiểu hoặc biết thì cho mình xin chỉ giúp để một ngày tốt hơn. tks

CODE :

var     a      : array[0..150] of string;         i,j,n : longint;         procedure swap(var x,y : string);  var    tmp : string;  begin         tmp := x;         x := y;         y := tmp;  end;   begin         n := 0;         repeat                 inc(n);                 readln(a[n]);         until                 eof;         for i := 1 to n-1 do                for j := i+1 to n do                      if (a[j]+a[i]>a[i]+a[j]) then swap(a[i],[j]);         for i :=  1 to n do write(a[i]); end.

Chia sẻ:

• X
• Facebook

Thích Đang tải...

Có liên quan