Code Contest RankA CTF [Beyond Human]

Dạo này lâu ngày không code gì cả nên trình độ đi xuống nhiều mà hạn report lại đến rồi, đành lôi 2 bài code contests ra làm report vậy. Đề bai a/c/e có thể tham khảo tại trang cực nổi tiếng của Framgia :v :v tại đây. Code sample anh em có thể chạy trực tiếp hoặc chạy test qua ide online.

Input

dòng 1: số lượng các loại coupon. dòng 2: số items cần mua ứng với loại coupon ở trên. dòng 3: số lượng items HuyND cần mua (k). dòng 4: giá của từng items ở dòng 3.

Mục tiêu: mua k items với ít tiền nhất. Ta chú ý rằng với mỗi coupon thì có max free 2 items vậy để mua được số items cần mà ít tiền nhất thì ta phải tận dụng tối đa số items free này.

Ý tưởng

Thực hiện mua với coupon có số lượng items cần mua ít nhất (như vậy sẽ có nhiều free items nhất).Đem sử dụng coupon này mua liên tục tới khi nào đủ k items. Tuy nhiên free items phải có giá rẻ hơn hoặc bằng với items mà coupon đó sử dụng để mua do đó với k items mà HuyND cần mua ta cần phải sort lại theo thứ tự giảm dần rồi mua từ items có giá cao trước -> pick free item có giá ngay sau đó -> tiếp tục mua.

cài đặt

```C++

using namespace std;
int findmin(int* myArray, int n){
    int count,min;
    min = myArray[0];
    for(count=0;count < n; count++){
       if(min > myArray[count])
        min = myArray[count];
    }
    return min;
    }

int main() {
	// Declare parameters
	int n,need_numbers,count;
	int coupon_min;
	int total_price = 0;
	// INPUT from 4 lines
	cin >> n;
	int coupon[n];
	for (count = 0; count < n; count ++)
	{
		cin >> coupon[count];
	}
	cin >> need_numbers;
	int price[need_numbers];
	for (count = 0; count < need_numbers; count ++)
	{
		cin >> price[count];
	}
	for (count = 0; count < n; count ++)
	{
	    cin >> coupon[count];
	}
	coupon_min = findmin(coupon,n);
	sort(price,price + need_numbers);

	// LET PICK ITEMS WITH MINIMUM BUY COUPON
    while(need_numbers >= coupon_min){
        for(count = need_numbers-1; count >= need_numbers- coupon_min;count--)
            total_price = total_price + price[count];       //Buy a min coupon
        need_numbers = need_numbers - coupon_min;           // recount need_numbers after buy
        // LET PICK FREE ITEMS AND RECOUNT need_numbers
        if(need_numbers >2)
            need_numbers = need_numbers -2;
        else{
            	need_numbers = 0;
            	break;
            }
    }
    if(need_numbers < coupon_min){
    	for(count=0;count<need_numbers;count++)
    	total_price = total_price + price[count];
    }
	cout << total_price << endl;
	return 0;
}

Các functions cần thiết:

Quang Binh's Fishes:

Input:

1. dòng 1: số cá câu được của HUYND, KhanhLD, số loại cá.
2. dòng 2: list các loại cá mà KhanhLD câu được.
3. dòng 3: list các loại cá mà KhanhLD câu được. Mục tiêu: liệu khối lượng cá mà KhanhLD câu được có lớn hơn khối lượng cá của HUYND câu được không?

Ý tưởng:

Vì các loại cá được sắp xếp theo mảng không giảm về khối lượng nhưng ta lại không biết được khối lượng từng loại. Vì vậy: Trường hợp 1: KHanhLD có cá loại to hơn mà HuyND không có, trong trường hợp này KHanhLD luôn có khả năng sở hữu khối lượng cá lớn hơn (giả sử con cá loại to đó có khối lượng rất lớn so với những loại còn lại) và câu trả lời luôn là YES. ví dụ : KhanhLD : 99999(rất lớn so với các loại còn lại), 3, 1 HuyND: 5, 4, 2 Trường hợp 2: khi so sánh từ cặp cá thứ tự từ lớn đến bé thì tại 1 cặp bất kỳ cá của KhanhLD lớn hơn của HuyND ví dụ: KhanhLD: 999998, 99994, 99985, 10, 6, 1 HuyND: 999999, 99995, 12, 11, 8, 7 Ở đây chỉ vị trí thứ 3 là KhanhLD có cá to hơn các vị trí còn lại HuyND đều có cá to hơn.Tuy nhiên vì độ chênh quá lớn nên trường hợp này câu trả lời vẫn là YES. Trường hợp 3: khi so sánh từng cặp cá HuyND luôn là cá to hơn => câu trả lời đương nhiên là NO. Như vậy chỉ cần sắp xếp lại cá của 2 người theo thứ tự không tăng, so sánh từng cặp sẽ giải quyết được vấn đề.

cài đặt:

```C++
void sort(int* number, int n){
     /*Sort the given array number , of length n*/
    int temp=0,j,i;
        for(i=1;i<n;i++)
        {
            for(j=0;j<n-i;j++)
            {
                if(number[j] >number[j+1])
                {
                    temp=number[j];
                    number[j]=number[j+1];
                    number[j+1]=temp;
                }
            }
        }
    }
 int main() {
	// INPUT SCANNER
	int a,b,c,count,i;
	int end_game = 0;
	scanf("%d", &a);
	scanf("%d", &b);
	scanf("%d", &c);
	int fishA[a];
	int fishB[b];

	for (count = 0; count < a; count ++)
	{
            scanf("%d", &fishA[count]);  // fish of KhanhLD
	}

	for (count = 0; count < b; count ++)
	{
		 scanf("%d", &fishB[count]);  // fish of HuyND
	}
	//ALOGTHIRM
	sort(fishA,a);
	sort(fishB,b);
	if(a>b){
        printf("YES");// trường hợp 1
	    end_game =1;
	    return 0;
	}
	else{           //  if(a==b)
	    for(i=0;i<a;i++){
	        if(fishA[a-i-1]>fishB[b-i-1]){
	            printf("YES");     // trường hợp 2
            	end_game =1;
            	return 0;
	        }
	    }

	    printf("NO");    // trường hợp 3
        end_game =1;
        return 0;
	}
}

Các functions cần thiết

Những xử lý logic còn lại đều implements theo đúng những trường hợp đã đặt ra.

Thường thì rankA của CTF không quá khó nhưng cần phải phân tích đề bài kỹ để tránh bị quá mất thời gian vào những sai lầm nhỏ. RankC và RankD thì sẽ khó hơn và thường phải xử lý các giới hạn tính toán của ngôn ngữ.Đủ 20 helpful hoặc bị chấm không đạt yêu cầu thì sẽ viết bài cho rankC,D =)). Chúc a/c/e sẽ kiếm được điểm trong những code contest sắp tới của công ty