[CPP T2 2024]. TEST 1 : TOÁN TỬ, VÒNG LẶP, HÀM, MẢNG 1 CHIỀU CƠ BẢN

Lũy thừa cơ số 2

Nộp bài
Time limit: 1.0 / Memory limit: 256M

Point: 1

Nhiệm vụ của bài tập này đơn giản, bạn hãy kiểm tra số tự nhiên N có phải là lũy thừa với số mũ nguyên không âm của 2 hay không. Ví dụ về các số thỏa mãn : 4, 8, 32, 1024...

Gợi ý : N là lũy thừa cơ số 2 thì khi liên tục chia cho 2 tới khi không chia hết nó sẽ bằng 1. VD 32 / 2 = 16 / 2 = 8 / 2 = 4 / 2 = 2 / 2 = 1


Đầu vào

Dòng duy nhất chứa số nguyên dương N


Giới hạn

1<=N<=10^18


Đầu ra

In ra YES nếu N là lũy thừa với cơ số 2, ngược lại in NO


Ví dụ :

Input 01
16
Output 01
YES

Chữ số đứng giữa lớn nhất

Nộp bài
Time limit: 1.0 / Memory limit: 256M

Point: 1

Một số nguyên dương N được gọi là số đẹp nếu nó thỏa mãn đồng thời những điều kiện sau :

  1. Có số lượng chữ số là số lẻ

  2. Không có chữ số nào của N được lớn hơn chữ số đứng giữa

Ví dụ : N = 12321 là số đẹp, N = 12939 là số đẹp, N = 18891 không được coi là số đẹp

Bạn hãy liệt kê các số đẹp như vậy trong đoạn 2 số [a, b], nếu trong đoạn [a, b] không tồn tại số đẹp thì in ra "28tech"

Gợi ý : Đếm xem N có bao nhiêu chữ số, khi tách chữ số tới giữa thì ghi nhận lại chữ số đứng giữa, so sánh chữ số đừng giữa vs chữ số lớn nhất nếu bằng nhau thì thỏa mãn.

Ví dụ N = 12981 có 5 chữ số thì khi tách tới chữ số thứ 3 từ cuối về thì ghi nhận lại số 9 là số đứng giữa. Trong quá trình tách thì tìm luôn cả chữ số lớn nhất.


Đầu vào

1 dòng duy nhất chứa 2 số a, b


Giới hạn

1<=a<=b<=10^6


Đầu ra

In ra các số đẹp mỗi số cách nhau 1 dấu cách hoặc in ra "28tech" nếu không tồn tại số đẹp trong đoạn [a, b]


Ví dụ :

Input 01
100 121
Output 01
110 111 120 121

[Kiểu dữ liệu-if else]. Bài 46. Can chi

Nộp bài
Time limit: 1.0 / Memory limit: 256M

Point: 2

Đã gần đến Tết Nguyên Đán 2025, vậy các bạn đã biết năm 2025 âm lịch có tên gọi là gì chưa? Để xác định tên âm lịch của 1 năm người ta dựa vào Can Chi, có 10 Thiên Can lần lượt tương ứng với các số từ 0 tới 9, 12 Chi tương ứng với 12 con Giáp

10 Can : 0 : Canh, 1 : Tân, 2 : Nhâm, 3 : Quý, 4 : Giáp, 5 : Ất, 6 : Bính, 7 : Đinh, 8 : Mậu, 9 : Kỷ

12 Chi : , Sửu, Dần, Mão, Thìn, Tị, Ngọ, Mùi, Thân, Dậu, Tuất, Hợi

Vậy để xác định tên âm lịch của 1 năm họ sẽ dựa vào chữ số cuối cùng của năm đó để biết năm đó có Can là gì, ví dụ năm 2023 có tận cùng là 3 nên nó sẽ can là Qúy, năm 2023 là năm Mão vì thế 2023 có tên âm lịch là Quý Mão.

Biết năm 1980 là năm Canh Thân, vậy bạn hãy xác định năm X (1980-2100) có tên âm lịch là gì ? Khi in ra đáp án hãy dùng chữ in hoa không dấu, Chú ý : Tý và Tị và chữ i dài i ngắn trong các tên Can, Chi.


Đầu vào

Dòng duy nhất chứa năm X.


Giới hạn

1980<=X<=2100


Đầu ra

In ra năm âm lịch tương ứng


Ví dụ :

Input 01
1981
Output 01
TAN DAU

Tam giác sao & số

Nộp bài
Time limit: 1.0 / Memory limit: 256M

Point: 2

Cho N là số dòng của tam giác cân, bạn hãy in ra hình tương ứng như quy luật trong ví dụ mẫu.


Đầu vào

Số nguyên dương N


Giới hạn

5<=N<=100


Đầu ra

In ra tam giác cân theo yêu cầu


Ví dụ :

Input 01
8
Output 01
*
**
*3*
*44*
*555*
*6666*
*77777*
********

Vẽ hình chữ nhật sao & số

Nộp bài
Time limit: 1.0 / Memory limit: 256M

Point: 2

Cho N là số dòng của HCN cần in, bạn hãy in ra HCN sao cho :

  • Các vị trí viền của HCN là dấu *
  • Các vị trí không phải viền của HCN thì dòng chẵn in ra các dấu ~, dòng lẻ in ra các dấu #

Đầu vào
  • Số nguyên dương N

Giới hạn

3<=N<=100


Đầu ra

In ra hình theo yêu cầu


Ví dụ :

Input 01
7
Output 01
*******
*~~~~~*
*#####*
*~~~~~*
*#####*
*~~~~~*
*******

Số Tribonacci

Nộp bài
Time limit: 1.0 / Memory limit: 256M

Point: 2

Dãy số Tribonacci được định nghĩa như sau :

T1 = 0

T2 = 0

T3 = 1

T(n) = T(n - 1) + T(n - 2) + T(n - 3) với n >= 4

Những số Tribonacci đầu tiên : 0, 0, 1, 1, 2, 4, 7, 13, 24....

Nhiệm vụ của bạn là hãy in ra N số Tribonacci đầu tiên.


Đầu vào

Dòng duy nhất chứa số nguyên N


Giới hạn

1<=N<=50


Đầu ra

In ra N số Tribonacci đầu tiên, mỗi số cách nhau một dấu cách.


Ví dụ :

Input 01
9
Output 01
0 0 1 1 2 4 7 13 24

Liệt kê giá trị khác nhau theo thứ tự ngược

Nộp bài
Time limit: 1.0 / Memory limit: 256M

Point: 2

Cho mảng A[] gồm N phần tử, bạn hãy liệt kê các giá trị khác nhau xuất hiện trong mảng theo thứ tự từ phải qua trái

Ví dụ : A[] = {5, 5, 1, 3, 3, 3, 1, 2, 3, 4, 1} sẽ in ra 1, 4, 3, 2, 5


Đầu vào
  • Dòng đầu tiên là N : số lượng phần tử trong mảng

  • Dòng 2 gồm N số trong mảng cách nhau 1 dấu cách


Giới hạn

1<=N<=1000

0<=A[i]<=10^6


Đầu ra

In ra các giá trị khác nhau trong mảng theo thứ tự từ cuối về, mỗi giá trị chỉ liệt kê 1 lần


Ví dụ :

Input 01
5
1 1 2 2 3
Output 01
3 2 1

Dãy số 28Tech

Nộp bài
Time limit: 1.0 / Memory limit: 256M

Point: 3

Dãy số 28Tech được định nghĩa như sau :

  • F[1] = 2

  • F[2] = 8

  • F[n] = 2 * F[n - 1] + 8 * F[n-2] với n >= 3

Dãy số 28Tech gồm những số đầu tiên là : 2, 8, 32, 128, 512, 2048 .....

Bạn hãy in ra số 28Tech thứ N sau khi chia dư cho 1000000007

Gợi ý : Làm tương tự như số Fibonacci, lưu dãy 28Tech vào mảng F[], tính trước mảng F tới số thứ 1000000, sau đó mỗi test nhập N thì in ra F[N], nhớ chia dư trong quá trình tính toán.


Đầu vào
  • Dòng 1 là số bộ test T

  • T dòng tiếp theo mỗi dòng là số N


Giới hạn
  • 1<=T<=1000

  • 1<=N<=10^6


Đầu ra

In ra kết quả của mỗi test trên 1 dòng


Ví dụ :

Input 01
3
5
2
3
Output 01
512
8
32

Chia mảng

Nộp bài
Time limit: 1.0 / Memory limit: 256M

Point: 3

Cho mảng A[] gồm N phần tử và số nguyên dương S, nhiệm vụ của bạn là chia mảng thành ít nhất các mảng con liên tiếp sao cho không có mảng con nào có tổng vượt quá S.

Ví dụ : A[] = {1, 3, 3, 2, 8, 1, 3, 4, 6, 8} và S = 10 thì bạn có thể chia mảng A[] thành ít nhất 5 mảng con là {1, 3, 3, 2}, {8, 1}, {3, 4}, {6}, {8}

Gợi ý : Dùng 1 biến sum để tính tổng các phần tử của dãy con, duyệt qua mảng A[] thì cộng A[i] vào sum, nếu sum > S => Đếm thêm 1 dãy con và reset biến sum về A[i] để xét dãy con mới bắt đầu từ A[i]. Lưu ý dãy con kết thúc bởi phần tử cuối cùng trong mảng


Đầu vào

Dòng 1 là NS

Dòng 2 gồm N số trong mảng A[]


Giới hạn

1<=N<=10^6

0<=A[i]<=10^6

A[i]<=S<=10^18


Đầu ra

In ra số mảng con ít nhất được chia


Ví dụ :

Input 01
5 5
1 1 1 1 1
Output 01
1
Input 02
5 8
3 2 5 3 8
Output 02
3

Di chuyển mảng đối xứng

Nộp bài
Time limit: 1.0 / Memory limit: 256M

Point: 3

Cho mảng A[] gồm N phần tử, 28Tech rất thích mảng đối xứng nên anh ấy muốn nhờ bạn xác định xem liệu có thể thay đổi vị trí của các phần tử trong mảng sao cho mảng trở thành đối xứng hay không ?

Ví dụ : A[] = {1, 1, 1, 1, 2, 3, 3, 2} có thể thay đổi thành mảng đối xứng là {1, 2, 1, 3, 3, 1, 2, 1}

In ra 28tech nếu có thể biến đổi mảng thành đối xứng, ngược lại in ra 29tech

Gợi ý : Mảng có chia thành đối xứng hay không thì số lần xuất hiện của các phần tử phải chẵn thì mới chia đề về 2 phía được, chỉ chấp nhận duy nhất 1 số có số lần xuất hiện lẻ, mình sẽ cho nó đứng giữa.

Thêm fast IO vào để tránh TLE vì bài này đọc ghi rất nhiều số :

ios::sync_with_stdio(false);
cin.tie(NULL);

Đầu vào
  • Dòng đầu tiên là T : số bộ test

Mỗi bộ test gồm 2 dòng :

  • Dòng 1 là N : số phần tử trong mảng

  • Dòng thứ 2 gồm N số trong mảng


Giới hạn

1<=T<=100

1<=N<=10^5

0<=A[i]<=10^6


Đầu ra

In ra 28tech hoặc 29tech cho mỗi test ở trên 1 dòng


Ví dụ :

Input 01
2
5
1 2 3 1 2
3
1 2 3
Output 01
28tech
29tech

Ước Chung Lớn Nhất Của Dãy Số

Nộp bài
Time limit: 1.0 / Memory limit: 256M

Point: 3

Cho mảng A[] gồm N phần tử, bạn hãy tìm ước chung lớn nhất của 2 phần tử bất kỳ trong mảng.

Gợi ý : Sử dụng sàng để có thể có độ phức tạp tốt hơn

  • Bước 1 : Đếm xem mỗi phần tử trong mảng A[] xuất hiện bao nhiêu lần

  • Bước 2 : Duyệt i từ maxval (giá trị lớn nhất trong mảng) về 1, mình sẽ xét i là ước chung lớn nhất của bao nhiêu số trong mảng bằng cách duyệt qua các bội của i từ i tới maxval, dùng 1 vòng for duyệt từ i tới maxval, bước nhảy là i để chỉ duyệt các bội của i, duyệt tới bội gọi là j thì dựa vào tần suất của j để xác định xem i có bao nhiêu bội trong mảng A[], nếu đếm được >= 2 bội thì có thể kết luận sớm và dừng chương trình.


Đầu vào
  • Dòng 1 là N

  • Dòng 2 gồm N số trong mảng A[]


Giới hạn

2<=N<=10^6

1<=A[i]<=10^6


Đầu ra

In ra đáp án của bài toán


Ví dụ :

Input 01
5
2 8 10 2 16
Output 01
8