CodeforcesRound#231(Div.2)

Problems # Name A Counting Sticks standard input/output 1 s, 256 MB x2326 B Very Beautiful Number standard input/output 1 s, 256 MB x856 C Dominoes standard input/output 2 s, 256 MB x803 D Physical Education and Buns standard input/output

Problems

#	Name
A	Counting Sticks standard input/output 1 s, 256 MB		x2326
B	Very Beautiful Number standard input/output 1 s, 256 MB		x856
C	Dominoes standard input/output 2 s, 256 MB		x803
D	Physical Education and Buns standard input/output 2 s, 256 MB		x234
E	Lightbulb for Minister standard input/output 1 s, 256 MB		x49

A题：先处理字符串把3个位置的数字保存下来，在去判断相等或者差值为2，去移动即可。

B题：枚举最后一位数字，模拟往前推数字，推到第一位判断是不是和一开始枚举的数字相同。

C题：贪心，10和01其实是一样的，所以先保存下11，10和01的总数，00的个数，先从左往右放11，放完之后，在从右边往左边去放10,01，每行交替着放即可，剩下的就是00。

D题：从小到大排序后，先枚举公差d，先变化后的序列A1是0，然后求出整个需要去向上移动的最大值和最小值（可能是负的），那么变化后的序列其实可以看成一条斜率k是d，b是A1的直线，然后这条直线无论上移下移，那么对于最大值和最小值肯定还是原来那2个位置，那么只要保证移动到最大值和最小值中的最大值尽可能小，那么就是去中间肯定是最优的，为(up + down + 1)/2 （要向上取整所以+1），最后维护ans的最小值即可。

D题：还有一种解法，二分答案，然后去判断，判断的方式先枚举公差，在用O(n)的方法去维护每个上下区间从大到小。

代码：

A题：

#include 
#include 

char c;

int main() {
 int num[3], s = 0; 
 memset(num, 0, sizeof(num));
 while ((c = getchar()) != EOF && c != '\n') {
 if (c == '+' || c == '=') s++;
 else num[s]++;
 }
 if (num[0] - 1 + num[1] == num[2] + 1) {
 if (num[0] == 1) num[1]--;
 else if (num[1] == 1) num[0]--;
 else if (num[0] != 1 && num[1] != 1) num[0]--;
 num[2]++;
 }
 else if (num[0] + num[1] == num[2]) {
 
 }
 else if (num[0] + 1 + num[1] == num[2] - 1) {
 if (num[2] == 1) {
 printf("Impossible\n");
 return 0;
 }
 num[2]--;
 num[0]++;
 }
 else {
 printf("Impossible\n");
 return 0;
 }
 int i;
 for (i = 0; i < num[0]; i++)
 printf("|");
 printf("+");
 for (i = 0;i < num[1]; i++)
 printf("|");
 printf("=");
 for (i = 0; i < num[2]; i++)
 printf("|");
 printf("\n");
 return 0;
}

#include 
#include 

int p, x, ans[1000005];

int main() {
 scanf("%d%d", &p, &x);
 int yu = 0;
 for (int i = 0; i <= 9; i++) {
 int s = i; int j; yu = 0;
 for (j = 0; j < p; j++) {
 ans[j] = s;
 int ji = s * x + yu;
 s = ji % 10;
 yu = ji / 10;
 }
 if (s == i && j == p && ans[p - 1] != 0 && yu == 0) {
 for (int j = p - 1; j >= 0; j--)
 printf("%d", ans[j]);
 printf("\n");
 return 0;
 }
 }
 printf("Impossible\n");
 return 0;
}

C题：

#include 
#include 

int n, m, i, j;
int num10, num00, num11;
char str[10], ans[1005][1005][4];

int main() {
 num10 = num00 = num11 = 0;
 scanf("%d%d", &n, &m);
 for (i = 0; i < n; i++)
 for (j = 0; j < m; j++) {
 scanf("%s", str);
 if (strcmp(str, "00") == 0)
 num00++;
 if (strcmp(str, "01") == 0 || strcmp(str, "10") == 0)
 num10++;
 if (strcmp(str, "11") == 0)
 num11++;
 }
 
 for (i = 0; i < n; i++)
 for (j = 0; j < m; j++)
 strcpy(ans[i][j], "00");
 i = 0; j = 0;
 while (num11) {
 strcpy(ans[i][j], "11");
 j++;
 if (j == m) {
 j = 0;
 i++;
 }
 num11--;
 }
 int jj = m - 1;
 while (num10) {
 strcpy(ans[i][jj], "10");
 num10--;
 if (jj == j) break;
 jj--;
 }
 i++;
 jj = m - 1;
 while (num10) {
 strcpy(ans[i][jj], "01");
 num10--;
 if (jj == j) break;
 jj--;
 }
 int flag = 0; j--;
 if (j == -1) {
 j = m - 1;
 i++;
 }
 while (num10) {
 if (flag == 0)
 strcpy(ans[i][j], "01");
 else
 strcpy(ans[i][j], "10");
 j--;
 if (j == -1) {
 j = m - 1;
 i++;
 flag = 1 - flag;
 }
 num10--;
 }
 for (i = 0; i < n; i++) {
 for (j = 0; j < m - 1; j++) {
 printf("%s ", ans[i][j]);
 }
 printf("%s\n", ans[i][j]);
 }
 return 0;
}

#include 
#include 
#include 
#define INF 0x3f3f3f3f
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
using namespace std;

const int N = 1005;
int n, num[N];

void solve() {
 int ans = INF, start, dd;
 sort(num, num + n);
 for (int d = 0; d <= 20000; d++) {
 int up = -INF, down = INF;
 for (int i = 0; i < n; i++) {
 up = max(up, i * d - num[i]);
 down = min(down, i * d - num[i]);
 }
 int res = (up - down + 1) / 2;
 if (ans > res) {
 ans = res; start = -up + res; dd = d;
 }
 }
 printf("%d\n%d %d\n", ans, start, dd);
}

int main() {
 scanf("%d", &n);
 for (int i = 0; i < n; i++)
 scanf("%d", &num[i]);
 solve();
 return 0;
}

#include 
#include 
#include 
#define INF 0x3f3f3f3f
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
using namespace std;

const int N = 1005;
const int M = 10005;
int n, num[N], start, dd;

bool judge(int Max) {
	for (int d = 0; d <= 20000; d++) {
	int up = num[n - 1] + Max, down = num[n - 1] - Max;
	for (int i = n - 2; i >= 0; i--) {
	up = min(num[i] + Max, up - d);
	down = max(num[i] - Max, down - d);
	}
	if (down <= up) {
	start = down;
	dd = d;
	return true;
	}
	}
	return false;
}

void solve() {
	int l = 0, r = M;
	sort(num, num + n);
	while (l < r) {
	int mid = (l + r) / 2;
	if (judge(mid)) r = mid;
	else l = mid + 1;
	}
	printf("%d\n%d %d\n", l, start, dd);
}

int main() {
	scanf("%d", &n);
	for (int i = 0; i < n; i++)
	scanf("%d", &num[i]);
	solve();
 return 0;
}