[Lập trình newbie] Mỗi ngày một bài toán (số 13)

[09520281]

Hi all, thấy các bạn sĩ tử trao đổi mấy toppic kia sôi nổi quá nên ra bài số 13 hơi muộn hi. Mình đi ngay vào bài toán nhé :sogood:.

Hai bạn học sinh trong lúc nhàn rỗi nghĩ ra trò chơi sau đây.
Mỗi bạn chọn trước một dãy số gồm n số nguyên. Giả sử dãy số mà bạn thứ nhất chọn là:b₁, b₂, ..., b_ncòn dãy số mà bạn thứ hai chọn làc₁, c₂, ..., c_nMỗi lượt chơi mỗi bạn đưa ra một số hạng trong dãy số của mình. Nếu bạn thứ nhất đưa ra số hạng b_i (1 ≤ i ≤ n), còn bạn thứ hai đưa ra số hạng c_j (1 ≤ j ≤ n) thì giá của lượt chơi đó sẽ là |b_i+c_j|.Ví dụ: Giả sử dãy số bạn thứ nhất chọn là 1, -2; còn dãy số mà bạn thứ hai chọn là 2, 3. Khi đó các khả năng có thể của một lượt chơi là (1, 2), (1, 3), (-2, 2), (-2, 3). Như vậy, giá nhỏ nhất của một lượt chơi trong số các lượt chơi có thể là 0 tương ứng với giá của lượt chơi (-2, 2).

Yêu cầu

Hãy xác định giá nhỏ nhất của một lượt chơi trong số các lượt chơi có thể.
Time limit: 1s
Memory: 5MB

Dữ liệu

• Dòng đầu tiên chứa số nguyên dương n (n ≤ 10⁵)
• Dòng thứ hai chứa dãy số nguyên b₁, b₂, ..., b_n (|b_i| ≤ 10⁹, i=1, 2, ..., n)
• Dòng thứ hai chứa dãy số nguyên c₁, c₂, ..., c_n (|c_i| ≤ 10⁹, i=1, 2, ..., n)

Hai số liên tiếp trên một dòng được ghi cách nhau bởi dấu cách.

Kết quả

Ghi ra giá nhỏ nhất tìm được.

Ràng buộc

• 60% số tests ứng với 60% số điểm của bài có 1 ≤ n ≤ 1000.

Ví dụ


Dữ liệu:
2
1 -2
2 3
Kết qủa
0
Have fun :shy:

[11520132]

theo như mình hiểu cái đề thì là "trong tập hợp tất cả tổng của 1 số trong dãy này + 1 số trong dãy kia", tìm tổng có trị tuyệt đối bé nhất.
Hix, em làm nó in ra 100000 số hơn 1s rồi
còn kết quả với số cho radom thì lúc nào cũng 0 vì abs=0 là bé nhất rồi.

[quoctinvn]

Binary search

[09520500]

:go: code lun đi thôi :sogood:

Binary search

[11520086]

hehe mình cũng chơi hàm rand(), nhập 99999 e nó đứng đơ ra luôn, còn từ 1 đến 1000 thì okie:look_down:

theo như mình hiểu cái đề thì là "trong tập hợp tất cả tổng của 1 số trong dãy này + 1 số trong dãy kia", tìm tổng có trị tuyệt đối bé nhất.
Hix, em làm nó in ra 100000 số hơn 1s rồi
còn kết quả với số cho radom thì lúc nào cũng 0 vì abs=0 là bé nhất rồi.

[10520237]

cái này sort 2 dãy b,c. 1 dãy chạy tiến, 1 cái chạy lùi sao cho |b+c| min là ok. căn bản là cái sort. thường thì thấy quýt sọt là nhanh, không thì binary search cũng ok (cái này ta ghét:hellboy

[quoctinvn]

cái này sort 2 dãy b,c. 1 dãy chạy tiến, 1 cái chạy lùi sao cho |b+c| min là ok. căn bản là cái sort. thường thì thấy quýt sọt là nhanh, không thì binary search cũng ok (cái này ta ghét:hellboy

cách này không được đâu ạ :salute:

const
   fi = '';
   fo = '';
var
   f1,f2:text;
   n:longint;
   a,b: array[1..100000] of longint;
procedure openfiles;
begin
   assign(f1,fi); reset(f1);
   assign(f2,fo); rewrite(f2);
end;

procedure closefiles;
begin
   close(f1); close(f2);
end;

procedure sort(l,h:longint);
var
   i,j,p,tmp:longint;
begin
   if l>=h then exit;
   i:=l; j:=h;
   p:=b[(l+h) div 2];
   repeat
      while b[i] > p do inc(i);
      while b[j] < p do dec(j);
      if i<= j then
         begin
            if i < j then
               begin
                  tmp:=b[i];
                  b[i]:=b[j];
                  b[j]:=tmp;
               end;
            inc(i); dec(j);
         end;
   until i>=j;
   sort(l,j); sort(i,h);
end;

function binarysearch(s:longint):longint;
var
   min,max,mid,l,r:longint;
begin
   l:=1; r:=n; binarysearch:=0; min:=n; max:=1;
   repeat
      mid:=(l+r) div 2;
      if b[mid] = s then exit(mid);
      if b[mid] > s then
         begin
            if b[mid] < b[max] then max:=mid;
            l:=mid+1;
         end;
      if b[mid] < s then
         begin
            if b[mid] > b[min] then min:=mid;
            r:=mid-1;
         end;
   until l>r;
   if abs(s-b[min]) < abs(s-b[max]) then
      exit(min)
   else
      exit(max);
end;

procedure init;
var
   i:longint;
begin
   readln(f1,n);
   for i:=1 to n do read(f1,a[i]);
   for i:=1 to n do read(f1,b[i]);
   sort(1,n);
end;

procedure solve;
var
   i,k:longint;
   min:int64;
begin
   min:=10000000000;
   for i:=1 to n do
      begin
         k:=binarysearch(-a[i]);
         if abs(a[i]+b[k])=0 then
            begin
               write(f2,0);
               exit;
            end
         else
            if (min > abs(a[i]+b[k])) then min:=abs(a[i]+b[k]);
      end;
   write(f2,min);
end;

begin
   openfiles;
   init;
   solve;
   closefiles;
end.

Trong 2 dãy ở input, sort 1 dãy theo thứ tự tăng dần. Với mỗi giá trị ở dãy còn lại, dùng binary search 2 vị trí gần trái nhất và gần phải nhất sao cho trị tuyệt đối của 2 vị trí kia là min rồi so sánh 2 vị trí đó chọn 1. Lấy min trong tất cả các giá trị tìm được.

[ga9xvn]

Mấy bài toán kiủ này có qui đinh viết bằng cái gì hong mấy a thấy ông trên viết bằng pascal hả ji ak!

[08520257]

Đã 5 năm mới thấy code pascal đó.

[ga9xvn]

Theo nghiên cứu thì ông quoctinvn mới học 12 xong nên chưa học thêm ngôn ngữ nào hết! Chỉ được học pascal trong trương trình 11 nếu mới học mà viết được như vậy là pro rồi (nếu đúng, làm biếng test)!

[10520237]

cách này không được đâu ạ :salute:

Trong 2 dãy ở input, sort 1 dãy theo thứ tự tăng dần. Với mỗi giá trị ở dãy còn lại, dùng binary search 2 vị trí gần trái nhất và gần phải nhất sao cho trị tuyệt đối của 2 vị trí kia là min rồi so sánh 2 vị trí đó chọn 1. Lấy min trong tất cả các giá trị tìm được.

ko đc ở chỗ nào? đây là cách của miềng test vs n=5

void main()
{
	int kq,n=5;
	int b[5]={1,5,4,2,0};
	int c[5]={-2,-7,4,10,3};
	QuickSort(b,0,4);
	QuickSort(c,0,4);
	kq=abs(b[0]+c[0]);
	int i=0, j=n-1;
	while(i<(n-1) && j>0)
	{
		if(abs(b[i]+c[j])<kq)
			kq=abs(b[i]+c[j]);
		if((b[i]+c[j])>=0)
			j--;
		else
			i++;
	}
	cout<<"\ncuoi cung:"<<kq;
	system("pause");
}

[quoctinvn]

Ví dụ
3
-3 -2 -1
-3 -4 -5

Code của anh ra KQ nhiêu ? ps:

[10520237]

Ví dụ
3
-3 -2 -1
-3 -4 -5

Code của anh ra KQ nhiêu ? ps:

tạch! :unhappy: chưa test đến trường hợp này

[11520132]

thế có ai cho 100000 số mà <1s chưa
tính cả công đoạn in 100000 số đó cũng mệt :doubt:

[quoctinvn]

Thuật em nlogn đấy ạ :sogood:

thế có ai cho 100000 số mà <1s chưa
tính cả công đoạn in 100000 số đó cũng mệt :doubt: