Algorithm: 2016

Sunday, October 30, 2016

Friday, October 28, 2016

Kỹ năng nhân ma trận

Tham khảo: >>Thư viện vnoi

LATGACH4 - SPOJ ||Thuật toán ||Code
SEQ - SPOJ ||Thuật toán ||Code
THBAC - SPOJ ||Thuật toán ||Code
VMATRIX - SPOJ ||Thuật toán ||Code
PK and interesting language-HackerEarth ||Thuật toán ||Code
Long walks from Office to Home Sweet Home-HackerEarth ||Thuật toán ||Code
Tiles - HackerEarth ||Thuật toán ||Code
ABCD Strings - HackerEarth ||Thuật toán ||Code
Mehta and the difficult task - HackerEarth ||Thuật toán ||Code
Mehta and the Evil Strings - HackerEarth ||Thuật toán ||Code
PA06ANT - SPOJ ||Thuật toán ||Code
CONNECTE - SPOJ ||Thuật toán ||Code

Thursday, July 14, 2016

Một số bài toán về cây khung

Tham khảo: >> Một số vấn đề đáng chú ý trong môn tin học - Trang 133

IOIBIN - SPOJ || Thuật toán || Code
NKRACING - SPOJ || Thuật toán || Code
SƠ ĐỒ MẠNG ĐIỆN || Thuật toán || Code
NKCITY - SPOJ || Thuật toán || Code

Tuesday, July 12, 2016

Bài tập tìm kiếm nhị phân và ứng dụng

Tham khảo: >> Một số vấn đề đáng chú ý trong môn tin học - Trang 140

LIS - SPOJ || Thuật toán || Code (Submitted 12-07-2016)
ASSIGN1 - SPOJ || Thuật toán || Code (Submitted 12-07-2016)
YUGI - SPOJ || Thuật toán || Code (Submitted 13-07-2016)
MTWALK - SPOJ || Thuật toán || Code (Submitted 13-07-2016)

Friday, May 27, 2016

Tóm tắt nội dung lý thuyết đại số tuyến tính

Chương 1: Ma trận và hệ phương trình tuyến tính

>> Link download tài liệu chương 1 (Thầy Luyện - ĐH KHTN)

Chương 2: Định thức

>> Link download tài liệu chương 2 (Thầy Luyện - ĐH KHTN)

Chương 3: Không gian vector

>> Link download tài liệu chương 3 (Thầy Luyện - ĐH KHTN)

Chương 4: Ánh xạ tuyến tính

>> Link download tài liệu chương 4 (Thầy Luyện - ĐH KHTN)

Lưu ý: Click hoặc download để xem ảnh rõ hơn
Vẫn còn update...

Bài viết về chủ đề toán

ĐẠI SỐ TUYẾN TÍNH:

>> Tóm tắt nội dung lý thuyết đại số tuyến tính

GIẢI TÍCH B2:

>> Nội dung đang cập nhật

Sunday, May 15, 2016

Bài tập xử lý số nguyên (Số nguyên lớn, hàm mod)

Tham khảo: >> Một số vấn đề đáng chú ý trong môn tin học - Trang 175

XỬ LÝ SỐ NGUYÊN LỚN

HÀM MOD TRONG CÁC BÀI TOÁN TIN HỌC

MYSTERY - SPOJ || Thuật toán || Code (Submitted 11-07-2016)
TREENUM - SPOJ || Thuật toán || Code (Submitted 11-07-2016)
SPACESET - SPOJ || Thuật toán || Code (Submitted 12-07-2016)

Vẫn còn update ...

Friday, May 13, 2016

Các bài tập về heap và ứng dụng

Tham khảo: >> Một số vấn đề đáng chú ý trong môn tin học - Trang 183

Vẫn còn update ....

Saturday, May 7, 2016

Các bài tập về cây IT (interval tree) và BIT (binary index tree)

Tham khảo: >> Một số vấn đề đáng chú ý trong môn tin học - Trang 191

INTERVAL TREE

NKLINEUP - SPOJ || Thuật toán || Code (Submitted 08-05-2016)
QMAX - SPOJ || Thuật toán || Code (Submitted 08-05-2016)
QMAX2 - SPOJ || Thuật toán || Code (Submitted 09-05-2016)
LITES - SPOJ || Thuật toán || Code (Submitted 09-05-2016)
MARBLE - SPOJ || Thuật toán || Code (Submitted 15-05-2016)

BINARY INDEX TREE

Lưu ý: Nếu không xem được code thì nhấn Raw để tải về

Vẫn còn update....

Một số trang web luyện thi ACM và HSG tin học

Codeforces: Đây là trang web học lập trình hiệu quả nhất, thu hút rất đông lập trình viên tham gia. Trang này thường xuyên tổ chức các kì thi online chia ra làm 2 cấp độ (div1 và div2), hầu hết các bài toán đều có lời giải chi tiết (tutorial) và cho phép tham khảo code người khác. Ngoài ra trang còn có nhiều tính năng khác rất hay.
Spoj: Là trang web tập hợp nhiều bài toán khó, tuy nhiên không hỗ trợ giải đáp bài tập, các bài tập khá gần và phù hợp để luyện thi HSG
Topcoder: Trang web lập trình rất phổ biến trên thế giới, thường xuyên tổ chức các cuộc thi với phần thưởng khá cao, đề thường chia ra làm 2 cấp độ (div1 và div2). Có hỗ trợ nhiều chức năng tương tự như codeforces.
Codechef: Trang web của Ấn Độ, thường tổ chức các kì thi lớn hàng tháng và hàng năm (có thưởng), hệ thống bài tập nhiều, nhiều câu khó, tuy nhiên phần lớn các câu đều không có phân loại.
Codejam: Trang thi lập trình của google, được tổ chức hàng năm với quy mô lớn.
Hackerearth: Trang web với hệ thống bài tập đa dạng. Đặc biệt còn có trình bày về các thuật toán, kỹ thuật trong lập trình.
Uva: Trang web luyện thi ACM, tổng hợp đề ACM các năm.
Timus: Trang luyện thi ACM, tập hợp nhiều câu rất khó
Hackerrank

Ngoài ra còn có các trang hỗ trợ học lập trình như

VNOI: Diễn đàn olympic tin học Việt Nam
Group VNOI: Group facebook hỗ trợ giải bài tập

Vẫn còn update....

Wednesday, March 23, 2016

Đọc và xử lý file hình ảnh BMP

Tập tin Bitmap Tập tin Bitmap (hay còn gọi là BMP) là một định dạng tập tin dùng để lưu trữ dữ liệu hình ảnh rất phổ biến trên môi trường Windows. Xuất hiện lần đầu tiên trong phiên bản Windows 1.0, định dạng BMP vẫn tồn tại và phát triển cho đến ngày nay.
Sỡ dĩ có thời gian tồn tại lâu như vậy là do tập tin BMP có cấu trúc rất đơn giản, dữ liệu màu của từng điểm ảnh được lưu trực tiếp, không áp dụng giải thuật nén và bảo toàn được chất lượng ảnh sau khi lưu trữ.

Cấu trúc tập tin Bitmap

Code

#include <stdio.h>
#include <stdlib.h>
#define _WIN32_WINNT 0x0500
#include <windows.h>
#include <stdint.h>
const char source[]="E:\\testi.bmp";
const char path[]="E:\\testo.bmp";
#pragma pack(1)

////////////////////////////////////////////////

typedef struct bmp_color
{
    unsigned char R;
    unsigned char G;
    unsigned char B;
} color;
typedef struct bmp_header
{
    char isbmp[2];
    uint32_t sizeof_bmp;
    uint16_t other_1;
    uint16_t other_2;
    uint32_t place_data;
} header;
typedef struct bmp_dib
{
    uint32_t sizeof_dib;
    uint32_t picture_width;
    uint32_t picture_height;
    uint16_t color_layers;
    uint16_t color_deep;
    uint32_t impress_method;
    uint32_t picture_size;
    uint32_t resolution_row;
    uint32_t resolution_column;
    uint32_t colors_used;
    uint32_t main_colors;
    char *thirt_part;
} dib;
typedef struct bmp_data
{
    color **c;
    char padding;
} data;
typedef struct bmp_file
{
    header h;
    dib d;
    data a;
} file;

////////////////////////////////////////////////

file bmp;
color before, after;
FILE *fi=fopen(source,"rb");
FILE *fo=fopen(path,"wb");

////////////////////////////////////////////////

void scan_bmp_file()
{
    if (fi==NULL) return;
    fread(&bmp.h,sizeof(header),1,fi);
    fread(&bmp.d,sizeof(dib),1,fi);
    bmp.a.padding=(4-(bmp.d.picture_size/8)%4)%4;
    bmp.d.thirt_part=new char[bmp.h.place_data-sizeof(header)-sizeof(dib)];
    fread(bmp.d.thirt_part,bmp.h.place_data-sizeof(header)-sizeof(dib),1,fi);
    bmp.a.c = new color*[bmp.d.picture_height];
    for (int i=0; i<bmp.d.picture_height;i++)
    {
        bmp.a.c[i]=new color[bmp.d.picture_width];
        for (int j=0;j<bmp.d.picture_width;j++)
            fread(bmp.a.c[i]+j,sizeof(color),1,fi);
    }
}
void change_bmp_color()
{
    printf("Input color need to chang (RGB): ");
    scanf("%d%d%d",&before.R,&before.G,&before.B);
    printf("Input color to replace (RGB): ");
    scanf("%d%d%d",&after.R,&after.G,&after.B);
    for (int i=0;i<bmp.d.picture_height;i++)
        for (int j=0;j<bmp.d.picture_width;j++)
            if (bmp.a.c[i][j].R==before.R && bmp.a.c[i][j].G==before.G && bmp.a.c[i][j].B==before.B)
            {
                bmp.a.c[i][j].R=after.R;
                bmp.a.c[i][j].G=after.G;
                bmp.a.c[i][j].B=after.B;
            }
}
void print_bmp_console()
{
    HWND console=GetConsoleWindow();
    HDC  hdc=GetDC(console);
    for (int i=bmp.d.picture_height-1;i>=0;i--)
        for (int j=0;j<bmp.d.picture_width;j++)
            SetPixel(hdc,j,bmp.d.picture_height-i-1,RGB(bmp.a.c[i][j].R,bmp.a.c[i][j].G,bmp.a.c[i][j].B));
    ReleaseDC(console, hdc);
}
void print_bmp_file()
{
    if (fo==NULL) return;
    fwrite(&bmp.h,sizeof(header),1,fo);
    fwrite(&bmp.d,sizeof(dib),1,fo);
    fwrite(bmp.d.thirt_part,bmp.h.place_data-sizeof(header)-sizeof(dib),1,fo);
    for (int i=0;i<bmp.d.picture_height;i++)
    {
        for (int j=0;j<bmp.d.picture_width;j++)
            fwrite(bmp.a.c[i]+j,sizeof(color),1,fo);
        for (int j=0;j<bmp.a.padding;j++) fprintf(fo,"0");
    }
}

////////////////////////////////////////////////

int main()
{
    if (fi==NULL || fo==NULL)
    {
        printf("Input error");
        return 0;
    }
    scan_bmp_file();
    change_bmp_color();
    print_bmp_console();
    print_bmp_file();
    fclose(fi);
    fclose(fo);
    return 0;
}

Hình ảnh test:

Vẫn còn update...

Tuesday, March 22, 2016

Thuật toán luồng cực đại trên mạng

Mạng là đồ thị có hướng G = (V, E) trong đó có duy nhất 1 đỉnh A không có cung đi vào và duy nhất 1 đỉnh B không có cung đi ra và mỗi cung của nó có trọng số không âm.

Luồng là phép gán trọng số mỗi cạnh trong mạng bởi 1 số không âm nhỏ hơn trọng số đó và sao cho tổng giá trị nối vào 1 đỉnh bằng tổng giá trị đi ra khỏi đỉnh đó.

Giá trị của 1 luồng là tổng luồng trên các cung đi ra đỉnh phát A ( hoặc thu B).

Luồng cực đại là luồng có giá trị lớn nhất.

Lát cắt, đường tăng luồng, định lý Ford – Fulkerson

Lát cắt (X, Y) là cách phân các tập đỉnh của mạng thành 2 tập X, Y trong đó X chứa đỉnh phát A và Y chứa đỉnh thu B. Khả năng thông qua của lát cắt là tổng trọng số các cạnh (u, v) với u thuộc X và v thuộc Y.

Định lý Ford-Fulkerson: Lát cắt nhỏ nhất (hẹp nhất) chính là giá trị của luồng cực đại.

Thuật toán: với f là một luồng trong mạng G(V, E).

Xây dựng đồ thị tăng luồng Gf(V, Ef):

Nếu f[u, v] < c[u, v] thì thêm (u, v) vào Ef với trọng số c[u, v] – f[u, v] (cung thuận) chỉ khả năng tăng luồng trên cung (u, v).
Nếu f[u, v] > 0 thì thêm cung (v, u) vào Ef với trọng số f[u, v] (cung nghịch) chỉ khả năng giảm luồng trên cung (u, v).

2. Tìm đường đi cơ bản từ A B trên đồ thị Gf. Gọi Delta là giá trị nhỏ nhất trên đường đi và đặt

f[u, v] = f[u, v] + Delta nếu (u, v) nằm trên đường đi và là cung thuận.
f[u, v] = f[u, v] - Delta nếu (u, v) nằm trên đường đi và là cung nghịch.

Khi đó giá trị luồng f tăng Delta so với luồng cũ và đường đi tìm được gọi là đường tăng luồng
Tiến hành thực hiện đường tăng luồng cho đến khi không tăng được nữa. Đồ thị f kết quả chính là luồng cực đại cần tìm.

Vậy các bước cụ thể tìm luồng cực đại trên mạng:

Khởi tạo luồng 0
Tìm đường đi cơ bản từ A B trên đồ thị tăng luồng (đường tăng luồng), cập nhật lại kết quả f và Gf, lặp lại bước này cho đến khi không tìm được nữa.
Xuất kết quả luồng cực đại tìm được.

Code luồng cực đại dùng định lý Ford - Fulkerson:

#include <stdio.h>
#define ma 1002
long long n,m,s,t,a[ma][ma]={0},max_flow=0,trace[ma][2],current[ma][ma]={0};
void scan_input()
{
    long long i,u,v,c;
    scanf("%lld%lld%lld%lld",&n,&m,&s,&t);
    for (i=0;i<m;i++)
    {
        scanf("%lld%lld%lld",&u,&v,&c);
        a[u][v]+=c;
    }
}
long long mi(long long value1, long long value2)
{
    return value1>value2?value2:value1;
}
bool find_path()
{
    long long free[ma],que[ma],i,fron=-1,rear=0;
    for (i=1;i<=n;i++) free[i]=0;
    que[rear]=s;
    trace[s][1]=ma;
    free[s]=1;
    while (fron<rear)
    {
        fron++;
        for (i=1;i<=n;i++)
            if (free[i]==0 && (a[que[fron]][i]>0 || current[i][que[fron]]>0))
            {
                rear++;
                que[rear]=i;
                free[i]=1;
                trace[i][0]=que[fron];
                if (a[que[fron]][i]==0) trace[i][0]=-trace[i][0];
                if (a[que[fron]][i]>0) trace[i][1]=mi(a[que[fron]][i],trace[que[fron]][1]);
                else trace[i][1]=mi(current[i][que[fron]],trace[que[fron]][1]);
                if (i==t) return true;
            }
    }
    return false;
}
void increase_flow()
{
    long long i=t,min_value=trace[i][1];
    while (i!=s)
    {
        if (trace[i][0]>0)
        {
            a[trace[i][0]][i]-=min_value;
            current[trace[i][0]][i]+=min_value;
        }
        else
        {
            a[i][-trace[i][0]]+=min_value;
            current[i][-trace[i][0]]-=min_value;
        }
        i=trace[i][0]>0?trace[i][0]:-trace[i][0];
    }
}
void print_result()
{
    long long i;
    for (i=1;i<=n;i++)
        if (current[s][i]>0) max_flow+=current[s][i];
    printf("%lld",max_flow);
}
int main()
{
    scan_input();
    while (find_path()) increase_flow();
    print_result();
    return 0;
}

Tham khảo: >> Giải thuật và lập trình - Trang 257
                 >> Competitive programming 3 - Trang 163
Bài tập:
1. UVa 00259 - Software Allocation    Code(Submitted 16-06-2017)
2. UVa 00820 - Internet Bandwidth Code(Submitted 17-06-2017)
3. UVa 10092 - The Problem with the ...        Code(Submitted 17-06-2017)
4. UVa 10511 - Councilling    Code(Submitted 27-06-2017)
5. UVa 10779 - Collectors Problem               Code(Submitted 28-06-2017)
6. UVa 11045 - My T-Shirt Suits Me
7. UVa 11167 - Monkeys in the Emei ...
8. UVa 11418 - Clever Naming Patterns
9.   UVa 10330 - Power Transmission
10. UVa 10480 - Sabotage
11. UVa 11380 - Down Went The Titanic
12. UVa 11506 - Angry Programmer
13. UVa 12125 - March of the Penguins

Funny code 1 - Copy file

Code C/C++ thực hiện copy file có định dạng bất kì từ một địa chỉ sang địa chỉ khác

#include <stdio.h>
#include <string.h>
#include <windows.h>
#include <time.h>
const char source[]="E:\\test_inputfile.exe";
const char path[]="D:\\test_outputfile.exe";
#define oneread 10000000
char s[oneread];
long long value=0,cou,current=0,time_begin,i;
int main()
{
    FILE *f=fopen(source,"rb");
    FILE *f1=fopen(path,"wb");
    while ((cou=fread(s,1,oneread,f))!=0) value+=cou;
    fseek(f,0,0L);
    if (f==NULL || f1==NULL)
    {
        if (f==NULL) printf("Source file not found!!");
        if (f1==NULL) printf("Path directory not correct!!");
        return 0;
    }
    system("color 2");
    while ((cou=fread(s,1,oneread,f))!=0)
    {
        time_begin=clock();
        fwrite(s,1,cou,f1);
        current+=cou;
        system("cls");
        printf("Size of file: %.2f MB\n",value/1024.0/1024);
        for (i=1;i<=100*(value-current)/value;i++) printf("|");
        if (100*(value-current)/value==0) printf("\nComplete\n");
        else printf("\nCopying... %I64d%% remain\n",100*(value-current)/value);
        printf("Speed %.2f MB/s",cou/((clock()-time_begin)/1000.0)/1024/1024);
    }
    fclose(f);
    fclose(f1);
    return 0;
}

Algorithm

Bài viết mới