头像

季科


访客:5122

离线:1小时前



季科
3天前

题目描述

Farmer John 正在考虑改变他给奶牛挤奶的时候分配牛奶桶的方式。

他认为这最终能使得他使用数量更少的桶,然而他不清楚具体是多少,请帮助他!

Farmer John 有 N 头奶牛,方便起见编号为 1…N。

第 i 头奶牛需要从时间 si 到时间 ti 之间挤奶,并且挤奶过程中需要用到 bi 个桶。

于是多头奶牛可能在同一时刻都在挤奶;如果这样,她们不能使用相同的桶。

也就是说,一个在第 i 头奶牛挤奶时用的桶不可以被任何在时间 si 到时间 ti 之间挤奶的其他奶牛使用。

当然,这个桶在这段时间之外可以被其他奶牛所使用。

为了简化他的工作,FJ 保证在任一时刻,至多只有一头奶牛开始或是结束挤奶(也就是说,所有的 si 和 ti 各不相同)。

FJ 有一个储藏室,里面有依次编号为 1、2、3、…… 的桶。

在他的挤奶策略中,当某一头奶牛(比如说,奶牛 i)开始挤奶(在时间 si),FJ 就跑到储藏室取出编号最小的 bi 个桶分配给第 i 头奶牛用来挤奶。

请求出 FJ 需要在储藏室中存放多少个桶才能使得他能够顺利地给所有奶牛挤奶。

输入格式
输入的第一行包含 N。

以下 N 行,每行描述了一头奶牛,包含三个空格分隔的数 si,ti,bi。

其中 si 和 ti 均为 1…1000 之间的整数,bi 为 1…10 之间的整数。

输出格式
输出一个整数,为 FJ 需要的桶的数量。

数据范围
1≤N≤100

样例

输入样例:
3
4 10 1
8 13 3
2 6 2
输出样例:
4
样例解释
在这个例子中,FJ 需要 4 个桶:他用桶 1 和桶 2 来给奶牛 3 挤奶(从时间 2 开始)。

他用桶 3 给奶牛 1 挤奶(从时间 4 开始)。

当奶牛 2 在时间 8 开始挤奶时,桶 1 和桶 2 可以再次利用,然而桶 3 不可以,所以他会使用桶 1、桶 2 和桶 4。

算法1

(暴力枚举) $O(nm)$

这个题其实就是求某个点的最多的桶子数目,我们可以枚举每个区间,然后将区间中的每个点加上需要的桶子数目,然后找到整个区间中的最大值就可以了。

C++ 代码

#include<bits/stdc++.h>
using namespace std;
const int N=1010;
int st[N];
int main()
{
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        int l,r,x;
        cin>>l>>r>>x;
        for(int j=l;j<=r;j++)
            st[j]+=x;
    }
    int ans=0;
    for(int i=1;i<=N;i++)
        ans=max(ans,st[i]);
    cout<<ans;
    return 0;
} 

算法2

(差分数组) $O(n+m)$

因为是区间中的每个点都改变,所以我们可以用差分数组来做。这样我们就将本来需要循环区间中的每个点优化成了只需要改变两个点,不过后面需要求一遍前缀和。

C++ 代码

#include<bits/stdc++.h>
using namespace std;
const int N=1010;
int st[N],sum[N];
int main()
{
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        int l,r,x;
        cin>>l>>r>>x;
        st[l]+=x;
        st[r+1]-=x;
    }
    for(int i=1;i<=N;i++)
        sum[i]=sum[i-1]+st[i];
    int ans=0;
    for(int i=1;i<=N;i++)
        ans=max(ans,sum[i]);
    cout<<ans;
    return 0;
} 



季科
3天前

题目描述

业,尤其是生产牛奶,是一个竞争激烈的行业。

Farmer John 发现如果他不在牛奶生产工艺上有所创新,他的乳制品生意可能就会受到重创!

幸运的是,Farmer John 想出了一个好主意。

他的三头获奖的乳牛,Bessie、Elsie 和 Mildred,各自产奶的口味有些许不同,他打算混合这三种牛奶调制出完美的口味。

为了混合这三种不同的牛奶,他拿来三个桶,其中分别装有三头奶牛所产的奶。

这些桶可能有不同的容积,也可能并没有完全装满。

然后他将桶 1 的牛奶倒入桶 2,然后将桶 2 中的牛奶倒入桶 3,然后将桶 3 中的牛奶倒入桶 1,然后再将桶 1 的牛奶倒入桶 2,如此周期性地操作,共计进行 100 次(所以第 100 次操作会是桶 1 倒入桶 2)。

当 Farmer John 将桶 a 中的牛奶倒入桶 b 时,他会倒出尽可能多的牛奶,直到桶 a 被倒空或是桶 b 被倒满。

请告诉 Farmer John 当他倒了 100 次之后每个桶里将会有多少牛奶。

输入格式
输入文件的第一行包含两个空格分隔的整数:第一个桶的容积 c1,以及第一个桶里的牛奶量 m1。

第二和第三行类似地包含第二和第三个桶的容积和牛奶量。

输出格式
输出三行,给出倒了 100 次之后每个桶里的牛奶量。

数据范围
1≤c1,m1≤109

样例

输入样例:
10 3
11 4
12 5
输出样例:
0
10
2
样例解释
在这个例子中,每倒一次之后每个桶里的牛奶量如下:

初始状态:   3  4  5
1. 桶1->2:  0  7  5
2. 桶2->3:  0  0  12
3. 桶3->1:  10 0  2
4. 桶1->2:  0  10 2
5. 桶2->3:  0  0  12
(之后最后三个状态循环出现……)

算法1

(暴力枚举)

这个题直接枚举就可以,在倒牛奶的时候,我们可以计算当前的两个桶的总奶量,尽量放在后一个,如果有剩余的就放在第一个。为了操作起来方便,我们可以用一个结构体来存储,然后三个桶放在数组里面。

C++ 代码

#include<bits/stdc++.h>
using namespace std;
struct Node
{
    int x,y;
};
Node node[3];
int main()
{
    for(int i=0;i<3;i++)
        cin>>node[i].x>>node[i].y;
    for(int i=0;i<100;i++)
    {
        int j=i%3,k=(i+1)%3;//j是第一个,k是第二个 
        int s=node[j].y+node[k].y;//s总奶量 
        if(s>node[k].x)
        {
            node[k].y=node[k].x;
            node[j].y=s-node[k].x;  
        }else
        {
            node[k].y=s;
            node[j].y=0;
        }
    }
    for(int i=0;i<3;i++)
        cout<<node[i].y<<endl;
    return 0;
} 



季科
4天前

题目描述

农夫约翰的农场上有 N 个山丘,每座山的高度都是整数。

在冬天,约翰经常在这些山上举办滑雪训练营。

不幸的是,从明年开始,国家将实行一个关于滑雪场的新税法。

如果滑雪场的最高峰与最低峰的高度差大于17,国家就要收税。

为了避免纳税,约翰决定对这些山峰的高度进行修整。

已知,增加或减少一座山峰 x 单位的高度,需要花费 x2 的金钱。

约翰只愿意改变整数单位的高度。

请问,约翰最少需要花费多少钱,才能够使得最高峰与最低峰的高度差不大于17。

输入格式
第一行包含整数 N。

接下来 N 行,每行包含一个整数,表示一座山的高度。

输出格式
输出一个整数,表示最少花费的金钱。

数据范围
1≤N≤1000,
数据保证,每座山的初始高度都在 1∼100 之间。

样例

输入样例:
5
20
4
1
24
21
输出样例:
18
样例解释
最佳方案为,将高度为 1 的山峰,增加 3 个单位高度,将高度为 24 的山峰,减少 3 个单位高度。

算法1

(暴力枚举) $O(nm)$

获取所有的高度,将高度从低到高排序,然后枚举所有的可能的最矮的山峰,去判断每个山峰需要修改的费用

C++ 代码

#include<bits/stdc++.h>
using namespace std;
const int N=1010;
int a[N];
int main()
{
    int n;
    cin>>n;
    int minv=101,maxv=-1;
    for(int i=0;i<n;i++)
    {
        cin>>a[i];
        minv=min(minv,a[i]);
        maxv=max(maxv,a[i]);
    }
    int res=INT_MAX;
    for(int i=minv;i<=maxv;i++) //a[i]作为最低的山峰 
    {
        int sum=0;
        for(int j=0;j<n;j++)
        {
            if(a[j]<i) //比最低的还矮 
                sum=sum+(i-a[j])*(i-a[j]);
            if(a[j]>i+17) //超过了最高的
                sum=sum+(a[j]-i-17)*(a[j]-i-17);
        }
        res=min(sum,res);
    }
    cout<<res;
    return 0;
}



季科
7天前

题目描述

给定一个如下乘法算式:

      * * *
   x    * *
    -------
      * * *         
    * * *           
    -------
    * * * *

现在,给定 N 个 1∼9 之间的数字,请你在这些数字中选取合适的数字填入算式,代替 * 号,使得算式成立。

所给的数字可以在算式中出现多次。

算式中不能出现没有给出的数字。

请问,共有多少种不同的填法?

输入格式
第一行包含整数 N。

第二行包含 N 个整数,表示给定的数字,数据保证这 N 个数字互不相同。

输出格式
输出一个整数,表示可以使得算式成立的总填法数量。

数据范围
1≤N≤9

样例

输入样例:
5
2 3 4 6 8
输出样例:
1
样例解释
唯一的使得算式成立的填法如下:

      2 2 2
    x   2 2
     ------
      4 4 4
    4 4 4
  ---------
    4 8 8 4
每个代替 * 号的数字均在给出数字之中,满足条件。

再看一组不满足条件的填法:

      2 2 2   <-- OK:  三个数字均在 {2, 3, 4, 6, 8} 之中
    x   2 3   <-- OK:  两个数字均在 {2, 3, 4, 6, 8} 之中
     ------
      6 6 6   <-- OK:  三个数字均在 {2, 3, 4, 6, 8} 之中
    4 4 4     <-- OK:  三个数字均在 {2, 3, 4, 6, 8} 之中
  ---------
    5 1 0 6   <-- NOT OK: 5,1,0 均不在 {2, 3, 4, 6, 8} 之中



算法1

(暴力枚举)

这个题目也是暴力,我们枚举所有的3位数和2位数的乘积,然后依次判断,第一个数是不是一个三位数,第二个数是不是一个三位数,结果是不是一个四位数,因为需要枚举两个因子和三个积中的所有数是否都出现过,这个时候我们可以用一个数组来保存所有的数,然后循环处理一遍就可以了

C++ 代码

#include<bits/stdc++.h>
using namespace std;
bool st[10];
int t[10];
bool f()
{
    for(int i=0;i<5;i++)//依次判断每个数 
    {
        int a=t[i]; 
        while(a) 
        {
            if(st[a%10]==false)//某个数字没有出现 
            return false;
            a/=10;
        }
    }
    return 1;
}
int main()
{
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        int x;
        cin>>x;
        st[x]=1;
    }
    int cnt=0;
    for(int i=100;i<=999;i++)
        for(int j=10;j<=99;j++)
        {
            int a=i*(j%10),b=i*(j/10),c=i*j;
            if(a>=100&&a<=999&&b>=100&b<=999&&c>=1000&&b<=9999)//a是3位数,b是3位数,c是4位数 
            {
                t[0]=i,t[1]=j,t[2]=a,t[3]=b,t[4]=c;//5个数依次赋值 
                if(f()) //每个数字都出现过 
                    cnt++;
            }
        }
    cout<<cnt<<endl;
    return 0;
} 



季科
7天前

题目描述

回文数是指数字从前往后读和从后往前读都相同的数字。

例如,12321 是一个回文数,77778 不是一个回文数。

当然回文数没有前导 0 和尾数 0,因此 0220 不是一个回文数。

我们观察数字 21,它在十进制表示下不是一个回文数,但是在二进制表示下它却是一个回文数(10101)。

现在请你编写一个程序,读入两个整数 N 和 S,输出满足大于 S 并且至少在两种进制表示下(二进制至十进制)都是回文数的前 N 个整数。

输入格式
共一行,包含两个整数 N 和 S。

输出格式
共 N 行,每行输出一个满足条件的整数。

数字按从小到大顺序依次输出。

数据范围
1≤N≤15,
0<S<10000

28

样例

输入样例:
3 25
输出样例:
26
27
28

算法1

(暴力枚举)

这个题直接从s+1开始枚举,然后依次判断数在x进制下是否为回文数,如果找到了,那么就将回文次数的个数+1,如果可以至少出现2次回文,那么这就是一个满足要求的数,当我们找到了n个数以后,我们就可以跳出循环了,否则就需要一直执行下去。

C++ 代码

#include<bits/stdc++.h>
using namespace std;
bool f(int s,int x)//判断某个数在x进制下是否为回文数 
{
    int t=s;
    stack<int> stk;
    while(t)
    {
        stk.push(t%x);
        t/=x;
    } 
    while(stk.size())
    {
        if(stk.top()!=s%x)
            return false;
        stk.pop();
        s/=x;
    }
    return true;
}
int main()
{
    int n,s;
    cin>>n>>s;
    int cnt=0;
    s++;
    while(1)
    {
        if(cnt==n)//找到了n个数 
        {
            break;
        }
        int t=0;
        for(int x=2;x<=10;x++)//从2进制到10进制枚举 
        {
            if(f(s,x))
                t++;
        }
        if(t>=2) cout<<s<<endl,cnt++;//至少有2种进制下为回文次数 
        s++;
    }
    return 0;
}




季科
7天前

题目描述

你有一条由 N 个珠子串成的项链,珠子的颜色有红、白、蓝三种,珠子在项链中呈随机分布。

例如 N=29 时,两个项链的示例如下所示:

            1 2                               1 2
        r b b r                           b r r b
      r         b                       b         b
     r           r                     b           r
    r             r                   w             r
   b               r                 w               w
  b                 b               r                 r
  b                 b               b                 b
  b                 b               r                 b
   r               r                 b               r
    b             r                   r             r
     b           r                     r           r
       r       r                         r       b
         r b r                             r r w
        样例 A                            样例 B
                    r 红珠子
                    b 蓝珠子
                    w 白珠子

图片对项链的第一颗珠子和第二颗珠子进行了标记。

样例 A 中的项链只包含蓝红两种颜色的珠子,将所有珠子按顺序记录颜色为:

brbrrrbbbrrrrrbrrbbrbbbbrrrrb
假设你现在要将项链从某个点处断开,并将断开后的项链拉直摆放,然后从一端开始收集相同颜色的珠子,直到碰到另一种颜色的珠子为止,完成后在另一端进行相同的操作(这次收集的珠子的颜色可能与之前收集的颜色并不相同)。

现在,你需要判断在项链的哪一处将项链断开,可以使得我们收集珠子的数量达到最多。

例如,对于样例 A 提供的项链,我们在 9 号珠子和 10号珠子之间断开项链,或者在 24 号珠子和 25 号珠子之间断开项链,可以收集到最多 8 个珠子。

另外,某些项链除蓝红珠子外,还包含白珠子,如样例 B 所示。

收集珠子时,如果我们遇到了白色珠子,那么我们可以将它视为红色或蓝色,并将其涂上相应的颜色。

表示项链的字符串只包含 r,w,b 三种字符。

请你编写一个程序,求出我们可以收集珠子的最大数目。

输入格式
第一行包含整数 N,表示珠子的数量。

第二行包含一个由 N 个字符构成的字符串,字符串中只包含r,w,b 三种字符。

输出格式
共一行,包含一个整数表示我们可以收集珠子的最大数目。

数据范围
3≤N≤350

样例

输入样例:
29
wwwbbrwrbrbrrbrbrwrwwrbwrwrrb
输出样例:
11

算法1

(暴力枚举) $O(n^2)$

我们可以直接将字符串扩大一倍,然后分别从左右开始搜索,这里有两个需要注意的点:
1.第一个遇到的颜色可能是白色,那么我们可以将它变为最近遇到的颜色
2.如果收集到的珠子的数目大于项链中的珠子的数目,那么我们直接输出珠子的数目就可以了。

C++ 代码

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    cin>>n;
    string str;
    cin>>str;
    str=str+str;//字符串扩大两倍
    int res=0;
    for(int i=0;i<n;i++)
    {
        int l=0;
        int j=i,k=0;//j是起点,k是偏移量
        char ch=str[j]; //第一个颜色,可能是白色
        while(k<n&&(str[j]==str[j+k]||str[j+k]=='w'||ch=='w'))//可能的匹配
        {
            if(ch=='w'&&str[j+k]!='w')//如果是白色更新为最近的颜色
                ch=str[j+k];
            l++;
            k++;
        }
        j=i+n-1,k=0;//另一个端点
        int r=0;
        ch=str[j-k];
        while(k<n&&(str[j]==str[j-k]||str[j-k]=='w'||ch=='w'))//可能的匹配
        {
            if(ch=='w'&&str[j-k]!='w') //如果是白色则更新为最近的颜色
                ch=str[j-k];
            r++;
            k++;
        }
        res=max(res,l+r);
    }
    if(res>n) res=n;//如果收到的珠子数目大于所有的珠子
    cout<<res<<endl;
    return 0;
}



季科
12天前

题目描述

农夫约翰对奶牛的传承非常的重视。

他的每头牛都有一个唯一的大写字母编号。

他用一个二叉树记录了牛的传承关系,示例如下:

              C
            /   \
           /     \
          B       G
         / \     /
        A   D   H
           / \
          E   F

现在,给定这个二叉树的中序遍历和前序遍历,请你求出这个二叉树的后序遍历。

中序遍历:首先遍历左子树,然后访问根结点,最后遍历右子树。
前序遍历:首先访问根结点,然后遍历左子树,最后遍历右子树。
后序遍历:首先遍历左子树,然后遍历右子树,最后访问根结点。

输入格式
一个大写字母构成的字符串,表示树的中序遍历。

一个大写字母构成的字符串,表示树的前序遍历。

输出格式
输出一个字符串,表示树的后序遍历。

数据范围
树中结点的数目不超过 26 个。

输入样例:
ABEDFCHG
CBADEFGH
输出样例:
AEFDBHGC

算法分析
由于要求输出后序遍历,我们可以先输出一个树的左子树/右子树,然后再输出根节点,由于树是属于递归定义的一种数据结构,我们也可以递归实现输出,对于任何一棵树,前序遍历的第一个点是当前树的根节点,然后我们可以由中序遍历处理左右子树的节点输出,然后再输出根节点。

#include<bits/stdc++.h>
using namespace std;
void dfs(string a,string b)
{
    if(a.size()==0) return ;
    int t=b.find(a[0]); //左子树节点个数
    dfs(a.substr(1,t),b.substr(0,t));//左子树
    dfs(a.substr(t+1),b.substr(t+1)); //右子树
    cout<<a[0];//当前树的根节点

}
int main()
{
    string a,b;
    cin>>b>>a;
    dfs(a,b);
    return 0;
}



季科
18天前

题目描述

Farmer John的 N 头奶牛总是会迷路走到农场上遥远的地方去!

他需要你帮助将她们一起赶回来。

农场的草地大体是一块狭长的区域——我们可以将其想象成一条数轴,奶牛可以占据数轴上的任意整数位置。

这 N 头奶牛现在正位于不同的整数位置,Farmer John想要移动她们,使得她们占据相邻的位置(例如,位置 3、4、5、6、7、8)。

不幸的是,奶牛们现在很困,Farmer John要让她们集中精力听从命令移动并不容易。

任意时刻,他只能使得一头处在“端点”(在所有奶牛中位置最小或最大)位置的奶牛移动。

当他移动奶牛时,他可以命令她走到任意一个未被占用的整数位置,只要在新的位置上她不再是一个端点。

可以看到随着时间的推移,这样的移动可以使奶牛们趋向越来越近。

请求出使得奶牛们集中到 N 个相邻位置所进行的移动次数的最小和最大可能值。

输入样例

3
7
4
9

输出样例

1
2

C++ 代码

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int a[N];
int main()
{
    int n;
    cin>>n;
    for(int i=0;i<n;i++)
        cin>>a[i];
    sort(a,a+n);
    if(a[n-2]-a[0]==n-2&&a[n-1]-a[n-2]>2)//1 2 3 6
    {
        cout<<2;
    }
    else if(a[n-1]-a[1]==n-2&&a[1]-a[0]>2)//1 4 5 6
    {
        cout<<2;
    }else
    {
        int x=0;
        for(int i=0,j=0;i<n;i++)//枚举i为左端点,j为右端点的区间
        {
            while(j<n-1&&a[j+1]-a[i]<=n-1)
                j++;
            x=max(x,j-i+1);
        }
        cout<<n-x;
    }
    cout<<endl;
    cout<<max(a[n-2]-a[0],a[n-1]-a[1])-(n-2);//为了走的足够远,就是空位足够多
    return 0;
}




季科
2个月前

算法1

(暴力枚举) $O(n^2)$

这个题我们可以直接使用一个函数来返回每个数的需要的火柴数目,然后我们对函数相加做一个判断即可。n最大值为24,那么我们去除掉+=的4个,就只有20个,在去掉一个一位数最少为1,只有18个火柴棒,平均分配到两个数的话,必定是一个4位数,我们假定a为最小的a1111(8)+b1=c(1112)>24同理可得a的最大值肯定是不会超过1111的,所以我们枚举a和b的时候枚举到1111就可以了。

C++ 代码

#include<bits/stdc++.h>
using namespace std;
int nums[10]={6,2,5,5,4,5,6,3,7,6}; //每个数字需要多少个火柴棒 
int k[10010]; 
int f(int x) //每个数需要的火柴数目 
{
    int res=0;
    int t=x;
    while(x)
    {
        res+=nums[x%10];
        x/=10;
    }
    if(t==0) //如果这个数是0 
        res=6;
    return res;
}
int main()
{
    int res=0;
    int n;
    cin>>n;
    for(int i=0;i<=1111;i++) //枚举所有可能的数 
        for(int j=0;j<=1111;j++)
            if(f(i)+f(j)+f(i+j)+4==n)
            {
                res++;
            }
    cout<<res<<endl;
    return 0; 
}




季科
3个月前

算法1

(反向搜索)

从结尾到开头搜索,避免了缓存队列

C++ 代码

#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> PII;
const int N=1010,M=N*N;
#define x first
#define y second
int dx[]={-1,1,0,0},dy[]={0,0,-1,1};
int g[N][N];
int n;
PII q[M],pre[N][N];
void bfs(int x,int y)
{
    memset(pre,-1,sizeof pre);
    int hh=0,tt=0;
    q[hh]={x,y};
    tt++;
    while(hh<tt)
    {
        PII p=q[hh];
        hh++;
        for(int i=0;i<4;i++)
        {
            int a=p.x+dx[i],b=p.y+dy[i];
            if(a>=0&&a<n&&b>=0&&b<n&&pre[a][b].x==-1&&g[a][b]==0)
            {
                pre[a][b]=p;
                q[tt++]={a,b};
            }
        }
    }
}
int main()
{
    cin>>n;
    for(int i=0;i<n;i++)
        for(int j=0;j<n;j++)
            cin>>g[i][j];
    bfs(n-1,n-1);
    PII end={0,0};
    while(true)
    {
        cout<<end.x<<" "<<end.y<<endl;
        if(end.x==n-1&&end.y==n-1) break;
        end=pre[end.x][end.y];
    }
    return 0;
}

算法2

(正向搜索)

才左上角到右下角,需要用一个队列来缓存路径,然后输出。

C++ 代码

#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> PII;
const int N=1010,M=N*N;
#define x first
#define y second
int dx[]={-1,1,0,0},dy[]={0,0,-1,1};
int g[N][N];
int n;
PII q[M],pre[N][N];
void bfs(int x,int y)
{
    memset(pre,-1,sizeof pre);
    int hh=0,tt=0;
    q[hh]={x,y};
    tt++;
    while(hh<tt)
    {
        PII p=q[hh];
        hh++;
        for(int i=0;i<4;i++)
        {
            int a=p.x+dx[i],b=p.y+dy[i];
            if(a>=0&&a<n&&b>=0&&b<n&&pre[a][b].x==-1&&g[a][b]==0)
            {
                pre[a][b]=p;
                q[tt++]={a,b};
            }
        }
    }
}
int main()
{
    cin>>n;
    for(int i=0;i<n;i++)
        for(int j=0;j<n;j++)
            cin>>g[i][j];
    bfs(0,0);
    PII end={n-1,n-1};
    int tt=0;
    while(true)
    {
        q[tt++]={end.x,end.y};
        if(end.x==0&&end.y==0) break;
        end=pre[end.x][end.y];
    }
    for(int i=tt-1;i>=0;i--)
        cout<<q[i].x<<" "<<q[i].y<<endl;
    return 0;
}