P145PROC - ROUND 5C - Modulo

Link Sub: http://www.spoj.com/PTIT/problems/P145PROC/
Người Gửi: Dương Lee

• Problem:

Cho 2 số nguyên A và B, A modulo B là phần dư của A khi chia cho B. Ví dụ, 7, 14, 27 và 38 lần lượt là 1, 2 , 0 và 2 theo modulo 3.  
Cho trước một dãy số có 10 phần tử. Bạn hãy viết chương trình tính số lượng số giá trị khác nhau trong dãy sau khi lấy modulo 42.

Input

Gồm 10 số nguyên không âm <= 1000.

Output

Ghi ra một số nguyên duy nhất là số lượng giá trị có trong dãy số sau khi lấy MOD 42.

Example:

Input

1
2
3
4
5
6
7
8
9
10

Output:

10

Input

42
84
252
420
840
126
42
84
420
126

Output:

1

Input

39
40
41
42
43
44
82
83
84
85

Output:

6

• Solution:

Cách đơn giản nhất để làm bài này đó là sử dụng mảng đánh dấu.
Nhận thấy rằng khi chia lấy dư cho 42 các giá trị chỉ nhận nguyên ở trong đoạn [0, 41]. Vậy nên ta tạo mảng dd[42]={0} (có ít nhất 42 phần tử đều bằng 0), mỗi lần tính toán ta đánh dấu dd[A%42]=1. Sau đó ta chỉ việc đếm xem trong mảng dd [0, 41] có bao nhiêu số đã được đánh dấu.
VD đối với 5 số:
1
1
3
3
42
-> dd[0]=1, dd[1]=1, dd[2]=0, dd[3]=1, dd[4]=0, dd[5] =0,...

• Code:

C:

https://ideone.com/LUbcJe

#include <stdio.h>

int main ()
{
    int dd[43]={0};
    int A;
    for (int i=1; i<=10; i++)
    {
        scanf("%d", &A);
        dd[A%42]=1;
    }
    int dem = 0;
    for (int i=0; i<42; i++)
    {
        if (dd[i]==1)
            dem++;
    }
    printf ("%d", dem);
    return 0;
}

C++:

...

JAVA:

...

Python:

...

P166SUMA - ROUND 6A - Captain Boomerang

Link Sub: http://www.spoj.com/PTIT/problems/P166SUMA/
Người Gửi: Dương Lee

• Problem:

Captain Boomerang là người có khả năng rất đặc biệt. Như biệt danh của mình, anh là master trong việc sử dụng những chiếc boomerang. Ngoài ra, Captain Boomerang còn có sở thích rất kỳ lạ đó là thích chơi với các dãy hoán vị. Trong lúc rảnh rỗi, anh có nghĩ ra bài toán này và đem đi đố mọi người trong team.
Cho 1 dãy gồm n phần tử: a1, a2, …, an (1 <= ai <= 5000). Nhiệm vụ là phải chuyển dãy trên về 1 dãy hoán vị n phần tử, biết trong 1 bước, chỉ được thay đổi giá trị của 1 phần tử. Hỏi xem cần tối thiếu bao nhiêu bước để hoàn thành nhiệm vụ.
Biết rằng 1 dãy hoán vị n phần tử là hoán vị bất kỳ của dãy số 1, 2, 3, …, n
Do không ai trong team có sở thích kỳ lạ này nên cũng chẳng ai muốn làm, các bạn hãy giải đáp bài toán này của Captain Boomerang nhé.

Input

Dòng đầu tiên nhập 1 nguyên số n (1 <= n <= 5000).

Dòng tiếp theo nhập dãy gồm n số a1, a2, …, an (1 <= ai <= 5000).

Output

In ra kết quả bài toán – số bước ít nhất cần thực hiện.

Example:

Input

5
4 5 4 4 1

Output:

2

Input

2
1 1

Output:

1

• Solution:

Số các số còn thiếu = số bước cần thay đổi.
Sử dụng mảng đánh dấu để đếm các số còn thiếu

• Code:

C++:

https://ideone.com/2Osuid

#include <iostream>
using namespace std;

int main ()
{
    int n;
    cin>>n;
    int arr[5003] = {0};
    int a;
    for (int i=0; i<n; i++)
    {
        cin>>a;
        arr[a] = 1;
    }
    int count = 0;
    for (int i=1; i<=n; i++)
        if (arr[i]==0)
            count++;
    cout<<count;
    return 0;
}

JAVA:

...

Python:

...

P151PROG - ROUND 1G - Xếp hàng

Link Sub: http://www.spoj.com/PTIT/problems/P151PROG/
Người Gửi: Dương Lee

• Problem:

Trong giờ ăn trưa tại Học viên Công nghệ Bưu chính Viễn thông, có n sinh viên đang xếp hang để lấy đồ.  
Cảm thấy chán vì phải đứng đợi một mình, vì vậy mỗi sinh viên viết ra mã sinh viên của mình đứng ngay trước và ngay sau của mình. Nếu không có ai đứng trước hoặc không có ai đứng sau thì viết ra 0.  
Đột nhiên, xe chở nước sôi đi qua, tất cả sinh viên phải tránh. Khi họ trở lại, họ không nhớ vị trí của mình mà chỉ nhớ mã sinh viên của người đừn trước và người đứng sau.  
Hãy giúp các sinh viên PTIT tìm lại vị trí của mình!!!!
Input

Dòng đầu tiên gồm số tự nhiên n (2 ≤ n ≤ 2·10^5) – số lượng sinh viên.

n dòng tiếp theo, dòng thứ i gồm cặp số tự nhiên ai, bi (0 ≤ ai, bi ≤ 10^6), với ai là mã sinh viên của người đứng trước, bi là mã sinh viên của người đứng sau 1 sinh viên nào đó. Nếu không có ai đứng trước hoặc không có ai đứng sau nhập 0.

Mã sinh viên của mỗi sinh viên là khác nhau. 

Output
Trên 1 dòng, in ra n số  x1, x2, ..., xn  , danh sách của các sinh viên theo thứ tự ban đầu.

Example:

Input

4
92 31
0 7
31 0
7 141

Output:

92 7 31 141

• Solution:

Bài này sẽ có hai trường hợp chính: - n lẻ, dãy VD: 7 8 6 biểu diễn input là: 0 8 7 6 8 0 -> Sử dụng mảng đánh dấu ta lưu lại được 2 dãy liên kết: + arr[0] = 8, arr[8] = 0 -> truy vết thu được: D1: 8 (0 không tính vào dãy) + arr[6] = 7, arr[7] = -1 -> truy vết thu được: D2: 6 7 (Ở đây tìm được 6 là số cuỗi dãy 2 vì sau 6 không còn số nào liên kết với nó) -> In D2 và D1 xen kẽ: 7 8 6 (D1 in thuận, D2 in ngược). - n chẵn, dãy VD: 7 8 6 1 biểu diễn input là: 0 8 7 6 8 1 6 0 -> Sử dụng mảng đánh dấu ta lưu lại được 2 dãy liên kết: + arr[0] = 8, arr[8] = 1, arr[1]=-1 (=-1 là khởi tạo để kết thúc kết nối) -> truy vết thu được: D1: 8 1 + arr[0] = 6, arr[6] = 7, arr[7]=-1 (=-1 là khởi tạo để kết thúc kết nối) -> truy vết thu được: D2: 6 7 -> In D2 và D1 xen kẽ: 7 8 6 1 (D1 in thuận, D2 in ngược).

• Code:

C++:

https://ideone.com/HVFFEX

#include <iostream>
#include <vector>
using namespace std;

int SV_sau[1000006];
int SV_truoc[1000006];
void init ()
{
    for (int i=0; i<=1000000; i++)
    {
        SV_sau[i]=-1;
        SV_truoc[i]=-1;
    }
}

vector <int> so;
int dd[1000006] = {0};
void check (int x)
{
    if (dd[x]==0 && x!=0)
    {
        so.push_back(x);
        dd[x]=1;
    }
}

int main ()
{
    init ();
    int n;
    cin>>n;
    int vt1, vt2;
    for (int i=1; i<=n; i++)
    {
        int a, b;
        cin>>a>>b;
        check (a); check (b);
        SV_sau[a] = b;
        SV_truoc[b] = a;
    }
    vector <int> D1;
    vector <int> D2;
    if (n%2==0)
    {
    //Day 1
        int st = 0;
        while (1)
        {
            if (SV_sau[st]==-1) break;
            D1.push_back(SV_sau[st]);
            st = SV_sau[st];
        }
        // Day 2
        st = 0;
        while (1)
        {
            if (SV_truoc[st]==-1) break;
            D2.push_back(SV_truoc[st]);
            st = SV_truoc[st];
        }
        //IN
        int D_1 = 0, D_2 = D2.size()-1;
        for (int i=1; i<=n; i++)
        {
            if (i%2!=0)
            {
                cout<<D2[D_2]<<" ";
                D_2--;
            }
            else
            {
                cout<<D1[D_1]<<" ";
                D_1++;
            }
        }
    }
    else
    {
        //Day 1
        int st = 0;
        while (1)
        {
            if (SV_sau[st]==0) break;
            D1.push_back(SV_sau[st]);
            st = SV_sau[st];
        }
        st=0;
        for (int i=0; i<so.size(); i++)
        {
            if (SV_sau[so[i]]==-1)
            {
                st=so[i];
                break;
            }
        }
        if (st!=0) D2.push_back(st);
        while (1)
        {
            if (SV_truoc[st]==-1) break;
            D2.push_back(SV_truoc[st]);
            st = SV_truoc[st];
        }
        int D_1 = 0, D_2 = D2.size()-1;
        for (int i=1; i<=n; i++)
        {
            if (i%2!=0)
            {
                cout<<D2[D_2]<<" ";
                D_2--;
            }
            else
            {
                cout<<D1[D_1]<<" ";
                D_1++;
            }
        }
    }
    return 0;
}

JAVA:

PTIT017A - ACM PTIT 2017 A - ƯỚC SỐ NGUYÊN TỐ

Link Sub: http://www.spoj.com/PTIT/problems/PTIT017A/
Người Gửi: Sai

• Problem:

Cho các số nguyên A, B, K. Nhiệm vụ của bạn là hãy đếm xem trong đoạn [A, B] có bao nhiêu số có đúng K ước số nguyên tố.  
Ví dụ số 12 có 2 ước số nguyên tố (2 và 3), số 550 có 3 ước số nguyên tố (2, 5, và 11), trong khi số 17 chỉ có 1 ước số nguyên tố duy nhất là chính nó.
Input
Dòng đầu tiên là số lượng bộ test T (T ≤ 100).
Mỗi test gồm 3 số nguyên A, B, K (2 ≤ A, B ≤ 107, 1 ≤ K ≤ 109)

Output
Với mỗi test in ra chữ “Case” kèm theo số thứ tự bộ test và đáp án tìm được (theo mẫu như trong ví dụ).

Example:

Input

5
5 15 2
2 10 1
24 42 3
1000000 1000000 1
1000000 1000000 2

Output:

Case #1: 5
Case #2: 7
Case #3: 2
Case #4: 0
Case #5: 1

• Solution:

Chú Ý: Code dưới đây sub bằng C++6.3: time limit, C++4.3.2: 0.65s ??? Ý tưởng: - Sàng nguyên tố trong khoảng từ 1->10^7. (arr[]) - Mỗi nguyên tố xét duyệt các bội của nó. Bội của các số nguyên tố sẽ có ước là số nguyên tố đó -> dùng mảng đánh dấu (arr2[]) ghi nhận lại số ước số nguyên tố của số đó. VD: 1->5 -> (arr[1]=0, arr[2]=1, arr[3]=1, arr[4]=0, arr[5]=1); -> v[]={2, 3, 5} là các số nguyên tố. với v[0]=2 -> arr2[2]= 1, arr2[3]= 0, arr2[4]= 1, arr2[5]= 0; với v[1]=3 -> arr2[2]= 1, arr2[3]= 1, arr2[4]= 1, arr2[5]= 0; với v[3]=5 -> arr2[2]= 1, arr2[3]= 1, arr2[4]= 1, arr2[5]= 1; -> Vậy arr2[i] tương đương với số ước nguyên tố của i;

• Code:

C++:

https://ideone.com/HyEtOE

#include <iostream>
#include <math.h>
#include <stdio.h>
#include <vector>
#define MAX 10000000
using namespace std;


long arr[10000007];
long arr2[10000007];
void init ()
{
    for (long i=1; i<=MAX; i++)
    {
        arr[i]=1;
        arr2[i]=0;
    }
    arr[1]=0;
}

void sangNT ()
{
    for (long i=2; i<=sqrt(MAX); i++)
    {
        if (arr[i]==1)
        {
            for (long j=2; j<=MAX/i; j++)
            { 
                arr[j*i]=0;
            }
        }
    }
}

int main ()
{
    init ();
    sangNT ();
    vector <long> v;
    for (long i=1; i<=MAX; i++)
    {
        if (arr[i]==1) v.push_back(i);
    }
    for (long i=0; i<v.size(); i++)
    {
        for (long j=1; j<=MAX/v[i]; j++)
        {
            arr2[v[i]*j]++;
        }
    }
    int t;
    cin>>t;
    for (int k=1; k<=t; k++)
    {
        long A, B, K, count=0;
        cin>>A>>B>>K;
        for (long i=A; i<=B; i++)
        {
            if (arr2[i]==K) count++;
        }
        printf ("Case #%d: %ld\n", k, count);
    }
    
    return 0;
}

JAVA:

BCPP - Số phong phú

Link Sub: http://www.spoj.com/PTIT/problems/BCPP/
Người Gửi: Sai

• Problem:

Trong số học, số phong phú là các số mà tổng các ước số của số đó (không kể chính nó) lớn hơn số đó.   
Ví dụ, số 12 có tổng các ước số (không kể 12) là 1 + 2 + 3 + 4 + 6 = 16 > 12. Do đó 12 là một số phong phú.  
Bạn hãy lập trình đếm xem có bao nhiêu số phong phú trong đoạn [L,R].
Input
Gồm 2 số L, R (1 <= L <= R <= 106)
Có 50% số test có 1 <= L <= R <= 103

Output
Gồm 1 số nguyên duy nhất là số số phong phú trong đoạn [L, R].

Example:

Input

1 50

Output:

9

• Solution:

Từ 1 đến 50 có 9 số phong phú là: 12, 18, 20, 24, 30, 36, 40, 42, 48
Với cách duyệt trâu độ phức tạp lên tới O(10^9). -> Vậy nên cần một cách cải tiến của cách tìm ước số. - Cách làm: + Tư tưởng là sẽ làm theo cách sàng nguyên tố Eratosthenes. VD: khởi tạo từ 1->10^6; Với 1 ta có [10^6/1] số >= 1 và <= 10^6: Cộng 1 vào các số là bội của 1 (arr[1]=1, arr[2]=1, arr[3]=1, ... arr[6]=1,...); Với 2 ta có [10^6/2] số >= 2 và <= 10^6: Cộng 2 vào các số là bội của 2 (arr[1]=1, arr[2]=3, arr[3]=1, ... arr[6]=3,...); ... Cứ như vậy cho hết 10^6 ta sẽ thu được tổng các ước của của các số i:1->10^6 trong đó SUMDIV_i = arr[i]. Với độ phức tạp chỉ còn khoảng O (10^7). Vẫn tạm nhanh ^^. + Cuối cùng chỉ cần đếm số phong phú trong đoạn L, R thôi...

• Code:

C++:

JAVA:

PTIT124E - Họp mặt

Link Sub: http://www.spoj.com/PTIT/problems/PTIT124E/

Người Gửi: Sai

• Problem:

Có K người (1 ≤ K ≤ 100) đứng tại vị trí nào đó trong N địa điểm cho trước (1 ≤ N ≤ 1,000) được đánh số từ 1..N. Các điểm được nối với nhau bởi M đoạn đường một chiều (1 ≤ M ≤ 10,000) (không có đoạn đường nào nối một điểm với chính nó).  

Mọi người muốn cùng tụ họp tại một địa điểm nào đó. Tuy nhiên, với các đường đi cho trước, chỉ có một số địa điểm nào đó có thể được chọn là điểm họp mặt. Cho trước K, N, M và vị trí ban đầu của K người cùng với M đường đi một chiều, hãy xác định xem có bao nhiêu điểm có thể được chọn làm điểm họp mặt.

Input

Dòng 1: Ghi 3 số: K, N, và M  Dòng 2 đến K+1: dòng i+1 chứa một số nguyên trong khoảng (1..N) cho biết địa điểm mà người thứ i đang đứng.  

Dòng K+2 đến M+K+1: Mỗi dòng ghi một cặp số A và B mô tả một đoạn đường đi một chiều từ A đến B (cả hai trong khoảng 1..N và A != B).

Output

Số địa điểm có thể được chọn là điểm họp mặt.

Example:

Input

2 4 4
2
3
1 2
1 4
2 3
3 4

Output:

2

• Solution:

Giải thích test ví dụ: có thể họp mặt tại điểm 3 và điểm 4.

Cách làm chính: "loang". - Với mỗi người sẽ loang toàn bộ các điểm mà nó có thể đến được (tư tưởng theo DFS) bằng đệ quy - Đồng thời với mỗi điểm sẽ đếm xem có bao nhiêu người duyệt qua nó. - Kiểm tra lại các điểm: Với mỗi điểm nếu đếm = K lần duyệt thì đỉnh đó có thể họp mặt đủ K người. (*Chú ý: Sử dụng danh sách kề để giảm độ phức tạp xuống còn O(max(N,M)));

• Code:

C++:

JAVA:

P142SUMG - ROUND 2G - Mã hóa

Link Sub: http://www.spoj.com/PTIT/problems/P142SUMG/
Người Gửi: Sai

• Problem:

Mã hóa là một bước quan trọng trong việc truyền thông tin. Một trong những thuật toán đơn giản đó là dịch vòng tất cả các kí tự của từ mã (nội dung cần mã hóa) sang phải d kí tự. Chẳng hạn với d = 5, kí tự ‘A’ được mã hóa bằng ‘F’, ‘B’ bằng ‘G’, ..., ‘Z’ bằng ‘E’.  
Với một nội dung đã được mã hóa, để giải mã, người ta sẽ tìm khoảng cách dịch d và sau đó dịch ngược lại nội dung sang trái d kí tự. Khoảng cách d này được tính bằng số bước dịch sang phải từ chữ cái 'E' đến chữ cái được sử dụng nhiều nhất trong nội dung đã được mã hóa.  
Cho biết nội dung sau khi được mã hóa, các bạn hãy khôi phục lại từ mã ban đầu?
Input
Dòng đầu tiên là số lượng bộ test T (T <= 100).  
Mỗi bộ test là một nội dung đã được mã hóa, gồm nhiều chuỗi các chữ cái in hoa nằm trên một dòng (<= 1000 kí tự).

Output
Với mỗi test, in ra khoảng cách d và nội dung từ mã ban đầu. Nếu không giải mã được vì có nhiều giá trị d, in ra “NOT POSSIBLE”.

Example:

Input

3
RD TQIJW GWTYMJWX INFWD JSYWNJX ZXJ F XNRUQJ JSHWDUYNTS YJHMSNVZJ
THE QUICK BROWN FOX JUMPS OVER THE LAZY DOG
XVIDRE TFCCVXZRKV GIFXIRDDZEX TFEKVJK

Output:

5 MY OLDER BROTHERS DIARY ENTRIES USE A SIMPLE ENCRYPTION TECHNIQUE
10 JXU GKYSA RHEMD VEN ZKCFI ELUH JXU BQPO TEW
NOT POSSIBLE

• Solution:

- Các bước làm: + Nhập vào một xâu có dấu cách. + Đếm kí tự xuất hiện nhiều nhất bằng cách dùng mảng đánh dấu. (Nếu nhiều kí tự có cùng max thì in NOT POSSIBLE). + Tìm khoảng dịch d. (*Chú ý đây là dịch phải: VD: E->B thì phải dịch: E->Z->A->B); + Dịch các kí tự với khoảng d. (*Dịch phải là mã hóa còn dịch trái là đọc xâu).

• Code:

C++:

JAVA:

GOODFRIE - Good friends

Link Sub: http://www.spoj.com/PTIT/problems/GOODFRIE/
Người Gửi: Dương Lee

• Problem:

Trong một lớp học, cô giáo xếp hạng N học sinh theo thứ tự điểm số từ cao xuống thấp. Hai học sinh sẽ là bạn nếu thứ tự của họ là gần nhau, tức là khác biệt giữa thứ tự không quá K. Ví dụ: nếu K = 1, thì chỉ có 2 học sinh ở trước và sau danh sách là bạn của 1 học sinh. Thêm nữa, hai học sinh gọi là bạn tốt nếu họ là bạn và tên của họ có cùng độ dài.  
Viết chương trình tính số các cặp bạn tốt trong lớp.
Input
Dòng đầu chứ N (3<=N<=300 000) và K (1<= K <=N).  
N dòng tiếp theo, mỗi dòng chứa tên một học sinh theo danh sách xếp hạng (từ 2 đến 20 chữ cái tiếng Anh in hoa).

Output
Số cặp bạn tốt.

Example:

Input

4 2
IVA
IVO
ANA
TOM

Output:

5

Input

6 3
CYNTHIA
LLOYD
STEVIE
KEVIN
MALCOLM
DABNEY

Output:

2

• Solution:

Quy hoạch mảng arr có dạng: tất cả độ dài của xâu_i có arr[i] = tất cả độ dài của xâu_(i-1) arr[i-1] + 1 (của độ dài xâu_i). VD: 3 IV IVO AN -> arr[0] = {at[0]=0, at[1]=0, at[2]=0,...}; arr[1] = arr[0] + arr[0]{at[2]++} = {at[0]=0, arr[1]=0, arr[2]=1, arr[3]=0,...}; arr[2] = arr[1] + arr[1]{at[3]++} = {at[0]=0, arr[1]=0, arr[2]=1, arr[3]=1,...}; arr[3] = arr[2] + arr[2]{at[2]++} = {at[0]=0, arr[1]=0, arr[2]=2, arr[3]=1,...}; -> Như vậy: arr[i].at[j] lưu lại số lượng xâu có độ dài là j từ xâu: 1->i; -> Tại mỗi xâu ta có thể xác định số cặp có thể ghép được với xâu đó bằng phép tính: (arr[i].at[len] - arr[i-k-1].at[len] - 1);

• Code:

C++:

JAVA:

PTIT127E - Điểm chung

Link Sub: http://www.spoj.com/PTIT/problems/PTIT127E/
Người Gửi: Sai

• Problem:

Trong một lớp có N bàn, mỗi bàn có 2 học sinh. Trong giờ trả bài kiểm tra, mỗi học sinh đều nhận được số điểm kiểm tra của mình. Một đoạn bàn liên tiếp có điểm chung là K, nếu như mỗi bàn trong đoạn bàn đó đều có ít nhất một học sinh có điểm K. Bạn hãy xác định xem đoạn bàn liên tiếp nào có điểm chung với khoảng cách dài nhất.
Input
-       Dòng 1: Số N (1 ≤ N ≤ 100 000).  – là số bàn trong lớp.  
-       Dòng 2..N+1: Dòng i+1 chứa 2 số nguyên A_i và B_i là điểm kiểm tra của bàn thứ i. (1 ≤ A_i, B_i ≤ 5)

Output
Một dòng chứa 2 số nguyên cách nhau bởi dấu cách: độ dài của đoạn bàn có điểm chung dài nhất và điểm chung K của đoạn bàn đó. Nếu có nhiều đoạn bàn có độ dài dài nhất như nhau, in ra điểm chung K thấp nhất.

Example:

Input

1
1 5

Output:

1 1

Input

3
3 5
4 5
1 3

Output:

2 5

Input

4
2 1
3 2
5 3
2 5

Output:

2 2

• Solution:

- Với mỗi số điểm nhập vào sẽ xét thêm các số điểm trước nó. (trừ trường hợp bàn 1). - Để lưu lại số điểm trước đó ta sẽ dùng mảng đánh dấu lưu lại điểm tại mỗi lần nhập vào. VD: Bàn 1: 4 5 -> table[1]: có arrA[4]=1, arrB[5]=1; Bàn 2: 5 6 -> table[2]: có arrA[5]=1+arrB[5]=2, arrB[6]=1; .... Cứ như vậy thì mỗi lần ta sẽ có tính được dãy các bàn liên tiếp có cùng điểm. (Chú ý: vì dãy dài nhất không phụ thuộc vào người 1 có cùng điểm hay người 2 cùng điểm hay thậm chí cả hai cùng điểm vẫn được nên khi xét và cộng thêm số lượng dãy sau thì chỉ cần xét một trường hợp đúng là đủ)

• Code:

C++:

https://ideone.com/h3rXZy

#include <iostream>
using namespace std;

int n;
struct data
{
    int arrA [10];
    int arrB [10];
} typedef data;
data table [100005];

void init ()
{
    for (int i=1; i<=n; i++)
    {
        for (int j=1; j<=5; j++)
        {
            table[i].arrA[j]=0;
            table[i].arrB[j]=0;
        }
    }
}

int main ()
{
    cin>>n;
    init ();
    int lenMax=0;
    int pointMin=10;
    for (int i=1; i<=n; i++)
    {
        int A, B;
        cin>>A>>B;
        if (i==1)
        {
            table[i].arrA[A]++;
            table[i].arrB[B]++;
            if (table[i].arrA[A]>lenMax)
            {
                lenMax=table[i].arrA[A];
                pointMin=A;
            }
            else if (table[i].arrA[A]==lenMax)
            {
                if (A<pointMin)
                pointMin=A;
            }
            if (table[i].arrB[B]>lenMax)
            {
                lenMax=table[i].arrB[B];
                pointMin=B;
            }
            else if (table[i].arrB[B]==lenMax)
            {
                if (A<pointMin)
                pointMin=B;
            }
        }
        else
        {
            table[i].arrA[A]++;
            if (table[i-1].arrA[A]!=0) table[i].arrA[A]+=table[i-1].arrA[A];
            else if (table[i-1].arrB[A]!=0) table[i].arrA[A]+=table[i-1].arrB[A];
            
            table[i].arrB[B]++;
            if (table[i-1].arrA[B]!=0) table[i].arrB[B]+=table[i-1].arrA[B];
            else if (table[i-1].arrB[B]!=0) table[i].arrB[B]+=table[i-1].arrB[B];
            
            if (table[i].arrA[A]>lenMax)
            {
                lenMax=table[i].arrA[A];
                pointMin=A;
            }
            else if (table[i].arrA[A]==lenMax)
            {
                if (A<pointMin)
                pointMin=A;
            }
            if (table[i].arrB[B]>lenMax)
            {
                lenMax=table[i].arrB[B];
                pointMin=B;
            }
            else if (table[i].arrB[B]==lenMax)
            {
                if (A<pointMin)
                pointMin=B;
            }
        }
    }
    cout<<lenMax<<" "<<pointMin;
    return 0;
}

JAVA:

PTIT015A - ACM PTIT 2015 A - Ghép số

Link Sub: http://www.spoj.com/PTIT/problems/PTIT015A/
Người Gửi: Dương Lee

• Problem:

Cho ba số nguyên dương a,b,c không quá 100 chữ số. Người ta muốn tạo ra một số lớn nhất có thể khi ghép các chữ số của các số này lại với nhau. Quy tắc ghép là vẫn đảm bảo số lượng chữ số như ban đầu nhưng có thể hoán đổi vị trí của chúng  
Hãy tìm cách ghép để nhận được số lớn nhất.
Input
Dữ liệu vào gồm nhiều bộ dữ liệu tương ứng với nhiều test. Dòng đầu tiên chứa số nguyên K (K≤100), là số bộ dữ liệu. Tiếp theo là K dòng, mỗi dòng là một bộ dữ liệu ghi ba số nguyên dương  (các số không vượt quá 100 chữ số).

Output
Với mỗi bộ dữ liệu ghi ra trên một dòng, mỗi dòng ghi ra một số nguyên là số lớn nhất ghép được.

Example:

Input

2
1 2 3
82 8 1

Output:

321
8821

• Solution:

- Áp dụng mảng đánh dấu: + Đọc vào mỗi xâu. Đọc từng kí tự và chuyển nó về dạng số (dựa vào bảng mã: ASCII). + Với mỗi kí tự sẽ tương ứng với phần tử trong mảng (a[]) VD: a[0] là đại diện cho số 0, a[5] là đại diện cho số 5, a[6],... a[4] = 6 -> có 6 số 4 ... Vậy sau khi đếm và đánh dấu chỉ cần in ra các số từ lớn đến bé thôi. VD: 4 99 Sẽ có: a[4]=1, a[9] = 2; -> in ra: 994.

• Code:

C++:

JAVA: