Link Sub: http://www.spoj.com/PTIT/problems/PTIT121K/
Người Gửi: Dương Lee
- Problem:
Sau những tiết học ban đầu hứng thú với môn Điện tử số về hệ cơ số, MĐ dần thấy nản khi phải đối mặt với các loại mạch và cổng @@. Đầu óc cứ nghĩ đến mấy cái hệ cơ số, MĐ lại nghĩ ra một bài toán khác để thử tài các bạn SV PTIT :D. Bài toán như sau:
Cho một bảng vuông (n x n) ô (2<=n<=100) các ô ghi các số là 0 hoặc 1. Bạn hãy tìm đường đi từ góc trái trên xuống góc phải dưới theo nguyên tắc chỉ được dịch chuyển sang phải và xuống dưới sao cho các số trên đường đi tạo thành một số nhị phân có giá trị lớn nhất.
InputCho một bảng vuông (n x n) ô (2<=n<=100) các ô ghi các số là 0 hoặc 1. Bạn hãy tìm đường đi từ góc trái trên xuống góc phải dưới theo nguyên tắc chỉ được dịch chuyển sang phải và xuống dưới sao cho các số trên đường đi tạo thành một số nhị phân có giá trị lớn nhất.
- Dòng đầu tiên ghi giá trị n
- n dòng tiếp theo, trên mỗi dòng ghi n số 0 hoặc 1 các số này cách nhau ít nhất một khoảng trắng.
- n dòng tiếp theo, trên mỗi dòng ghi n số 0 hoặc 1 các số này cách nhau ít nhất một khoảng trắng.
Output
Example:
- Một số duy nhất là giá trị trong hệ cơ số 16 của số nhị phân được tạo thành ở trên.
Input
5
1 0 1 1 0
0 0 1 0 1
0 0 1 0 1
1 0 0 1 1
1 1 0 1 0
Output:
176
- Solution:
- Đối với những bài dạng di chuyển chỉ phải - xuống, lên - trái ta có thể dùng quy hoạch động đơn giản để xét các trạng thái của nó tại mỗi vị trí.
- Ta có dãy các nhị phân: F[][] là mảng max dãy nhị phân. F[i][j] = max(F[i-1][j], F[i][j-1])+(char)(arr[i][j]);
- Sau đó là chuyển dãy nhị phân trên thành dãy các mã hệ 16 (Hex). Code dưới đây chuyển xâu bit thành xâu bit có độ dài chia hết cho 4 và xét 4 bít một để chuyển về Hex (Không thừa số 0 ở đầu).
- Ta có dãy các nhị phân: F[][] là mảng max dãy nhị phân. F[i][j] = max(F[i-1][j], F[i][j-1])+(char)(arr[i][j]);
- Sau đó là chuyển dãy nhị phân trên thành dãy các mã hệ 16 (Hex). Code dưới đây chuyển xâu bit thành xâu bit có độ dài chia hết cho 4 và xét 4 bít một để chuyển về Hex (Không thừa số 0 ở đầu).
- Code:
C++:
https://ideone.com/OMPxBJ
#include <iostream>
#include <math.h>
using namespace std;
int n;
int arr[102][102];
void read ()
{
cin>>n;
for (int i=1; i<=n; i++)
for (int j=1; j<=n; j++)
cin>>arr[i][j];
}
string F[102][102];
string He2 ()
{
for (int i=1; i<=n; i++)
{
F[0][i]="";
F[i][0]="";
}
for (int i=1; i<=n; i++)
{
for (int j=1; j<=n; j++)
{
char tmp = (arr[i][j]+'0');
F[i][j] = max(F[i-1][j], F[i][j-1])+tmp;
}
}
return F[n][n];
}
string BinToHex (string x)
{
string rs = "";
while (x.size()%4!=0)
x="0"+x;
for (int i=0; i<x.size(); i=i+4)
{
string tmp = x.substr(i, 4);
int d = 0;
for (int j=0; j<4; j++)
{
d+=((tmp[j]-'0')*pow(2,(3-j)));
}
char c;
if (d>=0 && d<=9)
c = d+'0';
else
c = d-10+'A';
rs = rs+c;
}
if (rs=="") return "0";
else
{
while (1)
{
if (rs.size()-1==0 || rs[0]!='0') break;
rs.erase(rs.begin(), rs.begin()+1);
}
}
return rs;
}
int main ()
{
read ();
string He2Max = He2();
// cout<<He2Max<<endl;
cout<<BinToHex(He2Max);
return 0;
}JAVA:
...Python:
...