Giải P152PROF – ROUND 2F – Min max

Đề bài :

http://www.spoj.com/PTIT/problems/P152PROF/

Ý tường :

  • Với việc tìm số nhỏ nhất : đi từ cuối về đầu và gán với số lớn nhất có thể, sau khi gán nếu tại vị trí đầu có giá trị = 0 thì phải cho nó về 1 và bù vào cái số nào gần nhất nó
  • Với việc tím số lớn nhất : đi từ đầu tới cuối, cố gắng điền số lớn nhất có thể , có thể tất cả đằng sau là 0 cho nên khi a[i] = 0 thì có thể thoát vòng lặp luôn

Code C++ :

https://www.dropbox.com/s/aepx48s89a4hex9/P152PROF.cpp?dl=0

 

Tổng hợp những đoạn code hay dùng cho giải thuật

Sắp xếp nhanh :

void QuickSort(long long A[], int Left, int Right)
{
int i = Left, j = Right;
int pivot = A[(Left + Right) / 2];
/* partition */
while (i <= j)
{
while (A[i] < pivot) i++; while (A[j] > pivot)
j–;
if (i <= j)
{
Swap(A[i],A[j]);
i++;
j–;
}
}
/* recursion */
if (Left < j)
QuickSort(A, Left, j);
if (i < Right)
QuickSort(A, i, Right);
}

/*đảo giá trị*/

void Swap(long long &a,long long &b)
{
int temp = a;
a = b;
b = temp;
}

/*UCLN*/

int USCLN(int a, int b)
{
if(a==0) return b
return USCLN(b%a,a);
}

Giải bài P154PROI – ROUND 4I – Xâu cân bằng

Ý tường phân tích :

Bản chất ngôn ngữ C/C++ khi lưu dữ liệu char đã là lưu mã ascii

vậy nên ta không quan tâm nhiều đến vấn đề mà

ta cứ dùng mảng char và trừ đúng như công thức trong đề bài

chỉ có 1 chú ý là : k nên tốn time cho việc xây dựng chuỗi R
vì chuỗi R là đảo ngược chuỗi S nên hãy xử lý ngay ở chuỗi S
sẽ tiết kiệm dc time chạy

Code :

https://www.dropbox.com/s/d01xdzawspu0egd/P154PROI.cpp?dl=0

Giải bài P166SUMI – ROUND 6I – Rick Flag

Ý tưởng : Bài này đơn giản chỉ cần duyệt toàn bộ và đếm số lần xuất hiện của số 0

có 1 điều lưu ý là khi biến đếm được tăng lên thì kiểm tra luôn xem nó đã lớn hơn 1 chưa

nếu lớn hơn thì thoát khỏi hàm luôn, như vậy sẽ giảm dc time chạy trong trường hợp có nh số 0

Code :

#include<stdio.h>
int n;
int x[1000];
bool kiemTra(){
int dem = 0;
for (int i = 0 ; i<n; i++){
if (x[i] == 0) {
dem++;
if (dem > 1) return false;
}
}
if (dem == 0 ) return false;
else return true;
}
main(){

scanf(“%d”,&n);
for (int i = 0 ; i < n ; i++){
scanf(“%d”,&x[i]);
}

if (kiemTra()){
printf(“YES”);
}else{
printf(“NO”);
}
}

Phân tích và giải bài 1 – P153PROG

Ở bài này điều chú ý đầu tiên là kiểu dữ liệu đã cho là <= 10^12 vậy nên mình chọn long long luôn cho chắc cú :V
Tiếp theo, đề bài cho 2 bộ test rồi
thử xem sao
Bộ test 1:
n = 10, k = 3
n = 10 =>
dãy là : 1 3 5 7 9 2 4 6 8 10
index : 1 2 3 4 5 6 7 8 9 10
-> quy luật : nếu n là số chẵn thì
+ khi k <= n/2 -> giá trị = 2 * index – 1
+ khi k > n/2 -> giá trị = 2*(index – n/2)
Bộ test 2 :
n = 7, k = 7
dãy là : 1 3 5 7 2 4 6
index : 1 2 3 4 5 6 7
-> quy luật : nếu n là số lẻ thì
+ khi k <= n/2 -> giá trị = 2 * index – 1
+ khi k == n/2 +1 (giữa) -> giá trị = max = n
+ còn lại : giá trị = 2 * (index – n/2 – 1)
Theo đúng như thế, chuyển thành code

Cài đặt file apk thông qua command line

Bước 1 : Chuẩn bị tool

Download tại đây

Bước 2 : Sử dụng

Giải nén file download, copy file apk vào đó

Bước 3 : Thực hiện

  • Lệnh : adb devices  <hiển thị list devices đang kết nối với máy tính>
  • adb install

Ngoài ra cũng có các lệnh khác như sau :

adb install -r <app name.apk> [The -r option allows you to re-install or update an existing app on your device]
adb install -s <app name.apk> [The -s option lets you install app to SD card if the app supports move to SD card feature]
adb uninstall <app name.apk>

Cài Git vào Windows

Nếu bạn dùng Windows thì có thể tải file .exe cài đặt Git tại địa chỉ

http://adf.ly/1e8lf9. Khi cài bạn có thể để nguyên tùy chọn mặc định mà không cần tùy chỉnh gì thêm nếu bạn chưa hiểu về nó.

Sau khi cài đặt Git vào Windows, bạn sẽ cần mở ứng dụng Git Bash lên để bắt đầu sử dụng các dòng lệnh của Git.

Tiếp tục đọc “Cài Git vào Windows” →