nổi tiếng là 1 người đẹp trai còn hơn cả Sơn Tùng, tài hoa, lãng tử, là ước mơ của biết bao cô gái. Không những chỉ đẹp trai mà anh còn rất thông minh. có 1 sở thích là ra những bài toán. Hôm nay thách đố mọi cô gái trong vùng giải 1 bài toán, nếu ai giải được sẽ làm vợ của . Lisa là 1 cô gái xinh đẹp, tài giỏi, sinh ra trong đại gia tộc “Blinkpack”, hơn nữa cô đã crush từ lâu. Lần này là cơ hội tốt để làm vợ , mỗi tội thế mạnh của cô là nhảy hát chứ không phải giải toán nên Lisa muốn nhờ các bạn giải bài toán này hộ cô ấy.
Bài toán là cho 2 số tự nhiên \(l,r(l≤ r ≤10^{3})\), hãy đếm số lượng hình chữ nhật có 2 cạnh nằm trong khoảng từ \(l\) đến \(r\). 2 hình chữ nhật được tính là khác nhau nếu chiều rộng hoặc chiều dài của chúng khác nhau.
Yêu cầu: Hãy đếm số lượng hình chữ nhật thỏa mãn đề bài.
Test 1
1 23có các hình chữ nhật là \([1,1]; [2,2]; [1,2].\)
Test 2
2 46có các hình chữ nhật là \([2,4]; [2,3]; [3,3]; [4,4]; [2,2]; [3,4].\)
Hôm nay , ông trùm của tổ chức “Code ver 4.0” tổ chức \(1\) cuộc lọc thành viên. Để có thể ở lại tổ chức các thành viên phải giải 1 bài toán do ông trùm đưa ra. Bài toán là cho \(1\) số tự nhiên \(N (N≤10^7)\), các thành viên phải đưa ra số tam giác có \(3\) cạnh nguyên sao cho \(N\) là cạnh lớn nhất của tam giác (lớn nhất ở đây là lớn hơn hẳn). Rose là \(1\) thành viên mới của tổ chức, khổ nỗi do cô vừa mới đi làm MV "How that like you" nên đã quên hết kiến thức, vì rất sự bị loại nên cô muốn nhờ bạn giúp. Nếu giúp được cô ấy thì bạn sẽ được thưởng một nụ hôn đấy !
Subtask \(1\) (\(40\%\) số điểm): \(N≤10^4\).
Subtask \(2\) (\(60\%\) số điểm): \(N≤10^7\).
Test 1
31Test 2
42nổi tiếng là 1 người đẹp trai còn hơn cả Sơn Tùng, tài hoa, lãng tử, là ước mơ của biết bao cô gái. Không những chỉ đẹp trai mà anh còn rất thông minh. có 1 sở thích là ra những bài toán. Hôm nay thách đố mọi cô gái trong vùng giải 1 bài toán, nếu ai giải được sẽ làm vợ của . Lisa là 1 cô gái xinh đẹp, tài giỏi, sinh ra trong đại gia tộc “Blinkpack”, hơn nữa cô đã crush từ lâu. Lần này là cơ hội tốt để làm vợ , mỗi tội thế mạnh của cô là nhảy hát chứ không phải giải toán nên Lisa muốn nhờ các bạn giải bài toán này hộ cô ấy.
Bài toán là cho 2 số tự nhiên \(l,r(l\leq r \leq10^{18})\), hãy đếm số lượng hình chữ nhật có 2 cạnh nằm trong khoảng từ \(l\) đến \(r\). 2 hình chữ nhật được tính là khác nhau nếu chiều rộng hoặc chiều dài của chúng khác nhau.
Vì kết quả có thể rất lớn nên hãy in ra phần dư khi chia cho \(10^9+7.\)
Yêu cầu: Hãy đếm số lượng hình chữ nhật thỏa mãn đề bài.
Test 1
1 23có các hình chữ nhật là \([1,1]; [2,2]; [1,2].\)
Test 2
2 46có các hình chữ nhật là \([2,4]; [2,3]; [3,3]; [4,4]; [2,2]; [3,4].\)
Hôm nay và , \(2\) nam thần của làng K-pop đang đi chơi với nhau. May mắn thay họ gặp 1 cô em gái xinh đẹp tên là Jennie. Jennie vốn đã hâm mộ \(2\) người từ lâu nên đã đố họ \(1\) bài toán. Ai giải ra trươc là sẽ là người được đi chơi, hẹn hò với Jennie.
Bài toán là cho 1 dãy số nguyên dương \(A_1, A_2,…,A_n (n≤10^6, A_i≤10^9)\). 1 dãy con liên tiếp không rỗng của \(A\) được xem là dãy “ngu ngốc“ khi tổng phần tử của dãy con đó chia hết cho số nguyên dương \(k (1≤ k ≤10^6)\). Jennie đố và hãy tìm cách chia dãy \(A\) thành \(2\) dãy con “ngu ngốc” không giao nhau sao cho tổng độ dài \(2\) dãy là lớn nhất. rất muốn được hẹn hò với Jennie nhưng vì mải ngắm nhìn nhan sắc tuyệt trần của cô nên anh không có tâm trí nào mà giải toán nữa. Bạn hãy giúp nhé !
Subtask \(1\) (\(50\%\) số điểm): có \(n≤10^4\).
Subtask \(2\) (\(50\%\) số điểm): không có ràng buộc gì thêm.
Test 1
3 2
1 2 30không có cách chia.
Test 1
4 2
1 2 3 44chia 2 dãy \([1,2,3]\) và \([4]\).
Một hôm và đang đi chơi thì bị lạc vào một khu rừng tăm tối , đi được một hồi thì gặp người đàn ông , \(2\) người hỏi lối ra của khu rừng thì ông ta nói rằng nếu giải được bài toán này thì cả hai người đều được chỉ lối thoát , còn không thì một trong hai người phải ở lại . Vì tính đoàn kết nên hai người này nhất quyết phải thoát ra ngoài cùng nhau . Hãy giúp hai anh chàng này thoát ra khỏi khu rừng nhé !
Bài toán như sau : Cho một dãy số nguyên \(A\) gồm \(n\) phần tử và một số nguyên \(k\) , hãy chia dãy số thành các dãy con không giao nhau sao cho các dãy con có tổng bằng \(k\) là nhiều nhất .
Ví dụ : Dãy số là { 2 , 1 , 1 , 1 , 1 , 2 } và \(k =\) 4 ;
Chúng ta sẽ chia dãy thành {2,1,1} và {1,1,2} => có hai dãy con có tổng bằng k.
Yêu cầu : Hãy đưa ra số lượng dãy có tổng bằng \(k\) khi chia tối ưu.
Test 1
6 4
2 1 1 1 1 22Test 2
7 3
1 3 2 1 1 1 23chúng ta sẽ chia dãy thành {1},{3},{2,1},{1},{1,2} , như vậy ta sẽ có được \(3\) dãy con có tổng bằng \(k\).
Hôm nay , người mạnh nhất dòng họ Joseph, đang có trận chiến với boss cuối Dio để giải cứu crush của anh là Jisoo, để đánh bại Dio thì phải giải bài toán sau.
Bài toán là cho \(1\) dãy số nguyên dương \(A_1, A_2,….,A_n (A_i≤10^6, n≤10^5)\). Bộ chỉ số “The world” của dãy A là bộ các chỉ số \(i_1<i_2<i_3…<i_k\) \((2 ≤ k ≤ 10,i_j ≤ n)\) sao cho \(A_{i1}<A_{i2}, A_{i2}>A_{i3}, A_{i3}<A_{i4}, A_{i4}>A_{i5},….\) Cụ thể là \(A_{ij} < A_{ij+1}\) với \(j\) lẻ và ngược lại với \(j\) chẵn. cần bạn giúp đếm tất cả bộ chỉ số “The world” của dãy \(A\), hai bộ chỉ số sẽ khác nhau nếu có 1 vị trí trong hai bộ có chỉ số khác nhau. tuy rằng có stand mạnh nhất thế giới nhưng cậu ấy lại khá ngu toán. Hãy giúp cậu ấy nhé !
Vì kết quả có thể rất lớn nên hãy in ra phần dư khi chia cho \(10^9+7\).
Yêu cầu: đếm số lượng bộ chỉ số “The world” của dãy \(A\).
Dòng đầu tiên lần lượt là \(n, k\).
Dòng tiếp theo là dãy \(A\).
Subtask \(1\) (\(40\%\) số điểm): \(k=2, n \le 1000\).
Subtask \(2\) (\(60\%\) số điểm) không có ràng buộc gì thêm.
Test 1
4 3
1 2 1 51bộ chỉ số duy nhất là \([1,2,3]\)
Giới hạn:
40% test có \(k=2, n≤1000\).
60% test không có ràng buộc gì thêm.