POJ 2965-The Pilots Brothers' refrigerator

POJ 2965-The Pilots Brothers' refrigerator
The Pilots Brothers' refrigerator
Time Limit: 1000MS Memory Limit: 65536K
Total Submissions: 19188 Accepted: 7358 Special Judge
Description
The game “The Pilots Brothers: following the stripy elephant” has a quest where a player needs to open a refrigerator.
There are 16 handles on the refrigerator door. Every handle can be in one of two states: open or closed. The refrigerator is open only when all handles are open. The handles are represented as a matrix 4х4. You can change the state of a handle in any location [i, j] (1 ≤ i, j ≤ 4). However, this also changes states of all handles in row i and all handles in column j.
The task is to determine the minimum number of handle switching necessary to open the refrigerator.
Input
The input contains four lines. Each of the four lines contains four characters describing the initial state of appropriate handles. A symbol “+” means that the handle is in closed state, whereas the symbol “−” means “open”. At least one of the handles is initially closed.
Output
The first line of the input contains N – the minimum number of switching. The rest N lines describe switching sequence. Each of the lines contains a row number and a column number of the matrix separated by one or more spaces. If there are several solutions, you may give any one of them.
Sample Input
-+--
----
----
-+--
Sample Output
6
1 1
1 3
1 4
4 1
4 3
4 4
Source
Northeastern Europe 2004, Western Subregion

-+--
----
----
-+--


typedef struct P//翻转时的格子坐标
{
int x,y;
};
P trace[MAX_STATUS];//trace[i]到达i状态值时翻转的某个格子坐标
int pre[MAX_STATUS];//pre[i]记录i状态的前一个状态值


pre[i]数组用来记录到达i状态时的前一个状态，而trace[i]则用来记录到达该状态时翻转的格子坐标。这样通过成功状态回溯到开始状态就可以找到所有路径了，具体实现请看下面的代码。

#include<iostream>
#include<queue>
#include<vector>
using namespace std;
const int MAX_STATUS=65536;//2^16=65536种，所以[0,65535]
const int ALL_1=65535;//全1
int visited[MAX_STATUS]={0};//访问标记
int XOR[4]={0x111,0x1011,0x1101,0x1110};//列异或值
typedef struct POS//position翻转位置
{
int val;//当前翻转状态的值
int step;//到当前状态共翻转了多少次
};
typedef struct P//翻转时的格子坐标
{
int x,y;
};
P trace[MAX_STATUS];//trace[i]到达i状态值时翻转的某个格子坐标
int pre[MAX_STATUS];//pre[i]记录i状态的前一个状态值
//通过反向索引打印结果
void print_result(POS pos,int init_id)
{
cout<<pos.step<<endl;
vector<P> points;
points.push_back(trace[pos.val]);
int pre_val=pre[pos.val];
while(pre_val!=init_id)//当没有追溯到初始状态时，一直循环
{
points.push_back(trace[pre_val]);
pre_val=pre[pre_val];//追溯
}
int p_num=points.size();//顺着打印出来
for(int i=p_num-1;i>=0;i--)
cout<<points[i].x<<" "<<points[i].y<<endl;
}
//广度优先搜索
void BFS(int init_id)
{
POS p,next_p;
p.val=init_id;
p.step=0;
visited[p.val]=1;
pre[p.val]=-1;//没有前一个状态
queue<POS> Q_P;
Q_P.push(p);
while(!Q_P.empty())
{
p=Q_P.front();
Q_P.pop();
if(p.val==ALL_1)
{
print_result(p,init_id);
return;
}
for(int i=0;i<4;i++)
{
int curr_xor=XOR[i];//i不同时，翻转异或的值也不同
for(int j=0;j<4;j++)
{
next_p.val=p.val;
next_p.val^=0xf<<(4*(3-i));//横向翻转
next_p.val^=curr_xor<<(3-j);//纵向翻转
if(visited[next_p.val]==0)
{
visited[next_p.val]=1;
next_p.step=p.step+1;
pre[next_p.val]=p.val;//记录前一个状态值
trace[next_p.val].x=i+1;//注意输出的坐标是从1开始到4
trace[next_p.val].y=j+1;//所以这里加1
Q_P.push(next_p);
}
}
}
}
}
int main()
{
//freopen("input.txt","r",stdin);
char c;
int id=0;
for(int i=0;i<4;i++)
{
for(int j=0;j<4;j++)
{
cin>>c;
id<<=1;//id=id<<1;
if(c=='-')//-:1;+:0
id+=1;
}
}
BFS(id);
return 0;
}


POJ 1753-Flip Game

POJ 1753-Flip Game
Flip Game
Time Limit: 1000MS Memory Limit: 65536K
Total Submissions: 31655 Accepted: 13776
Description
Flip game is played on a rectangular 4x4 field with two-sided pieces placed on each of its 16 squares. One side of each piece is white and the other one is black and each piece is lying either it's black or white side up. Each round you flip 3 to 5 pieces, thus changing the color of their upper side from black to white and vice versa. The pieces to be flipped are chosen every round according to the following rules:
Choose any one of the 16 pieces.
Flip the chosen piece and also all adjacent pieces to the left, to the right, to the top, and to the bottom of the chosen piece (if there are any).
Consider the following position as an example:
bwbw
wwww
bbwb
bwwb
Here "b" denotes pieces lying their black side up and "w" denotes pieces lying their white side up. If we choose to flip the 1st piece from the 3rd row (this choice is shown at the picture), then the field will become:
bwbw
bwww
wwwb
wwwb
The goal of the game is to flip either all pieces white side up or all pieces black side up. You are to write a program that will search for the minimum number of rounds needed to achieve this goal.
Input
The input consists of 4 lines with 4 characters "w" or "b" each that denote game field position.
Output
Write to the output file a single integer number - the minimum number of rounds needed to achieve the goal of the game from the given position. If the goal is initially achieved, then write 0. If it's impossible to achieve the goal, then write the word "Impossible" (without quotes).
Sample Input
bwwb
bbwb
bwwb
bwww
Sample Output
4
Source
Northeastern Europe 2000

#include<iostream>
#include<queue>
using namespace std;
const int MAX_STATUS=65536;//2^16=65536种，所以[0,65535]
const int ALL_0=0;//全0
const int ALL_1=65535;//全1
int ans;
int visited[MAX_STATUS]={0};//访问标记
typedef struct POS//position翻转位置
{
int val;//当前翻转状态的值
int step;//到当前状态共翻转了多少次
};
//广搜
void BFS(int init_id)
{
queue<POS> Q_P;
POS s,next_p;
//初始位置
s.val=init_id;
s.step=0;
visited[s.val]=1;
Q_P.push(s);
while(!Q_P.empty())
{
s=Q_P.front();
Q_P.pop();
if(s.val==ALL_0||s.val==ALL_1)//找到结果
{
ans=s.step;
return;
}
//尝试翻16个位置
for(int i=0;i<4;i++)
{
for(int j=0;j<4;j++)
{
next_p.val=s.val;
//测试i，翻转[i,j]上下位置的格子
if(i==0)
next_p.val^=1<<(11-4*i-j);
else if(i==3)
next_p.val^=1<<(19-4*i-j);
else
{
next_p.val^=1<<(11-4*i-j);
next_p.val^=1<<(19-4*i-j);
}
//测试j，翻转[i,j]左右位置的格子
if(j==0)
next_p.val^=3<<(14-4*i-j);
else if(j==3)
next_p.val^=3<<(15-4*i-j);
else
next_p.val^=7<<(14-4*i-j);
if(visited[next_p.val]==0)//如果没有访问
{
visited[next_p.val]=1;//访问
next_p.step=s.step+1;//翻转次数加1
Q_P.push(next_p);//并加入队列
}
}
}
}
ans=-1;//到这里还没有return,说明impossible
}
int main()
{
//freopen("input.txt","r",stdin);
char c;
int id=0;
//输入转换
/*bwbw
wwww
bbwb
bwwb
排列成bwbw wwww bbwb bwwb，然后把b换成1，w换成0*/
for(int i=0;i<4;i++)
{
for(int j=0;j<4;j++)
{
cin>>c;
id<<=1;
if(c=='b')//b=1;w=0
id+=1;
}
}
BFS(id);
if(ans==-1)
cout<<"Impossible";
else
cout<<ans;
return 0;
}


hihoCoder 1051-补提交卡

hihoCoder 1051-补提交卡
#1051 : 补提交卡

3
5 1
34 77 82 83 84
5 2
10 30 55 56 90
5 10
10 30 55 56 90

76
59
100

#include<iostream>
#include<vector>
using namespace std;
int main()
{
int t;
cin>>t;
int n,m;
while(t--)
{
cin>>n>>m;
vector<int> a(n+1);
for(int i=0;i<n;i++)
cin>>a[i];
a[n]=101;//哨兵
if(m>=n)
cout<<100<<endl;
else
{
int max_days=0;//最长连续提交天数
int case_num=n-m+1;//总的枚举情况数
for(int i=0;i<case_num;i++)
{
int last_index=m+i-1;//该方案下最后一个下标
if(i==0)
{
if(a[last_index+1]-1>max_days)
max_days=a[last_index+1]-1;
}
else
{
if(a[last_index+1]-a[i-1]-1>max_days)
max_days=a[last_index+1]-a[i-1]-1;
}
}
cout<<max_days<<endl;
}
}
return 0;
}


POJ 2586-Y2K Accounting Bug

POJ 2586-Y2K Accounting Bug
Y2K Accounting Bug
Time Limit: 1000MS Memory Limit: 65536K
Total Submissions: 10647 Accepted: 5328
Description
Accounting for Computer Machinists (ACM) has sufferred from the Y2K bug and lost some vital data for preparing annual report for MS Inc.
All what they remember is that MS Inc. posted a surplus or a deficit each month of 1999 and each month when MS Inc. posted surplus, the amount of surplus was s and each month when MS Inc. posted deficit, the deficit was d. They do not remember which or how many months posted surplus or deficit. MS Inc., unlike other companies, posts their earnings for each consecutive 5 months during a year. ACM knows that each of these 8 postings reported a deficit but they do not know how much. The chief accountant is almost sure that MS Inc. was about to post surplus for the entire year of 1999. Almost but not quite.
Write a program, which decides whether MS Inc. suffered a deficit during 1999, or if a surplus for 1999 was possible, what is the maximum amount of surplus that they can post.
Input
Input is a sequence of lines, each containing two positive integers s and d.
Output
For each line of input, output one line containing either a single integer giving the amount of surplus for the entire year, or output Deficit if it is impossible.
Sample Input
59 237
375 743
200000 849694
2500000 8000000
Sample Output
116
28
300612
Deficit
Source
Waterloo local 2000.01.29

ACM knows that each of these 8 postings reported a deficit

#include<iostream>
#include<vector>
using namespace std;
int main()
{
int s,d;
while(cin>>s>>d)
{
int surplus_num;//盈余的月份数
vector<int> month(12,1);//初始的时候每个月都是surplus，1为surplus，0为deficit
for(int i=0;i<8;i++)//8个‘连续5个月’
{
surplus_num=0;
for(int j=0;j<5;j++)
surplus_num+=month[i+j];
int k=0;
while(surplus_num*s>=(5-surplus_num)*d)
{
month[i+4-k]=0;//亏损的月份尽量放到后面，因为可以和下一个周期重叠，这样总的surplus会大一些
surplus_num=0;
for(int j=0;j<5;j++)
surplus_num+=month[i+j];
k++;
}
}
surplus_num=0;
for(int i=0;i<12;i++)
surplus_num+=month[i];
int rs=surplus_num*s-(12-surplus_num)*d;//这一年总的盈亏
if(rs<0)
cout<<"Deficit"<<endl;
else
cout<<rs<<endl;
}
return 0;
}


1 2 3 4 5 6 7 8 9 10 11 12
s s s s d s s s s d s s //每5个月里只有1个月亏损
s s s d d s s s d d s s //每5个月里只有2个月亏损
s s d d d s s d d d s s //每5个月里只有3个月亏损
s d d d d s d d d d s d //每5个月里只有4个月亏损

#include<iostream>
using namespace std;
int main()
{
int a,b;
while(cin>>a>>b)
{
int ans = 0;
if(4*a-b<0)
{
ans = 10*a-2*b;
}
else if(3*a-2*b<0)
{
ans = 8*a-4*b;
}
else if(2*a-3*b<0)
{
ans = 6*a-6*b;
}
else if(a-4*b<0)
{
ans = 3*a-9*b;
}
else
{
ans = -1;
}
if(ans>0)
cout<<ans<<endl;
else
cout<<"Deficit"<<endl;
}
return 0;
}