Nguồn đề bài: http://www.spoj.com/PTIT/problems/P132SUMJ/
Nội dung bài viết
1. Đề bài P132SUMJ spoj PTIT
Cho trước một số nguyên dương X. Nhiệm vụ của bạn là tìm số nhỏ nhất lớn hơn X, mà có các chữ số giống hệt với X.
Input
Dòng đầu tiên là số nguyên X (1 ≤ X ≤ 999 999).
Chữ số đầu tiên của X luôn khác 0.
Output
In ra đáp số trên một dòng. Nếu không có đáp số, in ra “0”.
Example
Test 1:
Input:
156
Output:
165
Test 2:
Input:
330
Output:
0
Test 3:
Input:
27711
Output:
71127
2. Thuật toán bài P132SUMJ spoj PTIT
Đưa bài toán về dạng quay lui sinh hoán vị. Dễ dàng nhận thấy dãy hoán vị sinh được từ thuật toán quay lui sẽ tăng dần. do đó đầu tiên sắp xếp thứ tự các số từ nhỏ đến lớn. sau đó dùng thuật toán quay lui để tìm kết quả. nếu tìm thấy số lớn hơn số ban đầu thì đó chính là kết quả bài toán.
3. Code tham khảo P132SUMJ spoj PTIT
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 | const fi=''; nmax=999999; type data=longint; var f:text; kq,S,A,tmp:string; n,sl,i:data; dd:array[1..6] of boolean; procedure sort(l,r: longint); var i,j: longint; y,x:char; begin i:=l; j:=r; x:=s[(l+r) div 2]; repeat while s[i]<x do inc(i); while x<s[j] do dec(j); if not(i>j) then begin y:=s[i]; s[i]:=s[j]; s[j]:=y; inc(i); j:=j-1; end; until i>j; if l<j then sort(l,j); if i<r then sort(i,r); end; procedure try; var i:data; begin if sl=n then begin if kq>a then begin writeln(kq); halt; end; end else for i:=1 to n do if not dd[i] then begin inc(sl); dd[i]:=true; kq[sl]:=s[i]; try; dd[i]:=false; dec(sl); end; end; begin assign(f,fi); reset(f); readln(f,s); close(f); n:=length(s); a:=s; kq:=s; sort(1,n); for i:=n downto 1 do tmp:=tmp+s[i]; if tmp=a then begin writeln(0); halt; end; fillchar(dd,sizeof(dd),false); sl:=0; try; writeln(0); end. |
Bài viết liên quan
- BCCOW spoj PTIT – Đi xem phim
- P134SUMG PTIT spoj – SUM4 G – Gia vị
- PTIT016E spoj PTIT – ACM PTIT 2016 E – Kỳ thi ACM/ICPC
- NKH spoj – Tách Từ
- P156SUME spoj PTIT – ROUND 6E – Ước chung của chuỗi
- P156SUMH spoj PTIT – ROUND 6H – Kim cương
- P151SUMB spoj PTIT – ROUND 1B – Đong gạo
- BCACM11G spoj PTIT – Dãy con tăng dần tự nhiên bậc K
- BCACM11D spoj PTIT – Đường nguyên tố
- COIN34 spoj – 34 Đồng Xu
Chị nhập 156 sao kết quả lại ra 651 nhỉ
Ủa chị, em nhập 156 vẫn ra 165 mà chị 😀
https://ideone.com/mKqg0v