Skip to content

11596: 【原1596】黄昏之时

题目

题目描述

author: Spy 原OJ链接:https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1596

Description

「誰そ彼とわれをな問ひそ、九月の露に濡れつつ、君待つわれそ」——『万葉集』

黄昏之时,昼夜交错,时空亦是。

在两个不同的\(n*n\)时空里,泷和三叶分别位于\((n,1)\)和\((1,n)\)两个顶点处,他们约定在黄昏之时,一起到达\((i,j)\)相会。

他们各自沿网格的行进路线如图所示,是顺时针旋转的螺旋线。

为了准时在黄昏之时到达目的地,他们需要知道路程长度来估计时间,请你帮他们计算路程的长度。

Input Format

一行三个整数,\(N,i,j\),分别代表网格的大小,相约的地点。

Output Format

一行输出泷和三叶各自需要行走的步数,空格分隔。

Sample Input 1

3 2 3

Sample Output 1

5 1

Sample Input 2

8 3 6

Sample Output 2

54 48

Limits

对于\(30\%\)的数据,\(N\in [1,3]\)。

对于\(50\%\)的数据,\(N\in [1,10]\)。

对于\(90\%\)的数据,\(N\in [1,1000]\)。

对于\(100\%\)的数据,\(N\in [1,1000000], i,j\in [1,N]\)。

BugenZhao's solution

//
// Created by BugenZhao on 2019/3/17.
//
// 模拟走路

#include <iostream>
#include <algorithm>
#include <queue>

using namespace std;

static const auto _____ = []() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    return nullptr;
}();

using ll=long long;

ll getAnswer(int N, int i, int j) {
    ll ans = 0;
    int a[] = {i, j, N - i + 1, N - j + 1};
    sort(begin(a), end(a));
    int level = a[0];
    for (int k = 1; k < level; ++k) {
        ans += (N - (2 * k - 1)) * 4;
    }
    if (a[0] == j) {
        ans += N - i + 1 - level;
    } else if (a[0] == i) {
        ans += (N - (2 * level - 1)) + j - level;
    } else if (a[0] == N - j + 1) {
        ans += (N - (2 * level - 1)) * 2 + i - level;
    } else if (a[0] == N - i + 1) {
        ans += (N - (2 * level - 1)) * 3 + N - j + 1 - level;
    }
    return ans;
}

int main() {
    int N, i, j;
    cin >> N >> i >> j;
    cout << getAnswer(N, i, j) << " " << getAnswer(N, N - i + 1, N - j + 1) << endl;
    return 0;
}

FineArtz's solution

/* 黄昏之时 */
#include <iostream>
using namespace std;

inline long long min(long long a, long long b, long long c, long long d){
    long long ret = a;
    if (ret > b) ret = b;
    if (ret > c) ret = c;
    if (ret > d) ret = d;
    return ret;
}

long long step(long long n, long long x, long long y){
    if (y == 1) return x - 1;
    if (x == n) return n + y - 2;
    if (y == n) return n * 3 - x - 2;
    if (x == 1) return n * 4 - y - 3;
    long long k = min(x - 1, y - 1, n - x, n - y);
    return 4 * k * (n - k) + step(n - 2 * k, x - k, y - k);
}

int main(){
    long long n, i, j;
    cin >> n >> i >> j;
    cout << step(n, n - i + 1, j) << ' ' << step(n, i, n - j + 1) << endl;
    return 0;
}

ligongzzz's solution

#include "iostream"
using namespace std;

long long mmin(long long a, long long b) {
    return a < b ? a : b;
}

long long cal_step(long long n, long long x, long long y) {
    //记录当前边数
    long long gap = mmin(mmin(x - 1, n - x), mmin(y - 1, n - y));
    long long num = n - 2 * gap;
    long long step = n * n - num * num;

    long long dx[] = { 0,1,0,-1 };
    long long dy[] = { 1,0,-1,0 };
    //记录步数
    for (long long status = 0, i = (n - num) / 2 + 1, j = i - 1; i != x || j != y; step++) {
        i += dx[status];
        j += dy[status];
        //判断是否越界
        if (i + dx[status] > n - gap || i + dx[status]<gap + 1 || j + dy[status]>n - gap || j + dy[status] < gap + 1) {
            status = status < 3 ? status + 1 : 0;
        }
    }
    return step - 1;
}

int main() {
    long long n, x, y;
    cin >> n >> x >> y;

    cout << cal_step(n, y, n - x + 1) << " " << cal_step(n, n - y + 1, x);

    return 0;
}

skyzh's solution

#include <iostream>
using namespace std;

int N, i, j;

long long run1() {
    int a1 = 1, a2 = N, b1 = 1, b2 = N;
    long long step = 0;
    while (true) {
        if (j != b1) {
            step += a2 - a1 + 1;
            ++b1;
        } else {
            step += a2 - i;
            break;
        }
        if (i != a1) {
            step += b2 - b1 + 1;
            ++a1;
        } else {
            step += j - b1;
            break;
        }
        if (j != b2) {
            step += a2 - a1 + 1;
            --b2;
        } else {
            step += i - a1;
            break;
        }
        if (i != a2) {
            step += b2 - b1 + 1;
            --a2;
        } else {
            step += b2 - j;
            break;
        }
    }
    return step;
}

long long run2() {
    int a1 = 1, a2 = N, b1 = 1, b2 = N;
    long long step = 0;
    while (true) {
        if (j != b2) {
            step += a2 - a1 + 1;
            --b2;
        } else {
            step += i - a1;
            break;
        }
        if (i != a2) {
            step += b2 - b1 + 1;
            --a2;
        } else {
            step += b2 - j;
            break;
        }
        if (j != b1) {
            step += a2 - a1 + 1;
            ++b1;
        } else {
            step += a2 - i;
            break;
        }
        if (i != a1) {
            step += b2 - b1 + 1;
            ++a1;
        } else {
            step += j - b1;
            break;
        }
    }
    return step;
}

int main() {
    cin >> N >> i >> j;
    cout << run1() << " " << run2() << endl;
    return 0;
}