杂题——环形数组(hard)

环形数组(hard)

原题

题目描述

Cai_Guang 定义环形数组为从矩阵左上角开始顺时针围绕当前矩阵最外层蛇形填数的数组，如图为一个 4∗5 的环形数组。

img

可以证明对于任意大小的矩阵，这样的数组总存在。

你需要解决的问题是，给定一个矩阵的大小参数 n,m，和一个整数 x ，请你告诉 Cai_Guang 这个整数所在的位置。矩形从上往下依次为第 1 行 … 第 n 行，从左往右依次为第 1 列 第 m 列。

输入描述:

1
2
第一行一个整数 t，表示数据组数。(1≤t≤105)
对于每组数据，一行输入三个整数 n,m ，代表这个矩阵的行数、列数和询问的数字。(1≤n,m≤109,1≤x≤n×m)

输出描述:

1
对于每组数据，输出一行两个整数 i,j，表示 x 所在格子的行号和列号。

示例1

输入

复制

1
2
3
2
4 5 10
1 10 9

输出

复制

1
2
4 3
1 9

思路

​ 持续更新中……

代码

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
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
/*
Oh
you say someday when we're older
we'LL be shining like we're gold
won't we?   ------ someday / OneRepublic
*/

#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
#include <map>
#include <unordered_map>
#include <string>
#include <cmath>
#include <set>
#include <stack>
#include <vector>
#include <deque>
#include <bitset>
#include <cstdio>
#include <iomanip>

// #define int long long
#define ull unsigned long long
#define ed '\n'
#define fi first
#define se second
#define fore(i, l, r) for(int i = (int)(l); i <=(int)r; i++)
#define debug(x) cout << "#x = " << x << ed;
#define PI acos(-1)
#define E exp(1)
#define IOS ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define me0(st) memset(st, 0, sizeof st)
#define me3f(st) memset(st, 0x3f, sizeof st)
#define pdf(x) printf("%lf", double(x))
#define pif(x) printf("%d ",  int(x))
#define scf(x) printf("%d",  int(x))
#define re return 0
// #define max(a, b) ((a) > (b) ? (a) : (b))
// #define min(a, b) ((a) < (b) ? (a) : (b))
#define out(x, k) cout << fixed << setprecision(k) << x << ed

using namespace std;

typedef pair<int, int> PII;
typedef long long LL;
typedef double db;

LL n, m, x, q, g, s, st, len, width;

// 求fk层(从外到内的第fk层)
LL f(LL fk)
{
    return (2 * (n + m) - 4 * fk) * fk;
}
void solve()
{
    cin>>n>>m>>x;
    LL l = 1, r = min((n+1)/2,(m+1)/2);
    
    // 找到x所在层数
    while(l < r)
    {
        LL mid = l + r >> 1;
        if(f(mid) >= x) r = mid;
        else l = mid + 1;
    }
//     for(int i=1;i<=min((n+1)/2,(m+1)/2);i++) cout<<f(i)<<' ';
//     cout<<'\n';    
    
    // s为所在层的最后一个元素
    s = f(r);
    
    // q是层数
    q = r;
    
    // st是当前层的的元素个数
    st = s - (2*(n+m)+4-8*q) + 1;
    
    // 该层下还剩多少列
    len = m - (q-1)*2;
    
    // 该层下还有多少行
    width = n - (q-1)*2;
    /*
    8.  
    如果在上: r = q, c = q + x - st[i]
    如果在右: c = m - q + 1, r = q + x - (st[i]+len[i]-1);
    如果在下: r = n - q + 1, c = m - q + 1 + x - (st[i]+len[i]+width[i]-2)
    如果在左: c = q + x - (st[i]+2*len[i]+width[i]-3)
    */

    // 在上
    if(st <= x && x <= st + len - 1)
    {
        cout << q << ' ' << q + x - st << '\n';
    }
    // 在右
    else if(st+len-1<=x && x<=st+len+width-2)
    {
        cout<<q+x-(st+len-1)<<' '<<m-q+1<<ed;
    }
    
    // 在下
    else if(st+len+width-2<=x && x<=st+2*len+width-3)
    {
        cout<<n-q+1<<' '<<m-q+1-(x-(st+len+width-2))<<ed;
    }
    
    //在左
    else if(st+2*len+width-3<=x && x<=st+2*len+2*width-5)
    {
        cout<<n-q+1-(x-(st+2*len+width-3))<<' '<<q<<ed;
    }
}


int main()  
{
    IOS;
    int T = 1;
    cin >> T;
    while (T--) solve();
    return 0;
}