Hướng dẫn giải đề thi UIT Code Contest đợt 15

Bài 1: Đường đi đến trường

Áp dụng quy tắc nhân với n – 1 phần tử ban đầu và quy tắc cộng với phần tử cuối cùng

Lưu ý: sử dụng đúng kiểu dữ liệu long long int để phù hợp với yêu cầu bài toán (10^18).

 

Code Mẫu:

 

#include <iostream>

using namespace std;

int main()

{

int n;

cin >> n;

int* arr = new int[n];

for (int i = 0; i < n; i++)

{

cin >> arr[i];

}

long long int soDuongDi = 0, duong1 = 1, duong2 = arr[n-1];

 

for (int i = 0; i < n – 1; i++)

{

duong1 *= arr[i];

}

soDuongDi = duong1 + duong2;

cout << soDuongDi;

delete []arr;

return 0;

}

 

Bài 2: Trò chơi đảo chuỗi

Bài giải này dùng thuật toán stack thêm lần lượt các dấu ngoặc vào và xuất ngược lần lượt ra là đúng.

 

Code Mẫu:

 

#include <iostream>

#include <string>

using namespace std;

 

struct node1

{

string info;

node1* next;

};

struct Stack

{

node1* pHead; // pTail khong co cung duoc

node1* pTail;

};

void Init(Stack& S)

{

S.pHead =S.pTail = NULL;

}

string getWord(string s, int j, int i)

{

string h;

for (int k = j; k < i; k++)

h += s[k];

return h;

}

node1* Getnode(string s)

{

node1* p = new node1;

if (p != NULL)

{

p->info = s;

p->next = NULL;

}

return p;

}

void addTail(Stack& S, string s)

{

node1* p = Getnode(s);

if (p != NULL)

{

if (S.pTail == NULL) S.pHead = S.pTail = p;

else

{

S.pTail->next = p;

S.pTail = p;

}

}

}

void inputStack(Stack& S, string str)

{

int i = 0, j = 0;

while (i <= str.length())

{

if ((str[i] == ‘ ‘)||(str[i]==’\0′))

{

string s = getWord(str, j, i);

addTail(S, s);

j = i + 1;

}

i++;

}

}

string outputStack(Stack& S)

{

string h;

node1* p = S.pHead;

while (p != NULL)

{

for (int i = p->info.length()-1; i >= 0; i–)

h += p->info[i];

h+=’ ‘;

p = p->next;

}

return h;

}

string reverseWords(string str)

{

Stack S;

Init(S);

inputStack(S, str);

string h=outputStack(S);

return h;

}

 

Bài 3: Hacker

Phương pháp Qui hoạch động + trạng thái:

Hàm mục tiêu:

F[i][j] là số file có thể khôi phục được có độ dài dãy bit là j và 2 bit cuối cùng của dãy có trạng thái là i;

Với: 0: “11”, 1: “01”, 2: “10”, 3: “00”;

Công thức truy hồi:

            F[0][i] = (F[0][i – 2] + F[1][i – 2] + F[2][i – 2] + F[3][i – 2]) % base;

F[1][i] = (F[0][i – 2] + F[2][i – 2]) % base;

F[2][i] = (F[0][i – 2] + F[1][i – 2]) % base;

F[3][i] = F[0][i – 2];

Giải thích: 

  • Trường hợp 0: “11” có thể liền sau với cả 4 trường hợp mà không tạo ra dãy bị cấm.
  • Trường hợp 1: “01” chỉ có thể liền sau với “11” và “10” mà không tạo ra dãy bị cấm.
  • Trường hợp 2: “10” chỉ có thể liền sau với “11” và “01” mà không tạo ra dãy bị cấm.
  • Trường hợp 3: “00” chỉ có thể liền sau với “11” mà không tạo ra dãy bị cấm.

            Với i = 4 -> 10^6

Bài toán cơ sở:

            F[0][2] = F[1][2] = F[2][2] = F[3][2] = 1;

F[0][3] = 2;

F[1][3] = 2;

F[2][3] = 1;

F[3][3] = 1;

Kết quả: Với mỗi n nhập vào, tính (F[0][n] + F[1][n] + F[2][n] + F[3][n]) % base;

 

Code Mẫu:

 

#include <bits/stdc++.h>

using namespace std;

int F[4][1000001];

long n;

const int base = 1e7 + 9;

int main()

{

ios_base::sync_with_stdio(0);

cin.tie(0);

//freopen(“HACKER.inp”,”r”,stdin);

//freopen(“HACKER.out”,”w”,stdout);

F[0][2] = F[1][2] = F[2][2] = F[3][2] = 1;

F[0][3] = 2;

F[1][3] = 2;

F[2][3] = 1;

F[3][3] = 1;

for (int i = 4; i <= 1e6; i++)

{

F[0][i] = (F[0][i – 2] + F[1][i – 2] + F[2][i – 2] + F[3][i – 2]) % base;

F[1][i] = (F[0][i – 2] + F[2][i – 2]) % base;

F[2][i] = (F[0][i – 2] + F[1][i – 2]) % base;

F[3][i] = F[0][i – 2];

}

while (cin >> n && n)

{

cout << (F[0][n] + F[1][n] + F[2][n] + F[3][n]) % base << ” “;

}

}

Trả lời

Email của bạn sẽ không được hiển thị công khai. Các trường bắt buộc được đánh dấu *