Archives for Tháng Chín 2017


CBUYING – spoj

Đề bài:

Thuật toán:

  • Chọn số những sô cô la có giá rẻ nhất

Code:

#include <bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for (int i=(a),_b=(b);i<=_b;i=i+1)
#define FORD(i,b,a) for (int i=(b),_a=(a);i>=_a;i=i-1)
#define REP(i,n) for (int i=0,_n=(n);i<_n;i=i+1)
#define FORE(i,v) for (__typeof((v).begin()) i=(v).begin();i!=(v).end();i++)
#define ALL(v) (v).begin(),(v).end()
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
#define double db
typedef long long ll;
typedef pair<ll,ll> PII;
const ll mod=1000000007;
ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
const int MAXN = 1E6+3;
const int oo = 1e9+3;
 
int n;
ll ans, b;
PII a[MAXN];
 
bool cmp(PII a, PII b) {
    return (a.fi < b.fi);
}
 
int main() {
    cin >> n >> b;
    FOR(i,1,n) cin >> a[i].fi >> a[i].se;
    sort(a+1,a+n+1,cmp);
    FOR(i,1,n) {
        if (b < a[i].fi) break;
        ll tmp = b / a[i].fi;
        b -= min(tmp,a[i].se) * a[i].fi;
        ans += min(tmp,a[i].se);
    }
    cout << ans;
	return 0;
}

KPLANK – spoj

Đề bài:

Thuật toán:

  • Sừ dụng thuật toán tìm max/min trên một đoạn tịnh tiến.

Code:

uses math;
const
  fi='';
  fo='';
  maxn=trunc(1e6)+3;
var
  st : array[1..maxn] of longint;
  a,l,r : array[1..maxn] of longint;
  i,j,n : longint;
  res : int64;
  top : longint;
procedure enter;
  begin
    assign(input,fi);reset(input);
    readln(n);
    for i:=1 to n do read(a[i]);
  end;
procedure push(x : longint);
  begin
    inc(top);
    st[top] := x;
  end;
function get: longint;
  begin
    get := st[top];
  end;
procedure process;
  begin
    top :=0 ;
    for i:=1 to n do
      begin
        while (top<>0) and (a[get]>=a[i]) do dec(top);
        if top=0 then l[i] := 0 else l[i] := get;
        push(i);
      end;
    top := 0;
    for i:=n downto 1 do
      begin
        while (top<>0) and (a[get]>=a[i]) do dec(top);
        if top=0 then r[i]:=n+1 else r[i] := get;
        push(i);
      end;
    for i:=1 to n do
      if r[i]-l[i]-1>=a[i] then
        res := max(res, a[i]);
end;
procedure print;
  begin
    assign(output,fo);rewrite(output);
    writeln(res);
  end;
begin
  enter;
  process;
  print;
end.

Tìm kiếm nhị phân (chặt nhị phân) toàn tập

Đã lâu rồi mình chưa viết bài mới, hôm nay mình xin chia sẻ với các bạn cách code thuật toán tìm kiếm phân mà mình thường sử dụng.

Chắc mọi người cũng biết, cùng một thuật toán tìm kiếm nhị phân nhưng có rất nhiều cách code khác nhau, tất cả đều chính xác, tốc độ nhanh như nhau. Và cách mình chia sẻ dưới đây là một trong những cách dễ hiểu nhất, linh hoạt nhất mà tốc độ chạy cũng khá tốt (cách này của anh Kiên – HCB Olympic Tin học Quốc tế)

Dãy con tăng – Tìm phần tử lớn nhất nhỏ hơn x (chỉ số lớn nhất)

// day con tang – tim phan tu lon nhat nho hon x ( chi so lon nhat);

function tim2(r,x : longint) : longint;

  var d,c,g : longint;

  begin

    d:=0;c:=r;

    g:=(d+c) div 2;

    while (g<>d) and (g<>c) do

      begin

        if b[g]>=x then c:=g else d:=g;

        g:=(d+c) div 2;

      end;

    for g:=c downto  d do

      if b[g]<x then exit(g);

   end;

Dãy con tăng – Tìm số bé nhất lớn hơn hoặc bằng x (chỉ số bé nhất)

// day con tang – so be nhat lon hon hoac bang x (chi so be nhat);

sort(a);

left=1, right=n;
i = (left + right) / 2;

while (left != i) and (i != right) do
    if a[i]>=k then right = i;
    else left = i;
    i = (left + right) / 2;

for i = left to right do

if a[i]>=k then return a[i];

print “Not found”

Dãy con tăng – Tìm số bé nhất lớn hơn hoặc bằng x (chỉ số lớn nhất)

// day con tang – so be nhat lon hon hoac bang x ( chi so lon nhat);

sort(a);

left=1, right=n;
i = (left + right) / 2;

while (left != i) and (i != right) do
    if a[i]>k then right = i;
    else left = i;
    i = (left + right) / 2;

for i = right to left do

if a[i]<=k then return a[i];

print “Not found”

Dãy con giảm – Tìm phần tử cuối cùng lớn hơn x

//day con giam – tim phan tu cuoi cung lon hon x

function tim1(r,x : longint) : longint;

  var d,c,g : longint;

  begin

    d:=0;c:=r;

    g:=(d+c) div 2;

    while (g<>d) and (g<>c) do

      begin

        if b[g]>x then d:=g else c:=g;

        g:=(d+c) div 2;

      end;

    for g:=c downto d do

      if b[g]>x then exit(g);

  end;

Dãy con giảm – Tìm phẩn tử đầu tiên nhỏ hơn x

//day con giam – tim phan tu dau tien nho hon x

function tim1(r,x : longint) : longint;

  var d,c,g : longint;

  begin

    d:=0;c:=r;

    g:=(d+c) div 2;

    while (g<>d) and (g<>c) do

      begin

        if b[g]>x then d:=g else c:=g;

        g:=(d+c) div 2;

      end;

    for g:=d to c do

      if b[g]>x then exit(g);

  end;

Các bài khác nhau với các yêu cầu tìm kiếm khác nhau bạn có thể dễ dàng sửa đổi cho phù hợp nếu sử dụng cách tìm kiếm nhị phân mình vừa trình bày.

Mọi thắc mắc rất mong nhận được từ quý bạn đọc <3

Nhập, xuất dữ liệu từ file trong C++

Tất cả các chương trình mà ta đã gặp trong cuốn sách này đều lấy dữ liệu vào từ bàn phím và in ra màn hình. Nếu chỉ dùng bàn phím và màn hình là các thiết bị vào ra dữ liệu thì chương trình của ta khó có thể xử lý được khối lượng lớn dữ liệu, và kết quả chạy chương trình sẽ bị mất ngay khi ta đóng cửa sổ màn hình output hoặc tắt máy. Để cải thiện tình trạng này, ta có thể lưu dữ liệu  tại  các thiết bị lưu trữ thứ cấp mà thông dụng nhất thường là ổ đĩa cứng. Khi đó dữ liệu tạo bởi một chương trình có thể được lưu lại để sau này được sử dụng bởi chính nó hoặc các chương trình khác. Dữ liệu lưu trữ như vậy được đóng gói tại các thiết bị lưu trữ thành các cấu trúc dữ liệu gọi là tp (file).

Chương này sẽ giới thiệu về cách viết các chương trình lấy dữ liệu vào (từ bàn phím hoặc từ một tệp) và ghi dữ liệu ra (ra màn hình hoặc một  tệp).

Khái niệm dòng dữ liệu

Trong một số ngôn ngữ lập trình như C++ và Java, dữ liệu vào ra từ tệp, cũng  như từ bàn phím và màn hình, đều được vận hành thông qua các dòng dliu (stream). Ta có thể coi dòng dữ liệu là một kênh hoặc mạch dẫn  mà  dữ  liệu được truyền qua đó để chuyển từ nơi gửi đến nơi nhận.

Dữ liệu được truyền từ chương trình ra ngoài theo một dòng ra (output stream). Đó có thể là dòng ra chuẩn nối và đưa dữ liệu ra màn hình, hoặc dòng ra nối với một tệp và đẩy dữ liệu ra tệp đó.

Chương trình nhận dữ liệu vào qua một dòng vào (input stream). Dòng vào thì có thể là dòng vào chuẩn nối và đưa dữ liệu vào từ màn hình, hoặc dòng vào nối với một tệp và nhận dữ liệu vào từ tệp đó.

Dữ liệu vào và ra có thể là các kí tự, số, hoặc các byte chứa các chữ số nhị  phân.

Trong C++, các dòng vào ra được cài đặt bằng các đối tượng của các lớp dòng vào ra đặc biệt. Ví dụ, cout mà ta vẫn dùng để ghi ra màn hình chính là dòng ra chuẩn, còn cin là dòng vào chuẩn nối với bàn phím. Cả hai đều là các đối tượng dòng dữ liệu (khái niệm “đối tượng” này có liên quan đến tính năng hướng đối tượng của C++, khi nói về các dòng vào/ra của C++, ta sẽ phải đề cập nhiều đến tính năng này).

Tp văn bn và tp nhphân

Về bản chất, tất cả dữ liệu trong các tệp đều được lưu trữ dưới dạng một chuỗi các bit nhị phân 0 và 1. Tuy nhiên, trong một số hoàn cảnh, ta không  coi nội dung của một tệp là một chuỗi 0 và 1 mà coi tệp đó là một chuỗi các kí tự. Một   số tệp được xem như là các chuỗi kí tự và được xử lý bằng các dòng và hàm cho phép chương trình và hệ soạn thảo văn bản của bạn nhìn các chuỗi nhị phân như là các chuỗi kí tự. Chúng được gọi là các tp văn bn (text file). Những tệp không phải tệp văn bản là tp nhphân (binary file). Mỗi loại tệp được xử lý   bởi các dòng và hàm riêng.

Chương trình C++ của bạn được lưu trữ trong tệp văn bản. Các tệp ảnh và nhạc  là các tệp nhị phân. Do tệp văn bản là chuỗi kí tự, chúng thường trông giống nhau tại các máy khác nhau, nên ta có thể chép chúng  từ  máy này sang  máy khác mà không gặp hoặc gặp phải rất ít rắc rối. Nội dung của các tệp nhị phân thường lấy cơ sở là các giá trị số, nên việc sao chép chúng giữa các máy có thể gặp rắc rối do các máy khác nhau có thể dùng các quy cách lưu trữ số không giống nhau. Cấu trúc của một số dạng tệp nhị phân đã được chuẩn hóa để chúng có thể được sử dụng thống nhất tại các platform khác nhau. Nhiều dạng tệp ảnh và âm thanh thuộc diện này.

Mỗi kí tự trong một tệp văn bản được biểu diễn bằng 1 hoặc 2 byte, tùy theo đó  là kí tự ASCII hay Unicode. Khi một chương trình viết một giá trị vào một tệp văn bản, các kí tự được ghi ra tệp giống hệt như khi chúng được ghi ra màn hình bằng cách sử dụng cout. Ví dụ, hành động viết số 1 vào một tệp sẽ dẫn đến kết quả là 1 kí tự được ghi vào tệp, còn với số 1039582 là 7 kí tự được ghi vào  tệp.

Các tệp nhị phân lưu tất cả các giá trị thuộc một kiểu dữ liệu cơ bản theo cùng một cách, giống như cách dữ liệu được lưu trong bộ nhớ máy tính. Ví dụ, mỗi  giá trị int bất kì, 1 hay 1039582 đều chiếm một chuỗi 4 byte.

 Vào ra tệp

C++ cung cấp các lớp sau để thực hiện nhập và xuất dữ liệu đối với  tệp:

  • ofstream: lớp dành cho các dòng ghi dữ liệu ra tệp
  • ifstream: lớp dành cho các dòng đọc dữ liệu từ tệp
  • fstream: lớp dành cho các dòng vừa đọc vừa ghi dữ liệu ra tệp.

Đối tượng thuộc các lớp này do quan hệ thừa kế nên cách sử dụng chúng khá giống với cin và cout – các đối tượng thuộc lớp istream và ostream – mà chúng ta đã dùng. Khác biệt chỉ là ở chỗ ta phải nối các dòng đó với các  tệp.

c-p-yeulaptrinh.pw

Hình 8.1: Các thao tác cơ bn vi tp văn bn.

Chương trình trong Hình 8.1 tạo một tệp có tên hello.txt và ghi vào đó một câu “Hello!” theo cách mà ta thường làm đối với cout, chỉ khác ở chỗ thay cout bằng đối tượng dòng myfile đã được nối với một tệp. Sau đây là các bước thao tác với tệp.

  • Mở tệp

Việc đầu tiên là nối đối tượng dòng với một tệp, hay nói cách khác là mở một  tệp. Kết quả là đối tượng dòng sẽ đại diện cho tệp, bất kì hoạt động đọc và ghi  đối với đối tượng đó sẽ được thực hiện đối với tệp mà nó đại diện. Để mở một  tệp từ một đối tượng dòng, ta dùng hàm open của nó:

open (fileName, mode);


Trong đó, fileName là một xâu kí tự thuộc loại const char * với kết thúc là kí tự null (hằng xâu kí tự cũng thuộc dạng này), là tên của tệp cần mở, và mode là tham số không bắt buộc và là một tổ hợp của các cờ  sau:

ios::in     mở để đọc

ios::out    mở để ghi

ios::binary  mở ở dạng tệp nhị  phân

ios::ate    đặt ví trí bắt đầu đọc/ghi tại cuối tệp. Nếu cờ này không được đặt giá trị gì, vị trí khởi đầu sẽ là đầu tệp.

ios::app    mở để ghi tiếp vào cuối tệp. Cờ này chỉ được dùng  cho dòng mở tệp chỉ để ghi.

ios::trunc   nếu tệp được mở để ghi đã có từ trước, nội dung cũ sẽ bị  xóa

để ghi nội dung mới.
Các cờ trên có thể được kết hợp với nhau bằng toán tử bit OR (|). Ví dụ, nếu ta muốn mở tệp people.dat theo dạng nhị phân để ghi bổ sung dữ liệu vào cuối tệp, ta dùng lời gọi hàm sau:

ofstream myfile;
myfile.open ("people.dat",
   ios::out | ios::app | ios::binary);
Trong trường hợp lời gọi hàm open không cung cấp tham số mode, chẳng hạn Hình 8.1, chế độ mặc định cho dòng loại ostream là ios::out, cho dòng loại istream là ios::in, và cho dòng loại fstream là ios::in | ios::out.

Cách thứ hai để nối một dòng với một tệp là khai báo tên tệp và kiểu mở tệp  ngay khi khai báo dòng, hàm open sẽ được gọi với các đối số tương ứng. Ví dụ:

ofstream myfile ("hello.txt",
   ios::out | ios::app | ios::binary);

Để kiểm tra xem một tệp có được mở thành công hay không, ta dùng hàm thành viên is_open(), hàm này không yêu cầu đối số và trả về một giá trị kiểu bool bằng true nếu thành công và bằng false nếu xảy ra trường hợp ngược lại


if (myfile.is_open()) { /* file now open and ready */ }
  • Đóng tệp

Khi ta hoàn thành các công việc đọc dữ liệu và ghi kết quả, ta cần đóng tệp để

tài nguyên của nó trở về trạng thái sẵn sàng được sử dụng. Hàm thành viên này

 

không có tham số, công việc của nó là xả các vùng bộ nhớ có liên quan và đóng tệp:

 

Sau khi tệp được đóng, ta lại có thể dùng dòng myfile để mở tệp khác, còn tệp vừa đóng lại có thể được mở bởi các tiến trình  khác.

Hàm close cũng được gọi tự động khi một đối tượng dòng bị hủy trong khi    nó

đang nối với một tệp.

 

  • Xlý tp văn bn

Chế độ dòng tệp văn bản được thiết lập nếu ta không dùng cờ ios::binary khi mở tệp. Các thao tác xuất và nhập dữ liệu đối với tệp văn bản được thực hiện tương tự như cách ta làm với cout và cin.

#include <iostream>
#include <fstream>
 
using namespace std; 
 
int main ()
{
  ofstream courseFile (“courses.txt); if (courseFile.is_open())
  {
    courseFile <<1 Introduction to Programming\n”; courseFile <<2 Mathematics for Computer Science\n”; courseFile.close();
  }
  else cout << “Error: Cannot open file”;
  return 0;
}

Kết quả chạy chương trình [tệp courses.txt]

  • Introduction to Programming

 

  • Mathematics for Computer Science
Hình 8.2: Ghi dliu ra tp văn bn.
#include <iostream>
#include <fstream>
#include <string>
 
using namespace std; 
 
int main ()
{
  ifstream file (“courses.txt); 
  if (file.is_open())
  {
    while (! file.eof())
    {
      string  line; getline (file,line);
      cout << line << endl;
    }
    file.close();
  }
  else cout << “Error! Cannot open file”;
  return 0;
}

Kết quả chạy chương trình

  • Introduction to Programming
  • Mathematics for Computer Science

c-p-2-yeulaptrinh.pw

Hình 8.3: Đọc dliu ttp văn bn.

 

Chương trình ví dụ trong Hình 8.2 ghi hai dòng văn bản vào một tệp. Chương trình trong Hình 8.3 đọc nội dung tệp đó và ghi ra màn hình. Để ý rằng trong chương trình thứ hai, ta dùng một vòng lặp để đọc cho đến cuối tệp. Trong đó, myfile.eof() là hàm trả về giá trị true khi chạm đến cuối tệp, giá trị true mà myfile.eof() trả về đã được dùng làm điều kiện kết thúc vòng lặp đọc tệp.

Kiểm tra trạng thái của dòng

Bên cạnh hàm eof() có nhiệm vụ kiểm tra cuối tệp, còn có các hàm thành viên khác dùng để kiểm tra trạng thái của dòng:

bad()  trả về true nếu một thao tác đọc hoặc ghi bị thất bại. Ví dụ khi ta cố viết vào một tệp không được  mở  để ghi hoặc khi thiết bị lưu  trữ không còn chỗ trống để ghi.

fail() trả về true trong những trường hợp bad() trả về true và khi có lỗi định dạng, chẳng hạn như khi ta đang định đọc một số nguyên nhưng lại gặp phải dữ liệu là các chữ cái.

eof()   trả về true nếu chạm đến cuối tệp

good()    trả về false nếu xảy tình huống mà  một trong các hàm trên nếu được gọi thì sẽ trả về true.

Để đặt lại cờ trạng thái mà một hàm thành viên nào đó đã đánh dấu trước đó, ta dùng hàm thành viên clear.

STONE1 – spoj

Đề bài:

Thuật toán:

  • (đang cập nhập)

Code:

const
  fi='';//stone1.inp';
  fo='';//stone1.out';
  maxn=403;
  maxm=403;
type
  arr1 = array[1..maxn] of longint;
var
  link,head,ke : array[-maxm..maxm] of longint;
  f,deg : array[1..maxn] of longint;
  i,j,n,m,k : longint;
  st : array[1..maxn,1..maxn] of longint;
  top : array[1..maxn] of longint;
  a : array[1..maxn,1..maxn] of boolean;
  cx : array[1..maxn] of boolean;
procedure add(i,u,v : longint);
  begin
    link[i] := head[u];
    head[u] := i;
    ke[i] := v;
  end;
procedure enter;
  var u,v,i : longint;
  begin
    assign(input,fi);reset(input);
    read(n);
    for i := 1 to n do
      begin
        read(u,k);
        for j:=1 to k do
          begin
            read(v);
            if a[u,v] = false then
              begin
                a[u,v] := true;
                inc(deg[u]);
              end;
            if a[v,u] = false then
              begin
                a[v,u] := true;
                inc(deg[v]);
              end;
          end;
      end;
    close(input);
  end;
procedure push(i,x : longint);
  begin
    inc(top[i]);
    st[i,top[i]] := x;
  end;
procedure swap(var x,y : longint);
  var tg : longint;
  begin
    tg:=x;x:=y;y:=tg;
  end;
procedure qs(l,r : longint; var a : arr1);
  var i,j,x : longint;
  begin
    i :=l;j:=r;
    x := a[(l+r) div 2];
    repeat
      while a[i] > x do inc(i);
      while a[j] < x do dec(j);
      if i<=j then
        begin
          swap(a[i],a[j]);
          inc(i);dec(j);
        end;
    until i>j;
    if i<r then qs(i,r,a);
    if j>l then qs(l,j,a);
  end;
procedure dfs(u : longint);
  var i,v,s : longint;
  begin
    cx[u] := false;
    if deg[u] <= 1 then begin f[u] := 1; exit; end;
    for v := 1 to n do
      if a[u,v] then
      if cx[v] then
        begin
          dfs(v);
          push(u,f[v]);
        end;
    qs(1,top[u],st[u]);
    s := st[u,1];
    v := st[u,1]-1;
    for i:= 2 to top[u] do
      if v < st[u,i] then
      begin
        s := s + (st[u,i]-v);
        v := v + (st[u,i]-v);
        v := v - 1;
      end else v := v-1;
    f[u] := s;
  end;
procedure process;
  begin
    fillchar(cx,sizeof(cx),true);
    dfs(1);
  end;
procedure print;
  begin
    assign(output,fo);rewrite(output);
    writeln(f[1]);
    close(output);
  end;
begin
  enter;
  process;
  print;
end.

QBRECT – spoj

Đề bài:

Thuật toán:

Sau đây là cách tìm hình chữ nhật lớn nhất trong thời gian O(n^2):

Với mỗi ô j trên hàng i, ta tìm f(j) là số ô 1 liên tiếp trên cột j, tính từ hàng i trở lên. Sau đó, với mỗi cột j, ta tiếp tục tìm ô gần nhất bên trái và ô gần nhất bên phải có f nhỏ hơn f(j), sau đó tính diện tích hình chữ nhật ở cột j là S=f(j)×(r−l−1) với l,r là chỉ số 2 ô bên trái và bên phải nói trên.
Hình minh hoạ khi tính f(4):
deque-yeulaptrinh.pw
Để tìm l,r nhanh, ta dùng kĩ thuật sử dụng Deque tìm Min/Max trên đoạn tịnh tiến.

Code:

uses    math;
const   fi='';
        fo='';
        maxn=1000;
var     a:array[1..maxn,1..maxn] of byte;
        i,j,m,n,res,top:longint;
        h,s,left,right:array[1..maxn] of integer;
procedure nhap;
begin
    assign(input,fi);reset(input);
    readln(m,n);
    for i:=1 to m do
        for j:=1 to n do read(a[i,j]);
    close(input);
end;
procedure push(x:integer);
begin
    inc(top);
    s[top]:=x;
end;
function get:integer;
begin
    exit(s[top]);
end;
procedure pop;
begin
    dec(top);
end;
procedure xuly;
begin
    for i:=1 to m do
     begin
        for j:=1 to n do
           if a[i,j]=1 then
                begin
                    h[j]:=h[j]+1;
                end else h[j]:=0;
        top:=0;
        for j:=1 to n do
            begin
                while (top<>0) and (h[j]<=h[get]) do pop;
                if top=0 then left[j]:=0 else left[j]:=get;
                push(j);
            end;
        top:=0;
        for j:=n downto 1 do
                begin
                    while (top<>0) and (h[j]<=h[get]) do pop;
                    if top=0 then right[j]:=n+1 else right[j]:=get;
                    push(j);
                end;
        for j:=1 to n do
                begin
                    res:=max(res,h[j]*(right[j]-left[j]-1));
                end;
     end;
end;
procedure inkq;
begin
    assign(output,fo);rewrite(output);
    writeln(res);
    close(output);
end;
begin
    nhap;
    xuly;
    inkq;
end.

[Discrete Mathematics] Relations

1. Introduction

a. Definition

  • Let $A$ and $B$ be sets. A binary relation from $A$ to $B$ is a subset of A x B.$$ R \subseteq A × B $$$$ aRb : (a,b) \in R $$
  • relation on a set A is a relation from A to A.

b. Properties of relations

  • A relation $R$ on a set $A$ is called reflexive if $ (a, a) \in R, \forall a \in A $
  • A relation $R$ on a set $A$ is called symmetric if $ (a, b) \in R \Rightarrow (b,a) \in R, \forall a, b \in A $
  • A relation $R$ on a set $A$ is called antisymetric” if $ aRb \land bRa \Rightarrow a=b, \forall a,b \in A $
  • A relation $R$ on a set $A$ is called transitive if $ aRb \land bRc \Rightarrow aRc, \forall a,b,c \in A $

References

  • Discrete Mathematics and Its Applications 7th Edition, Kenneth H. Rosen
  • Đại số tuyến tính, Nguyễn Hữu Việt Hưng