Code Contest RankA CTF [Beyond Human]
This post hasn't been updated for 8 years
Mở đầu
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.
BigC Big Sale
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:
findmin(int* myArray, int n) : |
---|
Tìm ra coupon phải mua ít items nhất trong 1 list coupons. |
sort(price,price + need_numbers) : |
---|
Thực hiện sort theo thứ tự tăng dần của giá các items trong số need_numbers items mà HuyND cần mua. |
phần // LET PICK ITEMS WITH MINIMUM BUY COUPON. |
---|
Thực hiện mua các items với giá từ cao xuống thấp với mỗi lần mua với số lượng ít nhất có thể mà vẫn kèm theo coupons đã tìm ra ở bước 1. |
phần // LET PICK FREE ITEMS AND RECOUNT need_numbers. |
---|
Thực hiện mua tiếp nếu số lượng need_numbers >2, nếu không thì dừng mua vì thêm tối đa 2 items nữa là đủ số lượng cần thiết rồi. |
Quang Binh's Fishes:
Input:
- dòng 1: số cá câu được của HUYND, KhanhLD, số loại cá.
- dòng 2: list các loại cá mà KhanhLD câu được.
- 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
void sort(int* number, int n) |
---|
Thực hiện sort array number chứa n phần tử, dùng để sort 2 array cá của KhanhLD và HuyND |
Những xử lý logic còn lại đều implements theo đúng những trường hợp đã đặt ra.
Kết luận
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 .
All Rights Reserved