ntucoder – VERSUSGAME – Trò chơi đối kháng

1. Nội dung đề bài

• Dữ liệu vào: standard input
• Dữ liệu ra: standard output
• Giới hạn thời gian: 1.0 giây
• Giới hạn bộ nhớ: 128 megabyte

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 <= 10⁵)

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 <= 10⁶)

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

2. Hiểu đề bài như thế nào?

Ví dụ:

//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.

3. Cách tui giải và code

Kỹ năng	Đấm	Nhảy	Đẩy	Kéo	Đá Trên 0	Đá
index	1	2	3	4	5	6
value	5	4	4	3	1	10

---

Đâ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	Đá	Đấm	Nhảy	Đẩy	Kéo	Đá Trên  0
index	1	2	3	4	5	6
value	10	5	4	4	3	1

---

Bảng quy tắc như sau:

Kỹ năng	Đá	Đấm	Nhảy	Đẩy	Kéo	Đá Trên  0
index	1	2	3	4	5	6
value	-1	1	2	6	-1	-1

---

Từ những dữ liệu trên ta xây dựng được bảng như sau:

Value	1	3	5	10	15	19
Cần ? kỹ năng	1	1	2	1	2	3

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ó min₁ = 1 là cần 1 kỹ năng, vậy 2 thì min₁ cộng với 1 nữa là 2.

3 thì min₂+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 => min₃ = 1.

4 thì min₃+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) = min_{1 + 1} = 2. => min₄=2.

5 thì min₄+1 = 3. Mà giờ t có 1, 3, 5 thì tui làm với 3 trước min_{(5-3 =2)}+1 = min₂+ 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ị) = min₀+2= 2. Do đó min₅ = 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;
}
    

4. Các test case cho đề bài

#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

Kết Luận

Bài viết sau mình sẽ chia sẻ với các bạn ROBOT5 – Robot đi tuần nhé.