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

Bài 1: Giải mã số

– Sử dụng một mảng kí tự với chỉ số từ 10 đến 35 để lưu các chữ cái (bỏ trống 10 ô nhớ đầu). Hoặc có thể sử dụng struct để lưu trữ bảng mã.

– Duyệt từng chuỗi số. Nếu chuỗi số có số lượng lẻ thì in ra -1. i đi theo thứ tự 0, 2, 4,…, có một chuỗi temp rỗng để cộng arr[i] và arr[i+1] lại để biến thành số.

Kiểm tra số đó có nằm trong đoạn 10 đến 35 không, nếu không xuất ra -1 mà không cần duyệt tiếp, nếu có in ra chữ cái ứng với bảng mã đã tạo.

 

Code mẫu:

 

#include <iostream>

#include <string>

using namespace std;

 

void khoiTaoBangMa(char bangMa[])

{

char c = ‘a’;

for (int i = 10; i < 36; i++)

{

bangMa[i] = c;

c++;

}

}

 

int main()

{

char bangMa[36];

khoiTaoBangMa(bangMa);

 

int n;

cin >> n;

string *arr = new string[n];

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

cin >> arr[i];

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

{

string text = “”;

if (arr[i].length() % 2 == 1)

{

if (i == n – 1)

cout << -1;

else

cout << -1 << ” “;

continue;

}

for (int j = 0; j < arr[i].length(); j += 2)

{

string temp = “”;

temp = arr[i][j];

temp = temp + arr[i][j + 1];

int chuCai = atoi(temp.c_str());

if (chuCai > 35 || chuCai < 10)

{

cout << -1;

text = “”;

break;

}

else

text = text + bangMa[chuCai];

}

if (i == n – 1)

cout << text;

else

cout << text << ” “;

}

delete[] arr;

return 0;

}

 

 

Bài 2: Gia đình người ta

Từ công thức trên, ta thấy rằng các số đứng kề nhau phải lớn hơn tối đa là gấp đôi hoặc nhỏ hơn tối thiểu là một nửa so với số liền sau. Giả sử có một mảng số nguyên mà không thỏa công thức 1, tại vị trí ii + 1, số lượng các số cần thêm vào đạt ít nhất khi và chỉ khi các số đó tạo thành một mảng cấp số nhân thỏa công bội q = 2 hoặc q = 0.5 trong khoảng (a[i], a[i + 1]).

Ta gọi m là số lượng các số cần thêm vào mảng sau vị trí i, u là mảng thỏa cấp số nhân với u1 = a[i], un và a [i + 1] thỏa công thức trên; tương ứng ta sẽ gọi min = min (a[i], a [i + 1]) và max = max (a[i], a [i + 1]) ta sẽ biến đổi công thức cấp số nhân như sau:

Vì biến max có thể là một số nguyên thỏa công thức cấp số nhân tạo thành dãy m + 1 số nên ta phải trừ đi 1 số. m có thể là kiểu float nên phải ép kiểu về integer. Cứ áp dụng phương pháp tương tự tại nhiều vị trí cho đến khi hết mảng a.

Trong mọi trường hợp a[i] < a[i + 1] và a[i] > a[i + 1] thì phương pháp trên đều đúng.

Lưu ý: Đây là bài toán mở, có thể sẽ có nhiều cách để giải quyết bài toán.

 

Code mẫu:

 

#include <iostream>

#include <algorithm>

#include <cmath>

using namespace std;

 

int denseArray()

{

int n;

cin >> n;

float* a = new float[n];

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

cin >> a[i];

int count = 0;

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

{

if (max(a[i], a[i + 1]) / min(a[i], a[i + 1]) >= 2)

{

float _max = a[i] > a[i + 1] ? a[i] : a[i + 1];

float _min = a[i] < a[i + 1] ? a[i] : a[i + 1];

float x = log(_max / _min) / (log(2));

if (x – ((int)x) == 0)

{

count += x – 1;

}

else

{

count += (int)(x);

}

}

}

return count;

}

int main()

{

int t;

cin >> t;

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

{

cout << denseArray() << endl;

}

return 0;

}

 

Bài 3: Văn mẫu 02

Code mẫu:

#include<iostream>

#include<unordered_map>

#include<set>

 

using namespace std;

#define ll long long int

#define pb push_back

#define F first

#define S second

#define mp(a, b) make_pair(a, b)

#define faster() ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

#define deu 3000000

 

struct hash_pair {

template <class T1, class T2>

size_t operator()(const pair<T1, T2>& p) const{

auto hash1 = hash<T1>{}(p.first);

auto hash2 = hash<T2>{}(p.second);

return hash1 ^ hash2;

}

}; // build hashing

ll n;

ll res = 0;

void solve(){

ll n;

cin >> n;

ll a[n];

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

cin >> a[i];

unordered_map<ll, pair<ll, ll>> m2;

unordered_map<ll, ll> m3;

for (int i = 0; i < min(n, (ll)4000); i++) {

for (int j = i + 1; j < min(n, (ll)4000); j++) {

if (m3[a[i] + a[j]]) {

if (m2[a[i] + a[j]].F != i and m2[a[i] + a[j]].S != i and m2[a[i] + a[j]].F != j and m2[a[i] + a[j]].S != j){

cout << “YES” << ” “;

//cout << i + 1 << ” ” << j + 1 << ” ” << m2[a[i] + a[j]].first + 1 << ” ” << m2[a[i] + a[j]].second + 1 << endl;

res++;

return;

}

}

 

else {

m2[a[i] + a[j]] = mp(i, j);

m3[a[i] + a[j]] = 1;

}

}

}

if (res == 0)

cout << “NO”;

else cout << res;

}

 

int main(){

faster();

solve();

}

 

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 *