[Stack]Captcha - Simple Project

Bài toán này nằm trong loạt bài giới thiệu các kiểu dữ liệu - Data Structure

Captcha được phát minh ra nhằm mục đích bảo vệ các trang web và hệ thống khỏi các hành vi phá hoại của các chương trình giả dạng con người (nhằm các mục đích xấu) hay gọi là bot hoặc spam bots. Captcha là chương trình phép thử tự động được tạo ra với mục đích hầu hết mọi người có thể vượt qua trong khi các chương trình máy tính hiện đại không thể vượt qua, đảm bảo robot không thể liên tục truy cập vào server từ một địa chỉ. Captcha là một mã hình ảnh đã được xử lý để robot rất khó đọc được. Tuy nhiên Captcha nảy sinh ra một vấn đề, đó là tốn thời gian của người dùng một cách vô nghĩa . Một vài ông kỹ sư đầu to ở Mỹ đã nghĩ ra một cách rất thông minh giải quyết vấn đề này. Họ dùng mã Captcha cấu tạo gồm 2 phần, phần 1 hệ thống đã biết mã thật (nó hiển thị gì) và phần 2 chưa biết. Người ta sẽ thống kê các kết quả người dùng gõ mã mà đúng phần 1, và được 1 bảng dữ liệu cho phần mã 2. Dữ liệu này được dùng để xác định chính xác đoạn mã 2 viết gì. Nó được sử dụng để số hóa các văn bản mà các hệ thống bot khác không làm được (như dự án số hóa toàn bộ sách của Google cần cái này), giúp tiết kiệm bộ nhớ(lưu text thì đỡ tốn bộ nhớ hơn ảnh), nhận diện chữ viết, huấn luyện robot..vv... Và mã capcha sau khi dc giải mã có thể lại được dùng làm mã capcha thật (đoạn mã 1 ở trên), vào chắc chắn robot ko thể phá được. Sau khi thu thập được dữ liệu gõ capcha của người dùng, mã đúng của nó là kết quả mà trên 75% người dùng gõ. Đó là bài toán thực tế, nhưng hoạt động của nó không hề đơn giản, ở đây mình chỉ đưa ra 1 bài toán rất đơn giản, khi dữ liệu đã được thu thập và sắp xếp. Trong một bài khác, chúng ta sẽ làm việc với dữ liệu thực tế hơn.

Sử dụng Captcha để nhận diện chữ viết, dùng cho các ứng dụng khác

1. USING

Stack

2. QUESTION

Giả sử dữ liệu đã được thu thập và lưu trữ cho từng mã Captcha một, bài toán ở đây rất đơn giản, tìm và in ra đoạn mã được người dùng điền nhiều nhất và tỉ lệ phần trăm (định dạng %.0f) của mã đó trong toàn bộ dữ liệu được lưu.

3. INPUT & OUTPUT :

Giới hạn :
Số Testcase NT không quá 50
Lượng dữ liệu N trong 1 testcase không quá 10000
Độ dài 1 mã không quá 45

INPUT :
1 //- Dòng đầu tiên NT chỉ số lượng testcase
10 //- Dòng đầu tiên mỗi testcase chứa lượng dữ liệu N
aab //- 10 dòng tiếp chứa 10 mã
abb
aab
abd
aaa
aba
aab
abb
add
aab
OUTPUT :
TestCase #1 aab 40 // Mã xuất hiện nhiều nhất với 40%

Download File Testcase

Download File Answer

4. SAMPLE CODE:

#include <stdio.h>
#include <iostream>
#include <fstream>
#include <stdlib.h>

using namespace std;

#define MAX 45

int N = 0;
char Answer[MAX];
char input[10001][MAX];
int Count[10001];
int endStack;
void ResetStack(){
    endStack = 0;
    int i;
    for (i = 0; i < N; i++){
        Count[i] = 0;
    }
}
int InStack(char temp[MAX]){
    int i;
    for (i = 0; i < endStack; i++){
        if (strcmp(temp, input[i]) == 0)return i;
    }
    return -1;
}
void Push(char temp[MAX]){
    strcpy(input[endStack], temp);
    Count[endStack]++;
    endStack++;
}
void main(){
    freopen("input.txt", "r", stdin);
    int testcase, NT;
    scanf("%d", &NT);
    for (testcase = 1; testcase <= NT; testcase++){
        scanf("%d", &N);
        int i = 0;
        ResetStack();
        for (i = 0; i < N; i++){
            char temp[MAX];
            scanf("%s", temp);
            int dirInStack = InStack(temp);
            if (dirInStack >= 0)Count[dirInStack]++;
            else Push(temp);
        }
        int max = 0;
        for (i = 0; i < N; i++){
            if (Count[i]>max){
                max = Count[i];
                strcpy(Answer, input[i]);
            }
        }
        printf("Testcase #%d %s %.0f\n", testcase, Answer, ((float)max / N * 100));
    }
}