Untitled

mail@pastecode.io avatar
unknown
plain_text
a year ago
11 kB
3
Indexable
Hugo Về Nhà
 

Hugo đang trền đường về nhà và cần đi qua 1 đoạn đường B.

Trên đoạn đường đi qua có N cổng. Tại mỗi cổng có 1 số lượng binh sĩ và giá để đi qua cổng đó. Muốn đi qua mỗi cổng Hugo có 3 cách lựa chọn.

1. Pass

Trả số tiền quy định ở cổng đó để được đi qua

2. Hire

Trả gấp đôi số tiền ở cổng đó để thuê số binh sĩ gộp vào đoàn quân của mình

3. battle

Điều kiện để đánh nhau là số quân của Hugo >= số lượng lính tại cổng đó. Có các lưu ý:

+ Hugo k được tính vào số lượng của quân

+ Mỗi người lính chỉ tham gia được vào tối đa 3 trận đánh. Sau 3 trận đánh nếu đi nhóm binh sĩ đó còn sống thì cũng giải tán.

+ Mỗi trận đánh thì tất cả số binh sĩ đều tham gia.

+ Đánh nhau chết theo tỉ lệ 1: 1. Ai tham gia trước sẽ bị chết trước

Input:
Dòng đầu tiên là số lượng trường hợp thử nghiệm

Mỗi trường hợp thử nghiệm sẽ có
          Dòng đầu tiên chứa số lượng cổng N

          N dòng tiếp theo chứa 2 số là số binh lính và chi phí tại mỗi cổng

Output: In ra chi phí nhỏ nhất Hugo có thể đi qua đoạn đường B

Điều kiện input: số cổng <=20

-      2 <=Số lính và chi phí đi qua <=1000

VD:

Input
2

7

10 100

70 5

80 15

20 60

50 90

30 80

10 10

9

600 800

300 400

300 400

1000 400

300 600

100 300

600 300

600 500

1000 300

 

Output:

#1 150

#2 3000
=------------------------------------------------------------------=
Hugo Xếp Lịch Quảng Cáo
Hugo’s shop need to display the advertisement 3 times a day.

However, they only has 1 electric board to display the advertisement, hence they should select the time to display advertisements so that visitors can watch them as much as possible.

 

When visitors watch advertisement, they can get points which calculated as below :

1. Three Ads  have length L1, L2, L3 and the points a person can get after watched them P1, P2, P3.

2. A visitor can get the point of a Ads  only when he/she watch the Ads  fully (from beginning to the end of that Ads )

3. When a visitor watch more than one Ads  and also get the point for them, only the Ads  with highest point will be given to that person.

4. Only one Ads  can be displayed on electric board at a time (But the next Ads  can be displayed right after the previous one ended)

 

Given the length of each Ads L1, L2, L3 and the point gained for them P1, P2, P3, the arrival time of each visitor into the shop and the time duration that he/she stay in the shop, write a program to select advertisement display time so that as many points as possible can be given to visitors. Print out the total sum of points that the visitors can get.[Constraints]

- The number of visitors N (1 ≤ N ≤ 50)

- The arrival time Ai, the time duration Di of each visitor and the length of each Ads L1, L2, L3 are given as integers (1 ≤ Ai, Di, L1, L2, L3 ≤ 50)

- Ai + Di ≤ 50

- L1 + L2 + L3 ≤ 50

- The starting time of an Ads : 1 ≤ starting time ≤ 50

- P1, P2, P4 are integers (1 ≤ P1, P2, P3 ≤ 1000)

 

[Input]

The 1st line given T - the total number of TC (T ≤ 50)

In each TC :

 - The 1st line contains N, L1, L2, L3, P1, P2, P3 in this order

 - The next N lines : each line gives the arrival time Ai and time duration Di of each visitor

5                         // Number of test cases T=5

7 1 2 3 1 2 3         // Test case 1 N=7, L1=1, L2=2, L3=3, P1=1, P2=2, P3=3

2 2                       // A1 = 2, D1 = 2

6 4                       // ...

3 3

7 2

1 1

2 1

1 10

4 3 2 1 6 4 3

1 5

1 3

2 4

2 2
[Output]

Out put the maximum sum of points that visitors can get from watching advertisements.

Case #1

12

Case #2

18

Case #3

17

Case #4

16

Case #5

17998
=================================================================================================
Đi tàu

Trên một con tàu có N vị trí ngồi, Có 3 cửa để lên tàu. Hành khách đang đợi ở mỗi cửa là khác nhau

 

 

1

2

3

4

5

6

7

8

9

10

Vị trí

 

 

 

 

 

 

 

 

 

 

Khoảng cách

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Cửa 1

 

Cửa 2

 

 

 

Cửa 3

 

Để tránh xung đột và rối loạn, hành khách lên tàu cần thực hiện như sau:
1. Chỉ 1 cửa được mở tại một thời điểm, khi cửa mở tất cả hành khách sẽ được lên tàu.

2. Khi cửa mở, lần lượt hành khách sẽ được lên tàu, và hành khách sẽ đi tới vị trí trống gần nhất từ vị trí cửa

+ Khoảng cách từ cửa tới vị trí ngồi đối diện cửa là 1m. (Vị trí ngồi tại vị trí cửa)

+ Khi hành khách đi xa hơn một vị trí (sang trái hoặc sang phải), sẽ mất thêm 1m

Ví dụ: Vị trí cửa là 4, khoảng cách đến vị trí ngồi 4 là 1m, đến vị trí ngồi 3, 5 là 2m

3. Nếu có 2 vị trí ngồi trống gần nhất, hành khách có thể chọn bất kỳ chỗ nào (Bạn cần xem xét trường hợp này).

4. Sau khi 1 cửa được mở và hành khách đã lên tàu hết thì tiếp tục mở cửa tiếp theo cho hành khách lên tàu theo cách bên trên

 

Bạn cần tìm cách để tổng khoảng cách tất cả hành khách di chuyển là nhỏ nhất và viết ra..

Ex) Trong bảng bên dưới :

- Số lượng vị trí ngồi của tàu là : 10

- Cửa 1 : vị trí là 4, Số hành khác đang chờ lên tàu là 5

- Cửa 2 : vị trí là 6, Số hành khách đang chờ lên tàu là 2

- Cửa 3 : vị trí là 10, Số hành khách đang chờ lên tàu là 2

 

Trường hợp 1) Chúng ta mở các cửa theo thứ tự : Cửa 1 > Cửa 2 > Cửa 3

Khi cửa  1 mở, bảng bên dưới cho thấy khoảng cách và vị trí các hành khách khi lên tàu

 

1

2

3

4

5

6

7

8

9

10

Vị trí

 

G1

G1

G1

G1

G1

 

 

 

 

Khoảng cách

 

3

2

1

2

3

 

 

 

 

 

 

 

 

Cửa 1

 

Cửa 2

 

 

 

Cửa 3

 

Khi cửa  2 mở, bảng bên dưới cho thấy khoảng cách và vị trí các hành khách khi lên tàu

 

1

2

3

4

5

6

7

8

9

10

 

 

G1

G1

G1

G1

G1

G2

G2

 

 

Khoảng cách

 

3

2

1

2

3

2

3

 

 

 

 

 

 

Cửa 1

 

Cửa 2

 

 

 

Cửa 3

 

Khi cửa  3 mở, bảng bên dưới cho thấy khoảng cách và vị trí các hành khách khi lên tàu

 

1

2

3

4

5

6

7

8

9

10

 

 

G1

G1

G1

G1

G1

G2

G2

G3

G3

Khoảng cách

 

3

2

1

2

3

2

3

2

1

 

 

 

 

Cửa 1

 

Cửa 2

 

 

 

Cửa 3

 

Trong trường hợp này tổng khoảng cách hành khách di chuyển là : 3+2+1+2+3+2+3+2+1 = 19

 

Trường hợp 2) Chúng ta mở cửa theo thứ tự : Cửa 2 > Cửa 1 > Cửa 3

Khi mở cửa 2, hành khách đầu tiên sẽ chọn vị trí số 6, hành khách thứ 2 có thể chọn vị trí số 5 hoặc 7

 

 

5

6

7

Position

 

G2

G2

Khoảng cách

 

1

2

 

 

Cửa 2

 

 Hoặc

 

5

6

7

Position

G2

G2

 

Khoảng cách

2

1

 

 

 

Cửa 2

 

 

Trường hợp 2-1)

Khi cửa  2 mở, bảng bên dưới cho thấy khoảng cách và vị trí các hành khách khi lên tàu (hành khách thứ 2 chọn vị trí số 5)

 

1

2

3

4

5

6

7

8

9

10

 

 

 

 

 

G2

G2

 

 

 

 

Khoảng cách

 

 

 

 

2

1

 

 

 

 

 

 

 

 

Cửa 1

 

Cửa 2

 

 

 

Cửa 3

 

Khi cửa  1 mở, bảng bên dưới cho thấy khoảng cách và vị trí các hành khách khi lên tàu

 

1

2

3

4

5

6

7

8

9

10

 

G1

G1

G1

G1

G2

G2

G1

 

 

 

Khoảng cách

4

3

2

1

2

1

4

 

 

 

 

 

 

 

Cửa 1

 

Cửa 2

 

 

 

Cửa 3

 

Khi cửa  3 mở, bảng bên dưới cho thấy khoảng cách và vị trí các hành khách khi lên tàu

 

1

2

3

4

5

6

7

8

9

10

 

G1

G1

G1

G1

G2

G2

G1

 

G3

G3

Khoảng cách

4

3

2

1

2

1

4

 

2

1

 

 

 

 

Cửa 1

 

Cửa 2

 

 

 

Cửa 3

 

Trong trường hợp này, tổng là : 4+3+2+1+2+1+4+2+1 = 20

 

Trường hợp 2-2)

Khi cửa  2 mở, bảng bên dưới cho thấy khoảng cách và vị trí các hành khách khi lên tàu (hành khách thứ 2 chọn vị trí số 7)

 

1

2

3

4

5

6

7

8

9

10

 

 

 

 

 

 

G2

G2

 

 

 

Khoảng cách

 

 

 

 

 

1

2

 

 

 

 

 

 

 

Cửa 1

 

Cửa 2

 

 

 

Cửa 3

 

Khi cửa  1 mở, bảng bên dưới cho thấy khoảng cách và vị trí các hành khách khi lên tàu

 

1

2

3

4

5

6

7

8

9

10

 

G1

G1

G1

G1

G1

G2

G1

 

 

 

Khoảng cách

4

3

2

1

2

1

2

 

 

 

 

 

 

 

Cửa 1

 

Cửa 2

 

 

 

Cửa 3

 

Khi cửa  3 mở, bảng bên dưới cho thấy khoảng cách và vị trí các hành khách khi lên tàu

 

1

2

3

4

5

6

7

8

9

10

 

G1

G1

G1

G1

G1

G2

G1

 

G3

G3

Khoảng cách

4

3

2

1

2

1

2

 

2

1

 

 

 

 

Cửa 1

 

Cửa 2

 

 

 

Cửa 3

 

Trong trường hợp này, tổng là : 4+3+2+1+2+1+2+2+1 = 18

 

[Đầu vào]

- Dòng đầu tiên chứa số trường hợp thử nghiệm T (T <= 50)

- Mỗi trường hợp thử nghiệm:

          + Dòng đầu tiên chưa số ghế trên tàu N (10 <= N <= 60)

          + 3 dòng tiếp theo chưa thông tin của 3 cửa lên tàu :

                    > Vị trí cửa P ( 1 <= P <= N)

                    > Số lượng hành khách đang chờ ở cửa C ( 1 <= C <= 20 )

 

[Đầu ra]

Tổng di chuyển nhỏ nhất của tất cả các hành khách

Case #1

18

Case #2

25

Case #3

57

Case #4

86

Case #5

339
=====================================================================================================
Leave a Comment