Một bài trong đề thi Tin học trẻ TP Đà Nẵng 2010-2011

perfectstrong · 20-04-2011, 10:22 PM

Bài 3: (5đ) Số kề trước.
Cho một số tự nhiên N có K chữ số (0<K<=255). Bằng cách hoán vị các chữ số của N, ta sẽ được một số tự nhiên H.
Yêu cầu: Hãy tìm một số H lớn nhất và nhỏ hơn N từ cách làm trên

Input: File văn bản KETRUOC.INP gồm:
-dòng thứ 1 ghi số nguyên dương m (m<=10)
-m dòng tiếp theo, mỗi dòng ghi một số N.

Output: File văn bản KETRUOC.OUT có m dòng, mỗi dòng chứa một số H. Nếu không có số H thì ghi kết quả là -1.

Giới hạn: 5 giây.
======================
Ý kiến: Bài này, em dùng thuật toán tham lam, nhưng không thể quét sạch tất cả trường hợp trong 5 giây. Em xin hỏi có ai có thuật toán nào mạnh hơn, giải quyết bài này trong vòng không quá 5 giây không?

**batigoal** · 20-04-2011, 10:24 PM

Trích:

Nguyên văn bởi perfectstrong

Bài 3: (5đ) Số kề trước.
Cho một số tự nhiên N có K chữ số (0<K<=255). Bằng cách hoán vị các chữ số của N, ta sẽ được một số tự nhiên H.
Yêu cầu: Hãy tìm một số H lớn nhất và nhỏ hơn N từ cách làm trên

Input: File văn bản KETRUOC.INP gồm:
-dòng thứ 1 ghi số nguyên dương m (m<=10)
-m dòng tiếp theo, mỗi dòng ghi một số N.

Output: File văn bản KETRUOC.OUT có m dòng, mỗi dòng chứa một số H. Nếu không có số H thì ghi kết quả là -1.

Giới hạn: 5 giây.
======================
Ý kiến: Bài này, em dùng thuật toán tham lam, nhưng không thể quét sạch tất cả trường hợp trong 5 giây. Em xin hỏi có ai có thuật toán nào mạnh hơn, giải quyết bài này trong vòng không quá 5 giây không?

Em có thể dùng thuật toán vét cạn quay lui.Độ phức tạp của thuật toán này hình như là $0(n^2) $

perfectstrong · 22-04-2011, 03:36 PM

Trích:

Nguyên văn bởi batigoal

Em có thể dùng thuật toán vét cạn quay lui.Độ phức tạp của thuật toán này hình như là $0(n^2) $

Anh có thể trình bày đầy đủ lời giải được không?

duynhan · 22-04-2011, 09:27 PM

Trích:

Nguyên văn bởi perfectstrong

Bài 3: (5đ) Số kề trước.
Cho một số tự nhiên N có K chữ số (0<K<=255). Bằng cách hoán vị các chữ số của N, ta sẽ được một số tự nhiên H.
Yêu cầu: Hãy tìm một số H lớn nhất và nhỏ hơn N từ cách làm trên

Input: File văn bản KETRUOC.INP gồm:
-dòng thứ 1 ghi số nguyên dương m (m<=10)
-m dòng tiếp theo, mỗi dòng ghi một số N.

Output: File văn bản KETRUOC.OUT có m dòng, mỗi dòng chứa một số H. Nếu không có số H thì ghi kết quả là -1.

Giới hạn: 5 giây.

Bài này nếu suy nghĩ 1 chút ta sẽ thấy để số sau khi đổi lớn nhất ta cố gắng giữ càng nhiều số đầu thì càng tốt.

Bài này dò từ hàng đơn vị lên nếu mà 2 số liền kề mà chữ số thứ i-1 lớn hơn chữ số thứ i nghĩa là có cách chuyển để ta thu được 1 số mới nhỏ hơn N. Khi đó ta lấy số lớn nhất trong các số từ i đến length(N) ( số chữ số của N) đổi vị trí với n-1. Rồi sắp xếp các số từ i đến length(N) theo thứ tự giảm dần ta sẽ được số MAX.

Ví dụ:
123456784654321
123456768544321

Sẵn tiện cho mình hỏi, có đề THPT không, post lên giúp với !!

perfectstrong · 23-04-2011, 10:30 PM

Nếu N=4123 thì theo cách làm của anh sẽ cho ra H=?

duynhan · 23-04-2011, 10:37 PM

Trích:

Nguyên văn bởi perfectstrong

Nếu N=4123 thì theo cách làm của anh sẽ cho ra H=?

4123
--> 3421

twilight_2512 · 24-04-2011, 09:47 AM

Ơ hay!!
123456784654321 nếu chuyển thành 123456784654312 thì đúng hơn chứ nhỉ
vì 123456768544321 < 123456784654312 < 123456784654321 mà.

Mình vẫn chưa làm ra, nhưng theo mình thì bài này làm bằng Quy Hoạch Động.

perfectstrong · 24-04-2011, 10:24 AM

Trích:

Nguyên văn bởi twilight_2512

Ơ hay!!
123456784654321 nếu chuyển thành 123456784654312 thì đúng hơn chứ nhỉ
vì 123456768544321 < 123456784654312 < 123456784654321 mà.

Mình vẫn chưa làm ra, nhưng theo mình thì bài này làm bằng Quy Hoạch Động.

Anh trình bày thuật toán quy hoạch động của anh đi.

twilight_2512 · 24-04-2011, 07:14 PM

À không, cách của duynhan đúng rồi đấy, chỉ là cái ví dụ làm sai thôi, tức là theo thuật toán đó thì đúng là sẽ đổi chỗ 2 chữ số cuối cùng thôi.
Hồi sáng chưa đọc kỹ mà chỉ nhìn ví dụ, sr nha

caoxuanhuy · 25-04-2011, 10:14 AM

Em có ví dụ này.
37546129 thì theo thuật toán của anh duynhan thì sẽ là
37549621
cho mình hỏi luôn, anh perfectstrong đạt giải mấy.

duynhan · 26-04-2011, 08:39 AM

Trích:

Nguyên văn bởi caoxuanhuy

Em có ví dụ này.
37546129 thì theo thuật toán của anh duynhan thì sẽ là
37549621
cho mình hỏi luôn, anh perfectstrong đạt giải mấy.

Số lớn nhất nhỏ hơn số cần đổi chứ!!!

@all: Sr cái ví dụ mình cho nhầm ^^

Mashimaru · 26-04-2011, 10:41 AM

Code:

#include <cstdio>
#include <cstring>
using namespace std;

int m,num[10],result[255];
char N[255];

int main(){
    freopen("KETRUOC.INP","r",stdin);
    freopen("KETRUOC.OUT","w",stdout);
    scanf("%d",&m);
    while (m--){
          scanf("%s",&N); int length=strlen(N);
          for (int i=0; i<length; i++) num[N[i]-'0']++;
          for (int i=0; i<length; i++){
              if (i==length-1)
                 for (int j=0; j<10; j++)
                     if (num[j]){
                        result[i]=j;
                        num[j]--;
                     }
              bool ok=false;
              for (int j=0; j<N[i+1]-'0'; j++)
                  if (num[j]){
                     ok=true;
                     break;
                  }
              if (ok){
                 result[i]=N[i]-'0';
                 num[N[i]-'0']--;
              }
              else{
                   for (int j=N[i]-'0'-1; j>-1; j--)
                       if (num[j]){
                          result[i]=j;
                          num[j]--;
                          break;
                       }
                   int t=i+1;
                   for (int j=9; j>-1; j--) 
                       while (num[j]){
                             result[t++]=j;
                             num[j]--;
                       }
                   break;
              }
          }
          int k=0;
          while (!result[k]) k++;
          for (int i=k; i<length; i++) printf("%d",result[i]);
          printf("\n");
    }
    return 0;
}

Độ phức tạp O(n)

caoxuanhuy · 27-04-2011, 01:31 PM

Trích:

Nguyên văn bởi duynhan

Số lớn nhất nhỏ hơn số cần đổi chứ!!!

nhưng ở trên anh viết là dò từ hàng đơn vị lên nếu mà 2 số liền kề mà chữ số thứ i-1 lớn hơn chữ số thứ i nghĩa là có cách chuyển để ta thu được 1 số mới nhỏ hơn N. Khi đó ta lấy số lớn nhất trong các số từ i đến length(N) ( số chữ số của N) đổi vị trí với i-1. Rồi sắp xếp các số từ i đến length(N) theo thứ tự giảm dần ta sẽ được số MAX mà

perfectstrong · 27-04-2011, 08:15 PM

Trích:

Nguyên văn bởi caoxuanhuy

nhưng ở trên anh viết là dò từ hàng đơn vị lên nếu mà 2 số liền kề mà chữ số thứ i-1 lớn hơn chữ số thứ i nghĩa là có cách chuyển để ta thu được 1 số mới nhỏ hơn N. Khi đó ta lấy số lớn nhất trong các số từ i đến length(N) ( số chữ số của N) đổi vị trí với i-1. Rồi sắp xếp các số từ i đến length(N) theo thứ tự giảm dần ta sẽ được số MAX mà

Nếu vậy thì khi N=12362423489 thì làm theo thụât toán trên, ta đổi thế nào, không lẽ phải đổi chữ số 9 với chữ số 4 à?

duynhan · 28-04-2011, 04:56 AM

Trích:

Nguyên văn bởi perfectstrong

Nếu vậy thì khi N=12362423489 thì làm theo thụât toán trên, ta đổi thế nào, không lẽ phải đổi chữ số 9 với chữ số 4 à?

12362398442

Đây là code:

Code:

Var S:string;
    i, j, cs, k:integer;
    max, t:char;
Begin
   Readln(S);
   i:=length(S);
   While (i>1) and (s[i-1]<=s[i]) do dec(i); //Tim s[i-1]>s[i]
   If i=1 then
      Begin
         Write('Khong co cach doi');
         Exit;
      End;

   dec(i);
   max:='0';
   For j:=i+1 to length(S) do
     If (s[j]<s[i]) and (max<s[j]) then
       Begin
         max:=s[j];
         cs:=j;
       End;

   t:=s[i];
   s[i]:=s[cs];
   s[cs]:=t;

   k:=i+1;

   For i:=k to length(S)-1 do
     For j:=i+1 to length(S) do
        IF s[i]<s[j] then
          Begin
            t:=s[i];
            s[i]:=s[j];
            s[j]:=t;
          End;

   Write(S);

End.

20-04-2011, 10:22 PM	#1
perfectstrong +Thành Viên+ Tham gia ngày: Feb 2011 Đến từ: Đà Nẵng Bài gởi: 91 Thanks: 388 Thanked 35 Times in 25 Posts	Một bài trong đề thi Tin học trẻ TP Đà Nẵng 2010-2011 Bài 3: (5đ) Số kề trước. Cho một số tự nhiên N có K chữ số (0<K<=255). Bằng cách hoán vị các chữ số của N, ta sẽ được một số tự nhiên H. Yêu cầu: Hãy tìm một số H lớn nhất và nhỏ hơn N từ cách làm trên Input: File văn bản KETRUOC.INP gồm: -dòng thứ 1 ghi số nguyên dương m (m<=10) -m dòng tiếp theo, mỗi dòng ghi một số N. Output: File văn bản KETRUOC.OUT có m dòng, mỗi dòng chứa một số H. Nếu không có số H thì ghi kết quả là -1. Giới hạn: 5 giây. ====================== Ý kiến: Bài này, em dùng thuật toán tham lam, nhưng không thể quét sạch tất cả trường hợp trong 5 giây. Em xin hỏi có ai có thuật toán nào mạnh hơn, giải quyết bài này trong vòng không quá 5 giây không?

25-04-2011, 10:14 AM	#10
caoxuanhuy +Thành Viên+ Tham gia ngày: Apr 2011 Bài gởi: 6 Thanks: 12 Thanked 1 Time in 1 Post	ví dụ Em có ví dụ này. 37546129 thì theo thuật toán của anh duynhan thì sẽ là 37549621 cho mình hỏi luôn, anh perfectstrong đạt giải mấy.

23-04-2011, 10:30 PM	#5
perfectstrong +Thành Viên+ Tham gia ngày: Feb 2011 Đến từ: Đà Nẵng Bài gởi: 91 Thanks: 388 Thanked 35 Times in 25 Posts	Nếu N=4123 thì theo cách làm của anh sẽ cho ra H=?

24-04-2011, 09:47 AM	#7
twilight_2512 +Thành Viên+ Tham gia ngày: Jan 2010 Bài gởi: 2 Thanks: 0 Thanked 0 Times in 0 Posts	Ơ hay!! 123456784654321 nếu chuyển thành 123456784654312 thì đúng hơn chứ nhỉ vì 123456768544321 < 123456784654312 < 123456784654321 mà. Mình vẫn chưa làm ra, nhưng theo mình thì bài này làm bằng Quy Hoạch Động.

24-04-2011, 07:14 PM	#9
twilight_2512 +Thành Viên+ Tham gia ngày: Jan 2010 Bài gởi: 2 Thanks: 0 Thanked 0 Times in 0 Posts	À không, cách của duynhan đúng rồi đấy, chỉ là cái ví dụ làm sai thôi, tức là theo thuật toán đó thì đúng là sẽ đổi chỗ 2 chữ số cuối cùng thôi. Hồi sáng chưa đọc kỹ mà chỉ nhìn ví dụ, sr nha