FILE reverse 1
0 1 2 3 4 5 6 7 8
P 2
P 1
P 0
#include <assert.h>
#include <stdio.h>
#include <stdlib.h>
#define N 9
int min(int a, int b) { return a < b ? a : b; }
int ii[N], jj[N], aa[N], bb[N];
void display() {
int i;
for (i = 0; i < N; i++)
printf("%d ", aa[i]);
printf("\n");
}
int a_, active, limit, run;
void P(int i) {
run = 0;
if (a_ >= aa[i]) {
assert(a_-- == aa[i]);
if (!active)
active = 1, display();
printf("P %d\n", i + 1);
}
}
void S(int i, int j) {
if (active)
printf("S %d %d\n", i + 1, j + 1);
aa[j] = aa[i] + 1;
assert(i < N && j < N && ++run <= limit);
}
void Q(int lower, int k, int l, int n, int d_) {
int m, h, h_, d, d1, partial;
assert(k + l < n);
m = k + l;
if (k > 0)
k--;
else
l--;
for (h = 0; h < m; h++) {
bb[h] = lower;
if (h + 1 < m) {
if (k > 0)
lower += d_ + 1, k--;
else
lower += d_, l--;
}
}
partial = 0;
for (h = 0, h_ = 0; h < m; h++) {
for (d = aa[ii[n - 1 - h]] - aa[ii[n - 2 - h]] - 1; d > 0; d--) {
for (d1 = 0; d1 < d; d1++)
S(ii[d1 == 0 ? n - 2 - h : n - 1 - h], ii[n - 1 - h]);
for (d1 = d; d1 < d_; d1++)
if (h_ < h) {
if (!partial)
S(h_ == 0 ? N - 1 - n : ii[n - h_], ii[n - 1 - h_]), partial = 1;
else
S(ii[n - 1 - h_], ii[n - 1 - h_]);
if (aa[ii[n - 1 - h_]] == bb[h_])
h_++, partial = 0;
}
P(ii[n - 1 - h]);
}
for (d1 = 0; d1 < d_; d1++)
if (h_ <= h) {
if (!partial)
S(h_ == 0 ? N - 1 - n : ii[n - h_], ii[n - 1 - h_]), partial = 1;
else
S(ii[n - 1 - h_], ii[n - 1 - h_]);
if (aa[ii[n - 1 - h_]] == bb[h_])
h_++, partial = 0;
}
P(ii[n - 2 - h]);
}
for (h = 0; h < m; h++)
jj[h] = ii[n - 1 - h];
for (h = m; h < n; h++)
jj[h] = ii[h - m];
for (h = 0; h < n; h++)
ii[h] = jj[h];
}
int simulate(int k, int l, int n, int d_, int upper) {
int k_, l_, h;
if ((n - 2) * d_ * (d_ + 1) / 2 + d_ < (k - 1) * (d_ + 1) + l * d_)
return 0;
for ( ; k + l > 0; k = k_, l = l_) {
k_ = k, l_ = l;
if (k_ > 0)
k_--;
else
l_--;
if (k_ + l_ > 0) {
if (l_-- == 0)
return 0;
k_ -= n - 3;
if (k_ < 0)
l_ += k_, k_ = 0;
if (l_ < 0)
l_ = 0;
}
if (upper >= 0) {
if (k_ + l_ > 0)
Q(upper -= (k - k_) * (d_ + 1) + (l - l_) * d_, k - k_, l - l_, n, d_);
else if (k - k_ + l - l_ == 2 || k - k_ <= 1)
Q(upper -= (k - k_) * (d_ + 1) + (l - l_ - 1) * d_, k - k_, l - l_ - 1, n, d_);
else
Q(upper -= (k - k_ - 1) * (d_ + 1) + (l - l_) * d_, k - k_ - 1, l - l_, n, d_);
}
}
if (upper >= 0) {
for (h = n; h > 0; h--)
ii[h] = ii[h - 1];
ii[0] = N - 1 - n;
}
return 1;
}
int solve(int a, int d_) {
static int kk[N], ll[N];
int i, k, l, d, d1;
aa[N - 1] = 0, aa[N - 2] = aa[N - 1] + d_ + 1, aa[N - 3] = aa[N - 2] + d_ + d_ + 1;
for (i = N - 4; i >= 0; i--) {
kk[i] = 0, ll[i] = 0;
for (k = 1; k <= 100; k++)
for (l = 0; l <= 100; l++)
if (simulate(k, l, N - 1 - i, d_, -1) && kk[i] * (d_ + 1) + ll[i] * d_ < k * (d_ + 1) + l * d_)
kk[i] = k, ll[i] = l;
aa[i] = aa[i + 1] + kk[i] * (d_ + 1) + ll[i] * d_;
}
if (aa[0] < a)
return 0;
for (i = 1; i < N; i++)
aa[i] = aa[0] - aa[i];
aa[0] = 0;
limit = d_;
a_ = a, active = 0;
P(N - 1);
for (d = d_; d > 0; d--) {
for (d1 = 0; d1 < d; d1++)
S(d1 == 0 ? N - 2 : N - 1, N - 1);
P(N - 1);
}
for (d1 = 0; d1 < d_; d1++)
S(d1 == 0 ? N - 3 : N - 1, N - 1);
P(N - 2);
ii[0] = N - 3, ii[1] = N - 1, ii[2] = N - 2;
for (i = N - 4; i >= 0; i--)
simulate(kk[i], ll[i], N - 1 - i, d_, aa[i + 1]);
for (i = N - 2; i >= 0; i--) {
for (d = aa[ii[i + 1]] - aa[ii[i]] - 1; d > 0; d--) {
for (d1 = 0; d1 < d; d1++)
S(ii[d1 == 0 ? i : i + 1], ii[i + 1]);
P(ii[i + 1]);
}
P(ii[i]);
}
assert(a_ == -1);
return 1;
}
int main() {
int t, a, i, d_;
scanf("%d%d", &t, &a);
printf("FILE reverse %d\n", t);
if (a < N) {
for (i = 0; i < N; i++)
printf("%d ", i);
printf("\n");
for (i = a; i >= 0; i--)
printf("P %d\n", i);
return 0;
}
d_ = 1;
while (!solve(a, d_))
d_++;
return 0;
}
#include <assert.h>
#include <stdio.h>
#include <stdlib.h>
#define N 9
int min(int a, int b) { return a < b ? a : b; }
int ii[N], jj[N], aa[N], bb[N];
void display() {
int i;
for (i = 0; i < N; i++)
printf("%d ", aa[i]);
printf("\n");
}
int a_, active, limit, run;
void P(int i) {
run = 0;
if (a_ >= aa[i]) {
assert(a_-- == aa[i]);
if (!active)
active = 1, display();
printf("P %d\n", i + 1);
}
}
void S(int i, int j) {
if (active)
printf("S %d %d\n", i + 1, j + 1);
aa[j] = aa[i] + 1;
assert(i < N && j < N && ++run <= limit);
}
void Q(int lower, int k, int l, int n, int d_) {
int m, h, h_, d, d1, partial;
assert(k + l < n);
m = k + l;
if (k > 0)
k--;
else
l--;
for (h = 0; h < m; h++) {
bb[h] = lower;
if (h + 1 < m) {
if (k > 0)
lower += d_ + 1, k--;
else
lower += d_, l--;
}
}
partial = 0;
for (h = 0, h_ = 0; h < m; h++) {
for (d = aa[ii[n - 1 - h]] - aa[ii[n - 2 - h]] - 1; d > 0; d--) {
for (d1 = 0; d1 < d; d1++)
S(ii[d1 == 0 ? n - 2 - h : n - 1 - h], ii[n - 1 - h]);
for (d1 = d; d1 < d_; d1++)
if (h_ < h) {
if (!partial)
S(h_ == 0 ? N - 1 - n : ii[n - h_], ii[n - 1 - h_]), partial = 1;
else
S(ii[n - 1 - h_], ii[n - 1 - h_]);
if (aa[ii[n - 1 - h_]] == bb[h_])
h_++, partial = 0;
}
P(ii[n - 1 - h]);
}
for (d1 = 0; d1 < d_; d1++)
if (h_ <= h) {
if (!partial)
S(h_ == 0 ? N - 1 - n : ii[n - h_], ii[n - 1 - h_]), partial = 1;
else
S(ii[n - 1 - h_], ii[n - 1 - h_]);
if (aa[ii[n - 1 - h_]] == bb[h_])
h_++, partial = 0;
}
P(ii[n - 2 - h]);
}
for (h = 0; h < m; h++)
jj[h] = ii[n - 1 - h];
for (h = m; h < n; h++)
jj[h] = ii[h - m];
for (h = 0; h < n; h++)
ii[h] = jj[h];
}
int simulate(int k, int l, int n, int d_, int upper) {
int k_, l_, h;
if ((n - 2) * d_ * (d_ + 1) / 2 + d_ < (k - 1) * (d_ + 1) + l * d_)
return 0;
for ( ; k + l > 0; k = k_, l = l_) {
k_ = k, l_ = l;
if (k_ > 0)
k_--;
else
l_--;
if (k_ + l_ > 0) {
if (l_-- == 0)
return 0;
k_ -= n - 3;
if (k_ < 0)
l_ += k_, k_ = 0;
if (l_ < 0)
l_ = 0;
}
if (upper >= 0) {
if (k_ + l_ > 0)
Q(upper -= (k - k_) * (d_ + 1) + (l - l_) * d_, k - k_, l - l_, n, d_);
else if (k - k_ + l - l_ == 2 || k - k_ <= 1)
Q(upper -= (k - k_) * (d_ + 1) + (l - l_ - 1) * d_, k - k_, l - l_ - 1, n, d_);
else
Q(upper -= (k - k_ - 1) * (d_ + 1) + (l - l_) * d_, k - k_ - 1, l - l_, n, d_);
}
}
if (upper >= 0) {
for (h = n; h > 0; h--)
ii[h] = ii[h - 1];
ii[0] = N - 1 - n;
}
return 1;
}
int solve(int a, int d_) {
static int kk[N], ll[N];
int i, k, l, d, d1;
aa[N - 1] = 0, aa[N - 2] = aa[N - 1] + d_ + 1, aa[N - 3] = aa[N - 2] + d_ + d_ + 1;
for (i = N - 4; i >= 0; i--) {
kk[i] = 0, ll[i] = 0;
for (k = 1; k <= 100; k++)
for (l = 0; l <= 100; l++)
if (simulate(k, l, N - 1 - i, d_, -1) && kk[i] * (d_ + 1) + ll[i] * d_ < k * (d_ + 1) + l * d_)
kk[i] = k, ll[i] = l;
aa[i] = aa[i + 1] + kk[i] * (d_ + 1) + ll[i] * d_;
}
if (aa[0] < a)
return 0;
for (i = 1; i < N; i++)
aa[i] = aa[0] - aa[i];
aa[0] = 0;
limit = d_;
a_ = a, active = 0;
P(N - 1);
for (d = d_; d > 0; d--) {
for (d1 = 0; d1 < d; d1++)
S(d1 == 0 ? N - 2 : N - 1, N - 1);
P(N - 1);
}
for (d1 = 0; d1 < d_; d1++)
S(d1 == 0 ? N - 3 : N - 1, N - 1);
P(N - 2);
ii[0] = N - 3, ii[1] = N - 1, ii[2] = N - 2;
for (i = N - 4; i >= 0; i--)
simulate(kk[i], ll[i], N - 1 - i, d_, aa[i + 1]);
for (i = N - 2; i >= 0; i--) {
for (d = aa[ii[i + 1]] - aa[ii[i]] - 1; d > 0; d--) {
for (d1 = 0; d1 < d; d1++)
S(ii[d1 == 0 ? i : i + 1], ii[i + 1]);
P(ii[i + 1]);
}
P(ii[i]);
}
assert(a_ == -1);
return 1;
}
int main() {
int t, a, i, d_;
scanf("%d%d", &t, &a);
printf("FILE reverse %d\n", t);
if (a < N) {
for (i = 0; i < N; i++)
printf("%d ", i);
printf("\n");
for (i = a; i >= 0; i--)
printf("P %d\n", i);
return 0;
}
d_ = 1;
while (!solve(a, d_))
d_++;
return 0;
}
#include <assert.h>
#include <stdio.h>
#include <stdlib.h>
#define N 9
int min(int a, int b) { return a < b ? a : b; }
int ii[N], jj[N], aa[N], bb[N];
void display() {
int i;
for (i = 0; i < N; i++)
printf("%d ", aa[i]);
printf("\n");
}
int a_, active, limit, run;
void P(int i) {
run = 0;
if (a_ >= aa[i]) {
assert(a_-- == aa[i]);
if (!active)
active = 1, display();
printf("P %d\n", i + 1);
}
}
void S(int i, int j) {
if (active)
printf("S %d %d\n", i + 1, j + 1);
aa[j] = aa[i] + 1;
assert(i < N && j < N && ++run <= limit);
}
void Q(int lower, int k, int l, int n, int d_) {
int m, h, h_, d, d1, partial;
assert(k + l < n);
m = k + l;
if (k > 0)
k--;
else
l--;
for (h = 0; h < m; h++) {
bb[h] = lower;
if (h + 1 < m) {
if (k > 0)
lower += d_ + 1, k--;
else
lower += d_, l--;
}
}
partial = 0;
for (h = 0, h_ = 0; h < m; h++) {
for (d = aa[ii[n - 1 - h]] - aa[ii[n - 2 - h]] - 1; d > 0; d--) {
for (d1 = 0; d1 < d; d1++)
S(ii[d1 == 0 ? n - 2 - h : n - 1 - h], ii[n - 1 - h]);
for (d1 = d; d1 < d_; d1++)
if (h_ < h) {
if (!partial)
S(h_ == 0 ? N - 1 - n : ii[n - h_], ii[n - 1 - h_]), partial = 1;
else
S(ii[n - 1 - h_], ii[n - 1 - h_]);
if (aa[ii[n - 1 - h_]] == bb[h_])
h_++, partial = 0;
}
P(ii[n - 1 - h]);
}
for (d1 = 0; d1 < d_; d1++)
if (h_ <= h) {
if (!partial)
S(h_ == 0 ? N - 1 - n : ii[n - h_], ii[n - 1 - h_]), partial = 1;
else
S(ii[n - 1 - h_], ii[n - 1 - h_]);
if (aa[ii[n - 1 - h_]] == bb[h_])
h_++, partial = 0;
}
P(ii[n - 2 - h]);
}
for (h = 0; h < m; h++)
jj[h] = ii[n - 1 - h];
for (h = m; h < n; h++)
jj[h] = ii[h - m];
for (h = 0; h < n; h++)
ii[h] = jj[h];
}
int simulate(int k, int l, int n, int d_, int upper) {
int k_, l_, h;
if ((n - 2) * d_ * (d_ + 1) / 2 + d_ < (k - 1) * (d_ + 1) + l * d_)
return 0;
for ( ; k + l > 0; k = k_, l = l_) {
k_ = k, l_ = l;
if (k_ > 0)
k_--;
else
l_--;
if (k_ + l_ > 0) {
if (l_-- == 0)
return 0;
k_ -= n - 3;
if (k_ < 0)
l_ += k_, k_ = 0;
if (l_ < 0)
l_ = 0;
}
if (upper >= 0) {
if (k_ + l_ > 0)
Q(upper -= (k - k_) * (d_ + 1) + (l - l_) * d_, k - k_, l - l_, n, d_);
else if (k - k_ + l - l_ == 2 || k - k_ <= 1)
Q(upper -= (k - k_) * (d_ + 1) + (l - l_ - 1) * d_, k - k_, l - l_ - 1, n, d_);
else
Q(upper -= (k - k_ - 1) * (d_ + 1) + (l - l_) * d_, k - k_ - 1, l - l_, n, d_);
}
}
if (upper >= 0) {
for (h = n; h > 0; h--)
ii[h] = ii[h - 1];
ii[0] = N - 1 - n;
}
return 1;
}
int solve(int a, int d_) {
static int kk[N], ll[N];
int i, k, l, d, d1;
aa[N - 1] = 0, aa[N - 2] = aa[N - 1] + d_ + 1, aa[N - 3] = aa[N - 2] + d_ + d_ + 1;
for (i = N - 4; i >= 0; i--) {
kk[i] = 0, ll[i] = 0;
for (k = 1; k <= 100; k++)
for (l = 0; l <= 100; l++)
if (simulate(k, l, N - 1 - i, d_, -1) && kk[i] * (d_ + 1) + ll[i] * d_ < k * (d_ + 1) + l * d_)
kk[i] = k, ll[i] = l;
aa[i] = aa[i + 1] + kk[i] * (d_ + 1) + ll[i] * d_;
}
if (aa[0] < a)
return 0;
for (i = 1; i < N; i++)
aa[i] = aa[0] - aa[i];
aa[0] = 0;
limit = d_;
a_ = a, active = 0;
P(N - 1);
for (d = d_; d > 0; d--) {
for (d1 = 0; d1 < d; d1++)
S(d1 == 0 ? N - 2 : N - 1, N - 1);
P(N - 1);
}
for (d1 = 0; d1 < d_; d1++)
S(d1 == 0 ? N - 3 : N - 1, N - 1);
P(N - 2);
ii[0] = N - 3, ii[1] = N - 1, ii[2] = N - 2;
for (i = N - 4; i >= 0; i--)
simulate(kk[i], ll[i], N - 1 - i, d_, aa[i + 1]);
for (i = N - 2; i >= 0; i--) {
for (d = aa[ii[i + 1]] - aa[ii[i]] - 1; d > 0; d--) {
for (d1 = 0; d1 < d; d1++)
S(ii[d1 == 0 ? i : i + 1], ii[i + 1]);
P(ii[i + 1]);
}
P(ii[i]);
}
assert(a_ == -1);
return 1;
}
int main() {
int t, a, i, d_;
scanf("%d%d", &t, &a);
printf("FILE reverse %d\n", t);
if (a < N) {
for (i = 0; i < N; i++)
printf("%d ", i);
printf("\n");
for (i = a; i >= 0; i--)
printf("P %d\n", i);
return 0;
}
d_ = 1;
while (!solve(a, d_))
d_++;
return 0;
}
#include <assert.h>
#include <stdio.h>
#include <stdlib.h>
#define N 9
int min(int a, int b) { return a < b ? a : b; }
int ii[N], jj[N], aa[N], bb[N];
void display() {
int i;
for (i = 0; i < N; i++)
printf("%d ", aa[i]);
printf("\n");
}
int a_, active, limit, run;
void P(int i) {
run = 0;
if (a_ >= aa[i]) {
assert(a_-- == aa[i]);
if (!active)
active = 1, display();
printf("P %d\n", i + 1);
}
}
void S(int i, int j) {
if (active)
printf("S %d %d\n", i + 1, j + 1);
aa[j] = aa[i] + 1;
assert(i < N && j < N && ++run <= limit);
}
void Q(int lower, int k, int l, int n, int d_) {
int m, h, h_, d, d1, partial;
assert(k + l < n);
m = k + l;
if (k > 0)
k--;
else
l--;
for (h = 0; h < m; h++) {
bb[h] = lower;
if (h + 1 < m) {
if (k > 0)
lower += d_ + 1, k--;
else
lower += d_, l--;
}
}
partial = 0;
for (h = 0, h_ = 0; h < m; h++) {
for (d = aa[ii[n - 1 - h]] - aa[ii[n - 2 - h]] - 1; d > 0; d--) {
for (d1 = 0; d1 < d; d1++)
S(ii[d1 == 0 ? n - 2 - h : n - 1 - h], ii[n - 1 - h]);
for (d1 = d; d1 < d_; d1++)
if (h_ < h) {
if (!partial)
S(h_ == 0 ? N - 1 - n : ii[n - h_], ii[n - 1 - h_]), partial = 1;
else
S(ii[n - 1 - h_], ii[n - 1 - h_]);
if (aa[ii[n - 1 - h_]] == bb[h_])
h_++, partial = 0;
}
P(ii[n - 1 - h]);
}
for (d1 = 0; d1 < d_; d1++)
if (h_ <= h) {
if (!partial)
S(h_ == 0 ? N - 1 - n : ii[n - h_], ii[n - 1 - h_]), partial = 1;
else
S(ii[n - 1 - h_], ii[n - 1 - h_]);
if (aa[ii[n - 1 - h_]] == bb[h_])
h_++, partial = 0;
}
P(ii[n - 2 - h]);
}
for (h = 0; h < m; h++)
jj[h] = ii[n - 1 - h];
for (h = m; h < n; h++)
jj[h] = ii[h - m];
for (h = 0; h < n; h++)
ii[h] = jj[h];
}
int simulate(int k, int l, int n, int d_, int upper) {
int k_, l_, h;
if ((n - 2) * d_ * (d_ + 1) / 2 + d_ < (k - 1) * (d_ + 1) + l * d_)
return 0;
for ( ; k + l > 0; k = k_, l = l_) {
k_ = k, l_ = l;
if (k_ > 0)
k_--;
else
l_--;
if (k_ + l_ > 0) {
if (l_-- == 0)
return 0;
k_ -= n - 3;
if (k_ < 0)
l_ += k_, k_ = 0;
if (l_ < 0)
l_ = 0;
}
if (upper >= 0) {
if (k_ + l_ > 0)
Q(upper -= (k - k_) * (d_ + 1) + (l - l_) * d_, k - k_, l - l_, n, d_);
else if (k - k_ + l - l_ == 2 || k - k_ <= 1)
Q(upper -= (k - k_) * (d_ + 1) + (l - l_ - 1) * d_, k - k_, l - l_ - 1, n, d_);
else
Q(upper -= (k - k_ - 1) * (d_ + 1) + (l - l_) * d_, k - k_ - 1, l - l_, n, d_);
}
}
if (upper >= 0) {
for (h = n; h > 0; h--)
ii[h] = ii[h - 1];
ii[0] = N - 1 - n;
}
return 1;
}
int solve(int a, int d_) {
static int kk[N], ll[N];
int i, k, l, d, d1;
aa[N - 1] = 0, aa[N - 2] = aa[N - 1] + d_ + 1, aa[N - 3] = aa[N - 2] + d_ + d_ + 1;
for (i = N - 4; i >= 0; i--) {
kk[i] = 0, ll[i] = 0;
for (k = 1; k <= 100; k++)
for (l = 0; l <= 100; l++)
if (simulate(k, l, N - 1 - i, d_, -1) && kk[i] * (d_ + 1) + ll[i] * d_ < k * (d_ + 1) + l * d_)
kk[i] = k, ll[i] = l;
aa[i] = aa[i + 1] + kk[i] * (d_ + 1) + ll[i] * d_;
}
if (aa[0] < a)
return 0;
for (i = 1; i < N; i++)
aa[i] = aa[0] - aa[i];
aa[0] = 0;
limit = d_;
a_ = a, active = 0;
P(N - 1);
for (d = d_; d > 0; d--) {
for (d1 = 0; d1 < d; d1++)
S(d1 == 0 ? N - 2 : N - 1, N - 1);
P(N - 1);
}
for (d1 = 0; d1 < d_; d1++)
S(d1 == 0 ? N - 3 : N - 1, N - 1);
P(N - 2);
ii[0] = N - 3, ii[1] = N - 1, ii[2] = N - 2;
for (i = N - 4; i >= 0; i--)
simulate(kk[i], ll[i], N - 1 - i, d_, aa[i + 1]);
for (i = N - 2; i >= 0; i--) {
for (d = aa[ii[i + 1]] - aa[ii[i]] - 1; d > 0; d--) {
for (d1 = 0; d1 < d; d1++)
S(ii[d1 == 0 ? i : i + 1], ii[i + 1]);
P(ii[i + 1]);
}
P(ii[i]);
}
assert(a_ == -1);
return 1;
}
int main() {
int t, a, i, d_;
scanf("%d%d", &t, &a);
printf("FILE reverse %d\n", t);
if (a < N) {
for (i = 0; i < N; i++)
printf("%d ", i);
printf("\n");
for (i = a; i >= 0; i--)
printf("P %d\n", i);
return 0;
}
d_ = 1;
while (!solve(a, d_))
d_++;
return 0;
}
#include <assert.h>
#include <stdio.h>
#include <stdlib.h>
#define N 9
int min(int a, int b) { return a < b ? a : b; }
int ii[N], jj[N], aa[N], bb[N];
void display() {
int i;
for (i = 0; i < N; i++)
printf("%d ", aa[i]);
printf("\n");
}
int a_, active, limit, run;
void P(int i) {
run = 0;
if (a_ >= aa[i]) {
assert(a_-- == aa[i]);
if (!active)
active = 1, display();
printf("P %d\n", i + 1);
}
}
void S(int i, int j) {
if (active)
printf("S %d %d\n", i + 1, j + 1);
aa[j] = aa[i] + 1;
assert(i < N && j < N && ++run <= limit);
}
void Q(int lower, int k, int l, int n, int d_) {
int m, h, h_, d, d1, partial;
assert(k + l < n);
m = k + l;
if (k > 0)
k--;
else
l--;
for (h = 0; h < m; h++) {
bb[h] = lower;
if (h + 1 < m) {
if (k > 0)
lower += d_ + 1, k--;
else
lower += d_, l--;
}
}
partial = 0;
for (h = 0, h_ = 0; h < m; h++) {
for (d = aa[ii[n - 1 - h]] - aa[ii[n - 2 - h]] - 1; d > 0; d--) {
for (d1 = 0; d1 < d; d1++)
S(ii[d1 == 0 ? n - 2 - h : n - 1 - h], ii[n - 1 - h]);
for (d1 = d; d1 < d_; d1++)
if (h_ < h) {
if (!partial)
S(h_ == 0 ? N - 1 - n : ii[n - h_], ii[n - 1 - h_]), partial = 1;
else
S(ii[n - 1 - h_], ii[n - 1 - h_]);
if (aa[ii[n - 1 - h_]] == bb[h_])
h_++, partial = 0;
}
P(ii[n - 1 - h]);
}
for (d1 = 0; d1 < d_; d1++)
if (h_ <= h) {
if (!partial)
S(h_ == 0 ? N - 1 - n : ii[n - h_], ii[n - 1 - h_]), partial = 1;
else
S(ii[n - 1 - h_], ii[n - 1 - h_]);
if (aa[ii[n - 1 - h_]] == bb[h_])
h_++, partial = 0;
}
P(ii[n - 2 - h]);
}
for (h = 0; h < m; h++)
jj[h] = ii[n - 1 - h];
for (h = m; h < n; h++)
jj[h] = ii[h - m];
for (h = 0; h < n; h++)
ii[h] = jj[h];
}
int simulate(int k, int l, int n, int d_, int upper) {
int k_, l_, h;
if ((n - 2) * d_ * (d_ + 1) / 2 + d_ < (k - 1) * (d_ + 1) + l * d_)
return 0;
for ( ; k + l > 0; k = k_, l = l_) {
k_ = k, l_ = l;
if (k_ > 0)
k_--;
else
l_--;
if (k_ + l_ > 0) {
if (l_-- == 0)
return 0;
k_ -= n - 3;
if (k_ < 0)
l_ += k_, k_ = 0;
if (l_ < 0)
l_ = 0;
}
if (upper >= 0) {
if (k_ + l_ > 0)
Q(upper -= (k - k_) * (d_ + 1) + (l - l_) * d_, k - k_, l - l_, n, d_);
else if (k - k_ + l - l_ == 2 || k - k_ <= 1)
Q(upper -= (k - k_) * (d_ + 1) + (l - l_ - 1) * d_, k - k_, l - l_ - 1, n, d_);
else
Q(upper -= (k - k_ - 1) * (d_ + 1) + (l - l_) * d_, k - k_ - 1, l - l_, n, d_);
}
}
if (upper >= 0) {
for (h = n; h > 0; h--)
ii[h] = ii[h - 1];
ii[0] = N - 1 - n;
}
return 1;
}
int solve(int a, int d_) {
static int kk[N], ll[N];
int i, k, l, d, d1;
aa[N - 1] = 0, aa[N - 2] = aa[N - 1] + d_ + 1, aa[N - 3] = aa[N - 2] + d_ + d_ + 1;
for (i = N - 4; i >= 0; i--) {
kk[i] = 0, ll[i] = 0;
for (k = 1; k <= 100; k++)
for (l = 0; l <= 100; l++)
if (simulate(k, l, N - 1 - i, d_, -1) && kk[i] * (d_ + 1) + ll[i] * d_ < k * (d_ + 1) + l * d_)
kk[i] = k, ll[i] = l;
aa[i] = aa[i + 1] + kk[i] * (d_ + 1) + ll[i] * d_;
}
if (aa[0] < a)
return 0;
for (i = 1; i < N; i++)
aa[i] = aa[0] - aa[i];
aa[0] = 0;
limit = d_;
a_ = a, active = 0;
P(N - 1);
for (d = d_; d > 0; d--) {
for (d1 = 0; d1 < d; d1++)
S(d1 == 0 ? N - 2 : N - 1, N - 1);
P(N - 1);
}
for (d1 = 0; d1 < d_; d1++)
S(d1 == 0 ? N - 3 : N - 1, N - 1);
P(N - 2);
ii[0] = N - 3, ii[1] = N - 1, ii[2] = N - 2;
for (i = N - 4; i >= 0; i--)
simulate(kk[i], ll[i], N - 1 - i, d_, aa[i + 1]);
for (i = N - 2; i >= 0; i--) {
for (d = aa[ii[i + 1]] - aa[ii[i]] - 1; d > 0; d--) {
for (d1 = 0; d1 < d; d1++)
S(ii[d1 == 0 ? i : i + 1], ii[i + 1]);
P(ii[i + 1]);
}
P(ii[i]);
}
assert(a_ == -1);
return 1;
}
int main() {
int t, a, i, d_;
scanf("%d%d", &t, &a);
printf("FILE reverse %d\n", t);
if (a < N) {
for (i = 0; i < N; i++)
printf("%d ", i);
printf("\n");
for (i = a; i >= 0; i--)
printf("P %d\n", i);
return 0;
}
d_ = 1;
while (!solve(a, d_))
d_++;
return 0;
}
#include <assert.h>
#include <stdio.h>
#include <stdlib.h>
#define N 9
int min(int a, int b) { return a < b ? a : b; }
int ii[N], jj[N], aa[N], bb[N];
void display() {
int i;
for (i = 0; i < N; i++)
printf("%d ", aa[i]);
printf("\n");
}
int a_, active, limit, run;
void P(int i) {
run = 0;
if (a_ >= aa[i]) {
assert(a_-- == aa[i]);
if (!active)
active = 1, display();
printf("P %d\n", i + 1);
}
}
void S(int i, int j) {
if (active)
printf("S %d %d\n", i + 1, j + 1);
aa[j] = aa[i] + 1;
assert(i < N && j < N && ++run <= limit);
}
void Q(int lower, int k, int l, int n, int d_) {
int m, h, h_, d, d1, partial;
assert(k + l < n);
m = k + l;
if (k > 0)
k--;
else
l--;
for (h = 0; h < m; h++) {
bb[h] = lower;
if (h + 1 < m) {
if (k > 0)
lower += d_ + 1, k--;
else
lower += d_, l--;
}
}
partial = 0;
for (h = 0, h_ = 0; h < m; h++) {
for (d = aa[ii[n - 1 - h]] - aa[ii[n - 2 - h]] - 1; d > 0; d--) {
for (d1 = 0; d1 < d; d1++)
S(ii[d1 == 0 ? n - 2 - h : n - 1 - h], ii[n - 1 - h]);
for (d1 = d; d1 < d_; d1++)
if (h_ < h) {
if (!partial)
S(h_ == 0 ? N - 1 - n : ii[n - h_], ii[n - 1 - h_]), partial = 1;
else
S(ii[n - 1 - h_], ii[n - 1 - h_]);
if (aa[ii[n - 1 - h_]] == bb[h_])
h_++, partial = 0;
}
P(ii[n - 1 - h]);
}
for (d1 = 0; d1 < d_; d1++)
if (h_ <= h) {
if (!partial)
S(h_ == 0 ? N - 1 - n : ii[n - h_], ii[n - 1 - h_]), partial = 1;
else
S(ii[n - 1 - h_], ii[n - 1 - h_]);
if (aa[ii[n - 1 - h_]] == bb[h_])
h_++, partial = 0;
}
P(ii[n - 2 - h]);
}
for (h = 0; h < m; h++)
jj[h] = ii[n - 1 - h];
for (h = m; h < n; h++)
jj[h] = ii[h - m];
for (h = 0; h < n; h++)
ii[h] = jj[h];
}
int simulate(int k, int l, int n, int d_, int upper) {
int k_, l_, h;
if ((n - 2) * d_ * (d_ + 1) / 2 + d_ < (k - 1) * (d_ + 1) + l * d_)
return 0;
for ( ; k + l > 0; k = k_, l = l_) {
k_ = k, l_ = l;
if (k_ > 0)
k_--;
else
l_--;
if (k_ + l_ > 0) {
if (l_-- == 0)
return 0;
k_ -= n - 3;
if (k_ < 0)
l_ += k_, k_ = 0;
if (l_ < 0)
l_ = 0;
}
if (upper >= 0) {
if (k_ + l_ > 0)
Q(upper -= (k - k_) * (d_ + 1) + (l - l_) * d_, k - k_, l - l_, n, d_);
else if (k - k_ + l - l_ == 2 || k - k_ <= 1)
Q(upper -= (k - k_) * (d_ + 1) + (l - l_ - 1) * d_, k - k_, l - l_ - 1, n, d_);
else
Q(upper -= (k - k_ - 1) * (d_ + 1) + (l - l_) * d_, k - k_ - 1, l - l_, n, d_);
}
}
if (upper >= 0) {
for (h = n; h > 0; h--)
ii[h] = ii[h - 1];
ii[0] = N - 1 - n;
}
return 1;
}
int solve(int a, int d_) {
static int kk[N], ll[N];
int i, k, l, d, d1;
aa[N - 1] = 0, aa[N - 2] = aa[N - 1] + d_ + 1, aa[N - 3] = aa[N - 2] + d_ + d_ + 1;
for (i = N - 4; i >= 0; i--) {
kk[i] = 0, ll[i] = 0;
for (k = 1; k <= 100; k++)
for (l = 0; l <= 100; l++)
if (simulate(k, l, N - 1 - i, d_, -1) && kk[i] * (d_ + 1) + ll[i] * d_ < k * (d_ + 1) + l * d_)
kk[i] = k, ll[i] = l;
aa[i] = aa[i + 1] + kk[i] * (d_ + 1) + ll[i] * d_;
}
if (aa[0] < a)
return 0;
for (i = 1; i < N; i++)
aa[i] = aa[0] - aa[i];
aa[0] = 0;
limit = d_;
a_ = a, active = 0;
P(N - 1);
for (d = d_; d > 0; d--) {
for (d1 = 0; d1 < d; d1++)
S(d1 == 0 ? N - 2 : N - 1, N - 1);
P(N - 1);
}
for (d1 = 0; d1 < d_; d1++)
S(d1 == 0 ? N - 3 : N - 1, N - 1);
P(N - 2);
ii[0] = N - 3, ii[1] = N - 1, ii[2] = N - 2;
for (i = N - 4; i >= 0; i--)
simulate(kk[i], ll[i], N - 1 - i, d_, aa[i + 1]);
for (i = N - 2; i >= 0; i--) {
for (d = aa[ii[i + 1]] - aa[ii[i]] - 1; d > 0; d--) {
for (d1 = 0; d1 < d; d1++)
S(ii[d1 == 0 ? i : i + 1], ii[i + 1]);
P(ii[i + 1]);
}
P(ii[i]);
}
assert(a_ == -1);
return 1;
}
int main() {
int t, a, i, d_;
scanf("%d%d", &t, &a);
printf("FILE reverse %d\n", t);
if (a < N) {
for (i = 0; i < N; i++)
printf("%d ", i);
printf("\n");
for (i = a; i >= 0; i--)
printf("P %d\n", i);
return 0;
}
d_ = 1;
while (!solve(a, d_))
d_++;
return 0;
}
#include <assert.h>
#include <stdio.h>
#include <stdlib.h>
#define N 9
int min(int a, int b) { return a < b ? a : b; }
int ii[N], jj[N], aa[N], bb[N];
void display() {
int i;
for (i = 0; i < N; i++)
printf("%d ", aa[i]);
printf("\n");
}
int a_, active, limit, run;
void P(int i) {
run = 0;
if (a_ >= aa[i]) {
assert(a_-- == aa[i]);
if (!active)
active = 1, display();
printf("P %d\n", i + 1);
}
}
void S(int i, int j) {
if (active)
printf("S %d %d\n", i + 1, j + 1);
aa[j] = aa[i] + 1;
assert(i < N && j < N && ++run <= limit);
}
void Q(int lower, int k, int l, int n, int d_) {
int m, h, h_, d, d1, partial;
assert(k + l < n);
m = k + l;
if (k > 0)
k--;
else
l--;
for (h = 0; h < m; h++) {
bb[h] = lower;
if (h + 1 < m) {
if (k > 0)
lower += d_ + 1, k--;
else
lower += d_, l--;
}
}
partial = 0;
for (h = 0, h_ = 0; h < m; h++) {
for (d = aa[ii[n - 1 - h]] - aa[ii[n - 2 - h]] - 1; d > 0; d--) {
for (d1 = 0; d1 < d; d1++)
S(ii[d1 == 0 ? n - 2 - h : n - 1 - h], ii[n - 1 - h]);
for (d1 = d; d1 < d_; d1++)
if (h_ < h) {
if (!partial)
S(h_ == 0 ? N - 1 - n : ii[n - h_], ii[n - 1 - h_]), partial = 1;
else
S(ii[n - 1 - h_], ii[n - 1 - h_]);
if (aa[ii[n - 1 - h_]] == bb[h_])
h_++, partial = 0;
}
P(ii[n - 1 - h]);
}
for (d1 = 0; d1 < d_; d1++)
if (h_ <= h) {
if (!partial)
S(h_ == 0 ? N - 1 - n : ii[n - h_], ii[n - 1 - h_]), partial = 1;
else
S(ii[n - 1 - h_], ii[n - 1 - h_]);
if (aa[ii[n - 1 - h_]] == bb[h_])
h_++, partial = 0;
}
P(ii[n - 2 - h]);
}
for (h = 0; h < m; h++)
jj[h] = ii[n - 1 - h];
for (h = m; h < n; h++)
jj[h] = ii[h - m];
for (h = 0; h < n; h++)
ii[h] = jj[h];
}
int simulate(int k, int l, int n, int d_, int upper) {
int k_, l_, h;
if ((n - 2) * d_ * (d_ + 1) / 2 + d_ < (k - 1) * (d_ + 1) + l * d_)
return 0;
for ( ; k + l > 0; k = k_, l = l_) {
k_ = k, l_ = l;
if (k_ > 0)
k_--;
else
l_--;
if (k_ + l_ > 0) {
if (l_-- == 0)
return 0;
k_ -= n - 3;
if (k_ < 0)
l_ += k_, k_ = 0;
if (l_ < 0)
l_ = 0;
}
if (upper >= 0) {
if (k_ + l_ > 0)
Q(upper -= (k - k_) * (d_ + 1) + (l - l_) * d_, k - k_, l - l_, n, d_);
else if (k - k_ + l - l_ == 2 || k - k_ <= 1)
Q(upper -= (k - k_) * (d_ + 1) + (l - l_ - 1) * d_, k - k_, l - l_ - 1, n, d_);
else
Q(upper -= (k - k_ - 1) * (d_ + 1) + (l - l_) * d_, k - k_ - 1, l - l_, n, d_);
}
}
if (upper >= 0) {
for (h = n; h > 0; h--)
ii[h] = ii[h - 1];
ii[0] = N - 1 - n;
}
return 1;
}
int solve(int a, int d_) {
static int kk[N], ll[N];
int i, k, l, d, d1;
aa[N - 1] = 0, aa[N - 2] = aa[N - 1] + d_ + 1, aa[N - 3] = aa[N - 2] + d_ + d_ + 1;
for (i = N - 4; i >= 0; i--) {
kk[i] = 0, ll[i] = 0;
for (k = 1; k <= 100; k++)
for (l = 0; l <= 100; l++)
if (simulate(k, l, N - 1 - i, d_, -1) && kk[i] * (d_ + 1) + ll[i] * d_ < k * (d_ + 1) + l * d_)
kk[i] = k, ll[i] = l;
aa[i] = aa[i + 1] + kk[i] * (d_ + 1) + ll[i] * d_;
}
if (aa[0] < a)
return 0;
for (i = 1; i < N; i++)
aa[i] = aa[0] - aa[i];
aa[0] = 0;
limit = d_;
a_ = a, active = 0;
P(N - 1);
for (d = d_; d > 0; d--) {
for (d1 = 0; d1 < d; d1++)
S(d1 == 0 ? N - 2 : N - 1, N - 1);
P(N - 1);
}
for (d1 = 0; d1 < d_; d1++)
S(d1 == 0 ? N - 3 : N - 1, N - 1);
P(N - 2);
ii[0] = N - 3, ii[1] = N - 1, ii[2] = N - 2;
for (i = N - 4; i >= 0; i--)
simulate(kk[i], ll[i], N - 1 - i, d_, aa[i + 1]);
for (i = N - 2; i >= 0; i--) {
for (d = aa[ii[i + 1]] - aa[ii[i]] - 1; d > 0; d--) {
for (d1 = 0; d1 < d; d1++)
S(ii[d1 == 0 ? i : i + 1], ii[i + 1]);
P(ii[i + 1]);
}
P(ii[i]);
}
assert(a_ == -1);
return 1;
}
int main() {
int t, a, i, d_;
scanf("%d%d", &t, &a);
printf("FILE reverse %d\n", t);
if (a < N) {
for (i = 0; i < N; i++)
printf("%d ", i);
printf("\n");
for (i = a; i >= 0; i--)
printf("P %d\n", i);
return 0;
}
d_ = 1;
while (!solve(a, d_))
d_++;
return 0;
}
#include <assert.h>
#include <stdio.h>
#include <stdlib.h>
#define N 9
int min(int a, int b) { return a < b ? a : b; }
int ii[N], jj[N], aa[N], bb[N];
void display() {
int i;
for (i = 0; i < N; i++)
printf("%d ", aa[i]);
printf("\n");
}
int a_, active, limit, run;
void P(int i) {
run = 0;
if (a_ >= aa[i]) {
assert(a_-- == aa[i]);
if (!active)
active = 1, display();
printf("P %d\n", i + 1);
}
}
void S(int i, int j) {
if (active)
printf("S %d %d\n", i + 1, j + 1);
aa[j] = aa[i] + 1;
assert(i < N && j < N && ++run <= limit);
}
void Q(int lower, int k, int l, int n, int d_) {
int m, h, h_, d, d1, partial;
assert(k + l < n);
m = k + l;
if (k > 0)
k--;
else
l--;
for (h = 0; h < m; h++) {
bb[h] = lower;
if (h + 1 < m) {
if (k > 0)
lower += d_ + 1, k--;
else
lower += d_, l--;
}
}
partial = 0;
for (h = 0, h_ = 0; h < m; h++) {
for (d = aa[ii[n - 1 - h]] - aa[ii[n - 2 - h]] - 1; d > 0; d--) {
for (d1 = 0; d1 < d; d1++)
S(ii[d1 == 0 ? n - 2 - h : n - 1 - h], ii[n - 1 - h]);
for (d1 = d; d1 < d_; d1++)
if (h_ < h) {
if (!partial)
S(h_ == 0 ? N - 1 - n : ii[n - h_], ii[n - 1 - h_]), partial = 1;
else
S(ii[n - 1 - h_], ii[n - 1 - h_]);
if (aa[ii[n - 1 - h_]] == bb[h_])
h_++, partial = 0;
}
P(ii[n - 1 - h]);
}
for (d1 = 0; d1 < d_; d1++)
if (h_ <= h) {
if (!partial)
S(h_ == 0 ? N - 1 - n : ii[n - h_], ii[n - 1 - h_]), partial = 1;
else
S(ii[n - 1 - h_], ii[n - 1 - h_]);
if (aa[ii[n - 1 - h_]] == bb[h_])
h_++, partial = 0;
}
P(ii[n - 2 - h]);
}
for (h = 0; h < m; h++)
jj[h] = ii[n - 1 - h];
for (h = m; h < n; h++)
jj[h] = ii[h - m];
for (h = 0; h < n; h++)
ii[h] = jj[h];
}
int simulate(int k, int l, int n, int d_, int upper) {
int k_, l_, h;
if ((n - 2) * d_ * (d_ + 1) / 2 + d_ < (k - 1) * (d_ + 1) + l * d_)
return 0;
for ( ; k + l > 0; k = k_, l = l_) {
k_ = k, l_ = l;
if (k_ > 0)
k_--;
else
l_--;
if (k_ + l_ > 0) {
if (l_-- == 0)
return 0;
k_ -= n - 3;
if (k_ < 0)
l_ += k_, k_ = 0;
if (l_ < 0)
l_ = 0;
}
if (upper >= 0) {
if (k_ + l_ > 0)
Q(upper -= (k - k_) * (d_ + 1) + (l - l_) * d_, k - k_, l - l_, n, d_);
else if (k - k_ + l - l_ == 2 || k - k_ <= 1)
Q(upper -= (k - k_) * (d_ + 1) + (l - l_ - 1) * d_, k - k_, l - l_ - 1, n, d_);
else
Q(upper -= (k - k_ - 1) * (d_ + 1) + (l - l_) * d_, k - k_ - 1, l - l_, n, d_);
}
}
if (upper >= 0) {
for (h = n; h > 0; h--)
ii[h] = ii[h - 1];
ii[0] = N - 1 - n;
}
return 1;
}
int solve(int a, int d_) {
static int kk[N], ll[N];
int i, k, l, d, d1;
aa[N - 1] = 0, aa[N - 2] = aa[N - 1] + d_ + 1, aa[N - 3] = aa[N - 2] + d_ + d_ + 1;
for (i = N - 4; i >= 0; i--) {
kk[i] = 0, ll[i] = 0;
for (k = 1; k <= 100; k++)
for (l = 0; l <= 100; l++)
if (simulate(k, l, N - 1 - i, d_, -1) && kk[i] * (d_ + 1) + ll[i] * d_ < k * (d_ + 1) + l * d_)
kk[i] = k, ll[i] = l;
aa[i] = aa[i + 1] + kk[i] * (d_ + 1) + ll[i] * d_;
}
if (aa[0] < a)
return 0;
for (i = 1; i < N; i++)
aa[i] = aa[0] - aa[i];
aa[0] = 0;
limit = d_;
a_ = a, active = 0;
P(N - 1);
for (d = d_; d > 0; d--) {
for (d1 = 0; d1 < d; d1++)
S(d1 == 0 ? N - 2 : N - 1, N - 1);
P(N - 1);
}
for (d1 = 0; d1 < d_; d1++)
S(d1 == 0 ? N - 3 : N - 1, N - 1);
P(N - 2);
ii[0] = N - 3, ii[1] = N - 1, ii[2] = N - 2;
for (i = N - 4; i >= 0; i--)
simulate(kk[i], ll[i], N - 1 - i, d_, aa[i + 1]);
for (i = N - 2; i >= 0; i--) {
for (d = aa[ii[i + 1]] - aa[ii[i]] - 1; d > 0; d--) {
for (d1 = 0; d1 < d; d1++)
S(ii[d1 == 0 ? i : i + 1], ii[i + 1]);
P(ii[i + 1]);
}
P(ii[i]);
}
assert(a_ == -1);
return 1;
}
int main() {
int t, a, i, d_;
scanf("%d%d", &t, &a);
printf("FILE reverse %d\n", t);
if (a < N) {
for (i = 0; i < N; i++)
printf("%d ", i);
printf("\n");
for (i = a; i >= 0; i--)
printf("P %d\n", i);
return 0;
}
d_ = 1;
while (!solve(a, d_))
d_++;
return 0;
}
#include <assert.h>
#include <stdio.h>
#include <stdlib.h>
#define N 9
int min(int a, int b) { return a < b ? a : b; }
int ii[N], jj[N], aa[N], bb[N];
void display() {
int i;
for (i = 0; i < N; i++)
printf("%d ", aa[i]);
printf("\n");
}
int a_, active, limit, run;
void P(int i) {
run = 0;
if (a_ >= aa[i]) {
assert(a_-- == aa[i]);
if (!active)
active = 1, display();
printf("P %d\n", i + 1);
}
}
void S(int i, int j) {
if (active)
printf("S %d %d\n", i + 1, j + 1);
aa[j] = aa[i] + 1;
assert(i < N && j < N && ++run <= limit);
}
void Q(int lower, int k, int l, int n, int d_) {
int m, h, h_, d, d1, partial;
assert(k + l < n);
m = k + l;
if (k > 0)
k--;
else
l--;
for (h = 0; h < m; h++) {
bb[h] = lower;
if (h + 1 < m) {
if (k > 0)
lower += d_ + 1, k--;
else
lower += d_, l--;
}
}
partial = 0;
for (h = 0, h_ = 0; h < m; h++) {
for (d = aa[ii[n - 1 - h]] - aa[ii[n - 2 - h]] - 1; d > 0; d--) {
for (d1 = 0; d1 < d; d1++)
S(ii[d1 == 0 ? n - 2 - h : n - 1 - h], ii[n - 1 - h]);
for (d1 = d; d1 < d_; d1++)
if (h_ < h) {
if (!partial)
S(h_ == 0 ? N - 1 - n : ii[n - h_], ii[n - 1 - h_]), partial = 1;
else
S(ii[n - 1 - h_], ii[n - 1 - h_]);
if (aa[ii[n - 1 - h_]] == bb[h_])
h_++, partial = 0;
}
P(ii[n - 1 - h]);
}
for (d1 = 0; d1 < d_; d1++)
if (h_ <= h) {
if (!partial)
S(h_ == 0 ? N - 1 - n : ii[n - h_], ii[n - 1 - h_]), partial = 1;
else
S(ii[n - 1 - h_], ii[n - 1 - h_]);
if (aa[ii[n - 1 - h_]] == bb[h_])
h_++, partial = 0;
}
P(ii[n - 2 - h]);
}
for (h = 0; h < m; h++)
jj[h] = ii[n - 1 - h];
for (h = m; h < n; h++)
jj[h] = ii[h - m];
for (h = 0; h < n; h++)
ii[h] = jj[h];
}
int simulate(int k, int l, int n, int d_, int upper) {
int k_, l_, h;
if ((n - 2) * d_ * (d_ + 1) / 2 + d_ < (k - 1) * (d_ + 1) + l * d_)
return 0;
for ( ; k + l > 0; k = k_, l = l_) {
k_ = k, l_ = l;
if (k_ > 0)
k_--;
else
l_--;
if (k_ + l_ > 0) {
if (l_-- == 0)
return 0;
k_ -= n - 3;
if (k_ < 0)
l_ += k_, k_ = 0;
if (l_ < 0)
l_ = 0;
}
if (upper >= 0) {
if (k_ + l_ > 0)
Q(upper -= (k - k_) * (d_ + 1) + (l - l_) * d_, k - k_, l - l_, n, d_);
else if (k - k_ + l - l_ == 2 || k - k_ <= 1)
Q(upper -= (k - k_) * (d_ + 1) + (l - l_ - 1) * d_, k - k_, l - l_ - 1, n, d_);
else
Q(upper -= (k - k_ - 1) * (d_ + 1) + (l - l_) * d_, k - k_ - 1, l - l_, n, d_);
}
}
if (upper >= 0) {
for (h = n; h > 0; h--)
ii[h] = ii[h - 1];
ii[0] = N - 1 - n;
}
return 1;
}
int solve(int a, int d_) {
static int kk[N], ll[N];
int i, k, l, d, d1;
aa[N - 1] = 0, aa[N - 2] = aa[N - 1] + d_ + 1, aa[N - 3] = aa[N - 2] + d_ + d_ + 1;
for (i = N - 4; i >= 0; i--) {
kk[i] = 0, ll[i] = 0;
for (k = 1; k <= 100; k++)
for (l = 0; l <= 100; l++)
if (simulate(k, l, N - 1 - i, d_, -1) && kk[i] * (d_ + 1) + ll[i] * d_ < k * (d_ + 1) + l * d_)
kk[i] = k, ll[i] = l;
aa[i] = aa[i + 1] + kk[i] * (d_ + 1) + ll[i] * d_;
}
if (aa[0] < a)
return 0;
for (i = 1; i < N; i++)
aa[i] = aa[0] - aa[i];
aa[0] = 0;
limit = d_;
a_ = a, active = 0;
P(N - 1);
for (d = d_; d > 0; d--) {
for (d1 = 0; d1 < d; d1++)
S(d1 == 0 ? N - 2 : N - 1, N - 1);
P(N - 1);
}
for (d1 = 0; d1 < d_; d1++)
S(d1 == 0 ? N - 3 : N - 1, N - 1);
P(N - 2);
ii[0] = N - 3, ii[1] = N - 1, ii[2] = N - 2;
for (i = N - 4; i >= 0; i--)
simulate(kk[i], ll[i], N - 1 - i, d_, aa[i + 1]);
for (i = N - 2; i >= 0; i--) {
for (d = aa[ii[i + 1]] - aa[ii[i]] - 1; d > 0; d--) {
for (d1 = 0; d1 < d; d1++)
S(ii[d1 == 0 ? i : i + 1], ii[i + 1]);
P(ii[i + 1]);
}
P(ii[i]);
}
assert(a_ == -1);
return 1;
}
int main() {
int t, a, i, d_;
scanf("%d%d", &t, &a);
printf("FILE reverse %d\n", t);
if (a < N) {
for (i = 0; i < N; i++)
printf("%d ", i);
printf("\n");
for (i = a; i >= 0; i--)
printf("P %d\n", i);
return 0;
}
d_ = 1;
while (!solve(a, d_))
d_++;
return 0;
}
#include <assert.h>
#include <stdio.h>
#include <stdlib.h>
#define N 9
int min(int a, int b) { return a < b ? a : b; }
int ii[N], jj[N], aa[N], bb[N];
void display() {
int i;
for (i = 0; i < N; i++)
printf("%d ", aa[i]);
printf("\n");
}
int a_, active, limit, run;
void P(int i) {
run = 0;
if (a_ >= aa[i]) {
assert(a_-- == aa[i]);
if (!active)
active = 1, display();
printf("P %d\n", i + 1);
}
}
void S(int i, int j) {
if (active)
printf("S %d %d\n", i + 1, j + 1);
aa[j] = aa[i] + 1;
assert(i < N && j < N && ++run <= limit);
}
void Q(int lower, int k, int l, int n, int d_) {
int m, h, h_, d, d1, partial;
assert(k + l < n);
m = k + l;
if (k > 0)
k--;
else
l--;
for (h = 0; h < m; h++) {
bb[h] = lower;
if (h + 1 < m) {
if (k > 0)
lower += d_ + 1, k--;
else
lower += d_, l--;
}
}
partial = 0;
for (h = 0, h_ = 0; h < m; h++) {
for (d = aa[ii[n - 1 - h]] - aa[ii[n - 2 - h]] - 1; d > 0; d--) {
for (d1 = 0; d1 < d; d1++)
S(ii[d1 == 0 ? n - 2 - h : n - 1 - h], ii[n - 1 - h]);
for (d1 = d; d1 < d_; d1++)
if (h_ < h) {
if (!partial)
S(h_ == 0 ? N - 1 - n : ii[n - h_], ii[n - 1 - h_]), partial = 1;
else
S(ii[n - 1 - h_], ii[n - 1 - h_]);
if (aa[ii[n - 1 - h_]] == bb[h_])
h_++, partial = 0;
}
P(ii[n - 1 - h]);
}
for (d1 = 0; d1 < d_; d1++)
if (h_ <= h) {
if (!partial)
S(h_ == 0 ? N - 1 - n : ii[n - h_], ii[n - 1 - h_]), partial = 1;
else
S(ii[n - 1 - h_], ii[n - 1 - h_]);
if (aa[ii[n - 1 - h_]] == bb[h_])
h_++, partial = 0;
}
P(ii[n - 2 - h]);
}
for (h = 0; h < m; h++)
jj[h] = ii[n - 1 - h];
for (h = m; h < n; h++)
jj[h] = ii[h - m];
for (h = 0; h < n; h++)
ii[h] = jj[h];
}
int simulate(int k, int l, int n, int d_, int upper) {
int k_, l_, h;
if ((n - 2) * d_ * (d_ + 1) / 2 + d_ < (k - 1) * (d_ + 1) + l * d_)
return 0;
for ( ; k + l > 0; k = k_, l = l_) {
k_ = k, l_ = l;
if (k_ > 0)
k_--;
else
l_--;
if (k_ + l_ > 0) {
if (l_-- == 0)
return 0;
k_ -= n - 3;
if (k_ < 0)
l_ += k_, k_ = 0;
if (l_ < 0)
l_ = 0;
}
if (upper >= 0) {
if (k_ + l_ > 0)
Q(upper -= (k - k_) * (d_ + 1) + (l - l_) * d_, k - k_, l - l_, n, d_);
else if (k - k_ + l - l_ == 2 || k - k_ <= 1)
Q(upper -= (k - k_) * (d_ + 1) + (l - l_ - 1) * d_, k - k_, l - l_ - 1, n, d_);
else
Q(upper -= (k - k_ - 1) * (d_ + 1) + (l - l_) * d_, k - k_ - 1, l - l_, n, d_);
}
}
if (upper >= 0) {
for (h = n; h > 0; h--)
ii[h] = ii[h - 1];
ii[0] = N - 1 - n;
}
return 1;
}
int solve(int a, int d_) {
static int kk[N], ll[N];
int i, k, l, d, d1;
aa[N - 1] = 0, aa[N - 2] = aa[N - 1] + d_ + 1, aa[N - 3] = aa[N - 2] + d_ + d_ + 1;
for (i = N - 4; i >= 0; i--) {
kk[i] = 0, ll[i] = 0;
for (k = 1; k <= 100; k++)
for (l = 0; l <= 100; l++)
if (simulate(k, l, N - 1 - i, d_, -1) && kk[i] * (d_ + 1) + ll[i] * d_ < k * (d_ + 1) + l * d_)
kk[i] = k, ll[i] = l;
aa[i] = aa[i + 1] + kk[i] * (d_ + 1) + ll[i] * d_;
}
if (aa[0] < a)
return 0;
for (i = 1; i < N; i++)
aa[i] = aa[0] - aa[i];
aa[0] = 0;
limit = d_;
a_ = a, active = 0;
P(N - 1);
for (d = d_; d > 0; d--) {
for (d1 = 0; d1 < d; d1++)
S(d1 == 0 ? N - 2 : N - 1, N - 1);
P(N - 1);
}
for (d1 = 0; d1 < d_; d1++)
S(d1 == 0 ? N - 3 : N - 1, N - 1);
P(N - 2);
ii[0] = N - 3, ii[1] = N - 1, ii[2] = N - 2;
for (i = N - 4; i >= 0; i--)
simulate(kk[i], ll[i], N - 1 - i, d_, aa[i + 1]);
for (i = N - 2; i >= 0; i--) {
for (d = aa[ii[i + 1]] - aa[ii[i]] - 1; d > 0; d--) {
for (d1 = 0; d1 < d; d1++)
S(ii[d1 == 0 ? i : i + 1], ii[i + 1]);
P(ii[i + 1]);
}
P(ii[i]);
}
assert(a_ == -1);
return 1;
}
int main() {
int t, a, i, d_;
scanf("%d%d", &t, &a);
printf("FILE reverse %d\n", t);
if (a < N) {
for (i = 0; i < N; i++)
printf("%d ", i);
printf("\n");
for (i = a; i >= 0; i--)
printf("P %d\n", i);
return 0;
}
d_ = 1;
while (!solve(a, d_))
d_++;
return 0;
}
#include <assert.h>
#include <stdio.h>
#include <stdlib.h>
#define N 9
int min(int a, int b) { return a < b ? a : b; }
int ii[N], jj[N], aa[N], bb[N];
void display() {
int i;
for (i = 0; i < N; i++)
printf("%d ", aa[i]);
printf("\n");
}
int a_, active, limit, run;
void P(int i) {
run = 0;
if (a_ >= aa[i]) {
assert(a_-- == aa[i]);
if (!active)
active = 1, display();
printf("P %d\n", i + 1);
}
}
void S(int i, int j) {
if (active)
printf("S %d %d\n", i + 1, j + 1);
aa[j] = aa[i] + 1;
assert(i < N && j < N && ++run <= limit);
}
void Q(int lower, int k, int l, int n, int d_) {
int m, h, h_, d, d1, partial;
assert(k + l < n);
m = k + l;
if (k > 0)
k--;
else
l--;
for (h = 0; h < m; h++) {
bb[h] = lower;
if (h + 1 < m) {
if (k > 0)
lower += d_ + 1, k--;
else
lower += d_, l--;
}
}
partial = 0;
for (h = 0, h_ = 0; h < m; h++) {
for (d = aa[ii[n - 1 - h]] - aa[ii[n - 2 - h]] - 1; d > 0; d--) {
for (d1 = 0; d1 < d; d1++)
S(ii[d1 == 0 ? n - 2 - h : n - 1 - h], ii[n - 1 - h]);
for (d1 = d; d1 < d_; d1++)
if (h_ < h) {
if (!partial)
S(h_ == 0 ? N - 1 - n : ii[n - h_], ii[n - 1 - h_]), partial = 1;
else
S(ii[n - 1 - h_], ii[n - 1 - h_]);
if (aa[ii[n - 1 - h_]] == bb[h_])
h_++, partial = 0;
}
P(ii[n - 1 - h]);
}
for (d1 = 0; d1 < d_; d1++)
if (h_ <= h) {
if (!partial)
S(h_ == 0 ? N - 1 - n : ii[n - h_], ii[n - 1 - h_]), partial = 1;
else
S(ii[n - 1 - h_], ii[n - 1 - h_]);
if (aa[ii[n - 1 - h_]] == bb[h_])
h_++, partial = 0;
}
P(ii[n - 2 - h]);
}
for (h = 0; h < m; h++)
jj[h] = ii[n - 1 - h];
for (h = m; h < n; h++)
jj[h] = ii[h - m];
for (h = 0; h < n; h++)
ii[h] = jj[h];
}
int simulate(int k, int l, int n, int d_, int upper) {
int k_, l_, h;
if ((n - 2) * d_ * (d_ + 1) / 2 + d_ < (k - 1) * (d_ + 1) + l * d_)
return 0;
for ( ; k + l > 0; k = k_, l = l_) {
k_ = k, l_ = l;
if (k_ > 0)
k_--;
else
l_--;
if (k_ + l_ > 0) {
if (l_-- == 0)
return 0;
k_ -= n - 3;
if (k_ < 0)
l_ += k_, k_ = 0;
if (l_ < 0)
l_ = 0;
}
if (upper >= 0) {
if (k_ + l_ > 0)
Q(upper -= (k - k_) * (d_ + 1) + (l - l_) * d_, k - k_, l - l_, n, d_);
else if (k - k_ + l - l_ == 2 || k - k_ <= 1)
Q(upper -= (k - k_) * (d_ + 1) + (l - l_ - 1) * d_, k - k_, l - l_ - 1, n, d_);
else
Q(upper -= (k - k_ - 1) * (d_ + 1) + (l - l_) * d_, k - k_ - 1, l - l_, n, d_);
}
}
if (upper >= 0) {
for (h = n; h > 0; h--)
ii[h] = ii[h - 1];
ii[0] = N - 1 - n;
}
return 1;
}
int solve(int a, int d_) {
static int kk[N], ll[N];
int i, k, l, d, d1;
aa[N - 1] = 0, aa[N - 2] = aa[N - 1] + d_ + 1, aa[N - 3] = aa[N - 2] + d_ + d_ + 1;
for (i = N - 4; i >= 0; i--) {
kk[i] = 0, ll[i] = 0;
for (k = 1; k <= 100; k++)
for (l = 0; l <= 100; l++)
if (simulate(k, l, N - 1 - i, d_, -1) && kk[i] * (d_ + 1) + ll[i] * d_ < k * (d_ + 1) + l * d_)
kk[i] = k, ll[i] = l;
aa[i] = aa[i + 1] + kk[i] * (d_ + 1) + ll[i] * d_;
}
if (aa[0] < a)
return 0;
for (i = 1; i < N; i++)
aa[i] = aa[0] - aa[i];
aa[0] = 0;
limit = d_;
a_ = a, active = 0;
P(N - 1);
for (d = d_; d > 0; d--) {
for (d1 = 0; d1 < d; d1++)
S(d1 == 0 ? N - 2 : N - 1, N - 1);
P(N - 1);
}
for (d1 = 0; d1 < d_; d1++)
S(d1 == 0 ? N - 3 : N - 1, N - 1);
P(N - 2);
ii[0] = N - 3, ii[1] = N - 1, ii[2] = N - 2;
for (i = N - 4; i >= 0; i--)
simulate(kk[i], ll[i], N - 1 - i, d_, aa[i + 1]);
for (i = N - 2; i >= 0; i--) {
for (d = aa[ii[i + 1]] - aa[ii[i]] - 1; d > 0; d--) {
for (d1 = 0; d1 < d; d1++)
S(ii[d1 == 0 ? i : i + 1], ii[i + 1]);
P(ii[i + 1]);
}
P(ii[i]);
}
assert(a_ == -1);
return 1;
}
int main() {
int t, a, i, d_;
scanf("%d%d", &t, &a);
printf("FILE reverse %d\n", t);
if (a < N) {
for (i = 0; i < N; i++)
printf("%d ", i);
printf("\n");
for (i = a; i >= 0; i--)
printf("P %d\n", i);
return 0;
}
d_ = 1;
while (!solve(a, d_))
d_++;
return 0;
}
#include <assert.h>
#include <stdio.h>
#include <stdlib.h>
#define N 9
int min(int a, int b) { return a < b ? a : b; }
int ii[N], jj[N], aa[N], bb[N];
void display() {
int i;
for (i = 0; i < N; i++)
printf("%d ", aa[i]);
printf("\n");
}
int a_, active, limit, run;
void P(int i) {
run = 0;
if (a_ >= aa[i]) {
assert(a_-- == aa[i]);
if (!active)
active = 1, display();
printf("P %d\n", i + 1);
}
}
void S(int i, int j) {
if (active)
printf("S %d %d\n", i + 1, j + 1);
aa[j] = aa[i] + 1;
assert(i < N && j < N && ++run <= limit);
}
void Q(int lower, int k, int l, int n, int d_) {
int m, h, h_, d, d1, partial;
assert(k + l < n);
m = k + l;
if (k > 0)
k--;
else
l--;
for (h = 0; h < m; h++) {
bb[h] = lower;
if (h + 1 < m) {
if (k > 0)
lower += d_ + 1, k--;
else
lower += d_, l--;
}
}
partial = 0;
for (h = 0, h_ = 0; h < m; h++) {
for (d = aa[ii[n - 1 - h]] - aa[ii[n - 2 - h]] - 1; d > 0; d--) {
for (d1 = 0; d1 < d; d1++)
S(ii[d1 == 0 ? n - 2 - h : n - 1 - h], ii[n - 1 - h]);
for (d1 = d; d1 < d_; d1++)
if (h_ < h) {
if (!partial)
S(h_ == 0 ? N - 1 - n : ii[n - h_], ii[n - 1 - h_]), partial = 1;
else
S(ii[n - 1 - h_], ii[n - 1 - h_]);
if (aa[ii[n - 1 - h_]] == bb[h_])
h_++, partial = 0;
}
P(ii[n - 1 - h]);
}
for (d1 = 0; d1 < d_; d1++)
if (h_ <= h) {
if (!partial)
S(h_ == 0 ? N - 1 - n : ii[n - h_], ii[n - 1 - h_]), partial = 1;
else
S(ii[n - 1 - h_], ii[n - 1 - h_]);
if (aa[ii[n - 1 - h_]] == bb[h_])
h_++, partial = 0;
}
P(ii[n - 2 - h]);
}
for (h = 0; h < m; h++)
jj[h] = ii[n - 1 - h];
for (h = m; h < n; h++)
jj[h] = ii[h - m];
for (h = 0; h < n; h++)
ii[h] = jj[h];
}
int simulate(int k, int l, int n, int d_, int upper) {
int k_, l_, h;
if ((n - 2) * d_ * (d_ + 1) / 2 + d_ < (k - 1) * (d_ + 1) + l * d_)
return 0;
for ( ; k + l > 0; k = k_, l = l_) {
k_ = k, l_ = l;
if (k_ > 0)
k_--;
else
l_--;
if (k_ + l_ > 0) {
if (l_-- == 0)
return 0;
k_ -= n - 3;
if (k_ < 0)
l_ += k_, k_ = 0;
if (l_ < 0)
l_ = 0;
}
if (upper >= 0) {
if (k_ + l_ > 0)
Q(upper -= (k - k_) * (d_ + 1) + (l - l_) * d_, k - k_, l - l_, n, d_);
else if (k - k_ + l - l_ == 2 || k - k_ <= 1)
Q(upper -= (k - k_) * (d_ + 1) + (l - l_ - 1) * d_, k - k_, l - l_ - 1, n, d_);
else
Q(upper -= (k - k_ - 1) * (d_ + 1) + (l - l_) * d_, k - k_ - 1, l - l_, n, d_);
}
}
if (upper >= 0) {
for (h = n; h > 0; h--)
ii[h] = ii[h - 1];
ii[0] = N - 1 - n;
}
return 1;
}
int solve(int a, int d_) {
static int kk[N], ll[N];
int i, k, l, d, d1;
aa[N - 1] = 0, aa[N - 2] = aa[N - 1] + d_ + 1, aa[N - 3] = aa[N - 2] + d_ + d_ + 1;
for (i = N - 4; i >= 0; i--) {
kk[i] = 0, ll[i] = 0;
for (k = 1; k <= 100; k++)
for (l = 0; l <= 100; l++)
if (simulate(k, l, N - 1 - i, d_, -1) && kk[i] * (d_ + 1) + ll[i] * d_ < k * (d_ + 1) + l * d_)
kk[i] = k, ll[i] = l;
aa[i] = aa[i + 1] + kk[i] * (d_ + 1) + ll[i] * d_;
}
if (aa[0] < a)
return 0;
for (i = 1; i < N; i++)
aa[i] = aa[0] - aa[i];
aa[0] = 0;
limit = d_;
a_ = a, active = 0;
P(N - 1);
for (d = d_; d > 0; d--) {
for (d1 = 0; d1 < d; d1++)
S(d1 == 0 ? N - 2 : N - 1, N - 1);
P(N - 1);
}
for (d1 = 0; d1 < d_; d1++)
S(d1 == 0 ? N - 3 : N - 1, N - 1);
P(N - 2);
ii[0] = N - 3, ii[1] = N - 1, ii[2] = N - 2;
for (i = N - 4; i >= 0; i--)
simulate(kk[i], ll[i], N - 1 - i, d_, aa[i + 1]);
for (i = N - 2; i >= 0; i--) {
for (d = aa[ii[i + 1]] - aa[ii[i]] - 1; d > 0; d--) {
for (d1 = 0; d1 < d; d1++)
S(ii[d1 == 0 ? i : i + 1], ii[i + 1]);
P(ii[i + 1]);
}
P(ii[i]);
}
assert(a_ == -1);
return 1;
}
int main() {
int t, a, i, d_;
scanf("%d%d", &t, &a);
printf("FILE reverse %d\n", t);
if (a < N) {
for (i = 0; i < N; i++)
printf("%d ", i);
printf("\n");
for (i = a; i >= 0; i--)
printf("P %d\n", i);
return 0;
}
d_ = 1;
while (!solve(a, d_))
d_++;
return 0;
}
#include <assert.h>
#include <stdio.h>
#include <stdlib.h>
#define N 9
int min(int a, int b) { return a < b ? a : b; }
int ii[N], jj[N], aa[N], bb[N];
void display() {
int i;
for (i = 0; i < N; i++)
printf("%d ", aa[i]);
printf("\n");
}
int a_, active, limit, run;
void P(int i) {
run = 0;
if (a_ >= aa[i]) {
assert(a_-- == aa[i]);
if (!active)
active = 1, display();
printf("P %d\n", i + 1);
}
}
void S(int i, int j) {
if (active)
printf("S %d %d\n", i + 1, j + 1);
aa[j] = aa[i] + 1;
assert(i < N && j < N && ++run <= limit);
}
void Q(int lower, int k, int l, int n, int d_) {
int m, h, h_, d, d1, partial;
assert(k + l < n);
m = k + l;
if (k > 0)
k--;
else
l--;
for (h = 0; h < m; h++) {
bb[h] = lower;
if (h + 1 < m) {
if (k > 0)
lower += d_ + 1, k--;
else
lower += d_, l--;
}
}
partial = 0;
for (h = 0, h_ = 0; h < m; h++) {
for (d = aa[ii[n - 1 - h]] - aa[ii[n - 2 - h]] - 1; d > 0; d--) {
for (d1 = 0; d1 < d; d1++)
S(ii[d1 == 0 ? n - 2 - h : n - 1 - h], ii[n - 1 - h]);
for (d1 = d; d1 < d_; d1++)
if (h_ < h) {
if (!partial)
S(h_ == 0 ? N - 1 - n : ii[n - h_], ii[n - 1 - h_]), partial = 1;
else
S(ii[n - 1 - h_], ii[n - 1 - h_]);
if (aa[ii[n - 1 - h_]] == bb[h_])
h_++, partial = 0;
}
P(ii[n - 1 - h]);
}
for (d1 = 0; d1 < d_; d1++)
if (h_ <= h) {
if (!partial)
S(h_ == 0 ? N - 1 - n : ii[n - h_], ii[n - 1 - h_]), partial = 1;
else
S(ii[n - 1 - h_], ii[n - 1 - h_]);
if (aa[ii[n - 1 - h_]] == bb[h_])
h_++, partial = 0;
}
P(ii[n - 2 - h]);
}
for (h = 0; h < m; h++)
jj[h] = ii[n - 1 - h];
for (h = m; h < n; h++)
jj[h] = ii[h - m];
for (h = 0; h < n; h++)
ii[h] = jj[h];
}
int simulate(int k, int l, int n, int d_, int upper) {
int k_, l_, h;
if ((n - 2) * d_ * (d_ + 1) / 2 + d_ < (k - 1) * (d_ + 1) + l * d_)
return 0;
for ( ; k + l > 0; k = k_, l = l_) {
k_ = k, l_ = l;
if (k_ > 0)
k_--;
else
l_--;
if (k_ + l_ > 0) {
if (l_-- == 0)
return 0;
k_ -= n - 3;
if (k_ < 0)
l_ += k_, k_ = 0;
if (l_ < 0)
l_ = 0;
}
if (upper >= 0) {
if (k_ + l_ > 0)
Q(upper -= (k - k_) * (d_ + 1) + (l - l_) * d_, k - k_, l - l_, n, d_);
else if (k - k_ + l - l_ == 2 || k - k_ <= 1)
Q(upper -= (k - k_) * (d_ + 1) + (l - l_ - 1) * d_, k - k_, l - l_ - 1, n, d_);
else
Q(upper -= (k - k_ - 1) * (d_ + 1) + (l - l_) * d_, k - k_ - 1, l - l_, n, d_);
}
}
if (upper >= 0) {
for (h = n; h > 0; h--)
ii[h] = ii[h - 1];
ii[0] = N - 1 - n;
}
return 1;
}
int solve(int a, int d_) {
static int kk[N], ll[N];
int i, k, l, d, d1;
aa[N - 1] = 0, aa[N - 2] = aa[N - 1] + d_ + 1, aa[N - 3] = aa[N - 2] + d_ + d_ + 1;
for (i = N - 4; i >= 0; i--) {
kk[i] = 0, ll[i] = 0;
for (k = 1; k <= 100; k++)
for (l = 0; l <= 100; l++)
if (simulate(k, l, N - 1 - i, d_, -1) && kk[i] * (d_ + 1) + ll[i] * d_ < k * (d_ + 1) + l * d_)
kk[i] = k, ll[i] = l;
aa[i] = aa[i + 1] + kk[i] * (d_ + 1) + ll[i] * d_;
}
if (aa[0] < a)
return 0;
for (i = 1; i < N; i++)
aa[i] = aa[0] - aa[i];
aa[0] = 0;
limit = d_;
a_ = a, active = 0;
P(N - 1);
for (d = d_; d > 0; d--) {
for (d1 = 0; d1 < d; d1++)
S(d1 == 0 ? N - 2 : N - 1, N - 1);
P(N - 1);
}
for (d1 = 0; d1 < d_; d1++)
S(d1 == 0 ? N - 3 : N - 1, N - 1);
P(N - 2);
ii[0] = N - 3, ii[1] = N - 1, ii[2] = N - 2;
for (i = N - 4; i >= 0; i--)
simulate(kk[i], ll[i], N - 1 - i, d_, aa[i + 1]);
for (i = N - 2; i >= 0; i--) {
for (d = aa[ii[i + 1]] - aa[ii[i]] - 1; d > 0; d--) {
for (d1 = 0; d1 < d; d1++)
S(ii[d1 == 0 ? i : i + 1], ii[i + 1]);
P(ii[i + 1]);
}
P(ii[i]);
}
assert(a_ == -1);
return 1;
}
int main() {
int t, a, i, d_;
scanf("%d%d", &t, &a);
printf("FILE reverse %d\n", t);
if (a < N) {
for (i = 0; i < N; i++)
printf("%d ", i);
printf("\n");
for (i = a; i >= 0; i--)
printf("P %d\n", i);
return 0;
}
d_ = 1;
while (!solve(a, d_))
d_++;
return 0;
}
#include <assert.h>
#include <stdio.h>
#include <stdlib.h>
#define N 9
int min(int a, int b) { return a < b ? a : b; }
int ii[N], jj[N], aa[N], bb[N];
void display() {
int i;
for (i = 0; i < N; i++)
printf("%d ", aa[i]);
printf("\n");
}
int a_, active, limit, run;
void P(int i) {
run = 0;
if (a_ >= aa[i]) {
assert(a_-- == aa[i]);
if (!active)
active = 1, display();
printf("P %d\n", i + 1);
}
}
void S(int i, int j) {
if (active)
printf("S %d %d\n", i + 1, j + 1);
aa[j] = aa[i] + 1;
assert(i < N && j < N && ++run <= limit);
}
void Q(int lower, int k, int l, int n, int d_) {
int m, h, h_, d, d1, partial;
assert(k + l < n);
m = k + l;
if (k > 0)
k--;
else
l--;
for (h = 0; h < m; h++) {
bb[h] = lower;
if (h + 1 < m) {
if (k > 0)
lower += d_ + 1, k--;
else
lower += d_, l--;
}
}
partial = 0;
for (h = 0, h_ = 0; h < m; h++) {
for (d = aa[ii[n - 1 - h]] - aa[ii[n - 2 - h]] - 1; d > 0; d--) {
for (d1 = 0; d1 < d; d1++)
S(ii[d1 == 0 ? n - 2 - h : n - 1 - h], ii[n - 1 - h]);
for (d1 = d; d1 < d_; d1++)
if (h_ < h) {
if (!partial)
S(h_ == 0 ? N - 1 - n : ii[n - h_], ii[n - 1 - h_]), partial = 1;
else
S(ii[n - 1 - h_], ii[n - 1 - h_]);
if (aa[ii[n - 1 - h_]] == bb[h_])
h_++, partial = 0;
}
P(ii[n - 1 - h]);
}
for (d1 = 0; d1 < d_; d1++)
if (h_ <= h) {
if (!partial)
S(h_ == 0 ? N - 1 - n : ii[n - h_], ii[n - 1 - h_]), partial = 1;
else
S(ii[n - 1 - h_], ii[n - 1 - h_]);
if (aa[ii[n - 1 - h_]] == bb[h_])
h_++, partial = 0;
}
P(ii[n - 2 - h]);
}
for (h = 0; h < m; h++)
jj[h] = ii[n - 1 - h];
for (h = m; h < n; h++)
jj[h] = ii[h - m];
for (h = 0; h < n; h++)
ii[h] = jj[h];
}
int simulate(int k, int l, int n, int d_, int upper) {
int k_, l_, h;
if ((n - 2) * d_ * (d_ + 1) / 2 + d_ < (k - 1) * (d_ + 1) + l * d_)
return 0;
for ( ; k + l > 0; k = k_, l = l_) {
k_ = k, l_ = l;
if (k_ > 0)
k_--;
else
l_--;
if (k_ + l_ > 0) {
if (l_-- == 0)
return 0;
k_ -= n - 3;
if (k_ < 0)
l_ += k_, k_ = 0;
if (l_ < 0)
l_ = 0;
}
if (upper >= 0) {
if (k_ + l_ > 0)
Q(upper -= (k - k_) * (d_ + 1) + (l - l_) * d_, k - k_, l - l_, n, d_);
else if (k - k_ + l - l_ == 2 || k - k_ <= 1)
Q(upper -= (k - k_) * (d_ + 1) + (l - l_ - 1) * d_, k - k_, l - l_ - 1, n, d_);
else
Q(upper -= (k - k_ - 1) * (d_ + 1) + (l - l_) * d_, k - k_ - 1, l - l_, n, d_);
}
}
if (upper >= 0) {
for (h = n; h > 0; h--)
ii[h] = ii[h - 1];
ii[0] = N - 1 - n;
}
return 1;
}
int solve(int a, int d_) {
static int kk[N], ll[N];
int i, k, l, d, d1;
aa[N - 1] = 0, aa[N - 2] = aa[N - 1] + d_ + 1, aa[N - 3] = aa[N - 2] + d_ + d_ + 1;
for (i = N - 4; i >= 0; i--) {
kk[i] = 0, ll[i] = 0;
for (k = 1; k <= 100; k++)
for (l = 0; l <= 100; l++)
if (simulate(k, l, N - 1 - i, d_, -1) && kk[i] * (d_ + 1) + ll[i] * d_ < k * (d_ + 1) + l * d_)
kk[i] = k, ll[i] = l;
aa[i] = aa[i + 1] + kk[i] * (d_ + 1) + ll[i] * d_;
}
if (aa[0] < a)
return 0;
for (i = 1; i < N; i++)
aa[i] = aa[0] - aa[i];
aa[0] = 0;
limit = d_;
a_ = a, active = 0;
P(N - 1);
for (d = d_; d > 0; d--) {
for (d1 = 0; d1 < d; d1++)
S(d1 == 0 ? N - 2 : N - 1, N - 1);
P(N - 1);
}
for (d1 = 0; d1 < d_; d1++)
S(d1 == 0 ? N - 3 : N - 1, N - 1);
P(N - 2);
ii[0] = N - 3, ii[1] = N - 1, ii[2] = N - 2;
for (i = N - 4; i >= 0; i--)
simulate(kk[i], ll[i], N - 1 - i, d_, aa[i + 1]);
for (i = N - 2; i >= 0; i--) {
for (d = aa[ii[i + 1]] - aa[ii[i]] - 1; d > 0; d--) {
for (d1 = 0; d1 < d; d1++)
S(ii[d1 == 0 ? i : i + 1], ii[i + 1]);
P(ii[i + 1]);
}
P(ii[i]);
}
assert(a_ == -1);
return 1;
}
int main() {
int t, a, i, d_;
scanf("%d%d", &t, &a);
printf("FILE reverse %d\n", t);
if (a < N) {
for (i = 0; i < N; i++)
printf("%d ", i);
printf("\n");
for (i = a; i >= 0; i--)
printf("P %d\n", i);
return 0;
}
d_ = 1;
while (!solve(a, d_))
d_++;
return 0;
}
#include <assert.h>
#include <stdio.h>
#include <stdlib.h>
#define N 9
int min(int a, int b) { return a < b ? a : b; }
int ii[N], jj[N], aa[N], bb[N];
void display() {
int i;
for (i = 0; i < N; i++)
printf("%d ", aa[i]);
printf("\n");
}
int a_, active, limit, run;
void P(int i) {
run = 0;
if (a_ >= aa[i]) {
assert(a_-- == aa[i]);
if (!active)
active = 1, display();
printf("P %d\n", i + 1);
}
}
void S(int i, int j) {
if (active)
printf("S %d %d\n", i + 1, j + 1);
aa[j] = aa[i] + 1;
assert(i < N && j < N && ++run <= limit);
}
void Q(int lower, int k, int l, int n, int d_) {
int m, h, h_, d, d1, partial;
assert(k + l < n);
m = k + l;
if (k > 0)
k--;
else
l--;
for (h = 0; h < m; h++) {
bb[h] = lower;
if (h + 1 < m) {
if (k > 0)
lower += d_ + 1, k--;
else
lower += d_, l--;
}
}
partial = 0;
for (h = 0, h_ = 0; h < m; h++) {
for (d = aa[ii[n - 1 - h]] - aa[ii[n - 2 - h]] - 1; d > 0; d--) {
for (d1 = 0; d1 < d; d1++)
S(ii[d1 == 0 ? n - 2 - h : n - 1 - h], ii[n - 1 - h]);
for (d1 = d; d1 < d_; d1++)
if (h_ < h) {
if (!partial)
S(h_ == 0 ? N - 1 - n : ii[n - h_], ii[n - 1 - h_]), partial = 1;
else
S(ii[n - 1 - h_], ii[n - 1 - h_]);
if (aa[ii[n - 1 - h_]] == bb[h_])
h_++, partial = 0;
}
P(ii[n - 1 - h]);
}
for (d1 = 0; d1 < d_; d1++)
if (h_ <= h) {
if (!partial)
S(h_ == 0 ? N - 1 - n : ii[n - h_], ii[n - 1 - h_]), partial = 1;
else
S(ii[n - 1 - h_], ii[n - 1 - h_]);
if (aa[ii[n - 1 - h_]] == bb[h_])
h_++, partial = 0;
}
P(ii[n - 2 - h]);
}
for (h = 0; h < m; h++)
jj[h] = ii[n - 1 - h];
for (h = m; h < n; h++)
jj[h] = ii[h - m];
for (h = 0; h < n; h++)
ii[h] = jj[h];
}
int simulate(int k, int l, int n, int d_, int upper) {
int k_, l_, h;
if ((n - 2) * d_ * (d_ + 1) / 2 + d_ < (k - 1) * (d_ + 1) + l * d_)
return 0;
for ( ; k + l > 0; k = k_, l = l_) {
k_ = k, l_ = l;
if (k_ > 0)
k_--;
else
l_--;
if (k_ + l_ > 0) {
if (l_-- == 0)
return 0;
k_ -= n - 3;
if (k_ < 0)
l_ += k_, k_ = 0;
if (l_ < 0)
l_ = 0;
}
if (upper >= 0) {
if (k_ + l_ > 0)
Q(upper -= (k - k_) * (d_ + 1) + (l - l_) * d_, k - k_, l - l_, n, d_);
else if (k - k_ + l - l_ == 2 || k - k_ <= 1)
Q(upper -= (k - k_) * (d_ + 1) + (l - l_ - 1) * d_, k - k_, l - l_ - 1, n, d_);
else
Q(upper -= (k - k_ - 1) * (d_ + 1) + (l - l_) * d_, k - k_ - 1, l - l_, n, d_);
}
}
if (upper >= 0) {
for (h = n; h > 0; h--)
ii[h] = ii[h - 1];
ii[0] = N - 1 - n;
}
return 1;
}
int solve(int a, int d_) {
static int kk[N], ll[N];
int i, k, l, d, d1;
aa[N - 1] = 0, aa[N - 2] = aa[N - 1] + d_ + 1, aa[N - 3] = aa[N - 2] + d_ + d_ + 1;
for (i = N - 4; i >= 0; i--) {
kk[i] = 0, ll[i] = 0;
for (k = 1; k <= 100; k++)
for (l = 0; l <= 100; l++)
if (simulate(k, l, N - 1 - i, d_, -1) && kk[i] * (d_ + 1) + ll[i] * d_ < k * (d_ + 1) + l * d_)
kk[i] = k, ll[i] = l;
aa[i] = aa[i + 1] + kk[i] * (d_ + 1) + ll[i] * d_;
}
if (aa[0] < a)
return 0;
for (i = 1; i < N; i++)
aa[i] = aa[0] - aa[i];
aa[0] = 0;
limit = d_;
a_ = a, active = 0;
P(N - 1);
for (d = d_; d > 0; d--) {
for (d1 = 0; d1 < d; d1++)
S(d1 == 0 ? N - 2 : N - 1, N - 1);
P(N - 1);
}
for (d1 = 0; d1 < d_; d1++)
S(d1 == 0 ? N - 3 : N - 1, N - 1);
P(N - 2);
ii[0] = N - 3, ii[1] = N - 1, ii[2] = N - 2;
for (i = N - 4; i >= 0; i--)
simulate(kk[i], ll[i], N - 1 - i, d_, aa[i + 1]);
for (i = N - 2; i >= 0; i--) {
for (d = aa[ii[i + 1]] - aa[ii[i]] - 1; d > 0; d--) {
for (d1 = 0; d1 < d; d1++)
S(ii[d1 == 0 ? i : i + 1], ii[i + 1]);
P(ii[i + 1]);
}
P(ii[i]);
}
assert(a_ == -1);
return 1;
}
int main() {
int t, a, i, d_;
scanf("%d%d", &t, &a);
printf("FILE reverse %d\n", t);
if (a < N) {
for (i = 0; i < N; i++)
printf("%d ", i);
printf("\n");
for (i = a; i >= 0; i--)
printf("P %d\n", i);
return 0;
}
d_ = 1;
while (!solve(a, d_))
d_++;
return 0;
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
0 ms |
0 KB |
Wrong Answer: Printed value does not match expected value |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
0 ms |
0 KB |
Presentation Error: First Line is Malformed |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
0 ms |
0 KB |
Presentation Error: First Line is Malformed |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
0 ms |
0 KB |
Presentation Error: First Line is Malformed |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
0 ms |
0 KB |
Presentation Error: First Line is Malformed |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
0 ms |
0 KB |
Presentation Error: First Line is Malformed |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
0 ms |
0 KB |
Presentation Error: First Line is Malformed |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
0 ms |
0 KB |
Presentation Error: First Line is Malformed |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
0 ms |
0 KB |
Presentation Error: First Line is Malformed |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
0 ms |
0 KB |
Presentation Error: First Line is Malformed |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
0 ms |
0 KB |
Presentation Error: First Line is Malformed |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
0 ms |
0 KB |
Presentation Error: First Line is Malformed |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
0 ms |
0 KB |
Presentation Error: First Line is Malformed |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
0 ms |
0 KB |
Presentation Error: First Line is Malformed |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
0 ms |
0 KB |
Presentation Error: First Line is Malformed |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
0 ms |
0 KB |
Presentation Error: First Line is Malformed |
