Nguồn đề bài: http://www.spoj.com/PTIT/problems/P134SUMG/
1. Đề bài P134SUMG PTIT spoj
Tại một nhà hàng truyền thống của Ấn Độ, đầu bếp đang phân vân trong việc chọn gia vị cho món ăn của mình. Nhà hàng này rất nổi tiếng bởi bí quyết gia vị của họ, đặc biệt là vị chua và vị cay. Các món ăn của họ có vị chua và cay xen lẫn nhau rất đặc biệt.
Hiện tại đang có tất cả N loại gia vị. Mỗi loại có độ chua S_i và độ cay B_i đặc chưng. Khi trộn K loại gia vị vào món ăn, độ chua của món ăn sẽ bằng tích độ chua của K loại gia vị, trong khi đó độ cay sẽ bằng tổng độ cay của K loại gia vị.
Để cho món ăn được hấp dẫn và hài hòa, đầu bếp sẽ chọn các loại gia vị sao cho sự chênh lệch giữa độ chua và độ cay của món ăn là nhỏ nhất.
Dĩ nhiên, cần phải chọn ít nhất một loại gia vị cho món ăn. Các bạn hãy giúp đầu bếp thực hiện công việc này.
Input
Dòng đầu tiên là số thành phần gia vị N (1 ≤ N ≤ 10).
N dòng tiếp theo, mỗi dòng gồm 2 số S_i, B_i mô tả đặc trưng vị chua và vị cay của gia vị đó.
Input được đảm bảo rằng nếu trộn tất cả các loại gia vị, thì độ cay và độ chua của món ăn sẽ nhỏ hơn 10^9.
Output
In ra sự chênh lệch nhỏ nhất giữa vị chua và vị cay của món ăn.
Example
Test 1:
Input:
1
3 10
Output:
7
Test 2:
Input:
2
3 8
5 8
Output:
1
Test 3:
Input:
4
1 7
2 6
3 8
4 9
Output:
1
Giải thích test 3: Đầu bếp sẽ chọn 3 gia vị cuối. Độ chua của món ăn sẽ bằng 2*3*4 = 24, còn độ cay là 6+8+9 = 23. Hiệu của chúng bằng 1.
2. gợi ý P134SUMG PTIT spoj
– Sử dụng thuật toán quay lui.
3. code tham khảo P134SUMG PTIT spoj c++ và pascal
a. Code pascal
const fi='';
nmax=10;
type
data=longint;
var
n:data;
A,B:array[1..nmax] of data;
f:text;
TONG, TICH:int64;
gtmin:data;
dd:array[1..nmax] of boolean;
function min(a,b:data):data;
begin
if a<b then exit(a);
exit(b)
end;
procedure docfile;
var i:data;
begin
assign(f,fi); reset(f);
readln(f,n);
for i:=1 to n do
readln(f,A[i],B[i]);
close(f);
end;
procedure tinh;
begin
gtmin:=min(gtmin,abs(tich-tong));
end;
procedure try(x:data);
var i:data;
tmp:int64;
begin
if x<>n then
tinh
else
exit;
for i:=1 to n do
if (not dd[i]) then
begin
dd[i]:=true;
tich:=tich*a[i];
tong:=tong+b[i];
try(x+1);
tich:=tich div a[i];
tong:=tong-b[i];
dd[i]:=false;
end;
end;
procedure xuli;
var i,res:data;
begin
res:=high(data);
fillchar(dd,sizeof(dd),false);
for i:=1 to n do
begin
tich:=a[i];
tong:=b[i];
gtmin:=abs(a[i]-b[i]);
dd[i]:=true;
try(0);
dd[i]:=false;
res:=min(res,gtmin);
end;
writeln(res);
end;
begin
docfile;
xuli;
end.b. Code c++
#include <iostream>
#include <cmath>
using namespace std;
long chua[11],cay[11],a[11],n,schua=1,scay=0,min1=1000000000;
void init()
{
cin >> n;
for(int i=0;i<n;i++)
cin >> chua[i] >> cay[i];
}
void test()
{
schua=1;scay=0;
int t=0,l=0;
for(int i=0;i<n;i++)
{
if(a[i])
{
t=1;
if(chua[i]!=0)
schua*=chua[i];
scay+=cay[i];
}
}
if(t)
{
long d=schua-scay;
if(d<0) d=d*(-1);
if(d<min1) min1=d;
}
}
void tim(int i)
{
for(int j=0;j<=1;j++)
{
a[i]=j;
if(i==n-1) test();
else tim(i+1);
}
}
int main()
{
init();
if(n==1)
{
min1=chua[0]-cay[0];
if(min1<0) min1*=-1;
cout << min1;
}
else
{
tim(0);
cout << min1 ;
}
}
