TWOEARRAY

Small

Cho 2 dãy số nguyên A, B đều gồm N phần tử. Ban đầu tất cả các phần tử của dãy A đều bằng 0.

Bạn cần biến dãy A thành dãy B bằng cách thực hiện nhiều lần thao tác sau: chọn ra K phần tử của dãy A và tăng mỗi phần tử thêm 1 đơn vi.

Yêu cầu Kiểm tra xem có thể biến dãy A thành dãy B được hay không?

Dữ liệu

  • Dòng đầu tiên chứa số nguyên T là số bộ thử nghiệm. Mỗi bộ thử nghiệm gồm 2 dòng, dòng đầu chứa 2 số nguyên dương NK, dòng thứ 2 chứa dãy B.

Kết quả

  • Với mỗi bộ thử nghiệm, in kết quả ra 1 dòng, in YES nếu dãy A có thể biến thành dãy BNO nếu ngược lại.

Sample Input

2
5 3
1 2 3 4 5
3 2
1 1 4

Sample Output

YES
NO

Giải thích test ví dụ

  • Ở test ví dụ 1, ta có thể thực hiện biến đổi như sau:
    • A = 0, 0, 0, 0, 0, B = 1, 2, 3, 4, 5;
    • Chọn 3 chỉ số 1, 2, 5 \rightarrow A = 1, 1, 0, 0, 1; 
    • Chọn 3 chỉ số 2, 4, 5 \rightarrow A= 1, 2, 0, 1, 2;
    • Chọn 3 chỉ số 3, 4, 5 \rightarrow A= 1, 2, 1, 2, 3;
    • Chọn 3 chỉ số 3, 4, 5 \rightarrow A= 1, 2, 2, 3, 4;
    • Chọn 3 chỉ số 3, 4, 5 \rightarrow A= 1, 2, 3, 4, 5;
    • Như vậy ta có thể biến đổi dãy A thành dãy B sau 5 thao tác như trên.

Ràng buộc

  • T < 1000.
  • K < N < 10^5.
  • B[i] < 10^9.
  • Tổng N trong tất cả bộ thử nghiệm không quá 10^6.

Nguồn: FC115

Số tình nghĩa

jumptozero

Số "tình nghĩa" là số thoả mãn các điều kiện sau:

  • các chữ số của nó chỉ bao gồm 4 hoặc 7

  • Số lượng chữ số 4 bằng số lượng chữ số 7.

Ví dụ: 4774,477744 là các ví dụ về số "tình nghĩa"

Yêu cầu: Cho trước số nguyên dương n. Hãy in ra số "tình nghĩa" nhỏ nhất mà không nhỏ hơn n

Input:

  • Dòng thứ nhất chứa số t(1\le t\le 100)- Thể hiện số lượng testcase

  • t dòng tiếp theo, mỗi dòng chứa số nguyên n(1\le n\le 10^9)

Output:

  • Ứng với mỗi testcase, in ra đáp án cần tìm.

Ví dụ:

Input:

2
1
73

Output:

47
74

Faceapp

PhanDinhKhoi

Nhóm đồ án gồm Khôi, Huy, Cường đang cùng nhau tạo ra một app có thể chỉnh sửa gương mặt mang tên FaceApp. Tuy nhiên, họ đang gặp rắc rối với thuật toán nhận diện khuôn mặt.

Trong vấn đền này, một bức ảnh có thể biểu diễn thành 1 bảng ô m x n bằng các ký tự latin thường (từ a đến z). Một ô 2 x 2 sẽ được tính là một gương mặt nếu từ 4 ô này có thể tạo thành chữ “face”.
Bạn hãy giúp Khôi viết một chương trình đếm có bao nhiêu gương mặt trong bức hình. Biết rằng một ô có thể thuộc nhiều gương mặt.

Input

  • Dòng đầu tiên chứa hai số nguyên dương n, m (1 \leq n,m \leq 50) – lần lượt là chiều cao và chiều rộng của bức ảnh.
  • n dòng tiếp theo, mỗi dòng chứa m ký tự latin thường

Output

  • Số gương mặt trong bức hình.

Sample Input 1

4 4
xxxx
xfax
xcex
xxxx

Sample Output 1

1

Sample Input 2

2 3
fac
cef

Sample Output 2

2

Sample Input 3

1 4
face

Sample Output 3

0

** Giải Thích **

Ví dụ 1:

Ví dụ 2:

Ví dụ 3: Không có ô 2x2 nào cả nên không sẽ không có gương mặt nào.

CSES - Counting Reorders | Đếm số cách sắp xếp

nhphucqt

Tính số cách có thể sắp xếp lại các ký tự của một chuỗi sao cho không có hai ký tự liền kề nào giống nhau.

Ví dụ, kết quả cho aabc6, vì các thứ tự có thể là abac, abca, acab, acba, bacacaba.

Input

  • Một dòng duy nhất chứa một chuỗi n ký tự từ a - z.

Output

  • Một số nguyên duy nhất: kết quả sau khi được modulo cho 10^9 + 7.

Constraints

  • 1\leq n \leq 5000

Example

Sample input

aabc

Sample output

6

Trò chơi với những viên đá

jumptozero

Cho tập hợp gồm N số nguyên dương A=\left\{a_1,a_2,...,a_N\right\}. KaninhoHenry chơi với nhau một trò chơi như sau:

Ban đầu, chúng ta có một cái cột rỗng chứa K viên đá. Hai người chơi sẽ lần lượt thực hiện phép toán sau, bắt đầu từ Kaninho:

  • Chọn một phần tử x của tập A, và loại bỏ đi chính xác x hòn đá từ cột đó.

Người nào không thể thực hiện được phép toán trên, thì đó là người thua cuộc. Giả sử cả hai người đều chơi tối ưu, xác định người chiến thắng.

Input:

  • Dòng thứ nhất chứa hai số nguyên dương N,K(1\le N\le 100,1\le K\le 10^5)

  • Dòng thứ hai chứa N số nguyên dương thỏa mãn 1\le a_1<a_2<a_3<..<a_N\le K.

Output:

  • Nếu Kaninho là người thắng cuộc, in ra "First", ngược lại nếu Henry thắng in ra "Second".

Ví dụ:

Input:

2 4 
2 3

Output:

First

Giải thích: Nếu Kaninho loại bỏ đi 3 hòn đá đầu tiên, khi đó Henry không thể đi được nữa. Do đó, Kaninho là người chiến thắng.

Nguồn: DP Contest Atcoder

Những chiếc tất

admin

Levi mở cửa hàng bán quần áo, anh ta có 1 đống tất mà cần phải ghép đôi theo màu để bán. Mỗi màu có thể được biểu diễn bởi 1 số nguyên dương.

Yêu cầu: Hãy xác định giúp anh ta biết anh ta có thể có tối đa bao nhiêu đôi tất cùng màu.

Dữ liệu vào

  • Dòng đầu tiên gồm 1 số nguyên n đại diện cho số chiếc tất (1\le n \le 100)
  • Dòng thứ hai gồm n số nguyên dương, mỗi số đại diện cho 1 màu tất (các số này không lớn hơn 100)

Kết quả

  • Gồm 1 số duy nhất là kết quả của bài toán.

Sample Input

7
1 2 1 2 1 3 2

Sample Output

2

Nguồn: hackerrank

AEQLB

Small

Cho 2 số nguyên A, B và 2 thao tác sau:

  • Gấp đôi A hay A = A × 2;
  • Giảm B đi 2 đơn vị hay B = B − 2.

Bằng cách thực hiện bất kì số lần các thao tác trên (có thể là 0). Hãy kiểm tra xem có thể biến
đổi để A = B hay không?

Dữ liệu

  • Dòng đầu tiên chứa số nguyên T là số bộ thử nghiệm.
  • T dòng tiếp theo, mỗi dòng là một bộ thử nghiệm gồm 1 dòng chứa 2 số nguyên AB.

Kết quả

  • Với mỗi bộ thử nghiệm, in kết quả ra 1 dòng, in "YES" nếu có thể biến đổi để A = B
    "NO" nếu ngược lại (Lưu ý không in dấu ngoặc kép).

Sample Input

3
3 6
3 4
3 8

Sample Output

YES
NO
YES

Giải thích test ví dụ

  • Ở test ví dụ 1, ta có: 3 × 2 = 6.
  • Ở test ví dụ 3, ta có: 3 × 2 = 8 − 2.

Giới hạn

  • 1 ≤ T ≤ 1000.
  • 1 ≤ A, B ≤ 10^9.

Nguồn: FC

Subset Counting

Small

Nguồn: ICPC North 2021

CSES - Maximum Building I | Tòa nhà lớn nhất

nhphucqt

Bạn được đưa cho một bản đồ của một khu rừng, trong đó một số ô trống và một số ô vuông có cây.

Diện tích tối đa của một tòa nhà hình chữ nhật có thể đặt trong khu rừng để không phải chặt cây nào?

Input

  • Dòng đầu tiên chứa các số nguyên nm: kích thước của khu rừng.
  • n dòng sau, mỗi dòng chứa 1 xâu kí tự độ dài m chỉ gồm các kí tự . biểu thị ô trống hoặc * biểu thị ô có cây.

Output

  • In ra diện tích tối đa của tòa nhà hình chữ nhật.

Constraints

  • 1 \le n, m \le 1000

Example

Sample input

4 7  
...*.*.  
.*.....  
.......  
......*`

Sample output

12

FRACTION SUM

dang7rickroll

Cho số nguyên dương N. Tính tổng:
\sum\limits_{i = 1}^N {\frac{N \times i + i}{i}}<script type="math/tex">\sum\limits_{i = 1}^N {\frac{N \times i + i}{i}}</script>

Dữ liệu:

  • Dòng đầu ghi Q không quá 100 - số câu hỏi.
  • Q dòng tiếp theo, mỗi dòng ghi số nguyên dương N (N \le 10^{21})

Kết quả:

  • Ứng với mỗi câu hỏi, in ra đáp án cần tìm.

Sample input

3
4
5
6

Sample output
20
30
42

Subtasks:

  • Nhóm 1 bao gồm 40\% số test của bài có N \le 10^5.
  • Nhóm 2 bao gồm 50\% test của bài có N \le 10^{13}.
  • Nhóm 3 bao gồm 10\% test của bài có N \le 10^{21}.

Nguồn: Stack's 2021 Contest - A (29/12/2021)

Diện tích đa giác nhỏ nhất

jumptozero

Cho ba điểm A,B,C có toạ độ lần lượt là (x_A,y_A),(x_B,y_B),(x_C,y_C) trên mặt phẳng toạ độ Oxy. Hãy tìm đa giác đều có diện tích nhỏ nhất thoả mãn ba điểm A,B,C là ba đỉnh của đa giác đó.

Input:

  • Dòng thứ nhất chứa số t(1\le t\le 50) - Thể hiện số lượng testcase

  • t block tiếp theo, mỗi block có dạng như sau:

  • Dòng thứ nhất chứa hai số thực x_A,y_A (|x_A|,|y_A|\le 1000) và chúng không có quá 6 chữ số ở hàng thập phân

  • Dòng thứ hai chứa hai số thực x_B,y_B (|x_B|,|y_B|\le 1000) và chúng không có quá 6 chữ số ở hàng thập phân

  • Dòng thứ ba chứa hai số thực x_C,y_C (|x_C|,|y_C|\le 1000) và chúng không có quá 6 chữ số ở hàng thập phân

Output:

  • Ứng với mỗi testcase, in ra diện tích của đa giác cần tìm. (Biết rằng đáp án phải chính xác đến ít nhất 6 chữ số thập phân)

Ví dụ:

Input:

1
0.000000 0.000000
2.000000 2.000000
0.000000 2.000000

Output:

3.999999

Thu hoạch chanh

jumptozero

![Imgur](https://i.imgur.com/mwxXc17.png)

Kaninho trồng n cây chanh và được đánh số từ 1 đến n.

Cây chanh thứ i ra b_i quả chanh và sẽ được Kaninho thu hoạch vào ngày thứ a_{i}. Nhưng không may mắn thay, nếu không thu hoạch đúng thời điểm, chanh trên cây sẽ bị sâu đục và sẽ không thể ăn được nữa, do đó Kaninho quyết định sẽ thu hoạch nó vào ngày thứ a_i hoặc a_{i}+1 (tất cả những trái chanh không được thu hoạch vào hai ngày này sẽ bị hư).

Mặc dù bận trăm công nghìn việc nhưng anh ấy vẫn dành ra thời gian mỗi ngày để đem giỏ ra vườn và thu hoạch chanh. Vì chiếc giỏ này chỉ có khả năng chứa được tối đa v quả nên mỗi ngày, anh ấy cũng chỉ có thể thu được tối đa v quả mà thôi, biết rằng, mỗi ngày, anh ấy có thể thu hoạch chanh ở cùng một cây hoặc những cây chanh khác nhau. Hỏi sau tất cả, anh ấy có thể thu được tối đa bao nhiêu quả chanh ?

Input:

  • Dòng thứ nhất chứa số t(1\le t\le 50) - Thể hiện số lượng testcase

  • t block tiếp theo, mỗi block có dạng như sau:

  • Dòng thứ nhất chứa hai số nguyên n,v(1\le n,v\le 3000)

  • n dòng tiếp theo, mỗi dòng chứa hai số nguyên a_i,b_i(1\le a_i,b_i\le 3000 )

Output:

  • Ứng với mỗi testcase, in ra đáp án cần tìm

Ví dụ:

Input:

7
7 6
2 2
3 2
4 2
2 4
2 4
5 2
3 3
6 5
5 2
3 3
5 4
5 5
3 4
2 2
10 8
3 4
4 2
2 3
5 5
2 5
4 4
2 2
3 2
2 3
2 5
7 9
3 2
3 4
3 2
2 5
3 2
5 2
4 3
6 6
2 2
3 2
2 4
5 3
3 2
2 4
5 6
5 3
3 5
3 4
5 5
3 4
9 8
3 5
4 5
5 4
4 4
5 5
2 5
4 5
4 3
4 2

Output:

19
19
33
20
17
20
34

Vận chuyển châu báu

jumptozero

Henry không những là một cậu bé thông minh, học giỏi mà còn được sinh ra trong một gia đình giàu có ! Một hôm, nhân buổi tối trăng thanh, gió mát, bố của Henry đem ra một số thỏi vàng có hình lăng trụ đứng, tất cả chúng đều cùng chiều cao là h nhưng có 6 loại đáy khác nhau: 1*1,2*2,3*3,4*4,5*5,6*6 và ông ấy đố Henry một bài toán như sau: Chúng ta cần ít nhất bao nhiêu thùng xốp rỗng có chiều cao là h và đáy là 6*6 để có thể chứa tất cả các thỏi vàng trên và đem lại vào nhà !.

Có lẻ vì vàng quá chói lóa trong đêm thanh gió mát đã làm lu mờ đi sự thông minh của Henry, nên anh ấy quyết định nhờ bạn giúp đếm xem cần ít nhất bao nhiêu thùng xốp có kích thước h*6*6 để có thể mang tất cả vàng vào lại trong nhà !

Input:

  • Một dòng duy nhất chứa 6 số nguyên không âm, tương ứng với số lượng của từng thỏi vàng có kích thước lần lượt là h*1*1,h*2*2,h*3*3,h*4*4,h*5*5,h*6*6 (biết rằng số thỏi vàng từng loại không quá 1000)

Output:

  • In ra một số nguyên duy nhất là kết quả cần tìm

Ví dụ:

Input:

0 0 4 0 0 1

Output:

2

Giải thích: Ta nhận thấy rằng ở ví dụ này ta có 4 thỏi vàng kích thước h*3*31 thỏi vàng kích thước h*6*6. Do đó ta phải cần ít nhất 2 thùng xốp có kích thước h*6*6 để chứa hết số vàng này !

Tuổi đi học

Nam năm nay lên 7 tuổi và bước vào lớp 1. Nam tự hỏi nếu khi mình X tuổi thì Nam sẽ học lớp mấy. Nếu Nam chưa đủ tuổi vào lớp 1, in ra "Chua di hoc". Nếu Nam đã quá tuổi học lớp 12, in ra "Da tot nghiep". Nếu Nam ở độ tuổi học từ lớp 1 đến lớp 12, in ra "Lop A" với A là lớp Nam học khi X tuổi.

Input:

  • Dòng duy nhất chứa 1 số nguyên dương X (1 \leq X \leq 100)

Output:

  • Dòng duy nhất chứa kết quả:
    • Nếu Nam chưa đủ tuổi vào lớp 1, in ra "Chua di hoc"
    • Nếu Nam đã quá tuổi học lớp 12, in ra "Da tot nghiep"
    • Nếu Nam ở độ tuổi từ lớp 1 đến lớp 12, in ra "Lop A", với A là lớp của Nam.

Ví dụ:

Input 1:

9

Output 1:

Lop 3

Input 2:

19

Output 2:

Da tot nghiep

Input 3:

6

Output 3:

Chua di hoc

Chia kẹo 01

admin

Sau khi vượt qua một bài kiểm tra, Vasya được nhận một hộp gồm n cây kẹo. Anh quyết định ăn một lượng kẹo bằng nhau mỗi sáng cho đến khi không còn cây kẹo nào trong hộp nữa. Tuy nhiên, Petya đã phát hiện thấy chiếc hộp và quyết định "chôm" một ít kẹo cho mình.

Quá trình ăn kẹo là như sau: ban đầu Vasya chọn một số nguyên duy nhất là k, bằng nhau đối với tất cả các ngày. Sau đó, vào buổi sáng anh ấy ăn k cái kẹo từ chiếc hộp (nếu còn ít hơn k cái kẹo trong hộp, anh ấy ăn tất cả chúng), sau đó vào buổi tối Petya ăn 10\% số kẹo còn lại trong hộp. Nếu vẫn còn kẹo trong hộp, quá trình này được lặp lại - ngày hôm sau Vasya ăn k kẹo một lần nữa, và Petya ăn 10\% kẹo còn lại trong một hộp và cứ như vậy... Nếu số lượng kẹo trong hộp không chia hết cho 10, Petya làm tròn xuống theo số lượng anh ta lấy từ hộp. Ví dụ, nếu có 97 Kẹo trong hộp, Petya sẽ chỉ ăn 9 trong số chúng. Đặc biệt, nếu có ít hơn 10 cái kẹo trong hộp, Petya sẽ không ăn chút nào.

Nhiệm vụ của bạn là tìm ra số lượng tối thiểu k mà Vasya có thể chọn để anh ta ăn ít nhất một nửa trong n cái kẹo anh ban đầu có trong hộp. Lưu ý rằng số k phải là số nguyên.

Dữ liệu vào

  • Dòng đầu tiên chứa một số nguyên duy nhất n (1 ≤ n ≤ 10^{18}) là số lượng kẹo ban đầu trong hộp.

Kết quả

  • Xuất ra một số nguyên duy nhất là số lượng tối thiểu k điều đó sẽ cho phép Vasya ăn ít nhất một nửa số kẹo mà anh ta có.

Sample Input

68

Sample Output

3

Giải thích: Trong ví dụ, lượng kẹo với k = 3, sẽ thay đổi theo cách sau (Vasya ăn trước)
68 → 65 → 59 → 56 → 51 → 48 → 44 → 41 → 37 → 34 → 31 → 28
$ → 26 → 23 → 21 → 18 → 17 → 14 → 13 → 10 → 9 → 6 → 6 → 3 → 3 → 0$.

Tổng cộng, Vasya sẽ ăn 39 viên kẹo, trong khi Petya ăn 29.

Ràng buộc:

  • Có 70% số điểm thỏa mãn điều kiện: n ≤ 10^6.
  • 30% số điểm còn lại thỏa mãn điều kiện n ≤ 10^{18}

Nguồn: 2019 CLC

Tổng số ước các ước

PhanDinhKhoi

Hàm D[n] biểu thị số ước của một số nguyên n. Ví dụ D[24]=8 (Các ước của 241, 2, 3, 4, 6, 8, 12, 24).

Hàm F[n] biểu thị tổng số ước các ước của n. Ví dụ F[24]=D[1]+D[2]+D[3]+D[4]+D[6]+D[8]+D[12]+D[24]=30

Cho số tự nhiên n, hãy tính F[n!], trong đó n!= 1 * 2 * 3 * ... * n

Input

  • Input gồm nhiều dòng
  • Mỗi dòng chứa số nguyên dương n(n \leq 10^6)
  • Input kết thúc bởi số 0

Output

  • Gồm nhiều dòng, mỗi dòng tương ứng với mỗi test
  • Mỗi dòng chứa phần dư F[n!] cho 10^7 +7

Sample Input 1

4
5
1
0

Sample Output 1

30
90
1

Tổng chênh lệch

BichSonNhat

AhhShibaaa cung cấp cho bạn dãy số nguyên gồm N phần tử.

Nhiệm vụ của bạn là thay đổi một vài giá trị trong dãy về bằng 1 (hoặc giữ nguyên) sao cho tổng các chênh lệch tuyệt đối giữa 2 phần tử liên tiếp là lớn nhất.

Input

  • Dòng đầu tiên chứa số nguyên dương N (1 \le N \le 5*10^5).
  • Dòng thứ hai chứa N số nguyên dương a_1, a_2, \dots, a_n ( 1 \le a_i \le 10^6)

Output

Một số nguyên duy nhất là tổng trị tuyệt đối lớn nhất giữa 2 phần tử liên tiếp sau khi biến đổi.

Ví dụ

Input

3
1 8 9

Output
14

Giải thích

Tổng ban đầu : |1 - 8| + |8 - 9| = 8

Thay đổi : [1, 8, 9] \rightarrow [1, 8, 1]

Tổng lúc sau : |1 - 8| + |8 - 1| = 14

Subtask

  • Subtask 1: (30 %) n \le 20
  • Subtask 2: (30 %) n \le 10^3
  • Subtask 3: (40 %) n \le 5 * 10^5

CSES - Area of Rectangles | Diện Tích Của Các Hình Chữ Nhật

Cho n hình chữ nhật, nhiệm vụ của bạn là xác định tổng diện tích phần hợp của chúng.

Input

Dòng đầu vào đầu tiên chứa một số nguyên n: số lượng hình chữ nhật.

Sau đó, có n dòng mô tả các hình chữ nhật. Mỗi dòng chứa bốn số nguyên x_1, y_1, x_2y_2: hình chữ nhật bắt đầu tại điểm (x_1, y_1) và kết thúc tại điểm (x_2, y_2).

Output

In tổng diện tích được che phủ bởi các hình chữ nhật.

Constraints

  • 1 \leq n \leq 10 ^ 5
  • -10 ^ 6 \leq x_1 \leq x_2 \leq 10 ^ 6
  • -10 ^ 6 \leq y_1 \leq y_2 \leq 10 ^ 6

Example

Input:

3  
1 3 4 5  
3 1 7 4  
5 3 8 6

Output:

24