Trần Đức Trung
(Tonghophoa)
New Member
Mọi người có ai giỏi lập trình thì giải giúp em bài này với. Xin lỗi vì đề bài hơi dài lại bằng tiếng Anh.
You are given a set of 2n dominos, where n < 1000 is an integer. The dominos have width 1 and length 2. It is possible to arrange these dominos in such a way that they form a 4 × n rectangle. For instance, in Figure 1, we have arranged 12 dominos to form a 4 × 6 rectangle.
In fact, where n > 1, there are several ways of arranging dominos to form a 4 × n rectangle. For instance, in Figure 2, you can see the 5 different ways of forming a 4 × 2 rectangle:
Figure 2: The 5 different ways of forming a 4 × 2 rectangle.
We denote by Rn the number of different ways of forming a 4 × n rectangle with 2n dominos. For instance, R2 = 5, as you can see in Figure 2. As Rn can be quite large, even for small values of n, you are only asked to compute the last three digits of Rn. Your program should output the value of the last three digits of Rn without leading zeros. For instance, R17 = 26915305, so when n = 17, your program should output 305 (the last three digits). Another example, R2 = 5 (or 005), so when n = 2, your program should output 5. Should the last three digits be zeros for some Rn, your program should simply output 0.
Input
The file DOMINO.IN contains the integer n. Remember that n < 1000.
Output
You should write an integer giving the value of the last three digits of Rn without leading zeros in the output file DOMINO.OUT. (Note that the output value is simply the value Rn mod 1000; that is, the remainder of Rn divided by 1000.)
Input/Output Examples
For the example R2 = 5, the input and output files contain
Sample input 1
2
Sample output 1
5
For the example R17 = 26915305, the input and output files contain
Sample input 2
17
Sample output 2
305
Xin lỗi mọi người vì không đưa được mấy cái hình ví dụ lên. Em sẽ cố đưa lên sau. Bài này trích từ đề Olympic tin học của Sing, 2004. Giới hạn thời gian là 5 giây.
You are given a set of 2n dominos, where n < 1000 is an integer. The dominos have width 1 and length 2. It is possible to arrange these dominos in such a way that they form a 4 × n rectangle. For instance, in Figure 1, we have arranged 12 dominos to form a 4 × 6 rectangle.
In fact, where n > 1, there are several ways of arranging dominos to form a 4 × n rectangle. For instance, in Figure 2, you can see the 5 different ways of forming a 4 × 2 rectangle:
Figure 2: The 5 different ways of forming a 4 × 2 rectangle.
We denote by Rn the number of different ways of forming a 4 × n rectangle with 2n dominos. For instance, R2 = 5, as you can see in Figure 2. As Rn can be quite large, even for small values of n, you are only asked to compute the last three digits of Rn. Your program should output the value of the last three digits of Rn without leading zeros. For instance, R17 = 26915305, so when n = 17, your program should output 305 (the last three digits). Another example, R2 = 5 (or 005), so when n = 2, your program should output 5. Should the last three digits be zeros for some Rn, your program should simply output 0.
Input
The file DOMINO.IN contains the integer n. Remember that n < 1000.
Output
You should write an integer giving the value of the last three digits of Rn without leading zeros in the output file DOMINO.OUT. (Note that the output value is simply the value Rn mod 1000; that is, the remainder of Rn divided by 1000.)
Input/Output Examples
For the example R2 = 5, the input and output files contain
Sample input 1
2
Sample output 1
5
For the example R17 = 26915305, the input and output files contain
Sample input 2
17
Sample output 2
305
Xin lỗi mọi người vì không đưa được mấy cái hình ví dụ lên. Em sẽ cố đưa lên sau. Bài này trích từ đề Olympic tin học của Sing, 2004. Giới hạn thời gian là 5 giây.
Chỉnh sửa lần cuối:
)
