Untitled
unknown
plain_text
a year ago
24 kB
19
Indexable
Bai 1: De Men:
Với bản tính hay trêu chọc của mình Dế Choắt đã bị chị cốc nhốt vào trong một khối đất hình lập phương có kích thước NxNxN cm ( 5<= N <= 30),
có một mặt tiếp giáp với mặt đất và 5 mặt khác không tiếp giáp với vật khác.
Để thoát ra khỏi khối đất đó, Dế Choắt cần phải đào đất về phía 1 trong 5 mặt kia, tuy nhiên với thể trạng ốm yếu của mình Dế Choắt không thể đào được quá nhiều đất,
vì vậy Dế Choắt cần tìm một cách đào để thoát ra khỏi khối đất đó sao cho số lượng đất phải đào là ít nhất.
Cho thông tin về khối đất mà Dế Choắt bị nhốt, hãy tìm số lượng cm khối đất ít nhất mà Dế choắt cần phải đào để thoát khỏi khối đất đó.
Time limit: 3 second (Java : 6 sec).
[Input]
Dòng đầu tiên là số lượng test case T (T <= 50).
Mỗi test case bắt đầu bằng số N là kích thước của khối đất hình hộp chữ nhật.
Tiếp theo là N lát cắt liên tiếp của hình hộp lập phương, mỗi lát cắt được tách nhau bởi một dòng.
Lưu ý: Mỗi lát cắt được cắt từ trên xuống dưới tới phần tiếp xúc với mặt đất có kích thước NxNx1, được biểu thị dưới dạng một ma trận nhị phân vuông kích thước NxN,
giá trị 2 biểu thị vị trí Dế Choắt bị nhốt, 1 biểu thị vùng đó là đất, phần tử 0 biểu thị vùng đó rỗng. Ví dụ dưới đây là một lát cắt của hình hộp lập phương kích thước 5x5x5.
1 1 1 1 1 <- tầng trên cùng
1 1 1 0 1
0 1 0 0 1
1 1 1 1 1
1 1 1 1 1 <- tầng tiếp giáp với mặt đất
[Output]
In mỗi test case trên một dòng, bắt đầu là "#x", với x là số thứ tự của test case, tiếp là một dấu cách và số lượng cm khối đất ít nhất mà Dế Choắt cần đào để thoát khỏi khối đất đó.
[Sample]
Input
1
5
1 1 1 1 1
1 1 1 0 1
0 1 0 0 1
1 1 1 1 1
1 1 1 1 1
1 1 1 1 0
1 0 1 1 0
1 1 1 1 1
1 1 1 1 1
1 1 1 0 1
1 1 1 1 1
1 1 0 1 1
1 1 2 1 0
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
0 1 1 1 1
1 1 0 1 1
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
Output
#1 1
Code:
#include <iostream>
using namespace std;
#define inf 1000000
#define Size 31
int N;
int A[Size][Size][Size];
int D[Size][Size][Size];
int Q[inf], front, rear;
int Ans;
int sx,sy,sz;
int dx[6] = {1, -1, 0, 0, 0, 0};
int dy[6] = {0, 0, 1, -1, 0, 0};
int dz[6] = {0, 0, 0, 0, 1, -1};
void BFS(int a, int b, int c)
{
front = rear = 0;
Q[rear++] = a;
Q[rear++] = b;
Q[rear++] = c;
D[a][b][c] = 0;
while(front != rear)
{
int z = Q[front++];
int x = Q[front++];
int y = Q[front++];
for(int i = 0; i<6; i++)
{
int X = x + dx[i];
int Y = y + dy[i];
int Z = z + dz[i];
if(X<=0 || Y<=0 || X>N || Y>N || Z<=0 || Z>N || A[Z][X][Y] == 2 ) continue;
int temp = D[z][x][y] + A[Z][X][Y];
if(temp < D[Z][X][Y])
{
D[Z][X][Y] = temp;
Q[rear++] = Z;
Q[rear++] = X;
Q[rear++] = Y;
}
}
/*for(int i = 0; i<2; i++)
{
int Z = z + dz[i];
if(Z<=0 || Z>N || A[Z][x][y] == 2) continue;
int temp = D[z][x][y] + A[Z][x][y];
if(temp < D[Z][x][y])
{
D[Z][x][y] = temp;
Q[rear++] = Z;
Q[rear++] = x;
Q[rear++] = y;
}
}*/
}
}
void Check()
{
for(int i = 1; i <= N; i ++)
for(int j = 1; j <= N; j++)
{
if(D[1][i][j]!= inf && D[1][i][j] < Ans) Ans = D[1][i][j];
if(D[N][i][j]!= inf && D[N][i][j] < Ans) Ans = D[N][i][j];
if(D[i][1][j] != inf && D[i][1][j] < Ans) Ans = D[i][1][j];
if(D[i][j][1] != inf && D[i][j][1] < Ans) Ans = D[i][j][1];
if(D[i][j][N]!= inf && D[i][j][N] < Ans) Ans = D[i][j][N];
}
}
int main()
{
freopen("Demen.txt", "r", stdin);
int T;
cin >> T;
int tc;
for (tc = 1; tc <= T; tc ++)
{
cin >> N;
for(int i = 1; i <= N; i++)
{
for (int j = 1; j<= N; j++)
{
for(int k = 1; k <=N; k ++)
{
cin >> A[i][j][k];
D[i][j][k] = inf;
if(A[i][j][k] == 2)
{
sz = i;
sx = j;
sy = k;
}
}
}
}
Ans = inf;
BFS(sz,sx,sy);
Check();
cout << "#" << tc << " " << Ans << endl;
}
return 0;
}
Bai 2: [Restrictions]
Execution Time 10 sec (C/C++) / 10 sec (Java, Python) for 10 test cases combined
Memory Limit Maximum 256MB available for heap and stack combined (note: Maximum 1MB can be used for stack).
On a hot summer day, Paul and his friends decided to travel to Jeju Island and Paul inadvertently became in charge of planning…!
Paul and his friends have already picked out places that they want to visit, and will decide in what order they will visit the locations during their vacation period.
However, Paul started to panic since there were many places to visit but not enough time…!
Since Paul wanted to plan a satisfying trip for his friends, he decided to ask for help from a travel consultant.
You must help Paul plan a trip that will get the highest satisfaction level within the conditions given below.
1. Find the satisfaction level and travel route from the first day of arrival at the airport to the Mth day of departure at the airport
2. There are total of N number of locations that can be visited including the airport, hotel, and tourist points.
3. Each tourist point has a predetermined satisfaction level and a designated touring time. Also, you cannot revisit any of the tourist points once you have visited them.
4. There are roads that connect the tourist points, and there is a designated travel time. Also, you cannot take a detour.
5. Time spent on travel + touring cannot be more than 9 hours. You must be at the hotel before the given 9 hours are up. Whether you stay at the same hotel or a different hotel is irrelevant.
6. You may use 9 hours on the Mth day, but must be at the airport before time is up.
[Conditions]
1. The number of locations (N) is greater than or equal to 3 and less than or equal to 35. (3≤N≤35)
2. The vacation period (M) is greater than or equal to 1 and less than or equal to 5. (1≤M≤5)
3. There is only one airport.
4. The travel time between each location will be counted in minutes, and it must be greater than or equal to 30 minutes and less than or equal to 240 minutes.
5. The touring time at each tourist point will be counted in minutes, and it must be greater than or equal to 30 minutes and less than or equal to 240 minutes.
6. The satisfaction level (S) from each tourist point must be greater than or equal to 1 and less than or equal to 10.
[Input]
The first line contains T, the number of test cases.
The next line will have N number of locations, and M days of vacation period separated by a space.
The next N-1 line will have the travel time between locations.
But on the ith line, the travel time from the ith location to the i+1~Nth location will be separated by a space.
The corresponding route will have the same travel time when going the other way.
The next n lines will have information regarding each location.
The first letter on the ith line, will determine the ith location. (Airport (A), Tourist Point (P), Hotel (H))
Tourist points are separated by a space and in addition, ‘touring time’ and ‘satisfaction level’ will be given.
[Output]
For each test case, print #T.
and separating by a space, and the satisfaction level and route separating by a space.
Print the route separating by space the each location numbers.
If there are no available routes that satisfy the conditions, print the satisfaction level as 0 and do not print the route.
Input Example
1
10 3
60 90 100 110 240 40 30 60 30
60 120 140 200 120 100 60 60
90 110 170 100 100 30 90
50 110 40 80 90 90
70 30 50 90 90
100 140 180 120
40 90 40
100 20
70
A
P 240 6
P 120 4
P 240 5
P 60 4
P 200 6
P 180 1
P 180 1
H
H // Total number of all the test cases
// N number of locations, and M days of vacation period
// Travel time from Location 1 to 2~N
// Travel time from Location 2 to 3~N
// Travel time from Location N-1 to N
// Location 1 is the airport
// Location 2 is a tourist point, and the touring time is 240min and satisfaction level is 6
// Location 9 is the hotel.
Output Example
#1 25 2 3 9 5 6 10 4 1 // Output of 1st TC
Code:
#include<iostream>
#define _CRT_SECURE_NO_WARNINGS
using namespace std;
bool visited[105][105], matrix[105][105];
int m;
int ans;
int dfs(int i, int j)
{
visited[i][j] = true;
if (i == m) return 1;
else {
if (i + 1 <= m && matrix[i + 1][j] == 1 && visited[i + 1][j] == false) {
if (dfs(i + 1, j)) return 1;
}
if (j + 1 <= m && matrix[i][j + 1] == 1 && visited[i][j + 1] == false) {
if (dfs(i, j + 1)) return 1;
}
if (i - 1 > 0 && matrix[i - 1][j] == 1 && visited[i - 1][j] == false) {
if (dfs(i - 1, j)) return 1;
}
if (j - 1 > 0 && matrix[i][j - 1] == 1 && visited[i][j - 1] == false) {
if (dfs(i, j - 1)) return 1;
}
}
return 0;
}
int main(int argc, char** argv)
{
int test_case;
int T;
cin >> T;
for (test_case = 1; test_case <= T; ++test_case)
{
cin >> m;
for (int i = 1; i < 105; i++)
{
for (int j = 1; j < 105; j++)
{
visited[i][j] = false;
matrix[i][j] = 0;
}
}
int count = 0;
int x, y;
while (count < m * m)
{
cin >> x >> y;
count++;
matrix[x][y] = 1;
if (x == 1)
{
if (dfs(x, y))
{
ans = count;
break;
}
}
else
{
if (x + 1 <= m && visited[x + 1][y]) {
if (dfs(x, y))
{
ans = count;
break;
}
}
if (y + 1 <= m && visited[x][y + 1]) {
if (dfs(x, y))
{
ans = count;
break;
}
}
if (x - 1 > 0 && visited[x - 1][y]) {
if (dfs(x, y))
{
ans = count;
break;
}
}
if (y - 1 > 0 && visited[x][y - 1]) {
if (dfs(x, y))
{
ans = count;
break;
}
}
}
}
while (count < m * m)
{
count++;
cin >> x >> y;
}
cout << "#" << test_case << " " << ans << endl;
}
return 0;
}
Bai 3: Anh Uranus sắp tổ chức đám cưới, hôm nay anh muốn đi phát thiệp mời đến những người bạn trong team. Thấy Uranus đi mời cưới nên Tomoky giả vờ đi ra ngoài có việc để trốn. Uranus rất tức và quyết tâm tìm được Tomoky để mời.
Giả sử đường đi trong công ty tạo thành 1 đồ thị và, giữa hai điểm bất kỳ đều tồn tại đường đi trực tiếp hoặc gián tiếp thông qua một số điểm trung gian.
Do hỏi anh VenG nên anh Uranus biết trước điểm bắt đầu và điểm kết thúc trên đường đi của Tomoky, nhưng anh lại không biết Tomoky sẽ đi đường nào, do đó anh muốn tìm những điểm mà anh Tomoky bắt buộc phải đi qua trong hành trình của mình (trừ điểm đầu và điểm cuối)
Hãy giúp anh Uranus tìm số điểm bắt buộc phải đi qua trên đường đi của anh Tomoky.
Input
Dòng đầu tiên chứa số nguyên dương không lớn hơn 100 là số lượng các bộ dữ liệu. Các dòng tiếp theo chứa các bộ dữ liệu. Mỗi bộ dữ liệu gồm một nhóm dòng theo khuôn dạng:
Dòng 1 chứa 4 số nguyên N,M,u,v (u,v,N ≤ 100; M ≤ 1000). Trong đó N là số lượng đỉnh trên đồ thị. M là số đường đi.. u, v lần lượt là đỉnh bắt đầu và đỉnh kết thúc hành trình của anh Tomoky.
M dòng sau, mỗi dòng ghi hai số i, j cách nhau một khoảng trống cho biết có đường nối trực tiếp giữa i với j (1≤i,j≤N).
Output
Với mỗi bộ dữ liệu, đưa ra màn hình một số nguyên là số lượng đỉnh bắt buộc phải đi qua khi đi từ u,v.
Example
Input:
2
5 7 1 3
1 2
2 4
2 5
3 1
3 2
4 3
5 4
4 5 1 4
1 2
1 3
2 3
2 4
3 4
Output:
2
0
Bai 4:
Do không trốn được Uranus nên Tomoky đành ngậm ngùi nhận thiệp và hôm nay là ngày cưới của Uranus, anh dậy từ rất sớm để đến công ty đón xe đi ăn cưới.
Đường đi từ công ty đến nhà anh Uranus được biểu diễn bằng 1 đồ thị.
Có N đỉnh được nối với nhau bằng M đường một chiều, các đỉnh đánh số từ 1 đến N. Giả sử công ty là đỉnh 1, nhà anh Uranus - nơi tổ chức đám cưới là đỉnh 2.
Do biết trên xe là team SPen, một team rất giỏi STC ở SVMC nên bác lái xe vui tính muốn đố mọi người tìm đường đi để đi từ công ty đến đám cưới rồi quay về công ty sao cho đường đi thỏa mãn mà số các đỉnh khác nhau phải đi qua là tối thiểu.
Hãy viết chương trình giúp bác lái xe tìm đường đi trên.
Input
Dòng đầu tiên chứa số bộ test T. Sau đó là T bộ test, mỗi bộ test có dạng:
*Dòng 1: Số tự nhiên N và M (N<=20).
*Dòng 2..1+M: Mỗi dòng chứa 2 số nguyên khác nhau A và B (1<=A,B<=N) – biểu diễn đường đi một chiều giữa hai đỉnh A và B. Không có hai đường đi một chiều nào trùng nhau.
Output
Mỗi bộ test in trên một dòng là số đỉnh khác nhau tối thiểu phải đi qua khi đi từ đỉnh 1 đến đỉnh 2 rồi quay về 1.
Example
Input:
2
6 7
1 3
3 4
4 5
5 1
4 2
2 6
6 3
9 11
1 3
3 4
4 2
2 5
5 3
3 6
6 1
2 7
7 8
8 9
9 1
Output:
6
6
Bai 5: Hệ thống điện
Hệ thống điện
Sau khi anh VenG đã xây dựng đường đi giữa những hòn đảo, anh Eagle được cử sang để xây dựng hệ thống điện giữa các hòn đảo cho người dân, do muốn ăn bớt kinh phí nên anh Eagle không xây dựng trạm phát điện trên tất cả các đảo mà chỉ xây trên 1 số đảo nhất định. Các đảo kết nối với nhau thành 1 mạng lưới điện. Rõ ràng những đảo nào ở càng xa nguồn phát thì điện sẽ càng yếu.
Để đảm bảo người dân không than phiền điện yếu, nên anh Eagle muốn tính toán xem điện ở đảo nào sẽ yếu nhất.
Độ yếu của điện tại đảo X được tính bằng 0 nếu đảo đó có trạm phát điện, nếu đảo X có kết nối điện với đảo Y mà đảo Y ở gần trạm phát hơn, độ yếu tại đảo X = độ yếu tại đảo Y + 1. Nếu đảo X không có điện thì có độ yếu bằng vô cùng (infinity).
Input
Dòng đầu tiên chứa số testcase T.
Mỗi test case gồm:
Dòng đầu tiên gồm 3 số nguyên N, M, H lần lượt là số đảo, M là số đảo có trạm phát điện, H là số kết nối 2 chiều. (N, M <= 1 000, H <= 10 000).
Dòng tiếp theo gồm M số là ID các đảo có máy phát điện (ID đánh số từ 0 tới N-1).
H dòng tiếp theo, mỗi dòng gồm 2 số u, v, cho biết đảo u có kết nối với đảo v.
Output
In ra đảo độ yếu của điện là cao nhất. Nếu có nhiều đáp án, in ra đảo có ID nhỏ nhất.
Example
Input:
2
6 3 5
0 5 2
0 1
1 2
4 5
3 5
0 2
6 2 3
5 2
0 5
0 1
3 4
Output:
1
3
Bai 6: Jang keeps visiting and helping a number of departments right after he comes to work.
There is a rule in his movement. He stays at a department exactly for 10 minutes.
You are given a probability graph of their movements. Fig. 1 is an example graph.
Jang stays at dept. 1 for 10 minutes; then he moves to dept. 2 with a probability of 0.3 (then stays there for 10 minutes) or moves to dept. 3 with a probability of 0.7 (then stays there for 10 minutes). We do not consider the time for moving between departments.
There may be more than one outgoing arrow from a department; the sum of the chances of outgoing arrows from a department should be always 1.
The first department which he visit is always dept. 1.
Given a probability graph and a time T(in minutes), generate a program that finds the department at which Jang stays with the highest chance at time T.
In addition you have to report the corresponding probability.
In the Fig. 1 above, the department with the highest chance at time 10 is dept. 3 and the chance is 0.7. At time 9, Jang does not start moving; so he is at dept. 1 with a probability of 1.
Look at the situation at time 20. The chance of being at dept. 1 or dept. 2 is 0. He leaves dept. 1 exactly at time 10, and if he moves to dept. 2 then he leaves dept. 2 exactly at time 20.
The chance of being at dept. 4 at time 20 is 0.3*1.0+0.7*0.8=0.86.
When he arrives at a department without any outgoing arrow, the department becomes the last one that he finally visits; he stays at the department for 10 minutes and leaves work.
With the graph of Fig. 2, Jang is not in work at time 50; in case of Fig. 1, he may stay at work forever if he keeps staying at the same department with a loop probability, e.g, departments 3, 4, or 6
In addition, there is another person, Kang, who moves in the same way as Jang.
Jang always comes to work at time 0, but Kang comes at another time later than time 0. You also have to report the same type of contents for Kang.
If Kang’s arrival time is 4, answers related to him is computed exactly the same principle as Jang’s except he starts working 4 minutes later than Jang; in this case with Fig. 2, Kang stays at dept. 1 from time 4 to time 13 while Jang stays at dept. 1 from time 0 to time 9.
[Input]
10 test cases are given. Each case is given in two lines. Thus the input needs totally 20 lines.
For each case, the first line provides N (the number of departments), E (the number of arrows), K (Kang’s arrival time), and T (the time in minutes).
1<=N<=100. 1<=E<=200. 1<=K<=1000. 0<=T<=1000. K<=T.
The next line enumerates E arrows. Each arrow is denoted by “source-dept destination-dept probability”. The index for source dept. or destination dept. is an integer in 1 through 100, inclusive.
The time integer K and T are in minutes. For example, if the time T is 8, you have to determine the departments at which Jang and Kang, respectively, stay with the highest probabilities at time 8. The elements in the same line are separated by a space. There is no special order in which the arrows are enumerated.
[Output]
You write the 10 answers in 10 lines.
Each line starts with “#x” (Here, x means the case index.), puts a space, and writes the answer.
The answer consists of the department index with the highest chance followed by the corresponding probability. The dept. index is an integer and the probability is a real number, separated by a space.
If there is more than one department with the highest chance, you write the dept. of the lowest index.
If Jang is not at any department at the specified time, you write just “0 0.000000”. The probability is a real number in 0 through 1, inclusive; it should be accurate to six decimal places.
Another set of a department and the corresponding probability has to be provided for Kang. Thus the answer consists of four numbers in total.
Input
6 7 100 100
1 2 0.3 1 3 0.7 2 4 1.0 3 4 0.7 3 6 0.3 4 5 1.0 5 6 1.0
6 7 1 23
1 2 0.3 1 3 0.7 2 4 1.0 3 4 0.7 3 6 0.3 4 5 1.0 5 6 1.0
6 10 8 40
1 2 0.3 1 3 0.7 3 3 0.2 3 4 0.8 2 4 1 4 5 0.9 4 4 0.1 5 6 1.0 6 3 0.5 6 6 0.5
6 10 10 10
1 2 0.3 1 3 0.7 3 3 0.2 3 4 0.8 2 4 1 4 5 0.9 4 4 0.1 5 6 1.0 6 3 0.5 6 6 0.5
6 10 9 20
1 2 0.3 1 3 0.7 3 3 0.2 3 4 0.8 2 4 1 4 5 0.9 4 4 0.1 5 6 1.0 6 3 0.5 6 6 0.5
Output
#1 0 0.000000 1 1.000000
#2 4 0.790000 4 0.790000
#3 6 0.774000 5 0.774000
#4 3 0.700000 1 1.000000
#5 4 0.860000 3 0.700000
Bai 7: The Settlers of Catan
Settlers of Catan, một trò chơi của người Đức ở năm 1995, người chơi tham gia vào cuộc cai trị một hòn đảo bằng việc xây dựng các con đường, các khu định cư, và các thành phố qua các vùng hoang dã chưa được thám hiểm.
Bạn được một công ty phần mềm thuê để phát triển một phiên bản máy tính cho trò chơi này, và bạn được chọn để xây dựng một trong các luật đặc biệt của trò chơi.
Khi trò chơi kết thúc, người chơi mà xây dựng được con đường dài nhất sẽ được thêm 2 điểm thắng cuộc.
Vấn đề gặp phải ở đây là người chơi thường xây dựng các mạng lưới con đường rất phức tạp và không chỉ theo một đường tuyến tính. Vì lý do đó, việc xác định con đường dài nhất không phải đơn giản (mặc dù những người chơi thường có thể thấy ngay lập tức).
Đối chiếu tới trò chơi gốc, chúng ta sẽ giải quyết một vấn đề đơn giản ở đây: Bạn được cho trước một tập các nodes (thành phố) và một tập các cạnh (các đoạn đường) có chiều dài là 1 kết nối các nodes.
Con đường dài nhất được định nghĩa như là đường đi dài nhất trong mạng lưới đường mà không có cạnh nào được dử dụng hai lần. Dù vậy, các nodes có thể được thăm hơn một lần.
Ví dụ: Mạng lưới sau đây chứa một con đường dài nhất là 12.
Input
Input sẽ chứa một hoặc nhiều test cases.
Dòng đầu là số lượng test case T.
Dòng đầu tiên của mỗi test cases chứa 2 số nguyên: số nodes N (2<=N<=25) và số cạnh M (1<=M<=25). M dòng tiếp theo miêu tả M cạnh. Mỗi cạnh được cho bởi các số node kết nối với nhau. Các node được đánh số từ 0 -> N-1. Các cạnh không có hướng. Các node có bậc là 3 hoặc nhỏ hơn. Mạng lưới không cần thiết phải được kết nối thông suốt với nhau.
Output
Với mỗi test case, in ra chiều dài của con đường dài nhất trên một dòng.
Sample
Input
3
15 16
0 2
1 2
2 3
3 4
3 5
4 6
5 7
6 8
7 8
7 9
8 10
9 11
10 12
11 12
10 13
12 14
3 2
0 1
1 2
15 16
0 2
1 2
2 3
3 4
3 5
4 6
5 7
6 8
7 8
7 9
8 10
9 11
10 12
11 12
10 13
12 14
Output
12
2
12
Editor is loading...
Leave a Comment