Untitled
unknown
plain_text
2 years ago
9.4 kB
5
Indexable
// array
// 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.
#include <stdio.h>
#include <iostream>
using namespace std;
long long Sum[20005];
int Result;
int Number[20005];
int N;
int trace[2000005][3];
int beginQ, endQ;
int binarySearch(int i, int j, int head, int last){
if (i > j) return -1;
int mid = (j + i + 1) / 2;
if ((Sum[mid] - Sum[head-1]) * 2 == Sum[last] - Sum[head-1] ) return mid;
if ((Sum[mid] - Sum[head-1]) * 2 > Sum[last] - Sum[head-1] )
return binarySearch(i,mid-1,head,last);
else return binarySearch(mid+1,j,head,last);
}
int main(int argc, char** argv)
{
int tc, T;
// The freopen function below opens input.txt file in read only mode, and afterward,
// the program will read from input.txt file instead of standard(keyboard) input.
// To test your program, you may save input data in input.txt file,
// and use freopen function to read from the file when using cin function.
// You may remove the comment symbols(//) in the below statement and use it.
// Use #include<cstdio> or #include<stdio.h> to use the function in your program.
// But before submission, you must remove the freopen function or rewrite comment symbols(//).
/*
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
*/
cin >> T;
for(tc = 0; tc < T; tc++)
{
/**********************************
* Implement your algorithm here. *
***********************************/
Sum[0] = 0;
Result = 0;
cin >> N;
for( int i = 1; i<=N; ++i){
cin >> Number[i];
Sum[i] = Sum[i-1] + Number[i];
};
if (Sum[N] == 0) {
Result = N-1;
} else {
beginQ = 0;
endQ = 1;
trace[beginQ][0] = 1;
trace[beginQ][1] = N;
trace[beginQ][2] = 0;
int head, last, score;
//BackTrack(1,N,0);
while (beginQ < endQ)
{
head = trace[beginQ][0];
last = trace[beginQ][1];
score = trace[beginQ][2];
beginQ++;
Result = Result < score ? score : Result;
//if (Sum[last] - Sum[head-1])
int i;
for (i = head; i<=last; i++){
if ((Sum[i] - Sum[head-1]) * 2 == Sum[last] - Sum[head-1]){
trace[endQ][0] = i + 1;
trace[endQ][1] = last;
trace[endQ][2] = score + 1;
endQ++;
trace[endQ][0] = head;
trace[endQ][1] = i;
trace[endQ][2] = score + 1;
endQ++;
break;
}
}
// cout<<beginQ << " " <<endQ << endl;
}
}
//cout<<"#"<<beginQ << " " <<endQ << endl;
// Print the answer to standard output(screen).
cout<< Result<<endl;
}
return 0;//Your program should return 0 on normal termination.
}
// domino
// 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.
#include<iostream>
using namespace std;
#define SizeX 7
#define SizeY 8
int board[SizeX+2][SizeY+2],trave[SizeX+2][SizeY+2];
int dominos[7][7];
int numberDominos;
int Answer;
void cover(int x, int y, int number){
if ( x == 8) return;
if (trave[x][y] == 0) {
if( trave[x][y+1] == 0 && dominos[board[x][y]][board[x][y+1]] == 0){
trave[x][y] = 1;
trave[x][y+1] = 1;
dominos[board[x][y]][board[x][y+1]] = 1;
dominos[board[x][y+1]][board[x][y]] = 1;
number --;
//cout << board[x][y] << " " <<board[x][y+1] <<" #"<<number << endl;
if ( number == 0){
Answer ++;
//cout <<"**************************"<<endl;
} else {
if (y < 7) cover(x,y+2,number);
else cover(x+1,1,number);
}
trave[x][y] = 0;
trave[x][y+1] = 0;
dominos[board[x][y]][board[x][y+1]] = 0;
dominos[board[x][y+1]][board[x][y]] = 0;
number ++;
//cout << "**" << board[x][y] << " " <<board[x][y+1]<<" #"<<number << endl;
}
if( trave[x+1][y] == 0 && dominos[board[x][y]][board[x+1][y]] == 0){
trave[x][y] = 1;
trave[x+1][y] = 1;
dominos[board[x][y]][board[x+1][y]] = 1;
dominos[board[x+1][y]][board[x][y]] = 1;
number --;
//cout << board[x][y] << " " <<board[x+1][y]<<" #"<<number << endl;
if ( number == 0){
Answer ++;
//cout <<"**************************"<<endl;
} else {
if (y < 8) cover(x,y+1,number);
else cover(x+1,1,number);
}
trave[x][y] = 0;
trave[x+1][y] = 0;
dominos[board[x][y]][board[x+1][y]] = 0;
dominos[board[x+1][y]][board[x][y]] = 0;
number ++;
//cout << "**" << board[x][y] << " " <<board[x+1][y]<<" #"<<number << endl;
}
} else {
if (y < 8) cover(x,y+1,number);
else cover(x+1,1,number);
}
}
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.
*/
/////////////////////////////////////////////////////////////////////////////////////////////
for(int i = 1; i <= 7; ++i){
trave[i][0] = -1;
trave[i][9] = -1;
for(int j = 1; j<= 8; ++j){
trave[i][j] = 0;
cin >> board[i][j];
}
}
for(int j = 1; j<= 8; ++j){
trave[0][j] = -1;
trave[8][j] = -1;
}
for(int i = 0; i<= 6; ++i)
for(int j = 0; j<= 6; ++j){
dominos[i][j] = 0;
}
numberDominos = 28;
cover(1,1,numberDominos);
// Print the answer to standard output(screen).
cout << "#" << test_case << " " << Answer << endl;
}
return 0;//Your program should return 0 on normal termination.
}
// robot
// 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.
#include<iostream>
#define MAX_INT 999999
using namespace std;
int Queue[100025][2];
int startQ, endQ;
int room[105][105],visit[105][105];
int M,N,ct;
int Answer;
int dirty[15][2],dist[15][15];
int VsBacktrack[15];
void push(int x, int y){
Queue[endQ][0] = x;
Queue[endQ][1] = y;
endQ++;
}
bool check(int x,int y){
if(room[x][y] == 2 || visit[x][y] != MAX_INT) return false;
return true;
}
void setVisit(int x, int y,int value){
push(x,y);
visit[x][y] = value;
}
void BFS(int k){
for(int i = 1; i <= N; i++)
for(int j = 1; j <= M; j++) visit[i][j] = MAX_INT;
startQ = 0;
endQ = 0;
int x = dirty[k][0];
int y = dirty[k][1];
visit[x][y] = 0;
push(x,y);
while(startQ < endQ){
x = Queue[startQ][0];
y = Queue[startQ][1];
startQ++;
if(check(x+1,y)) setVisit(x+1,y,visit[x][y]+1);
if(check(x-1,y)) setVisit(x-1,y,visit[x][y]+1);
if(check(x,y+1)) setVisit(x,y+1,visit[x][y]+1);
if(check(x,y-1)) setVisit(x,y-1,visit[x][y]+1);
}
for(int i = 0; i<= ct; i++) {
dist[k][i] = visit[ dirty[i][0] ][ dirty[i][1] ];
}
}
void Backtrack(int x,int count ,int value){
if (count == ct) Answer = Answer > value ? value : Answer;
for (int i = 1; i<=ct; i++) {
if(VsBacktrack[i] == 0 && value + dist[x][i] < Answer){
VsBacktrack[i] = 1;
Backtrack(i,count+1,value + dist[x][i]);
VsBacktrack[i] = 0;
}
}
}
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 = MAX_INT;
cin >> N >> M;
ct = 0;
for(int i = 1; i <= N; i++){
for(int j = 1; j <= M; j++){
cin >> room[i][j];
if (room[i][j] == 3) {
dirty[0][0] = i;
dirty[0][1] = j;
}
if (room[i][j] == 1) {
ct++;
dirty[ct][0] = i;
dirty[ct][1] = j;
}
}
room[i][0] = 2;
room[i][M+1] = 2;
}
for(int i = 1; i <= M; i++){
room[0][i] = 2;
room[N+1][i] = 2;
}
for(int i = 0; i<= ct; i++) BFS(i);
for (int i = 1; i<= ct; i++)
if (dist[0][i] == MAX_INT) Answer = -1;
if (Answer == MAX_INT){
for (int i = 0; i<= ct; i++) VsBacktrack[i] = 0;
Backtrack(0,0,0);
}
/////////////////////////////////////////////////////////////////////////////////////////////
/*
Please, implement your algorithm from this section.
*/
/////////////////////////////////////////////////////////////////////////////////////////////
// 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...