Sol 23-11-2021

tags: `CTQH`

Người chơi thì có thể không thắng. Nhưng người không chơi thì không bao giờ thắng. [name=LamTer]

Weird Algorithm

Bài này có liên quan tới Phỏng đoán Collatz.

Bài này ta cần sử dụng vòng $while$ hoặc sử dụng đệ quy.

Code mẫu của LamTer:

#include <bits/stdc++.h>

using namespace std;

int main() {
    long long int n; cin >> n;
    while(n != 1) {
        cout << n << ' ';
        if(n & 1) n >>=1;
        else n = 3 * n + 1;
    }
    
    cout << 1;
}

Code mẫu của bạn Minh Hiên:

#include <bits/stdc++.h>
using namespace std;
long long int n,i,t;
int main(){
    freopen ("weirdalgorithm.inp","r",stdin);
    freopen ("weirdalgorithm.out","w",stdout);
    cin>>n;
    t=n;
    cout<<n<<" ";
    while (t!=1){
    if (t%2==0) t=t/2;
    else if (t%2!=0) t=(t*3)+1;
    cout<<t<<" ";}
}

Code mẫu của bạn LamTer (sử dụng đệ quy):

#include <bits/stdc++.h>

using namespace std;

void pro(long long int n) {
	cout << n << ' ';
	if(n == 1) exit(0);
	if(n % 2) pro(3 * n + 1);
	else pro(n / 2);
}

int main() {
	int n; cin >> n;
	pro(1LL * n);
}

Missing Number

Đây là một bài khá hay và có nhiều cách làm.

Cách 1: Sắp xếp

Nhận thấy rằng khi ta sắp xếp $n-1$ phần tử đó theo thứ tự bé đến lớn thì:

Phần tử thứ $1$ có giá trị là $1$
Phần tử thứ $2$ có giá trị là $2$
Phần tử thứ $3$ có giá trị là $3$

Tuy nhiên sẽ có một phần tử thứ $i$ mà giá trị của nó là $i + 1$. Thì $i$ chính là số bị mất.

Code mẫu của bạn Hoàng Hải:

#include<bits/stdc++.h>

using namespace std;

const int N = 2e5 + 5;

#define GoldEas "missingnumber"

int main(){
	if(fopen(GoldEas ".inp", "r")){
		freopen(GoldEas ".inp", "r", stdin);
		freopen(GoldEas ".out", "w", stdout);
	}	
	int n, a[N] = {};
	cin >> n;
	for(int i = 1; i < n; i++) cin >> a[i];
	sort(a, a+n);
	for(int i = 1; i < n; i++)
		if(a[i] != i)
		{
			cout << i;
			break;
		}
	return 0;  
}

Cách 2: Dùng hiệu

Ta nhận thấy là nếu lấy tổng từ $1$ đến $n$ trừ cho tổng tất cả các phần tử trong dãy thì sẽ tìm được phần tử còn thiếu.

Code mẫu của bạn Thảo Linh:

#include <bits/stdc++.h>

using namespace std;

int main() {
    int n, e, s_1=0, s_2=0;
    freopen("missingnumber.inp","r",stdin);
    freopen("missingnumber.out","w",stdout);
    vector<int> a;
    cin >> n;
    while (cin>>e) {
        a.push_back(e);
        s_1+=e;
    }
    for (int i=1; i<=n; i++) {
        s_2+=i;
    }
    cout << s_2-s_1 << "\n";

}

Cách 3: Dùng phép toán $xor$

Ta nhận thấy rằng $a \oplus a = 0$.

Ví dụ: $(a \oplus b \oplus c) \oplus (a \oplus b) = (a \oplus a) \oplus (b \oplus b) \oplus c=c$

Ở đây có thể hiêu $a,b,c$ là dãy gốc $a,b$ là dãy nhập vào còn $c$ là số mất tính. Thì ta thấy chỉ cần $xor$ là tìm được $c$.

Dựa vào tính chất này ta có thể tìm số bị mất bằng cách: $(1 \oplus 2 \oplus 3 \oplus \ldots \oplus n) \oplus (a_1 \oplus a_2 \oplus a_3 \oplus \ldots \oplus a_{n-1}) = the \ missing \ number$

Code mẫu của bạn LamTer:

#include <bits/stdc++.h>

using namespace std;

int main() {
	int n; cin >> n;
	int xorsum = n;

	for(int i = 1; i < n; i++) {
		int x; cin >> x;
		xorsum ^= x;
		xorsum ^= i;
	}

	cout << xorsum;
}

Repetitions

Code mẫu của LamTer:

#include <bits/stdc++.h>

using namespace std;

int main() {
    string s; cin >> s; s += '#';

    int ans = 1;
    //cur là biến lưu độ dài của chữ cái hiện tại đang xét
    for(int i = 1, cur = 1; i < (int) s.size(); i++) {
        //Nếu thứ i giống chữ thứ i giống chữ trước đó 
        //thì tăng độ dài hiện tại đang xét lên 1
        if(s[i] == s[i - 1]) cur++;
        else {
            //Nếu không thì chúng ta sẽ cập nhật chiều dài tối đa
            ans = max(ans, cur);
            //Và trả độ dài về 1
            cur = 1;
        }
    }
    
    //In ra đáp án
    cout << ans;
}

Increasing Array

Gọi mảng là $a$. Chi phí chuyển đổi là $cost$

Với mỗi $2 \leq i \leq n$ thì ta sẽ xem nếu $a_i < a_{i-1}$ thì ta sẽ tăng $a_i=a_{i-1}$ và cộng chi phí chuyển đổi $cost$ cho $a_{i-1}-a_i$.