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 << ” “;
}
}
