CodeforcesRound#222(Div.2)

A. Playing with Dice time limit per test 1 second memory limit per test 256 megabytes input standard input output standard output Two players are playing a game. First each of them writes an integer from 1 to 6, and then a dice is thrown.

A. Playing with Dice

time limit per test

memory limit per test

input

output

Two players are playing a game. First each of them writes an integer from 1 to 6, and then a dice is thrown. The player whose written number got closer to the number on the dice wins. If both payers have the same difference, it's a draw.

The first player wrote number a, the second player wrote number b. How many ways to throw a dice are there, at which the first player wins, or there is a draw, or the second player wins?

Input

The single line contains two integers a and b (1?≤?a,?b?≤?6) — the numbers written on the paper by the first and second player, correspondingly.

Output

Print three integers: the number of ways to throw the dice at which the first player wins, the game ends with a draw or the second player wins, correspondingly.

Sample test(s)

input

2 5

output

3 0 3

input

2 4

output

2 1 3

Note

The dice is a standard cube-shaped six-sided object with each side containing a number from 1 to 6, and where all numbers on all sides are distinct.

You can assume that number a is closer to number x than number b, if |a?-?x|?b?-?x|.

A题：a，bi两个数字，扔一个色字，求分别与a，b求差的绝对值，谁小就谁赢，相等平局，输出情况。

水：

#include 
#include 
#include 
#include 

int a, b;

int main() {
 int ans1 = 0, ans2 = 0, ans3 = 0;
 scanf("%d%d", &a, &b);
 for (int i = 1; i <= 6; i ++) {
 if (abs(a - i) < abs(b - i)) ans1++;
 if (abs(a - i) == abs(b - i)) ans2++;
 if (abs(a - i) > abs(b - i)) ans3++;
 }
 printf("%d %d %d\n", ans1, ans2, ans3);
 return 0;
}

#include 
#include 
const int N = 100005;
int n, a[N], b[N];
int an[N], bn[N];

void init() {
 scanf("%d", &n);
 memset(an, 0, sizeof(an));
 memset(bn, 0, sizeof(bn));
 for (int i = 0; i < n; i ++)
 scanf("%d%d", &a[i], &b[i]);
}

void solve() {
 int l = 0, r = 0, i;
 for (i = 0; i < n / 2; i ++)
 an[i] = bn[i] = 1;
 for (i = 0; i < n; i ++) {
 if (a[l] < b[r]) {
 an[l++] = 1;
 }
 else {
 bn[r++] = 1;
 }
 }
 for (i = 0; i < n; i ++)
 printf("%d", an[i]);
 printf("\n");
 for (i = 0; i < n; i ++)
 printf("%d", bn[i]);
 printf("\n");
}

int main() {
 init();
 solve();
 return 0;
}

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

const int N = 505;
const int d[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};

char g[N][N];
int n, m, k, pn, sum, Max_v, Max, snum;
struct P {
 int x, y, v;
} p[N * N];

int cmp(P a, P b) {
 return a.v > b.v;
}

void init() {
 sum = 0; Max = 0; snum = 0;
 memset(p, 0, sizeof(p));
 scanf("%d%d%d", &n, &m, &k);
 for (int i = 0; i < n; i ++)
 scanf("%s", g[i]);
}

void dfs1(int x, int y) {
 g[x][y] = 'X'; p[pn].v++;
 for (int i = 0; i < 4; i ++) {
 int xx = x + d[i][0];
 int yy = y + d[i][1];
 if (xx >= 0 && xx < n && yy >= 0 && yy < m && g[xx][yy] == '.')
 dfs1(xx, yy);
 }
}

void dfs2(int x, int y) {
 if (snum == sum - k) {
 return;
 }
 g[x][y] = '.'; snum ++;
 for (int i = 0; i < 4; i ++) {
 int xx = x + d[i][0];
 int yy = y + d[i][1];
 if (xx >= 0 && xx < n && yy >= 0 && yy < m && g[xx][yy] == 'X')
 dfs2(xx, yy);
 }
}

void print() {
 for (int i = 0; i < n; i ++)
 printf("%s\n", g[i]);
}

void solve() {
 for (int i = 0; i < n; i ++)
 for (int j = 0; j < m; j ++) {
 if (g[i][j] == '.') {
 dfs1(i, j);
 sum += p[pn].v;
 if (Max < p[pn].v) {
 Max_v = pn;
 Max = p[pn].v;
 }
 p[pn].x = i; p[pn].y = j; pn++;
 }
 }
 dfs2(p[Max_v].x, p[Max_v].y);
 print();
}

int main() {
 init();
 solve();
 return 0;
}

思路：二分+贪心+优先队列优化

#include 
#include 
#include 
#include 
using namespace std;

const int N = 100005;

int n, m, s, a[N], ans[N];

struct S {
 int b, c, id;
 friend bool operator < (S a, S b) {
 return a.c > b.c;
 }
} st[N];

struct B {
 int a, id;
} bd[N];

int cmp(S a, S b) {
 return a.b > b.b;
}

int cmp1(B a, B b) {
 return a.a < b.a;
}

void init() {
 int i;
 scanf("%d%d%d", &n, &m, &s);
 for (i = 0; i < m; i ++) {
 scanf("%d", &bd[i].a);
 bd[i].id = i;
 }
 for (i = 0; i < n; i ++) {
 scanf("%d", &st[i].b);
 st[i].id = i;
 }
 for (i = 0; i < n; i ++)
 scanf("%d", &st[i].c);
 sort(bd, bd + m, cmp1);
 sort(st, st + n, cmp);
}

bool judge1(int time) {
 int ss = s, sn = 0;
 priority_queueQ;
 for (int i = m - 1; i >= 0; i -= time) {
 while (st[sn].b >= bd[i].a && sn != n) {Q.push(st[sn++]);}
 if (Q.empty()) return false;
 S t = Q.top(); Q.pop();
 if (ss < t.c) return false;
 ss -= t.c;
 int e = i - time + 1;
 if (e < 0) e = 0;
 for (int j = i; j >= e; j--) {
 ans[bd[j].id] = t.id;
 }
 }
 return true;
}

bool judge(int time) {
 int ss = s, sn = 0;
 priority_queueQ;
 for (int i = m - 1; i >= 0; i -= time) {
 while (st[sn].b >= bd[i].a && sn != n) {Q.push(st[sn++]);}
 if (Q.empty()) return false;
 S t = Q.top(); Q.pop();
 if (ss < t.c) return false;
 ss -= t.c;
 }
 return true;
}

void solve() {
 int l = 0, r = m;
 if (!judge(r)) {
 printf("NO\n"); return;
 }
 while (l < r) {
 int mid = (l + r) / 2;
 if (judge(mid)) r = mid;
 else l = mid + 1;
 }
 judge1(r);
 printf("YES\n");
 for (int i = 0; i < m - 1; i++)
 printf("%d ", ans[i] + 1);
 printf("%d\n", ans[m - 1] + 1);
}

int main() {
 init();
 solve();
 return 0;
}

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

const int INF = 0x3f3f3f3f;
const int MAXN = 1111111;
const int N = 105;
const int M = 25;

int cmp(int a, int b) {
 return a > b;
}

int n, m, s[N], c[M], t[M], dp[MAXN], st;

void init() {
 memset(dp, INF, sizeof(dp));
 scanf("%d", &n);
 for (int i = 0; i < n; i++)
 scanf("%d", &s[i]);
 scanf("%d%*c", &m);
 for (int j = 0; j < m; j++)
 scanf("%c%*c%d%*c", &c[j], &t[j]);
}

int DP(int state, int num) {
 if (dp[state] != INF) return dp[state];
 int &ans = dp[state];
	ans = 0;
 if (c[num] == 'p') {
 int bit;
 for (bit = 0; bit < m; bit++)
 if ((state & (1<