Hùng đang chơi một trò chơi võ thuật đối kháng, trong trò chơi này, bạn sẽ phải đánh bại các đối thủ bằng các kỹ năng của mình, ở mỗi vòng bạn sẽ thi đấu với một đối thủ, mỗi lần thi triển kỹ năng, bạn nhận được một số điểm kỹ năng nhất định. Đặc biệt, trong trò chơi này, nếu bạn đã đánh bại đối thủ thì bạn chưa chắc đã chiến thắng, bạn còn phải đạt được chính xác số điểm kỹ năng mà đối thủ quy định sao cho số lần thi triển kỹ năng là ít nhất. Sau đây là các kỹ năng bạn có thể sử dụng và số điểm kỹ năng giành được khi thi triển:
++ Đấm: sau khi đấm bạn sẽ có thêm 5 điểm
++ Nhảy: sau khi nhảy bạn sẽ có thêm 4 điểm
++ Đẩy: sau khi đẩy bạn sẽ có thêm 4 điểm
++ Kéo: sau khi kéo bạn sẽ có thêm 3 điểm
++ Đá trên không: sau khi đá trên không bạn sẽ có thêm 1 điểm
++ Đá: sau khi đá bạn sẽ có thêm 10 điểm
Tuy nhiên, các kỹ năng này không thể sử dụng một cách tùy ý mà nó còn có những quy tắc nhất định:
++ Sau khi đấm, bạn bắt buộc phải đá.
++ Sau khi nhảy, bạn bắt buộc phải đấm.
++ Sau khi đẩy, bạn bắt buộc phải đá trên không.
Vì mải chơi nên không thể tính toán được, bạn hãy giúp Hùng tính cách chơi tối ưu nhất nhé.
Input
Dòng thứ nhất là số nguyên T – số vòng của trò chơi (1 <= T <= 105)
T dòng tiếp theo, mỗi dòng là số nguyên N là số điểm kỹ năng bạn phải đạt được trong vòng chơi tương ứng (1 <= N <= 106)
Output
Gồm T dòng, mỗi dòng là số lần thi triển kỹ năng ít nhất để đạt được chính xác số điểm kỹ năng mà vòng chơi đó yêu cầu
//input 4 1 2 3 4 //output 1 2 1 2
Như dữ liệu, ta thấy có 4 vòng chơi:
– Vòng 1: số điểm chính xác đạt được là: 1
=>chỉ có 1 phương án là đá trên không.
– Vòng 2: số điểm chính xác đạt được là: 2
=>chỉ có 1 phương án là 2 lần đá trên không.
– Vòng 3: số điểm chính xác đạt được là: 3
=>chỉ có 2 phương án là 3 lần đá trên không và 1 lần kéo. Do đó đáp án là 1
– Vòng 4: số điểm chính xác đạt được là: 4
=>chỉ có 2 phương án là 4 đá trên không và (1 kéo + 1 đá trên không). Do đó đáp án là 2.
Ở vòng 4 bạn không thể chọn nhảy hoặc đẩy. Vì chọn nhảy bạn phải đấm => 9, còn đẩy bạn phải đá trên không => 5. Do đó loại 2 đáp án này.
Kỹ năngĐấmNhảyĐẩyKéoĐá Trên 0Đáindex123456value5443110Đây là dữ liệu ban đầu, giờ tui sẽ biến nó lại thành theo thứ tự giảm dần.
Kỹ năngĐáĐấmNhảyĐẩyKéoĐá Trên 0index123456value1054431Bảng quy tắc như sau:
Kỹ năngĐáĐấmNhảyĐẩyKéoĐá Trên 0index123456value-1126-1-1Từ những dữ liệu trên ta xây dựng được bảng như sau:
Value135101519Cần ? kỹ năng112123
Ví dụ nếu tui tìm được số trước là min(kỹ năng cần có để đạt được) thì số sau tui thêm 1 vào thì có thể là Số kỹ năng min.
Ban đầu tui chỉ có giá trị 1 để cộng zô.
Giờ tui có min1 = 1 là cần 1 kỹ năng, vậy 2 thì min1 cộng với 1 nữa là 2.
3 thì min2+1 = 3. Nhưng giờ t có giá trị là 1 và 3 để cộng zô. Zậy t chỉ cần lấy 1 kỹ năng có giá trị 3 là được value đề bài yêu cầu => min3 = 1.
4 thì min3+1 = 2. Mà giờ tui có giá trị 1 và 3 vậy tui chọn 3. min(4-3 =1)+1(kỹ năng có giá trị 3) = min1 + 1 = 2. => min4=2.
5 thì min4+1 = 3. Mà giờ t có 1, 3, 5 thì tui làm với 3 trước min(5-3 =2)+1 = min2+ 1 = 3. Tiếp tục tui thử với min(5-5 =0)+2(do 2 kỹ năng tạo nên giá trị) = min0+2= 2. Do đó min5 = 2.
#include <bits/stdc++.h>
#define IO ios_base::sync_with_stdio(false);
using namespace std;
const int SIZE = 10e6+1;
int T, n;
int f[SIZE];
void process()
{
f[1] = 1;
f[2] = 2;
for (int i = 3; i <= SIZE; ++i) {
f[i] = f[i-1] + 1;
if (i >= 3) f[i] = min(f[i], f[i-3]+1);
if (i >= 5) f[i] = min(f[i], f[i-5]+2);
if (i >= 10) f[i] = min(f[i], f[i-10]+1);
if (i >= 15) f[i] = min(f[i],f[i-15]+2);
if (i >= 19) f[i] = min(f[i],f[i-19]+3);
}
}
int main()
{
IO;
process();
cin >> T;
while (T--) {
cin >> n;
cout << f[n] << endl;
}
return 0;
}
#test1 //input 10 808 250 74 659 931 273 545 879 924 710 //output 82 25 9 67 94 28 55 89 94 71 #test2 //Input 20 808 250 74 659 931 273 545 879 924 710 441 166 493 43 988 504 328 730 841 613 //Output 82 25 9 67 94 28 55 89 94 71 45 18 50 5 100 52 34 73 85 62 #test3 //Input 100 6808 5250 74 3659 8931 1273 7545 879 7924 7710 4441 8166 4493 3043 7988 2504 2328 1730 8841 2613 4304 3170 7710 7158 9561 934 3100 279 1817 5336 9098 7827 3513 9268 3811 7634 980 9150 6580 8822 1968 673 1394 9337 5486 1746 5229 4092 195 6358 5002 1154 6709 7945 5669 1491 8125 2197 9531 904 7723 4667 8550 8025 7802 6854 978 7409 8229 4934 299 8982 8636 8014 3866 9815 9064 4537 9426 1670 4116 ... //Output 682 525 9 367 894 128 755 89 794 771 445 818 450 305 800 252 234 173 885 262 432 317 771 717 957 95 310 29 184 535 911 785 352 928 382 765 98 915 658 884 198 6... #test4 //Input 100000 6808 5250 74 3659 8931 1273 7545 879 7924 7710 4441 8166 4493 3043 7988 2504 2328 1730 8841 2613 4304 3170 7710 7158 9561 934 3100 279 1817 5336 9098 7827 3513 9268 3811 7634 980 9150 6580 8822 1968 673 1394 9337 5486 1746 5229 4092 195 6358 5002 1154 6709 7945 5669 1491 8125 2197 9531 904 7723 4667 8550 8025 7802 6854 978 7409 8229 4934 299 8982 8636 8014 3866 9815 9064 4537 9426 1670 41 ... //Output 682 525 9 367 894 128 755 89 794 771 445 818 450 305 800 252 234 173 885 262 432 317 771 717 957 95 310 29 184 535 911 785 352 928 382 765 98 915 658 884 198 6... #test5 //Input 10 475249 612001 905329 420964 744900 857984 671936 370884 193929 568681 //Output 47526 61201 90534 42098 74490 85800 67195 37090 19394 56869 #test6 //Input 100 475249 612001 905329 420964 744900 857984 671936 370884 193929 568681 513600 567225 498064 413764 992169 385009 534929 729441 745600 782544 755809 582561 8681 482649 793600 490489 623801 757284 497856 762225 415409 846276 974144 157289 916100 682689 598441 964201 623241 910041 209089 891584 340449 480896 485225 145025 851984 716281 357636 931449 70001 849409 757264 907136 486224 820100 43937 ... //Output 47526 61201 90534 42098 74490 85800 67195 37090 19394 56869 51360 56723 49808 41378 99218 38502 53494 72945 74560 78256 75582 58257 869 48266 79360 49050 62381 75730 49787 ... #test7 //Input 1000 475249 612001 905329 420964 744900 857984 671936 370884 193929 568681 513600 567225 498064 413764 992169 385009 534929 729441 745600 782544 755809 582561 8681 482649 793600 490489 623801 757284 497856 762225 415409 846276 974144 157289 916100 682689 598441 964201 623241 910041 209089 891584 340449 480896 485225 145025 851984 716281 357636 931449 70001 849409 757264 907136 486224 820100 4393 ... //Output 47526 61201 90534 42098 74490 85800 67195 37090 19394 56869 51360 56723 49808 41378 99218 38502 53494 72945 74560 78256 75582 58257 869 48266 79360 49050 62381 75730 49787 ... #test8 //Input 10000 475249 612001 905329 420964 744900 857984 671936 370884 193929 568681 513600 567225 498064 413764 992169 385009 534929 729441 745600 782544 755809 582561 8681 482649 793600 490489 623801 757284 497856 762225 415409 846276 974144 157289 916100 682689 598441 964201 623241 910041 209089 891584 340449 480896 485225 145025 851984 716281 357636 931449 70001 849409 757264 907136 486224 820100 439 ... //Output 47526 61201 90534 42098 74490 85800 67195 37090 19394 56869 51360 56723 49808 41378 99218 38502 53494 72945 74560 78256 75582 58257 869 48266 79360 49050 62381 75730 49787 ... #test9 //Input 100000 475249 612001 905329 420964 744900 857984 671936 370884 193929 568681 513600 567225 498064 413764 992169 385009 534929 729441 745600 782544 755809 582561 8681 482649 793600 490489 623801 757284 497856 762225 415409 846276 974144 157289 916100 682689 598441 964201 623241 910041 209089 891584 340449 480896 485225 145025 851984 716281 357636 931449 70001 849409 757264 907136 486224 820100 43 ... //Output 47526 61201 90534 42098 74490 85800 67195 37090 19394 56869 51360 56723 49808 41378 99218 38502 53494 72945 74560 78256 75582 58257 869 48266 79360 49050 62381 75730 49787 ... #test10 //Input 10 1 2 3 4 5 6 7 8 100000 100001 //Output 1 2 1 2 2 2 3 3 10000 10001 #test11 //Input 4 1 2 3 4 //Output 1 2 1 2
Bài viết sau mình sẽ chia sẻ với các bạn ROBOT5 – Robot đi tuần nhé.
