AOJ0118 Property Distribution

Problem

タナカ氏が HW アールの果樹園を残して亡くなりました。果樹園は東西南北方向に H×W の区画に分けられ、区画ごとにリンゴ、カキ、ミカンが植えられています。タナカ氏はこんな遺言を残していました。

AOJ0033 Ball

Problem

図のように二股に分かれている容器があります。1 から 10 までの番号が付けられた10 個の玉を容器の開口部 A から落とし、左の筒 B か右の筒 C に玉を入れます。板 D は支点 E を中心に左右に回転できるので、板 D を動かすことで筒 B と筒 C のどちらに入れるか決めることができます。

開口部 A から落とす玉の並びを与えます。それらを順番に筒 B 又は筒 Cに入れていきます。このとき、筒 B と筒 C のおのおのが両方とも番号の小さい玉の上に大きい玉を並べられる場合は YES、並べられない場合は NO と出力するプログラムを作成してください。ただし、容器の中で玉の順序を入れ替えることはできないものとします。また、続けて同じ筒に入れることができるものとし、筒 B, C ともに 10 個の玉がすべて入るだけの余裕があるものとします。

Input

複数のデータセットが与えられます。1行目にデータセット数 N が与えられます。つづいて、N 行のデータセットが与えられます。各データセットに 10 個の番号が左から順番に空白区切りで与えられます。

Output

各データセットに対して、YES または NO を1行に出力して下さい。

Sample Input

1
2
3
2
3 1 4 2 5 6 7 8 9 10
10 9 8 7 6 5 4 3 2 1

Output for the Sample Input

1
2
YES
NO

Answer

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
#include <cstdio>

void solve1() {
bool ans = true;
for (int i = 0; i < 10; ++i)
scanf("%d", &a[i]);

int l = 0, r = 0;
for (int i = 0; i < 10; ++i) {
if (a[i] > l)
l = a[i];
else if (a[i] > r)
r = a[i];
else {
ans = false;
break;
}
}
printf("%s\n", ans ? "YES" : "NO");
}

int c[10], l[10], r[10];

bool dfs(int i, int j, int k) {
// i:该放 A[i],前面均以放好
// j:左序列的顶部
// k:右序列的顶部
if (i == 10) {
return true;
}
if (c[i] > l[j]) {
l[j+1] = c[i];
if (dfs(i+1, j+1, k))
return true;
}
if (c[i] > r[k]) {
r[k+1] = c[i];
if (dfs(i+1, j, k+1))
return true;
}
return false;
}

void solve2() {
l[0] = r[0] = -1;
printf("%s\n", dfs(0, 0, 0) ? "YES" : "NO");
}

int main() {
int T;

scanf("%d", &T);
while (T--) {
solve1();
solve2();
}
return 0;
}

Analysis

  1. 贪心算法。较大的值放在在左边。
  2. 1-10 号 10 个球,依次放入左右两个桶中,是否存在放完后每个桶都是增序排列。

AOJ0558 Cheese

問題

今年も JOI 町のチーズ工場がチーズの生産を始め,ねずみが巣から顔を出した.JOI 町は東西南北に区画整理されていて,各区画は巣,チーズ工場,障害物,空き地のいずれかである.ねずみは巣から出発して全てのチーズ工場を訪れチーズを 1 個ずつ食べる.

AOJ0121 Seven Puzzle

Problem

7 パズルは 8 つの正方形のカードとこれらのカードがぴたりと収まる枠で構成されています。それぞれのカードには、互いに区別できるように 0, 1, 2, ..., 7 と番号がつけられています。枠には、縦に 2 個、横に 4 個のカードを並べることができます。

AOJ0525 Osenbei

問題

IOI製菓では,創業以来の伝統の製法で煎餅(せんべい)を焼いている.この伝統の製法は,炭火で一定時間表側を焼き,表側が焼けると裏返して,炭火で一定時間裏側を焼くというものである.この伝統を守りつつ,煎餅を機械で焼いている.この機械は縦 R (1 ≤ R ≤ 10) 行, 横 C (1 ≤ C ≤ 10000) 列の長方形状に煎餅を並べて焼く.通常は自動運転で,表側が焼けたら一斉に煎餅を裏返し裏側を焼く.

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×