Untitled
unknown
plain_text
2 years ago
18 kB
5
Indexable
https://send.zcyph.cc/download/5c4508dad08d89f3/#b3KqQ51QmAwGGeTpxgCGYg
HUGO FIRE
struct Location
{
int row, col;
};
int nFire, nLake, nExit;
int Diamond[20][20];
int map[20][20];
int FireTime[20][20];
int MarkHugo[20][20];
int dx[] = {0,-1,0,1};
int dy[] = {-1,0,1,0};
Location Fire[1000];
Location Lake[1000];
Location Exit[1000];
int Row, Col; // MxN
int SR,SC; //Hugo
int maxDiamond;
void spreadFireBFS(Location fire){
Location queue[1000];
int front = 0;
int rear = 0;
// start from all Fire
for (int i = 0; i < nFire; i++)
{
queue[rear++] = Fire[i];
}
while (front < rear)
{
Location current = queue[front++];
int currentTime = FireTime[current.row][current.col];
for (int i = 0; i <4; i++)
{
int xx = current.row + dx[i];
int yy = current.col + dy[i];
if (xx <= 0 || xx > Row || yy <= 0 || yy > Col) continue;
if (map[xx][yy] != 2 && FireTime[xx][yy] > currentTime + 1)
{
FireTime[xx][yy] = currentTime + 1;
Location lc;
lc.row = xx;
lc.col = yy;
queue[rear++] = lc;
}
}
}
}
void BT(Location current, int time, int sumDiamond){
// in Exit
if (map[current.row][current.col] == 3) {
maxDiamond = maxDiamond < sumDiamond ? sumDiamond : maxDiamond;
return;
}
//
for (int i = 0; i <4; i++)
{
int xx = current.row + dx[i];
int yy = current.col + dy[i];
if (xx <= 0 || xx > Row || yy <= 0 || yy > Col) continue;
//
if (MarkHugo[xx][yy] == 0 && time + 1 < FireTime[xx][yy])
{
MarkHugo[xx][yy] = 1;
Location lc;
lc.row = xx;
lc.col = yy;
if (map[xx][yy] == 2) BT(lc,time + 2, sumDiamond + Diamond[xx][yy]);
else BT(lc,time + 1, sumDiamond + Diamond[xx][yy]);
MarkHugo[xx][yy] = 0;
}
}
}
int main(){
int T;
cin>>T;
for (int tc = 1; tc <= T; tc++)
{
maxDiamond = 0;
cin>>Row>>Col>>SR>>SC;
// initalize
for (int i = 1; i <= Row; i++)
for (int j = 1; j <= Col; j++){
map[i][j] = 1;
FireTime[i][j] = 10000;
MarkHugo[i][j] = 0;
}
// input
// fire
cin>>nFire;
for (int i = 0; i < nFire; i++)
{
Location lc;
cin>>lc.row>>lc.col;
map[lc.row][lc.col] = 0; // danh dau trong map la lua
FireTime[lc.row][lc.col] = 0;
Fire[i] = lc;
}
// Lake
cin>>nLake;
for (int i = 0; i < nLake; i++)
{
Location lc;
cin>>lc.row>>lc.col;
map[lc.row][lc.col] = 2; // danh dau trong map la lua
Lake[i] = lc;
}
// Exit
cin>>nExit;
for (int i = 0; i < nExit; i++)
{
Location lc;
cin>>lc.row>>lc.col;
map[lc.row][lc.col] = 3; // danh dau trong map la lua
Exit[i] = lc;
}
// Map kim cuong
for (int i = 1; i <= Row; i++)
for (int j = 1; j <= Col; j++){
cin>>Diamond[i][j];
}
}
return 0;
}
Mời Đám Cưới
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
// In Practice, You should use the statndard input/output
// in order to receive a score properly.
// Do not use file input and output. Please be very careful.
#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
using namespace std;
int Answer;
int N,M,u,v;
int visit[105], map[105][105];
int Queue[10025],startQ,endQ;
void push(int x){
Queue[endQ] = x;
visit[x] = 1;
endQ ++;
}
bool BFS(int k){
for(int i = 1 ; i<= N; i++) visit[i] = 0;
startQ = 0;
endQ = 0;
push(u);
while (startQ < endQ){
int x = Queue[startQ];
startQ ++ ;
for (int i = 1; i<= map[x][0] ; i++){
if (visit[ map[x][i] ] == 0 && map[x][i] != k) push(map[x][i]);
}
if (visit[v] == 1) return false;
}
return true;
}
int main(int argc, char** argv)
{
int test_case;
int T;
ios::sync_with_stdio(false);
/*
The freopen function below opens input.txt in read only mode and
sets your standard input to work with the opened file.
When you test your code with the sample data, you can use the function
below to read in from the sample data file instead of the standard input.
So. you can uncomment the following line for your local test. But you
have to comment the following line when you submit for your scores.
*/
//freopen("input.txt", "r", stdin);
//freopen("output.txt", "w", stdout);
cin >> T;
/*
Read each test case from standard input.
*/
for(test_case = 1; test_case <= T; ++test_case)
{
Answer = 0;
/////////////////////////////////////////////////////////////////////////////////////////////
/*
Please, implement your algorithm from this section.
*/
/////////////////////////////////////////////////////////////////////////////////////////////
cin >> N >> M >> u >> v;
for( int i = 1; i<=N; i++) map[i][0] = 0;
for( int i = 1; i<=M; i++){
int x,y;
cin >> x >> y;
map[x][0] ++;
map[x][ map[x][0] ] = y;
}
for (int i =1; i <= N; i++){
if (i == v) continue;
if (BFS(i)) Answer ++;
}
// Print the answer to standard output(screen).
cout << Answer << endl<<endl;
}
return 0;//Your program should return 0 on normal termination.
}
MARIO CLIMB
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
#include<iostream>
using namespace std;
int M,N, h;
int A[55][55];
int visit[55][55];
int x_st, y_st, x_end , y_end;
int f=-1;
int Qx[100000];
int Qy[100000];
int dx[4]= {1,-1,0,0};
int dy[4]= {0,0,1,-1};
void push(int x,int y)
{
f++;
Qx[f] =x;
Qy[f] =y;
}
void reset()
{
for(int i=1; i<= M; i++)
{
for(int j=1; j<=N; j++)
{
visit[i][j] =0;
}
}
}
void pop(int &x,int &y)
{
x= Qx[f];
y= Qy[f];
f--;
}
bool dfs(int x,int y,int h)
{
f=-1;
push(x,y);
visit[x][y] =1;
while(f != -1)
{
pop(x,y);
for(int i=1; i<=h; i++)
{
for(int j=0; j<4; j++)
{
int xx = x +i* dx[j];
int yy= y + dy[j];
if(visit[xx][yy] == 0 && xx>=1 && xx <=M && yy >=1 && yy <=N && A[xx][yy] != 0){
if(A[xx][yy] == 3) { return true; }
push(xx,yy);
visit[xx][yy] =1;
}
}
}
}
return false;
}
int main()
{
int t;
cin >> t;
for(int stt=1; stt <=t; stt++)
{
cin >> M >> N;
for(int i=1; i<= M; i++)
{
for(int j=1; j<=N; j++)
{
cin >> A[i][j];
if(A[i][j] ==2) { x_st = i; y_st = j;}
}
}
//////////////////////////
int ans =0;
for(int i=1; i<= N-1; i++){
reset();
if(dfs(x_st,y_st,i)){
ans = i;
break;
}
}
///////////////////
cout << "Case #" << stt << endl << ans << endl;
}
}
Tiết Kiệm Điện
Tiết kiệm điện
Văn phòng APS 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).
Có một quy định được ban hành trong APS P: Nhân viên rời văn phòng cuối cùng phải có trách nhiệm tắt đèn trong văn phòng sao cho số lượng bóng đèn được tắt là lớn nhất. Tuy nhiên để thử thách tư duy của các nhân viên, nhân viên rời văn phòng cuối đó chỉ được phép thay đổi trạng thái khóa tối đa 3 lần, mỗi lần được chọn tối đa 1 khóa.
Hãy tạo một chương trình giúp các nhân viên tìm ra phương án 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
#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
using namespace std;
int N,K;
int Light[105];
int sumOFF;
int Answer;
void Switch(int k){
for(int i = k; i <= N; i += k+1) Light[i] = 1 - Light[i];
}
void BackTrack(int h){
sumOFF = 0; // numbers of OFF-LIGHT
for(int i = 1; i <=N; i++){
if (Light[i] == 0) sumOFF ++;
}
Answer = Answer < sumOFF ? sumOFF : Answer; // find MAX of OFF-LIGHT
// Stop condition
if (h > 3) return;
// (k1,k1,k1) -> (k1,k1,k2) -> (k1,k1,k3) -> (k1,k2,k1) -> (k1,k2,k2) -> (k1,k2,k3)->.....
for(int i = 1 ; i<=K; i++){
Switch(i);
BackTrack(h + 1);
Switch(i);
}
}
int main(int argc, char** argv)
{
int test_case;
int T;
//freopen("input.txt", "r", stdin);
//freopen("output.txt", "w", stdout);
cin >> T;
for(test_case = 1; test_case <= T; ++test_case)
{
Answer = 0;
cin >> N >> K;
for (int i = 1; i <= N; i++) {
cin >> Light[i];
}
sumOFF = 0;
BackTrack(1);
cout << "#" << test_case << " " << Answer << endl;
}
return 0;
}
/// Dominating Area: BFS(0), BFS(i#0), demvung()
#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
using namespace std;
int Answer;
int N;
int map[105][105];
int visitD0[105][105];
int visit[105][105];
int Queue[1000025][2];
int startQ,endQ;
int dx[] = {-1, 0, 1, 0};
int dy[] = { 0, 1, 0,-1};
int Area;
int Dominated[100005],visitDominated[100005];
int countDominated, indexDominated[100005];
void push(int x, int y){
Queue[endQ][0] = x;
Queue[endQ][1] = y;
endQ++;
}
void BFS(int x, int y){
startQ = 0;
endQ = 0;
int count = 1;
push(x,y);
visit[x][y] = Area;
while (startQ < endQ){
int xCurent = Queue[startQ][0];
int yCurent = Queue[startQ][1];
startQ++;
for (int i = 0; i < 4; i++){
int xNext = xCurent + dx[i];
int yNext = yCurent + dy[i];
if (visit[xNext][yNext] == 0 && map[xNext][yNext] == map[xCurent][yCurent]){
push(xNext,yNext);
visit[xNext][yNext] = Area;
count ++;
}
}
}
Dominated[Area] = count;
visitDominated[Area] = 0;
Area ++;
}
void countArea(int x, int y){
startQ = 0;
endQ = 0;
push(x,y);
visit[x][y] = 1;
while (startQ < endQ){
int xCurent = Queue[startQ][0];
int yCurent = Queue[startQ][1];
startQ++;
for (int i = 0; i < 4; i++){
int xNext = xCurent + dx[i];
int yNext = yCurent + dy[i];
if (visit[xNext][yNext] == 0 && map[xNext][yNext] == map[xCurent][yCurent]){
push(xNext,yNext);
visit[xNext][yNext] = 1;
}
}
}
}
int main(int argc, char** argv)
{
int test_case;
int T;
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
cin >> T;
/*
Read each test case from standard input.
*/
for(test_case = 1; test_case <= T; ++test_case)
{
Answer = 0;
cin >> N;
/////////////////////////////////////////////////////////////////////////////////////////////
/*
Please, implement your algorithm from this section.
*/
/////////////////////////////////////////////////////////////////////////////////////////////
for(int i=1; i<=N;i++){
map[0][i] = -1;
map[N+1][i] = -1;
map[i][0] = -1;
map[i][N+1] = -1;
for(int j=1; j<=N;j++){
cin >> map[i][j];
visit[i][j] = 0;
}
}
Area = 1;
for(int i=1; i<=N;i++){
for(int j=1; j<=N;j++){
if( visit[i][j] == 0 && map[i][j] != 0){
BFS(i,j);
}
}
}
for(int i=1; i<=N;i++){
for(int j=1; j<=N;j++){
if( map[i][j] == 0 && visit[i][j] ==0 ){
int D[6];
for(int z = 1 ; z<=5 ;z++) D[z] =0;
countDominated = 0;
startQ = 0;
endQ = 0;
push(i,j);
visit[i][j] = -1;
while (startQ < endQ){
int xCurent = Queue[startQ][0];
int yCurent = Queue[startQ][1];
startQ++;
for (int i = 0; i < 4; i++){
int xNext = xCurent + dx[i];
int yNext = yCurent + dy[i];
if (visit[xNext][yNext] == 0 && map[xNext][yNext] == map[xCurent][yCurent]){
push(xNext,yNext);
visit[xNext][yNext] = Area;
}
int value = map[xNext][yNext];
if (value > 0 && visitDominated[ visit[xNext][yNext] ] == 0){
countDominated ++;
indexDominated[countDominated] = visit[xNext][yNext];
visitDominated[ visit[xNext][yNext] ] = 1;
D[value] += Dominated[visit[xNext][yNext]];
}
}
}
int maxx = 0;
int valueX;
for(int z = 1 ; z<=5 ;z++) {
if (maxx <= D[z]){
valueX = z;
maxx = D[z];
}
}
for(int z = 0 ; z< endQ ;z++) {
map[ Queue[z][0] ][ Queue[z][1] ] = valueX;
}
for(int z = 1; z <= countDominated; z++) visitDominated[ indexDominated[z] ] = 0;
}
}
}
for(int i=1; i<=N;i++){
for(int j=1; j<=N;j++){
visit[i][j] = 0;
}
}
for(int i=1; i<=N;i++){
for(int j=1; j<=N;j++){
if( visit[i][j] == 0 ){
Answer ++;
countArea(i,j);
}
}
}
// Print the answer to standard output(screen).
cout << "Case #" << test_case << endl << Answer << endl;
}
return 0;//Your program should return 0 on normal termination.
}
/// QUANG CAO
#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
using namespace std;
int N,L[4],P[4];
int A[55],D[55];
int visit[4];
int Answer;
int solution[6][3] = {{1,2,3},{1,3,2},{2,1,3},{2,3,1},{3,1,2},{3,2,1}};
void solve(int k){
for (int a = 1; a <= 50 ; a++){
for (int b = a+L[ solution[k][0] ]; b <= 50 ; b++){
for (int c = b+L[ solution[k][1] ]; c <= 50 ; c++){
int sum = 0;
int endA = a+L[ solution[k][0] ];
int endB = b+L[ solution[k][1] ];
int endC = c+L[ solution[k][2] ];
for (int i = 1; i<=N; i++){
int maxx = 0;
if (A[i] <= a && A[i] + D[i] >= endA){
maxx = maxx > P[ solution[k][0] ]? maxx : P[ solution[k][0] ];
}
if (A[i] <= b && A[i] + D[i] >= endB){
maxx = maxx > P[ solution[k][1] ]? maxx : P[ solution[k][1] ];
}
if (A[i] <= c && A[i] + D[i] >= endC){
maxx = maxx > P[ solution[k][2] ]? maxx : P[ solution[k][2] ];
}
sum += maxx;
}
Answer = Answer > sum ? Answer : sum;
}
}
}
}
int main(int argc, char** argv)
{
int test_case;
int T;
//freopen("input.txt", "r", stdin);
//freopen("output.txt", "w", stdout);
cin >> T;
/*
Read each test case from standard input.
*/
for(test_case = 1; test_case <= T; ++test_case)
{
Answer = 0;
/////////////////////////////////////////////////////////////////////////////////////////////
/*
Please, implement your algorithm from this section.
*/
/////////////////////////////////////////////////////////////////////////////////////////////
cin >> N >> L[1] >> L[2] >> L[3] >> P[1] >> P[2] >> P[3];
for (int i = 1; i <= N; i++){
cin >> A[i] >> D[i];
}
for( int i = 0; i< 6 ; i++){
solve(i);
}
// Print the answer to standard output(screen).
cout << "Case #" << test_case << endl << Answer << endl;
}
return 0;//Your program should return 0 on normal termination.
}
Editor is loading...