Untitled
unknown
plain_text
a year ago
80 kB
53
Indexable
Bai 1: Hugo va chi Ong
Hugo và chị ong nâu nấu nâu nấu lầu nâu
Hugo và chị ong nâu là hàng xóm của nhau. Tuy nhiên Hugo thì lười nhưng lại muốn lấy mật ăn, còn chị ong nâu thì chăm chỉ kiếm mật để đầy tổ của mình. Vì thèm ăn mật ong mà mãi chị ong nâu không cho nên sau 1 thời gian nằm gai nếm mật rình mò Hugo đã phát hiện ra các bố trí của các thùng chứa mật và số mật trong mỗi thùng ở nhà chị ong nâu. Mật ở nhà chị ong nâu được biểu diễn bằng 1 ma trận NxM ô, mỗi ô một thùng mật. Mỗi ô chứa lượng mật nhất định và có thể liên kết với 6 ô xung quanh theo cách bố trí của tổ ong. 2 ô được gọi là có liên kết nếu chúng có chung cạnh.
Hôm nay Hugo phát hiện chị ong nâu đi sang khu rừng bên cạnh để lấy mật. Hugo sẽ vào nhà chị ong nâu để ăn trộm mật ong của chị. Để không bị phát hiện Hugo chỉ có thể lấy tối đa 4 thùng ở 4 ô có liên kết với nhau. Hãy giúp Hugo tìm ra bình phương tổng lượng mật lớn nhất có thể lấy.
Ex: M = 5 , N = 3
Trong ví dụ trên, bình phương tổng lượng mật là
(300 + 410 + 185 + 95)2 = 980100
Trong ví dụ trên Hugo sẽ bị phát hiện và không thể lấy mật.
[Input]
- Dòng đầu tiên là số thử nghiệm T (T <= 50)
- Mỗi TC :
+ Dòng đầu tiên chưa kích thước ma trận M, N ( 3 ≤ N, M ≤ 15 )
+ Trong N dòng tiếp theo, lượng mật C ở mỗi ô sẽ được cho theo quy tắc bên dưới (0 ≤ C ≤ 1000)
5
5 3
300 410 150 55 370
120 185 440 190 450
165 70 95 420 50
5 5
356 55 41 453 12
401 506 274 506 379
360 281 421 311 489
425 74 276 371 164
138 528 461 477 470
[Output]
Ghi ra bình phương tổng lượng mật
Case #1
2250000
Case #2
3748096
Case #3
3928324
Case #4
7236100
Case #5
13104400
Code:
#include<iostream>
using namespace std;
int T, M, N;
int arr[20][20], visited[20][20];
int Answer;
// -1 0, 0 1, 1 1, 1 0, 1 -1, 0 -1
// -1 0, -1 1, 0 1, 1 0, 0 -1, -1 -1;
int dxc[6] = {-1, 0, 1, 1, 1, 0};
int dyc[6] = {0, 1, 1, 0, -1, -1};
int dxl[6] = {-1, -1, 0, 1, 0, -1};
int dyl[6] = {0, 1, 1, 0, -1, -1};
bool isValid(int x, int y){
return x >= 1 && x <= N && y > 0 && y <= M;
}
void bt(int x, int y, int sum, int count){
if(count == 4){
if(Answer < sum){
Answer = sum;
}
return;
}
for(int i = 0; i < 6; i++){
if(y % 2 == 0){
int nx = x + dxc[i];
int ny = y + dyc[i];
if(isValid(nx, ny) && visited[nx][ny] == 0 ){
visited[nx][ny] = 1;
bt(nx, ny, sum+ arr[nx][ny], count+1);
bt(x,y,sum+arr[nx][ny],count+1);
visited[nx][ny] = 0;
}
}
else{
int nx = x + dxl[i];
int ny = y + dyl[i];
if(isValid(nx, ny) && visited[nx][ny] == 0){
visited[nx][ny] = 1;
bt(nx, ny, sum+ arr[nx][ny], count+1);
bt(x,y,sum+arr[nx][ny],count+1);
visited[nx][ny] = 0;
}
}
}
}
void reset(){
for(int i = 1; i <= N; i++){
for(int j = 1; j <= M; j++){
visited[i][j] = 0;
}
}
}
int main(){
//freopen("input.txt", "r", stdin);
cin >> T;
for(int tc = 1; tc <= T; tc++){
Answer = 0;
cin >> M >> N;
for(int i = 1; i <= N; i++){
for(int j = 1; j <= M; j++){
cin >> arr[i][j];
}
}
for(int i = 1; i <= N; i++){
for(int j = 1; j <= M; j++){
visited[i][j] = 1;
int sum = arr[i][j];
bt(i, j, sum, 1);
reset();
}
}
cout << "Case #" <<tc << endl;
cout << long long( Answer * Answer) << endl;
}
return 0;
}
Bai 2: Nâng cấp máy tính
Anh Kim có 1 máy tính đã mua từ thời sinh viên nên hiện giờ cần phải nâng cấp và thay thế L linh kiện để đảm bảo máy tính hoạt động tốt.
Để tìm mua được các thiết bị đó với giá tốt nhất anh Kim đã qua chợ Trời và tham khảo được giá của tất cả N thiết bị của máy tính.
Không chỉ thế, anh đã tìm kiếm thêm trên mạng, và anh rất vui khi có M gói ưu đãi giá rẻ được rao bán trên mạng, mỗi gói có giá bán là P bao gồm K thiết bị của máy tính.
Anh Kim có thể mua một hoặc nhiều gói ưu đãi và có thể mua thừa linh kiện chưa cần thay thế.
Hãy giúp anh Kim mua được đủ L thiết bị cần thiết với tổng giá thành là nhỏ nhất.
Input
Dòng đầu tiên là số lượng test case T (T <= 50).
Mỗi test case gồm các thông tin sau:
- Dòng đầu tiên là số nguyên dương N (1 <= N <= 20) là số lượng thiết bị chính của máy tính.
- Dòng thứ 2 bao gồm N số, số thứ i tương ứng là giá của thiết bị thứ i được bán ở chợ Trời.
- Dòng thứ 3 là số nguyên dương M ( 0 <= M <= 30) là số lượng gói ưu đãi có trên mạng.
- M dòng tiếp theo, mỗi dòng thứ i là thông tin về gói ưu đãi thứ i. Số đầu tiên là giá của gói ưu đãi P ( 1 <= P <= 1000), số tiếp theo là số lượng thiết bị K ( 1 <= K< = N) trong gói ưu đãi đó,
K số tiếp theo là các thiết bị có trong gói ưu đãi đó.
- Dòng cuối cùng của mỗi test case là thông tin về các thiết bị mà anh Kim cần mua. Số đầu tiên là số lượng thiết bị L, L số tiếp theo là các thiết bị anh Kim cần mua
- Các thiết bị được đánh số trong đoạn từ 1 đến N và không có số nào trùng nhau
Output
Bắt đầu mỗi test case là "#x" với x là số thứ tự của test case (bắt đầu từ 1), tiếp theo là một dấu cách và giá thành nhỏ nhất mà anh Kim cần bỏ ra để mua đủ những thiết bị anh cần.
Sample
Input
1 <-- T = 1,
5 <-- Số linh kiện chính của máy tính
20 15 17 18 25 <-- giá chợ Trời của 5 thiết bị từ 1 đến 5 tương ứng
4 <-- 4 gói ưu đãi trên mạng
30 3 1 2 5 <-- gói thứ nhất có giá 30, gồm 3 linh kiện 1, 2, 5
25 2 2 3 <-- gói thứ 2 có giá 25, gồm 2 linh kiện 2, 3
35 3 1 3 5 <-- gói thứ 3 có giá 35, gồm 3 linh kiện 1, 3, 5
20 2 3 4 <-- gói thứ 4 có giá 20, gồm 2 linh kiện 3, 4
3 2 4 5 <-- Số lượng anh Kim cần là 3, lần lượt là 2, 4, 5
Output
#1 48
Giải thích: Để mua được 3 thiết bị 2, 4, 5 với giá rẻ nhất, ta sẽ mua gói giá rẻ 1 gồm 1, 2, 5 với giá 30 và mua thiết bị 4 ở chợ Trời với giá 18, tổng là 30 + 18 = 48.
Code:
#include <iostream>
using namespace std;
int n,m,k;
int marketPrice[25];
int sales[35][25];
int need[25];
int have[25];
int res;
bool check(int idx, int item) {
for (int i = 0; i < sales[idx][1]; i++) {
if (sales[idx][i+2] == item) return true;
}
return false;
}
void solve(int idx, int cost) {
if (idx == k) {
res = cost < res ? cost : res;
return;
}
if (cost >= res) return;
if (have[need[idx]] >= 1) solve(idx+1,cost);
have[need[idx]]++;
solve(idx+1,cost+marketPrice[need[idx]]);
have[need[idx]]--;
for (int i = 0; i < m; i++) {
if (check(i,need[idx])) {
for (int j = 0; j < sales[i][1]; j++) {
have[sales[i][j+2]]++;
}
solve(idx+1,cost+sales[i][0]);
for (int j = 0; j < sales[i][1]; j++) {
have[sales[i][j+2]]--;
}
}
}
}
int main() {
//freopen("input.txt","r",stdin);
int T;
cin >> T;
for (int tc = 1; tc <= T; tc++) {
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> marketPrice[i];
have[i] = 0;
}
cin >> m;
for (int i = 0; i < m; i++) {
cin >> sales[i][0] >> sales[i][1];
for (int j = 0; j < sales[i][1]; j++) {
cin >> sales[i][j+2];
}
}
cin >> k;
for (int i = 0; i < k; i++) {
cin >> need[i];
}
res = 999999;
solve(0,0);
cout << "#" << tc << " " << res << endl;
}
return 0;
}
Bai 3: Hugo Giao Hàng
Hugo Giao Hàng
Hugo đang làm việc cho công ty Samsung, tuy mức lương ở Samsung không hề nhỏ nhưng vì Hugo là lao động duy nhất trong nhà, vợ của Hugo mới sinh em bé. Hugo muốn kiếm thêm thu nhập để có thể có thêm tiền sữa, bỉm cho con. Hugo quyết định nhận giao bánh pizza ngoài giờ làm. Mỗi ngày, sau khi tan ca Hugo sẽ nhận N chiếc bánh pizza để giao tới N địa điểm khác nhau sau đó trở về nhà. Tuy nhiên hôm nay là sinh nhật bạn Đạo nên Hugo muốn tìm quãng đường đi giao bánh pizza từ công ty sau đó về nhà là ngắn nhất để có thể kịp dự sinh nhật Đạo. Thật may là Hugo có những người bạn là master về tìm đường đi tại Samsung nên Hugo sẽ nhờ các bạn ấy tìm giúp.
Hãy cùng giúp Hugo tìm đường nào các bạn.
Đầu vào
T test case <=50
Dòng đầu tiên chưa 4 số Sx, Sy, Hx, Hy tương ứng là vị trí của công ty và nhà của Hugo trên hệ trục tọa độ Oxy
Dòng tiếp theo bao gồm số N và N cặp số liên tiếp tương ứng là tọa độ các điểm mà Hugo cần giao pizza.
N<=10
Cách tính khoảng cách giữa 2 điểm x1,y1 x2,y2 D = |x1-x2|+|y1-y2|
Đầu ra
In ra quãng đường ngắn nhất Hugo di chuyển từ công ty để giao bánh sau đó trở về nhà.
10
57 61 50 61
5 86 53 4 104 27 3 55 34 69 0
96 47 60 28
5 0 6 43 84 84 35 44 57 95 50
48 32 67 42
5 53 51 92 1 48 19 8 3 82 37
97 28 66 41
5 93 72 9 79 46 31 12 66 54 11
38 62 93 86
5 87 83 40 83 83 26 98 11 74 103
23 42 71 16
5 12 76 47 74 24 5 88 82 45 85
96 85 14 6
5 86 91 104 60 72 35 59 22 58 39
99 49 68 1
5 48 80 96 101 56 88 75 56 25 81
51 14 75 51
5 29 62 103 15 75 84 67 94 96 57
87 39 57 77
5 105 85 31 40 1 88 83 89 29 18
Case #1 393
Case #2 323
Case #3 267
Case #4 294
Case #5 281
Case #6 300
Case #7 219
Case #8 283
Case #9 295
Case #10 344
Code:
#include<iostream>
using namespace std;
int T, Sx, Sy, Hx, Hy, N;
int x[20], y[20], arr[20][20];
long Answer;
bool visited[20];
int abs(int a){
return a > 0 ? a : -a;
}
int kc(int a, int b, int c, int d){
return abs(a-c) + abs(b-d);
}
void bt(int x, long sum, int count){
if(sum > Answer ){
return;
}
if(count == N){
sum += arr[x][N+1];
if(Answer > sum){
Answer = sum;
}
}
for(int i = 1; i <= N; i++){
//int nx = i;
if(visited[i] == 0){
/*visited[x][i] = 1;
visited[i][x] = 1;*/
visited[i] = 1;
int kc = arr[x][i];
bt(i, sum + kc, count +1);
visited[i]=0;
}
}
}
int main(){
//freopen("inputHugoGiaoHang.txt", "r", stdin);
cin >> T;
for(int tc = 1; tc <= T; tc++){
Answer = 99999999;
cin >> Sx >> Sy >> Hx >> Hy;
cin >> N;
for(int i = 1; i <= N; i++){
cin >> x[i] >> y[i];
}
x[0] = Sx;
y[0] = Sy;
x[N+1] = Hx;
y[N+1] = Hy;
for(int i = 0; i <= N+1; i++){
for(int j = 0; j <= N+1; j++){
arr[i][j] = kc(x[i], y[i], x[j], y[j]);
visited[i] = 0;
}
}
bt(0, 0, 0);
cout << "Case #" <<tc << " " << Answer << endl;
}
return 0;
}
Bai 4:
Hugo Phá Hủy Hệ Thống Điện
Hugo Phá hủy hệ thống điện
Sau khi biết tin Eagle xây dựng hệ thống điện và ăn bớt được rất nhiều kinh phí, Hugo rất tức vì khi anh xây cầu anh đã không ăn bớt được đồng nào. Do đó anh quyết phá hệ thống điện của Eagle.
Do sợ bị phát hiện nên anh sẽ chỉ phá hệ thống điện ở trên 1 hòn đào, và anh muốn tìm hòn đảo nào sau khi phá xong thì hệ thống điện của Eagle bị chia cắt thành nhiều phần nhất.
Hãy giúp Hugo tìm hòn đảo này.
Input:
Dòng đầu tiên ghi số bộ test, không lớn hơn 100.
Mỗi bộ test được tổ chức theo khuôn dạng sau:
Dòng đầu tiên ghi lại số tự nhiên N không lớn hơn 100 là số hòn đảo.
Những dòng kế tiếp ghi lại ma trận biểu diễn hệ thong mạng lưới điện, trong đó 0 được hiểu là không có đường dây điện nối giữa điểm i và j, 1 được hiểu có đường dây điện trực tiếp giữa điểm i và điểm j (1<=i, j <= N).
Output
Với mỗi bộ test, in ra màn hình trên một dòng một số duy nhất là hòn đảo bị phá hủy hệ thống điện thỏa mãn yêu cầu bài toán (nếu có nhiều đảo cùng thỏa mãn yêu cầu thì in ra đảo có giá trị nhỏ nhất). Nếu không thể chia cắt được hệ thống điện, hãy in ra số 0.
Example
Input:
2
5
0 1 1 0 0
1 0 1 0 0
1 1 0 1 1
0 0 1 0 0
0 0 1 0 0
5
0 1 1 0 0
1 0 1 0 1
1 1 0 1 1
0 0 1 0 1
0 1 1 1 0
Output:
3
0
Output of 5 tcs:
0
1
8
4
0
Code:
#include<iostream>
using namespace std;
int n;
int A[101][101];
int S[1000000];
int visit[101];
int top,bot;
void reset()
{
for(int i=0;i<=n;i++) visit[i]=0;
}
int check()
{
for(int i=1;i<=n;i++)
{
if(visit[i]==0) return i;
}
return 0;
}
int main()
{
freopen("HugoDien.txt","r",stdin);
int t;cin>>t;
for(int tc=1;tc<=t;tc++)
{
cin>>n;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
cin>>A[i][j];
}
}
//xet tung hon dao
int maxx=1;
int daokq=0;
for(int i=1;i<=n;i++)
{
reset();
top=bot=-1;
visit[i]=1;
int a=check();
int dem=0;//dem so luong chia cat
while(a)
{
// dua a vao queue;
top++;
S[top]=a;
while(top!=bot)
{
bot++;
int tmp=S[bot];
visit[tmp]=1;
for(int j=1;j<=n;j++)
{
if(A[tmp][j]==1 && j!=i && visit[j]==0 )
{
top++;
S[top]=j;
}
}
}
dem++;
a=check();
}
if(dem>maxx)
{
maxx=dem;
daokq=i;
}
}
cout<<daokq<<endl;
}
return 0;
}
Bai 5:Pizza Location
Our friend Picko is very reach and he wants to open lots of restaurants with delivery. The main food will be, of course, pizza. He has certain number of potential locations for the restaurants, and he knows the locations of the solitaires with lots of people which will often be his customers. Delivery of each restaurant will cover all the solitaires in given radius.
Picko can open only limited number of restaurants, and he wants that restaurants on the locations which will cover maximal number of people in solitaires.
Write a program that will calculate maximal number of people which we can cover with delivery.
Input
In the first line of the input file there are two integers K and R, separated with space, number of restaurants and radius of delivery, 1 ≤ K ≤ 10, 1 ≤ R ≤ 500.
In the second line there is integer M, number of locations, K ≤ M ≤ 20.
In each of the next M lines there are two integer X and Y, separated with space, coordinates of each location, -1000 ≤ X,Y ≤ 1000.
In the next line there is integer N, number of solitaires, 1 ≤ N ≤ 100.
In each of the next N lines there are three integers X, Y and S, separated with space, X and Y are coordinates of each solitaire, and S is number of people in that solitaire, -1000 ≤ X,Y ≤ 1000, 1 ≤ S ≤ 100.
We consider that solitaire is in radius of some restaurant if distance between them is less or equal to R. There are no two locations of restaurants on the same place.
Output
In only line of the output file we have to write maximal number from the text above.
Sample
Input
3
2 2
3
1 0
4 0
7 0
4
0 0 1
3 0 7
5 0 9
8 0 1
2 2
3
-2 0
0 1
3 0
8
-3 1 1
-3 0 1
-3 -1 1
-2 -1 1
0 0 3
0 2 1
2 1 3
4 0 2
3 3
5
0 0
1 6
2 3
6 6
7 2
8
0 1 2
0 5 3
0 6 1
1 0 1
3 2 3
3 6 2
6 2 4
8 6 3
Output
#1 18
#2 12
#3 17
Code: #include<iostream>
using namespace std;
int k,r;
int m,M[21][2];
int n,N[101][3];
int A[21][101]; // mxn
int maxx;
int X[11];
long long pow2(int a)
{
long long res=0;
res=a*a;
return res;
}
void tohop(int i)
{
for(int j=X[i-1] +1 ;j<=m-k+i;j++)
{
X[i]=j;
if(i==k)
{
//tinh toan
int dd[100]={0};
int tmp=0;
for(int a=1;a<=k;a++)
{
//dat nha hang tai vi tri X[a];
int vt=X[a]-1;
for(int b=0;b<n;b++)
{
if(A[vt][b]!=0) dd[b]=A[vt][b];
}
}
//
for(int a=0;a<n;a++) tmp+=dd[a];
if(tmp>maxx) maxx=tmp;
}
else
{
tohop(i+1);
}
}
}
int main()
{
//freopen("input.txt","r",stdin);
int t;cin>>t;
for(int tc=1;tc<=t;tc++)
{
cin>>k>>r;// so luong nha hang va ban kinh giao hang
cin>>m;//so luong dia diem de dat nha hang
for(int i=0;i<m;i++)
{
cin>>M[i][0]>>M[i][1];// toa do cac dia diem dat nha hang
}
cin>>n;//so bua tiec
for(int i=0;i<n;i++)
{
cin>>N[i][0]>>N[i][1]>>N[i][2];//toa do va sl nguoi cua moi bua tiec
}
//xu ly
for(int i=0;i<21;i++)
{
for(int j=0;j<101;j++) A[i][j]=0;
}
//1.tao 1 matran khoang cach
for(int i=0;i<m;i++)
{
for(int j=0;j<n;j++)
{
//diem I(hang i trong ma tran M) toi bua tiec thu J(hang j trong ma tran N)
if(pow2(M[i][0]-N[j][0]) + pow2(M[i][1]-N[j][1]) <= pow2(r))
{
A[i][j]=N[j][2];
}
}
}
//
maxx=0;
//
for(int i=0;i<11;i++) X[i]=0;
tohop(1);
cout<<"#"<<tc<<" "<<maxx<<endl;
}
return 0;
}
Bai 6: Hugo quản lý 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
Code:
#include <iostream>
using namespace std;
int N; // Số lượng người trong dãy
int people[1001], door[4], kc[4][1001], check[5], visit[1001]; // Mảng lưu thông tin về người, cửa, khoảng cách, kiểm tra và viếng thăm
int Max; // Biến lưu trữ kết quả tối ưu
// Hàm in mảng khoảng cách
void print(int kc[]) {
for (int i = 1; i <= N; i++) {
cout << kc[i] << " ";
}
cout << endl;
}
int abs(int x){
return x > 0 ? x : -x;
}
// Hàm backtrack để thực hiện quay lui
void backtrack(int indext, int sum) {
// Nếu đã duyệt hết 4 cửa
if (indext == 4) {
// Lưu kết quả tối ưu
Max = min(Max, sum);
return;
}
// Duyệt qua từng cửa
for (int s = 1; s <= 3; s++) {
// Nếu chưa kiểm tra cửa này
if (check[s] == 0) {
// Duyệt qua 2 trường hợp: mở cửa hoặc không mở
for (int k = 0; k < 2; k++) {
int dor = door[s]; // Cửa hiện tại
int guse = people[dor]; // Số người ở cửa đó
int cout = 0; // Biến đếm số lần di chuyển
int value = 0; // Biến lưu tổng khoảng cách
// Trường hợp mở cửa
if (k == 0) {
check[s] = 1;
while (guse > 0) {
int l = dor - cout; // Cửa bên trái
int r = dor + cout; // Cửa bên phải
// Nếu cửa bên trái hợp lệ và chưa được viếng thăm
if (l >= 1 && visit[l] == 0) {
visit[l] = dor;
value = value + cout + 1; // Cập nhật tổng khoảng cách
guse--; // Giảm số người cần di chuyển
}
// Nếu cửa bên phải hợp lệ và chưa được viếng thăm
else if (r <= N && visit[r] == 0) {
visit[r] = dor;
value = value + cout + 1; // Cập nhật tổng khoảng cách
guse--; // Giảm số người cần di chuyển
}
// Nếu cửa đã được viếng thăm hoặc vượt quá phạm vi
else if ((r <= N && visit[r] != 0) || (l >= 1 && visit[l] != 0)) {
cout++; // Tăng biến đếm
}
}
// Gọi đệ quy cho cửa tiếp theo
backtrack(indext + 1, sum + value);
check[s] = 0; // Đánh dấu cửa đã được kiểm tra
// Đặt lại các cửa đã được viếng thăm
for (int i = 1; i <= N; i++) {
if (visit[i] == dor)
visit[i] = 0;
}
}
// Trường hợp không mở cửa
else {
check[s] = 1;
while (guse > 0) {
int l = dor - cout; // Cửa bên trái
int r = dor + cout; // Cửa bên phải
if (r <= N && visit[r] == 0) { // Nếu cửa bên phải hợp lệ và chưa được viếng thăm
visit[r] = dor;
value = value + cout + 1;
guse--;
}
else if (l >= 1 && visit[l] == 0) { // Nếu cửa bên trái hợp lệ và chưa được viếng thăm
visit[l] = dor;
value = value + cout + 1;
guse--;
} else {
cout++;
}
}
// Gọi đệ quy cho cửa tiếp theo
backtrack(indext + 1, sum + value);
check[s] = 0; // Đánh dấu cửa đã được kiểm tra
// Đặt lại các cửa đã được viếng thăm
for (int i = 1; i <= N; i++) {
if (visit[i] == dor)
visit[i] = 0;
}
}
}
}
}
}
int main() {
//freopen("HugoQuanLy.txt", "r", stdin);
int T;
cin >> T; // Nhập số lượng bộ test
for (int t = 1; t <= T; t++) {
cin >> N; // Nhập số lượng người trong dãy
// Nhập thông tin về cửa và số người ở mỗi cửa
for (int i = 1; i <= 3; i++) {
int x;
cin >> x;
door[i] = x;
cin >> people[x];
}
// Tính toán khoảng cách từ mỗi cửa đến từng người
for (int i = 1; i <= 3; i++) {
int k = door[i];
for (int j = 1; j <= N; j++) {
kc[i][j] = abs(k - j) + 1;
}
}
Max = 10000; // Khởi tạo kết quả tối ưu
backtrack(1, 0); // Gọi hàm backtrack để tìm kết quả tối ưu
// In kết quả
cout << "Case #" << t << endl;
cout << Max << endl;
}
return 0;
}
Bai 7: Mỏ khai thác vàng
Cho bản đồ mỏ vàng có thể được biểu diễn dưới dạng ma trận NxN
Trong bản đồ này, có một số mỏ vàng nằm ở những vị trí ngẫu nhiên (tối đa 4 mỏ trên mỗi bản đồ). Một trại sẽ được thiết lập trên bản đồ để khai thác vàng. Hàng ngày, công nhân sẽ đi từ khu trại đến địa điểm mỏ vàng. Để giảm chi phí, công ty muốn thiết lập trại sao cho khoảng cách từ trại đến địa điểm khai thác được tối ưu hóa.
Hãy xem xét bản đồ 5x5 dưới đây:
- Công nhân không thể đi xuyên qua đá
- Mất 1 giờ để di chuyển một ô trên bản đồ
Có hai mỏ, từ điểm xuất phát (địa điểm cắm trại), đi đến mỗi mỏ vàng phải mất 4h. Giả sử chi phí cuối cùng sẽ là chi phí cao nhất trong số đó, thì nếu chúng ta đặt trại như hình trên thì chi phí cuối cùng sẽ là 4.
Bây giờ, chúng ta xem xét ví dụ khác:
Trong ví dụ thứ 3, chi phí cuối cùng sẽ tối thiểu (1)
[ Đầu vào ]
Dòng đầu tiên nhập vào sẽ là số test case T (T ≤ 50)
Trong mỗi TC:
- Dòng đầu tiên sẽ cho biết kích thước bản đồ N (N ≤ 20) và số lượng mỏ vàng G (2 ≤ G ≤ 4)
- Các dòng G tiếp theo sẽ là vị trí R (hàng) & C (cột) mỏ vàng (chỉ số 1 base)
- N dòng tiếp theo sẽ là số liệu của bản đồ: 1 tượng trưng cho đường đi & mỏ vàng, 0 tượng trưng cho tảng đá (không thể đi qua)
[ Đầu ra ]
Chương trình của bạn sẽ đưa ra Chi phí cuối cùng tối thiểu để đi từ trại đến mỏ vàng.
Trường hợp 1
1
Trường hợp số 2
2
Trường hợp số 3
2
Trường hợp số 4
7
Trường hợp số 5
6
[ Hạn chế ]
- Bạn có thể di chuyển theo 4 hướng (lên/trái/xuống/phải)
- Bạn không thể dựng trại ở vị trí mỏ vàng hoặc đá
- Bạn có thể đi qua mỏ vàng sau đó đi đến mỏ vàng khác
- Bạn phải cắm trại để công nhân có thể đi tới tất cả các mỏ vàng
Code: #include<iostream>
using namespace std;
int T, N, G, gx[5], gy[5], arr[21][21], visited[21][21], check[21][21];
int maxx, Answer;
int dx[4] = {-1, 1, 0, 0};
int dy[4] = {0, 0, 1, -1};
const int MAX = 101;
struct Queue
{
int queue[MAX];
int front, rear;
Queue(){
reset();
}
void reset(){
front = -1;
rear = -1;
}
void push(int value){
queue[++rear % MAX] = value;
}
int pop(){
return queue[++front % MAX];
}
bool isEmpty(){
return front == rear;
}
};
bool isValid(int x, int y){
return x > 0 && x <= N && y > 0 && y <= N;
}
void bfs(int x, int y){
for(int i = 1; i <= N; i++){
for(int j = 1; j <= N; j++){
visited[i][j] = 0;
}
}
visited[x][y] = 1;
Queue q;
q.push(x);
q.push(y);
while(!q.isEmpty()){
int r = q.pop();
int c = q.pop();
for(int i = 0; i < 4; i++){
int nx = r + dx[i];
int ny = c + dy[i];
if(arr[nx][ny] == 1 && isValid(nx, ny) && visited[nx][ny] == 0){
visited[nx][ny] = visited[r][c] + 1;
q.push(nx);
q.push(ny);
}
}
}
maxx = 0;
for(int i = 1; i <= G; i++){
if(visited[gx[i]][gy[i]] == 0){
return;
}
int k = visited[gx[i]][gy[i]] - 1;
if(maxx < k) maxx = k;
}
if(Answer > maxx) Answer = maxx;
}
void resetCheck(){
for(int i = 1; i <= N; i++){
for(int j = 1; j <= N; j++){
check[i][j] = 0;
}
}
}
int main(){
//freopen("GoldMining.txt", "r", stdin);
//freopen("input.txt", "r", stdin);
cin >> T;
for(int tc = 1; tc <= T; tc++){
Answer = 999;
cin >> N >> G;
resetCheck();
for(int i = 1; i <= G; i++){
cin >> gx[i] >> gy[i];
check[gx[i]][gy[i]] = 99;
}
for(int i = 1; i <= N; i++){
for(int j = 1; j <= N; j++){
cin >> arr[i][j];
visited[i][j] = 0;
}
}
for(int i = 1; i <= N; i++){
for(int j = 1; j <= N; j++){
if(arr[i][j] == 1 && check[i][j] != 99){
bfs(i, j);
}
}
}
cout << "Case #" << tc << endl;
if(Answer == 999) cout << -1 << endl;
else cout << Answer << endl;
}
return 0;
}
Bai 8: Hugo thi chạy
Sắp tới công ty nên Hugo làm việc tổ chức sự kiện Olympic dành cho toàn bộ nhân viên. Có rất nhiều bộ môn thi đấu như Bóng bàn, cầu long, cờ vua, cờ tướng, bơi lội, và có cả thể thao điện tử nữa. Là một người quan tâm tới sức khỏe của bản thân vì vậy Hugo thường xuyên chạy bộ để rèn luyện sức khỏe. Thật may trong các môn thi đấu Olympic có hạng mục này. Trong quá trình tập luyện Hugo đã luyện cho mình được 5 kiểu chạy khác nhau, mỗi kiểu chạy sẽ tiêu tốn số lượng năng lượng nhất định và thời gian chạy hết 1km là khác nhau. Mỗi kiểu chạy sẽ sử dụng cho 1km.
Năng lượng của Hugo là có hạn, nếu sử dụng vượt Hugo sẽ bị bệnh.
Sau khi tham khảo thông tin Hugo biết được quãng đường cần chạy bộ D của cuộc thi. Nhân viên y tế có thể giúp Hugo tính toán được số năng lượng tối đa của Hugo.
Cho thông tin của 5 kiểu chạy của Hugo bao gồm số phút, số giây (số phút <= 6 và số giây <= 60) và số năng lượng tiêu tốn.
Hãy tính thời gian ngắn nhất để Hugo về đích mà không bị bệnh.
Input
Dòng đầu số test T (T<=50)
Mỗi test bao gồm 2 dòng
Dòng 1 chứa số năng lượng tối đa M <=60 và chiều dài quãng đường D<=40km
Dòng thứ 2 chứa thông tin của 5 kiểu chạy lần lượt là số phút, số giây, số năng lượng tiêu tốn
Output
In ra thời gian ngắn nhất để Hugo về đích mà không bị bệnh theo dạng số phút, số giây. Nếu không thể hãy in ra -1
Input
4
297 10
5 38 23 5 22 12 4 16 6 5 38 20 0 20 17
192 10
2 6 12 6 5 24 2 22 22 4 13 12 4 30 16
503 10
1 42 20 1 8 14 0 33 15 2 6 6 5 3 16
122 10
2 37 21 3 59 22 6 0 22 4 56 5 0 9 10
Output
Case #1
3 20
Case #2
21 0
Case #3
5 30
Case #4
1 30
Code: #include <iostream>
using namespace std;
int nang_luong;
int quang_duong;
int phut[15];
int giay[15];
int tieuton[15];
int kq;
void backtrack(int a, int b, long time, int start) // a quang duong, b nang luong tieu ton
{
if(time > kq)
{
return;
}
if (b > nang_luong)
{
return;
}
if(a == quang_duong)
{
if (time < kq)
kq = time;
return;
}
for (int i = start; i < 5; i++)
{
backtrack(a + 1,b + tieuton[i], time + phut[i]*60 + giay[i],i);
}
}
int main()
{
freopen("HugoThiChay.txt", "r" , stdin);
int T;
cin >> T;
for (int tc = 1; tc <= T; tc++)
{
kq = 999999;
cin >> nang_luong >> quang_duong;
for (int i = 0; i < 5; i++)
{
cin >> phut[i] >> giay[i] >> tieuton[i];
}
backtrack(0,0,0,0);
cout << "Case #" << tc << endl;
if(kq != 999999)
cout << kq /60 << " " << kq % 60 << endl;
else
cout << "-1" << endl;
}
return 0;
}
Bai 9: Tắt Đèn
Nhà Ngô Tất Tố hiện tại đang có N bóng đèn và có K khóa. Các khóa được nối vào các bóng đèn theo quy luật như sau:
Khóa thứ K sẽ được nối vào các bóng đèn thứ K+n(K+1) (n>=0; 0<=K+n(K+1) <=N).
Ví dụ:
Khóa thứ 1 sẽ nối vào các bóng đèn số 1, 3, 5, 7,9…
Khóa thứ 2 sẽ nối vào các bóng đèn số 2, 5, 8, 11,…
Khóa thứ 3 sẽ nối vào các bóng đèn số 3, 7, 11, 15,…
Nếu khóa thứ k được thay đổi trạng thái, tất cả các bóng đèn đang nối với khóa k sẽ chuyển trạng thái (Bật->Tắt, tắt->bật).
Ngô Tất Tố mỗi lần ra khỏi nhà sẽ đóng khóa sao cho số lượng bóng đèn được tắt là lớn nhất. Anh ta phát hiện ra rằng sự thay đổi trạng thái các khóa khác nhau để tắt có thể có số lượng đèn khác nhau được tắt. Anh ta đang nghĩ đến làm sao nếu chỉ thay đổi trạng thái khóa tối đa 3 lần sẽ tắt được nhiều bóng điện nhất. Mặc dù là một nhà toán học nhưng anh ấy đang bận sáng tác thơ cho cho kỳ thi sắp tới. Nên anh ấy cần các bạn nhân viên tìm ra phương pháp tối ưu để tắt đèn với tối đa 3 lần tác động vào khóa^.^
Input:
Dòng 1 chứa số T là số TC.
Mỗi testcase bao gồm các thông tin sau:
- Dòng đầu tiên chứa số lượng bóng đèn N và số Khóa K (10<=N<=100, 3<=K<=10);
- Dòng tiếp theo là N bóng đèn, mỗi bóng đèn nhận 1 trong 2 trạng thái: 1 là bật, 0 là tắt.
OutPut:
In ra số lượng bóng đèn tối đa có thể tắt tại mỗi case.
Đáp số của mỗi TC in ra trên 1 dòng theo định dạng:
# TC Answer
Ví dụ:
Input
1
10 3 (10 bóng đèn và 3 khóa)
0 0 1 1 1 1 0 0 1 0 (lần lượt là 10 trạng thái của 10 bóng đèn, 1 là đang bật, 0 là đang tắt)
Output:
#1 6
Giải thích: Chọn tác động vào công tắc thứ 1, các bóng đèn sau sẽ bị thay đổi trạng thái:1 3 5 7 9
Stt bóng đèn 1 2 3 4 5 6 7 8 9 10
Ban đầu 0 0 1 1 1 1 0 0 1 0
Sau khi tác động vào khóa 1 1 0 0 1 0 1 1 0 0 0
Code: #include<iostream>
using namespace std;
int T, N, K, arr[200], arr2[200], arr3[200], arr4[200];
int Answer;
void khoa(int k){
for(int i = k; i <= N; i += (k+1)){
arr2[i] = !arr2[i];
}
}
void reset(){
for(int i = 1; i <= N; i++){
arr2[i] = arr[i];
arr3[i] = 0;
arr4[i] = 0;
}
}
int tinhSoLanTat(){
int count = 0;
for(int i = 1; i <= N; i++){
if(arr2[i] == 0){
count++;
}
}
/*for(int i = 1; i <= N; i++){
cout << arr[i] << " ";
}
cout << endl;
for(int i = 1; i <= N; i++){
cout << arr2[i] << " ";
}
cout << endl;
cout << count << endl;*/
return count;
}
int tat1Lan(){
int max = 0;
for(int i = 1; i <= K; i++){
khoa(i);
int tmp = tinhSoLanTat();
if(tmp > max) max = tmp;
reset();
}
return max;
}
void reset2(){
for(int i = 1; i <= N; i++){
arr3[i] = arr2[i];
}
}
void reset_2(){
for(int i = 1; i <= N; i++){
arr2[i] = arr3[i];
}
}
int tat2Lan(){
int max = 0;
for(int i = 1; i <= K; i++){
khoa(i);
reset2();
for(int j = i; j <= K; j++){
khoa(j);
int tmp = tinhSoLanTat();
if(tmp > max) max = tmp;
reset_2();
}
reset();
}
return max;
}
void reset3(){
for(int i = 1; i <= N; i++){
arr4[i] = arr2[i];
}
}
void reset_3(){
for(int i = 1; i <= N; i++){
arr2[i] = arr4[i];
}
}
int tat3Lan(){
int max = 0;
for(int i = 1; i <= K; i++){
khoa(i);
reset2();
for(int j = i; j <= K; j++ ){
khoa(j);
reset3();
for(int k = j; k <= K; k++){
khoa(k);
int tmp = tinhSoLanTat();
if(tmp > max) max = tmp;
reset_3();
}
reset_2();
}
reset();
}
return max;
}
int max(int a, int b, int c){
if(a >= b && b >= c) return a;
else if(b >= a && b >= c) return b;
else if(c >= a && c >= b) return c;
}
int main(){
//freopen("input.txt", "r", stdin);
//freopen("TatDen.txt", "r", stdin);
cin >> T;
for(int tc = 1; tc <= T; tc++){
cin >> N >> K;
for(int i = 1; i <= N; i++){
cin >> arr[i];
}
reset();
int a = 0, b = 0, c = 0;
a = tat1Lan();
b = tat2Lan();
c = tat3Lan();
Answer = max(a, b, c);
cout << "#" << tc << " " << Answer << endl;
}
return 0;
}
Bai 10: Prime Ring
Một vòng gồm N phần tử hình tròn. Trong mỗi hình tròn sẽ chứa một số nguyên P và tổng hai số nguyên trong hai hình tròn cạnh nhau trên vòng tròn tạo thành một số nguyên tố. Nhiệm vụ của bạn là với một chuỗi gồm N phần tử số nguyên, đưa ta tổng số cách xếp N phần tử đó vào vòng tròn thỏa mãn yêu cầu trên.
Ví dụ
Ta có đầu vào là một dãy gồm 6 phần tử: 1, 2, 3, 4, 5, 6. Thì đầu ra sẽ có 2 cách xếp là cách 1: 1 - 4 - 3 - 2 - 5 - 6 và cách 2: 1 - 6 - 5 - 2 - 3 - 4
Cách 1: 1 - 4 - 3 - 2 - 5 - 6
Input
Dòng đầu liên là T chính là số testcase (T ≤ 100). Mỗi testcase sẽ bao gồm 2 dòng:
Dòng đầu tiên là N chính là số lượng phần tử các số nguyên. (3 ≤ N ≤ 16)\
Dòng thứ hai là một dãy gồm N số nguyên P ( 1 ≤ P ≤ 50)
Output
Kết quả được in ra trên một dòng theo định sạng sau: “Case number_testcase: answer”
Sample
Input
2
8
1 2 3 4 5 6 7 8
6
1 2 3 4 5 6
Output
Case 1: 4
Case 2: 2
Code:
Bai 11: Advertisement Schedule
A 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.
Ex: There are 7 visitors go to the shop with the arrival time and staying duration as below
Visitor 1 Visitor 2 Visitor 3 Visitor 4 Visitor 5 Visitor 6 Visitor 7
Arrival Time 2 6 3 7 1 2 1
Time Duration 2 4 3 2 1 1 10
Length Point(s)
Advertisement 1 1 1
Advertisement 2 2 2
Advertisement 3 3 3
Assuming that Ads1 is displayed at time 2, Ads2 at time 7 and Ad3 at time 3, the visitors will watched the ads as below schedule :
Visitor 1 Visitor 2 Visitor 3 Visitor 4 Visitor 5 Visitor 6 Visitor 7
Ads 1 Watch - - - - Watch Watch
Ads 2 - Watch - Watch - - Watch
Ads 3 - - Watch - - - Watch
(Note that visitor 1 didn't watch Ads3 fully, so the point of Ads3 is not given to him)
The points that each visitor can get from watching Ads is show as below :
Visitor 1 Visitor 2 Visitor 3 Visitor 4 Visitor 5 Visitor 6 Visitor 7
Ads 1 1 - - - - 1 1
Ads 2 - 2 - 2 - - 2
Ads 3 - - 3 - - - 3
Total 12 Points 1 2 3 2 0 1 3
(Visitor 7 watched all Ads fully, however he can only get the highest of one Ads - which is 3 points of Ads 3)
There are many way to arrange the display time, and the method above give us the maximum sum of points which visitors can get, so the answer in this case is 12.
[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
Bai 12: Tổng kết lại
Cho một tổng t xác định và một danh sách n số nguyên, hãy tìm tất cả các tổng riêng biệt bằng cách sử dụng các số từ danh sách có tổng bằng t. Ví dụ: nếu t = 4, n = 6 và danh sách là [4, 3, 2, 2, 1, 1] thì có bốn tổng khác nhau bằng 4: 4, 3+1, 2+2, và 2+1+1. (Một số có thể được sử dụng trong một tổng số lần nó xuất hiện trong danh sách và một sốber được tính là tổng.) Công việc của bạn là giải bài toán này nói chung.
Đầu vào
Tệp đầu vào sẽ chứa một hoặc nhiều trường hợp kiểm thử, mỗi trường hợp trên một dòng. Mỗi test chứa t, tổng, theo sau là n, số số nguyên trong danh sách, theo sau là n số nguyên x1, . . . ,xn. t sẽ là số nguyên dương nhỏ hơn 1000, n sẽ là số nguyên từ 1 đến 12 (đã bao gồm) và x1, . . . , xn sẽ là số nguyên dương nhỏ hơn 100. Tất cả các số sẽ cách nhau đúng một dấu cách. Các số trong mỗi danh sách có thể lặp lại.
đầu ra
Đối với mỗi trường hợp kiểm thử, xuất kết quả tổng, nếu không xuất ra -1.
Vật mẫu
Đầu vào
4
4 6
4 3 2 2 1 1
5 3
2 1 1
400 12
50 50 50 50 50 50 25 25 25 25 25 25
20 10
1 2 3 4 5 6 7 8 9 10
đầu ra
#1 4
#2 -1
#3 2
#4 31
Giải thích
#1
4
3+1
2+2
2+1+1
#3
50+50+50+50+50+50+25+25+25+25
50+50+50+50+50+25+25+25+25+25+25
#4
1+2+3+4+10
1+2+3+5+9
1+2+3+6+8
1+2+4+5+8
1+2+4+6+7
1+2+7+10
1+2+8+9
1+3+4+5+7
1+3+6+10
1+3+7+9
1+4+5+10
1+4+6+9
1+4+7+8
1+5+6+8
1+9+10
2+3+4+5+6
2+3+5+10
2+3+6+9
2+3+7+8
2+4+5+9
2+4+6+8
2+5+6+7
2+8+10
3+4+5+8
3+4+6+7
3+7+10
3+8+9
4+6+10
4+7+9
5+6+9
5+7+8
Code: #include<iostream>
using namespace std;
int tong,n;
int A[15];
int used[15];
int dem;
int mangkiemtra[1000][15];
int stt;
void reset()
{
for(int i=0;i<1000;i++)
for(int j=0;j<15;j++) mangkiemtra[i][j]=0;
}
bool kiemtratrunglap(int temp[],int sopt)
{
for(int i=0;i<stt;i++)
{
if(mangkiemtra[i][0]==sopt)
{
bool flag=true;
for(int j=1;j<=sopt;j++)
{
if(temp[j]!=mangkiemtra[i][j])
{
flag=false;
break;
}
}
if(flag)
{
return false;
}
}
}
return true;
}
void back(int idx)
{
for(int i=0;i<=1;i++)
{
used[idx]=i;
if(idx==n-1)
{
//
int tmp=0;
for(int j=0;j<n;j++) tmp+=used[j]*A[j];
if(tmp==tong)
{
//tao mang temp luu gia tra A[used[i]==1] va dem sl phan tu(temp luu tu 1)
//sap xep lai mang va dua vao ham kiemtratrung lap
//neu true: dem++, dua tmp vao mangkiemtra[stt] va stt++;
//neu false: ko lam gi ca
int temp[15],sopt=0;
for(int a=0;a<n;a++)
{
if(used[a]==1)
{
sopt++;
temp[sopt]=A[a];
}
}
//sapxep
/*for(int a=1;a<=sopt;a++)
{
for(int b=a+1;b<=sopt;b++)
{
if(temp[a]>temp[b])
{
int x=temp[a];temp[a]=temp[b];temp[b]=x;
}
}
}*/
//
if(kiemtratrunglap(temp,sopt))
{
dem++;
mangkiemtra[stt][0]=sopt;
for(int a=1;a<=sopt;a++) mangkiemtra[stt][a]=temp[a];
stt++;
}
}
}
else
{
back(idx+1);
}
}
}
int main()
{
freopen("input.txt","r",stdin);
int t;cin>>t;
for(int tc=1;tc<=t;tc++)
{
cin>>tong>>n;
for(int i=0;i<n;i++)
{
cin>>A[i];
used[i]=0;
}
//
dem=0;
stt=0;
reset();
//
back(0);
//
cout<<"#"<<tc<<" ";
if(dem==0) cout<<-1<<endl;
else cout<<dem<<endl;
}
return 0;
}
Bai 13: HoDen
Tất cả vị trí trong vũ trụ được cho bởi tọa độ 2 chiều (X, Y).
Tàu vũ trụ chỉ có thể di chuyển theo hướng song song với trục X hoặc trục Y và mất 1 giây để di chuyển khoảng cách 1 đơn vị.
Do đó, thời gian mà tàu vũ trụ cần để di chuyển từ tọa độ (x1, y1) tới (x2, y2) được tính như sau:
Có tất cả N hố đen trong không gian. Ki là thời gian để di chuyển qua mỗi hố đen, mỗi hố đen có Ki khác nhau.
Và hố đen cho phép di chuyển theo 2 chiều.
Để thuận tiện, 2 lối vào của hố đen được gọi là Cổng A và Cổng B.
※ Không bắt buộc phải sử dụng tất cả hố đen để di chuyển tới điểm đích. Cũng có thể không cần dùng đến bất kì hố đen nào trong quá trình di chuyển.
Cũng không bắt buộc phải di chuyển qua hố đen mặc dù tàu vũ trụ gặp một cổng của hố đen đó.
▶ Cho thông tin về điểm bắt đầu và điểm đích (tọa độ) của tàu vũ trụ và thông tin về mỗi hố đen,
hãy tìm thời gian ngắn nhất để di chuyển từ điểm bắt đầu tới điểm đích.
[Giới hạn]
1. Số lượng hố đen N lớn hơn hoặc bằng 0 và nhỏ hơn hoặc bằng 5 (0 ≤ N ≤ 5).
2. Thời gian để di chuyển qua một hố đen Ki lớn hơn hoặc bằng 0 và nhỏ hơn hoặc bằng 3,000. (0 ≤ Ki ≤ 3,000)
3. X, Y, tọa độ trong vũ trụ lớn hơn hoặc bằng 0 và nhỏ hơn hoặc bằng 1,000. (0 ≤ X, Y ≤ 1,000)
4. Không có trường hợp nào mà tọa độ của điểm bắt đầu, điểm đích của tàu vũ trụ và tọa độ của những hố đen giống nhau.
[Input]
Dòng đầu tiên của là số lượng phép thử T. Từ dòng tiếp theo là thông tin về mỗi phép thử.
Dòng đầu tiên của mỗi phép thử là số lượng hố đen N.
Dòng thứ 2 là điểm bắt đầu [x1, y1] và điểm đích [x2, y2] của tàu vũ trụ.
Từ dòng thứ 3 tới dòng thứ ‘N+1’ là thông tin về mỗi hố đen.
Tọa độ [x, y] của Cổng A và [x, y] của Cổng B của mỗi hố đen, và thời gian để di chuyển qua hố đen.
[Output]
In “#T” cho phép thử thứ T, tiếp theo là một khoảng cách và in câu trả lời (T là số thứ tự của phép thử bắt đầu từ 1).
[Input Mẫu]
[Output Mẫu]
Bai 14: Mario
Mario
Mario Climb
0 0 1 3
1 1 1 0
0 0 0 0
2 1 1 1
Mario cần phải di chuyển từ vị trí có giá trị bằng 2 và ăn vàng ở ô có giá trị bằng 3
0 là nhữngô Mario không thể qua
1 là nhữngô Mario có thể qua
2 là vị trícủa Mario
3 là vị trí Mario cần di chuyển đến
Các vị trí này được thể hiện bằng ma trận NxM( 2<=N,M<=50)
Mario có thểdi chuyển theo hàng ngang hoặc hàng dọc
Hàng ngang mario chỉ nhảy được tối đa 1 bước
Hàng dọc mario có thể nhảy được “h” bước
Tìm bước nhảy “h” tối thiểu để Mario có thể ăn được vàng
Sample Input
3
5 8
1 1 1 1 0 0 0 0
0 0 0 3 0 1 1 1
1 1 1 0 0 1 0 0
0 0 0 0 0 0 1 0
2 1 1 1 1 1 1 1
5 6
0 1 1 1 0 0
3 1 0 1 1 0
0 0 0 0 1 1
0 0 0 0 0 1
2 1 1 1 1 1
9 13
0 1 1 1 1 1 1 1 1 1 1 1 1
1 1 0 0 0 0 0 0 0 0 0 1 1
0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0
1 1 0 0 0 0 0 0 0 0 0 1 3
0 0 0 0 0 0 0 0 0 0 0 0 0
1 1 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0
2 1 1 1 1 1 1 1 1 1 1 1 1
Sample output
Case #1
2
Case #2
1
Case #3
3
Code: #include <iostream> // Thư viện nhập xuất cơ bản
using namespace std; // Sử dụng không gian tên std
const int MAX = 51; // Định nghĩa hằng số tối đa
int arr[MAX][MAX]; // Mảng lưu trữ ma trận
bool visited[MAX][MAX]; // Mảng lưu trữ các ô đã được duyệt
int n, m; // Kích thước ma trận
int ans; // Biến lưu trữ kết quả
int T, startX, startY;
// Hàm giải quyết bài toán đệ quy
void solve(int x, int y, int diff) {
// Kiểm tra điều kiện thoát của đệ quy
if (x < 0 || y < 0 || x >= n || y >= m) {
return;
}
if (arr[x][y] == 3) {
ans = min(ans, diff); // Cập nhật kết quả nếu gặp ô mục tiêu
return;
}
visited[x][y] = true; // Đánh dấu ô đã được duyệt
// Duyệt các ô xung quanh
int up = x - 1;
while (arr[up][y] == 0 && up >= 0) {
up--;
}
if (up >= 0 && !visited[up][y]) {
solve(up, y, max(diff, x - up));
}
int down = x + 1;
while (arr[down][y] == 0 && down < n) {
down++;
}
if (down < n && !visited[down][y]) {
solve(down, y, max(diff, down - x));
}
if (arr[x][y + 1] != 0 && !visited[x][y + 1] && y + 1 < m) {
solve(x, y + 1, diff);
}
if (arr[x][y - 1] != 0 && !visited[x][y - 1] && y - 1 >= 0) {
solve(x, y - 1, diff);
}
visited[x][y] = false; // Hủy đánh dấu ô đã được duyệt
}
int main() {
// Mở file input.txt để đọc dữ liệu
//freopen("input.txt", "r", stdin);
freopen("Mario.txt", "r", stdin);
cin >> T;
for(int tc = 1; tc <= T; tc++){
cin >> n >> m; // Nhập kích thước ma trận
// Nhập ma trận từ file hoặc bàn phím
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
cin >> arr[i][j];
if(arr[i][j] == 2){
startX = i;
startY = j;
}
}
}
// Khởi tạo mảng visited
for (int i = 0; i < MAX; i++) {
for (int j = 0; j < MAX; j++) {
visited[i][j] = false;
}
}
ans = 100; // Khởi tạo kết quả
solve(startX, startY, 0); // Gọi hàm giải quyết bài toán
cout << "Case #" << tc << endl;
cout << ans << endl; // In kết quả
}
return 0;
}
Bai 15:
Pink and Blue
Xenny was a teacher and he had N students. The N children were sitting in a room. Each child was wearing a white T-shirt, with a unique number from the range 1 to N written on it. T-Shirts of pink and blue color were to be distributed among the students by Xenny. This made the students very happy.
Xenny felt that a random distribution of T-Shirts would be very uninteresting. So, he decided to keep an interesting condition:
Every student would get a T-Shirt that is of a different color than his/her friends. That is, if X and Y are friends and X has a Pink T-Shirt, then Y should compulsorily have a Blue T-Shirt, and vice-versa.
Also, Xenny had a belief that Boys should wear blue T-Shirts and Girls should wear pink T-Shirts. If a boy was given a pink T-Shirt or a girl was given a Blue T-Shirt, he called it an inversion.
So, Xenny wanted to distribute T-Shirts in the above-mentioned interesting manner and also wanted to minimize "inversions". Help him solve the task.
Note: There are no disjoint groups of friends in the room. That is, 2 distinct groups with finite number of students do not exist, but exactly 1 group of students exists in the given situation.
Input
The first line is the number of test cases T.
First line of each test case contains 2 space-separated integers - N and M - number of students and number of friendships present respectively.
Second line consists of N space-separated characters, where ith character denotes the gender of the ith student. B: Boy, G: Girl.
M lines follow. Each line consists of 2 space-separated integers, u and v, showing that u is a friend of v and vice-versa.
Output
If Xenny could distribute the T-Shirts in the desired way, print the minimum number of inversions required.
Else, print -1.
Constraints
1 ≤ N ≤ 105
1 ≤ M ≤ 105
1 ≤ u, v ≤ N
Colors of T-Shirt are represented by uppercase characters 'B' and 'G'
Sample
Input
3
3 2
B G B
1 2
1 3
6 9
B B B G G G
3 5
2 6
4 2
6 3
3 1
3 4
6 1
5 1
1 4
6 5
G G G B G G
6 3
1 3
2 3
4 3
5 3
Output
1
-1
2
Explanation
#1
Student 1 can be given a Blue T-Shirt. Hence, Student 2 and 3 would receive Pink T-Shirts. Since, Student 3 is a Boy and has received a Pink T-Shirt, number of inversions = 1.
Bai 16:
Mountain Walking
Cho một bản đồ kích thước NxN (2 <= N <= 100), mỗi ô mang giá trị là độ cao của ô đó (0 <= độ cao <= 110). Bác John và bò Bessie đang ở ô trên trái (dòng 1, cột 1) và muốn đi đến cabin (dòng N, cột N). Họ có thể đi sang phải, trái, lên trên và xuống dưới nhưng không thể đi theo đường chéo. Hãy giúp bác John và bò Bessie tìm đường đi sao cho chênh lệch giữa điểm cao nhất và thấp nhất trên đường đi là nhỏ nhất.
Input
Dòng 1: Số test case
Dòng 2: N
N dòng tiếp theo chứa N số nguyên, mỗi số cho biết cao độ của một ô.
Output
In ra #test case và một số nguyên là chênh lệch độ cao nhỏ nhất.
Sample
Input
5
5
1 1 3 6 8
1 2 2 5 5
4 4 0 3 3
8 0 2 3 4
4 3 0 2 1
5
99 85 38 22 55
89 28 33 3 65
99 20 14 67 90
36 27 28 77 31
50 45 12 9 14
2
92 83
19 91
5
61 49 32 34 28
100 65 0 10 89
34 99 40 86 4
10 97 49 21 30
95 33 79 51 65
2
17 60
94 27
Output
#1 2
#2 85
#3 9
#4 50
#5 43
#include<iostream>
using namespace std;
int T, N, arr[101][101], visited[101][101];
int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, -1, 1};
const int MAX = 100000;
struct Queue{
int front, rear;
int queue[MAX];
Queue(){
front = rear = -1;
}
void push(int value){
queue[++rear] = value;
}
int pop(){
return queue[++front];
}
bool isEmpty(){
return rear == front;
}
};
bool isValid(int x, int y){
return x >= 1 && x <= N && y >= 1 && y <= N;
}
void reset(){
for(int i = 1; i <= N; i++){
for(int j = 1; j <= N; j++){
visited[i][j] = 0;
}
}
}
bool check(int x, int y){
Queue q;
q.push(1);
q.push(1);
visited[1][1] = 1;
if(arr[1][1] < x || arr[1][1] > y || arr[N][N] < x || arr[N][N] > y) return false;
while(!q.isEmpty()){
int r = q.pop();
int c = q.pop();
if(r == N && c == N){
return true;
}
for(int i = 0; i < 4; i++){
int nx = r + dx[i];
int ny = c + dy[i];
if(isValid(nx, ny) && visited[nx][ny] == 0 && arr[nx][ny] >= x && arr[nx][ny] <= y){
visited[nx][ny] = 1;
q.push(nx);
q.push(ny);
}
}
}
return false;
//return true;
}
int main(){
//freopen("MoutainWorking.txt", "r", stdin);
//freopen("input.txt", "r", stdin);
cin >> T;
for(int tc = 1; tc <= T; tc++){
int maxx = 0;
cin >> N;
for(int i = 1; i <= N; i++){
for(int j = 1; j <= N; j++){
cin >> arr[i][j];
//if(arr[i][j] > maxx) maxx = arr[i][j];
}
}
reset();
int Hleft = 0, Hright = 111;
/*if(check(0, 4)){
cout << "Thangdz" << endl;
}*/
int mid = 0;
while(Hleft < Hright){
mid = (Hleft + Hright) / 2;
bool ok = false;
for(int st = 0; st <= 111; st++){
reset();
if(check(st, st+ mid)){
ok = true;
break;
}
}
if(ok){
Hright = mid;
}
else{
Hleft = mid+1;
}
reset();
}
cout << "#" << tc << " " << Hleft << endl;
}
return 0;
}
Bai 17: Tuan Trang Mat
Tuần Trăng Mật
Tuần trăng mật
Đám cưới anh Uranus diễn ra rất vui vẻ, chỉ có Tomoky là có chút hậm hực. Sau đám cưới, anh Uranus muốn đi tuần trăng mật ở thành phố Đà Lạt xinh đẹp.
Thành phố Đà Lạt gồm n điểm du lịch trọng điểm, được đánh số từ 1 tới n. Hệ thống giao thông trong vùng gồm m (m <= n*(n-1)) tuyến đường một chiều khác nhau, tuyến đường thứ j (j = 1,2,…m) cho phép đi từ địa điểm u_j tới địa điểm v_j với chi phí đi lại là số nguyên dương c(u_j, v_j).
Anh Uranus muốn xuất phát từ điểm du lịch 1 và đi thăm k địa điểm du lịch s_1, s_2, …, s_k (khác địa điểm 1) và sau đó quay về địa điểm xuất phát 1 với tổng chi phí là nhỏ nhất.
Cho thông tin về hệ thống giao thông và k địa điểm du lịch s_1, s_2, …, s_k. Hãy giúp anh Uranus xây dựng một hành trình du lịch xuất phát từ địa điểm du lịch 1 và đi thăm k địa điểm s_1, s_2, …, s_k sau đó quay về địa điểm du lịch 1 với tổng chi phí nhỏ nhất.
Input
• Dòng đầu tiên chứa số nguyên dương T là số bộ test. Mỗi bộ test gồm:
• Dòng thứ nhất chứa 3 số nguyên n, m, k (n <= 1000 và k <= 15).
• Dòng thứ hai chứa k số nguyên dương s_1, s_2, …, s_k.
• Dòng thứ j trong m dòng tiếp theo chứa 3 số nguyên dương u_j, v_j, c(u_j, v_j) cho biết thông tiên về tuyến đường thứ j. Biết rằng u_j luôn khác v_j, và c(u_j, v_j) <= 10^9.
Output
In ra một số nguyên là tổng chi phí nhỏ nhất tìm được. Nếu không tìm được một hành trình du lịch nào, in ra số -1.
Example
Input:
1
6 8 2
2 5
1 2 4
2 4 2
4 3 3
3 1 4
4 1 5
3 5 5
5 3 1
5 6 7
Output:
Case #1
19
Case #2
57
Code: package TuanTrangMat;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.Scanner;
public class Solution {
static int n;// diem du lich
static int m;// so tuyen duong
static int k;
static int desti[];
static int dsLK[][];
static int dsWeight[][];
static int dsVisit[][];
static int visitDisti[];
static int choose[];
static int min;
static void input(Scanner sc) {
n = sc.nextInt();
m = sc.nextInt();
k = sc.nextInt();
desti = new int[k + 1];
choose = new int[k + 1];
visitDisti = new int[k + 1];
dsLK = new int[n + 1][n + 1];
dsWeight = new int[n + 1][n + 1];
dsVisit = new int[n + 1][n + 1];
for (int i = 1; i <= k; i++) {
desti[i] = sc.nextInt();
}
for (int i = 0; i < m; i++) {
int index1 = sc.nextInt();
int index2 = sc.nextInt();
int weight = sc.nextInt();
dsLK[index1][0]++;
dsLK[index1][dsLK[index1][0]] = index2;
dsWeight[index1][dsLK[index1][0]] = weight;
}
// for (int i = 1; i <= n; i++) {
// for (int j = 1; j <= n; j++) {
// System.out.print(dsWeight[i][j] + " ");
// }
// System.out.println();
// }
}
static void solve() {
min = Integer.MAX_VALUE;
dfs(1, 1, 0);
System.out.println(min);
}
static void dfs(int x, int stt, int sum) {
if (stt > k) {
// update
update(sum);
}
for (int i = 1; i <= dsLK[x][0]; i++) {
int tmp = dsLK[x][i];
if (dsVisit[x][i] == 0) {
dsVisit[x][i] = 1;
if (check(tmp) == true) {
choose[stt] = tmp;
// visitDisti[tmp] = 1;
dfs(tmp, stt + 1, sum + dsWeight[x][i]);
} else if (sum < min) {
dfs(tmp, stt, sum + dsWeight[x][i]);
}
dsVisit[x][i] = 0;
}
}
}
static void update(int sum) {
int x = choose[k];
// reset visit
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= dsVisit[i][0]; j++) {
dsVisit[i][j] = 0;
}
}
dfs2(x, sum);
}
static void dfs2(int x, int sum) {
for (int i = 1; i <= dsLK[x][0]; i++) {
int tmp = dsLK[x][i];
if (dsVisit[x][i] == 0) {
dsVisit[x][i] = 1;
if (tmp == 1) {
// update
//
update2(sum + dsWeight[x][i]);
} else if (sum < min) {
dfs2(tmp, sum + dsWeight[x][i]);
}
dsVisit[x][i] = 0;
}
}
}
static void update2(int sum) {
if (min > sum) {
min = sum;
}
}
static boolean check(int x) {
for (int i = 1; i <= k; i++) {
if (desti[i] == x && visitDisti[i] == 0) {
visitDisti[i] = 1;
return true;
}
}
return false;
}
public static void main(String[] args) throws FileNotFoundException {
// TODO Auto-generated method stub
System.setIn(new FileInputStream("src/TuanTrangMat/input.txt"));
Scanner sc = new Scanner(System.in);
int T = sc.nextInt();
for (int t = 1; t <= T; t++) {
System.out.println("Case #" + t);
input(sc);
solve();
}
}
}
Bai 18: Mời đám cưới
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
Code: #include<iostream>
using namespace std;
int T, N, M, u, v, arr[101][101];
int visited[101], Answer;
const int MAX = 100000;
struct Queue
{
int front, rear;
int queue[MAX];
Queue(){
front = rear = -1;
}
void push(int value){
queue[++rear] = value;
}
int pop(){
return queue[++front];
}
bool isEmpty(){
return front == rear;
}
};
//struct Stack
//{
// int stack[MAX];
// int top;
// Stack()
// {
// top=-1;
// }
//
// int isEmpty()
// {
// return top == -1 ;
// }
//
//
// void push(int value)
// {
// stack[++top]=value;
//
// }
//
// int pop()
// {
// return stack[top--];
// }
//
//};
void reset(){
for(int i = 1; i <= N; i++){
visited[i] = 0;
}
}
//bool dfs(int x, int y){
// Stack s;
// s.push(x);
// visited[x] = 1;
// while(!s.isEmpty()){
// int _x = s.pop();
// if(_x == y) {
// return false;
// }
// for(int i = 1; i < N; i++){
// if(arr[_x][i] == 1 && visited[i] == 0){
// s.push(i);
// visited[i] = 1;
// }
// }
// }
// return true;
//}
void bfs(int x){
Queue q;
q.push(x);
visited[x] = 1;
while(!q.isEmpty()){
int _x = q.pop();
for(int i = 1; i <= N; i++){
if(arr[_x][i] == 1 && visited[i] == 0){
q.push(i);
visited[i] = 1;
}
}
}
}
int main(){
//freopen("input.txt", "r", stdin);
//freopen("MoiDamCuoi.txt", "r", stdin);
cin >> T;
for(int tc = 1; tc <= T; tc++){
Answer = 0;
cin >> N >> M >> u >> v;
for(int i = 1; i <= N; i++){
for(int j = 1; j <= N; j++){
arr[i][j] = 0;
}
visited[i] = 0;
}
int a, b;
for(int i = 1; i <= M; i++){
cin >> a >> b;
arr[a][b] = 1;
}
for(int i = 1; i <= N ; i++){
reset();
if(i != u && i != v){
visited[i] = 1;
bfs(u);
if(visited[v] == 0){
Answer++;
//cout << i << " ";
}
}
}
cout << Answer << endl;
cout << endl;
}
return 0;
}
Bai 19: Đi ăn cưới
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
Code: #include<iostream>
using namespace std;
int nt; // Số lượng bộ test
int n, m; // Số đỉnh và số cạnh trong đồ thị
int map[21][21]; // Ma trận lưu trữ đồ thị
int dem[21]; // Mảng đếm số lần đi qua mỗi đỉnh
int vx, vy; // Biến tạm thời lưu giá trị các đỉnh trong cạnh
int mindiem;
// Khởi tạo lại ma trận đồ thị
void restmap() {
for(int i = 0; i <= n; i ++) {
for(int j = 0; j <= n; j++) {
map[i][j]= 0;
}
}
}
// Khởi tạo lại mảng đếm số lần đi qua đỉnh
void resetDem() {
for(int i =0 ; i <= n; i++) {
dem[i]=0;
}
}
// Đếm số lượng đỉnh khác nhau đã đi qua
int countdiem() {
int len = 0;
for(int i = 1; i <= n; i++) {
if(dem[i]!=0) {
len++;
}
}
return len;
}
// Thuật toán Backtracking để tìm đường đi tối ưu
void Backtrack(int v) {
// Nếu đến được đích và số đỉnh 1 và 2 đều được đi qua đúng số lần
if(v==1 && dem[1]==2 && dem[2]==1) {
// Đếm số lượng đỉnh khác nhau đã đi qua và cập nhật vào mindiem
int len = countdiem();
if(len < mindiem) {
mindiem = len;
}
return;
}
// Nếu số đỉnh khác nhau đã đi qua lớn hơn mindiem, dừng lại
if(countdiem() > mindiem) {
return;
}
// Thử tất cả các cách di chuyển từ đỉnh hiện tại v
for(int i = 1; i <= n; i++) {
// Nếu có đường đi từ i
if(map[v][i] == 1 && ((dem[2]==1 && dem[i] < 2) || (dem[2]==0 && dem[i]<1))) {
// Đánh dấu đã đi qua đỉnh i
dem[i]++;
// Thử di chuyển đến đỉnh i
Backtrack(i);
// Quay lui: bỏ đánh dấu đã đi qua đỉnh i
dem[i]--;
}
}
}
int main() {
//freopen("input.txt", "r", stdin);
cin >> nt;
for(int test = 1; test <= nt; test++) {
// Đọc số đỉnh và số cạnh của đồ thị
cin >> n >> m;
// Khởi tạo lại ma trận đồ thị và mảng đếm số lần đi qua đỉnh
restmap();
resetDem();
// Đọc các cạnh của đồ thị và lưu vào ma trận đồ thị
for(int i = 0; i < m; i++) {
cin >> vx >> vy;
map[vx][vy] = 1;
}
// Khởi tạo biến mindiem với giá trị lớn để lưu số đỉnh tối thiểu cần đi qua
mindiem = 9999999;
// Bắt đầu thử tất cả các đường đi có thể từ đỉnh 1
dem[1] = 1;
Backtrack(1);
// In ra màn hình số đỉnh tối thiểu cần đi qua từ đỉnh 1 đến đỉnh 2 và quay lại đỉnh 1
cout << mindiem << endl;
}
return 0;
}
Bai 20:
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
Code: #define INF 1e9
#include<iostream>
using namespace std;
const int maxS = 1e6;
int N, H, M;
bool hasElectric[1001];//danh sach dao co tram phat dien
int map[1001][1001];
int doyeu[1001];
int Q[maxS];
int top, bot;
void init() {
for(int i = 0; i < N; i++) {
doyeu[i] = INF;
hasElectric[i] = false;
}
for(int i = 0; i < N; i++) {
for(int j = 0; j < N; j++) {
map[i][j] = 0;
}
}
}
void reset() {
top = -1, bot = -1;
}
bool isEmpty() {
return top == bot;
}
void push(int x) {
if(top == maxS-1) top = -1;
top++;
Q[top] = x;
}
void pop(int &x) {
if(bot == maxS-1) bot = -1;
bot++;
x = Q[bot];
}
void bfs(int x) {
reset();
push(x);
while(!isEmpty()) {
pop(x);
for(int i = 0; i < N; i++) {
if(!hasElectric[i] && map[x][i] == 1 && (doyeu[i] > doyeu[x]+1)) {
doyeu[i] = doyeu[x]+1;
push(i);
}
}
}
}
int main() {
//freopen("HeThongDien.txt", "r", stdin);
int T;
cin >> T;
for(int t = 1; t <= T; t++) {
cin >> N >> M >> H;
init();
int dao;
for(int i = 0; i < M; i++) {
cin >> dao;
hasElectric[dao] = true;
doyeu[dao] = 0;
}
int x, y;
for(int i = 0; i < H; i++) {
cin >> x >> y;
map[x][y] = 1;
map[y][x] = 1;
}
for(int i = 0; i < N; i++) {
if(hasElectric[i]==true) {
bfs(i);
}
}
int weekness = 0;
for(int i = 1; i < N; i++){
if(doyeu[i] > doyeu[weekness]) {
weekness = i;
}
}
cout<<weekness<<endl;
}
return 0;
}
Bai 21: DaoCot
Code: #include <iostream>
using namespace std;
const int MAX_N = 1000; // Số hàng tối đa
const int MAX_M = 1000; // Số cột tối đa
int n, m, k, ans;
int arr[MAX_N][MAX_M]; // Mảng 2 chiều
int find(int x) {
int count = 0;
for (int i = 0; i < m; i++) {
if (arr[x][i] == 0) {
count++;
}
}
if (k >= count && (k - count) % 2 == 0) {
ans = 1;
for (int i = 0; i < n; i++) {
bool check = true;
if (i != x) {
for (int j = 0; j < m; j++) {
if (arr[x][j] != arr[i][j]) {
check = false;
}
}
if (check) {
ans++;
}
}
}
}
return ans;
}
int main() {
freopen("DaoCot.txt", "r", stdin);
int T;
cin >> T; // Đọc số lượng test case
for (int tc = 1; tc <= T; tc++) {
cin >> n >> m >> k; // Đọc các giá trị n, m, k cho mỗi test case
// Đọc dữ liệu vào mảng arr
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
cin >> arr[i][j];
}
}
ans = 0;
// Duyệt qua từng hàng và tìm số lượng cột có giá trị 0
for (int i = 0; i < n; i++) {
int num = find(i);
if (ans < num) {
ans = num;
}
}
cout << "Case #" << tc << " " << ans << endl; // In kết quả cho mỗi test case
}
return 0;
}
Bai 22: 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
Code: #include <iostream>
using namespace std;
const int maxSize = 30;
int T, node, edge, maxx = 0;
int maTranKe[maxSize][maxSize];
int visit[maxSize][maxSize];
//int sum = 0;
void BT(int step, int sum) {
if (sum > maxx) maxx = sum;
for (int i = 0; i < node; i++) {
if (maTranKe[step][i] == 1 && visit[step][i] == 0) {
visit[step][i] = 1;
visit[i][step] = 1;
BT(i, sum+1);
visit[step][i] = 0;
visit[i][step] = 0;
}
}
}
void reset() {
for (int i = 0; i <= node; i++) {
for (int j = 0; j <= node; j++) {
visit[i][j] = 0;
maTranKe[i][j] = 0;
}
}
}
void resetVisit() {
for (int i = 0; i <= node; i++) {
for (int j = 0; j <= node; j++) {
visit[i][j] = 0;
}
}
}
int main() {
freopen("TheSettlersOfCatan.txt", "r", stdin);
cin >> T;
for (int tc = 1; tc <= T; tc ++) {
cin >> node >> edge;
reset();
for (int i = 1; i <= edge; i++) {
int temp1, temp2;
cin >> temp1 >> temp2;
maTranKe[temp1][temp2] = 1;
maTranKe[temp2][temp1] = 1;
}
maxx = 0;
for (int i = 0; i < node; i++) {
BT(i, 0);
}
cout << maxx << " " << endl;
}
//while(1);
return 0;
}
Bai 22:
Editor is loading...
Leave a Comment