做推广网站公司,拟定一个物流网站的建设方案,开发网站需要时间,wordpress中国主题题目链接
[NOIP2012 提高组] 开车旅行
题目描述
小 A \text{A} A 和小 B \text{B} B 决定利用假期外出旅行#xff0c;他们将想去的城市从 1 1 1 到 n n n 编号#xff0c;且编号较小的城市在编号较大的城市的西边#xff0c;已知各个城市的海拔高度互不相同#xf…题目链接
[NOIP2012 提高组] 开车旅行
题目描述
小 A \text{A} A 和小 B \text{B} B 决定利用假期外出旅行他们将想去的城市从 1 1 1 到 n n n 编号且编号较小的城市在编号较大的城市的西边已知各个城市的海拔高度互不相同记城市 i i i 的海拔高度为 h i h_i hi城市 i i i 和城市 j j j 之间的距离 d i , j d_{i,j} di,j 恰好是这两个城市海拔高度之差的绝对值即 d i , j ∣ h i − h j ∣ d_{i,j}|h_i-h_j| di,j∣hi−hj∣。
旅行过程中小 A \text{A} A 和小 B \text{B} B 轮流开车第一天小 A \text{A} A 开车之后每天轮换一次。他们计划选择一个城市 s s s 作为起点一直向东行驶并且最多行驶 x x x 公里就结束旅行。
小 A \text{A} A 和小 B \text{B} B 的驾驶风格不同小 B \text{B} B 总是沿着前进方向选择一个最近的城市作为目的地而小 A \text{A} A 总是沿着前进方向选择第二近的城市作为目的地注意本题中如果当前城市到两个城市的距离相同则认为离海拔低的那个城市更近。如果其中任何一人无法按照自己的原则选择目的城市或者到达目的地会使行驶的总距离超出 x x x 公里他们就会结束旅行。
在启程之前小 A \text{A} A 想知道两个问题
1、 对于一个给定的 x x 0 xx_0 xx0从哪一个城市出发小 A \text{A} A 开车行驶的路程总数与小 B \text{B} B 行驶的路程总数的比值最小如果小 B \text{B} B 的行驶路程为 0 0 0此时的比值可视为无穷大且两个无穷大视为相等。如果从多个城市出发小 A \text{A} A 开车行驶的路程总数与小 B \text{B} B 行驶的路程总数的比值都最小则输出海拔最高的那个城市。
2、对任意给定的 x x i xx_i xxi 和出发城市 s i s_i si小 A \text{A} A 开车行驶的路程总数以及小 B \text B B 行驶的路程总数。
输入格式
第一行包含一个整数 n n n表示城市的数目。
第二行有 n n n 个整数每两个整数之间用一个空格隔开依次表示城市 1 1 1 到城市 n n n 的海拔高度即 h 1 , h 2 . . . h n h_1,h_2 ... h_n h1,h2...hn且每个 h i h_i hi 都是互不相同的。
第三行包含一个整数 x 0 x_0 x0。
第四行为一个整数 m m m表示给定 m m m 组 s i s_i si 和 x i x_i xi。
接下来的 m m m 行每行包含 2 2 2 个整数 s i s_i si 和 x i x_i xi表示从城市 s i s_i si 出发最多行驶 x i x_i xi 公里。
输出格式
输出共 m 1 m1 m1 行。
第一行包含一个整数 s 0 s_0 s0表示对于给定的 x 0 x_0 x0从编号为 s 0 s_0 s0 的城市出发小 A \text A A 开车行驶的路程总数与小 B \text B B 行驶的路程总数的比值最小。
接下来的 m m m 行每行包含 2 2 2 个整数之间用一个空格隔开依次表示在给定的 s i s_i si 和 x i x_i xi 下小 A \text A A 行驶的里程总数和小 B \text B B 行驶的里程总数。
样例 #1
样例输入 #1
4
2 3 1 4
3
4
1 3
2 3
3 3
4 3样例输出 #1
1
1 1
2 0
0 0
0 0样例 #2
样例输入 #2
10
4 5 6 1 2 3 7 8 9 10
7
10
1 7
2 7
3 7
4 7
5 7
6 7
7 7
8 7
9 7
10 7样例输出 #2
2
3 2
2 4
2 1
2 4
5 1
5 1
2 1
2 0
0 0
0 0提示
【样例1说明】 各个城市的海拔高度以及两个城市间的距离如上图所示。
如果从城市 1 1 1 出发可以到达的城市为 2 , 3 , 4 2,3,4 2,3,4这几个城市与城市 1 1 1 的距离分别为 1 , 1 , 2 1,1,2 1,1,2但是由于城市 3 3 3 的海拔高度低于城市 2 2 2所以我们认为城市 3 3 3 离城市 1 1 1 最近城市 2 2 2 离城市 1 1 1 第二近所以小A会走到城市 2 2 2。到达城市 2 2 2 后前面可以到达的城市为 3 , 4 3,4 3,4这两个城市与城市 2 2 2 的距离分别为 2 , 1 2,1 2,1所以城市 4 4 4 离城市 2 2 2 最近因此小B会走到城市 4 4 4。到达城市 4 4 4 后前面已没有可到达的城市所以旅行结束。
如果从城市 2 2 2 出发可以到达的城市为 3 , 4 3,4 3,4这两个城市与城市 2 2 2 的距离分别为 2 , 1 2,1 2,1由于城市 3 3 3 离城市 2 2 2 第二近所以小 A \text A A 会走到城市 3 3 3。到达城市 3 3 3 后前面尚未旅行的城市为 4 4 4所以城市 4 4 4 离城市 3 3 3 最近但是如果要到达城市 4 4 4则总路程为 2 3 5 3 2353 2353所以小 B \text B B 会直接在城市 3 3 3 结束旅行。
如果从城市 3 3 3 出发可以到达的城市为 4 4 4由于没有离城市 3 3 3 第二近的城市因此旅行还未开始就结束了。
如果从城市 4 4 4 出发没有可以到达的城市因此旅行还未开始就结束了。
【样例2说明】
当 x 7 x7 x7 时如果从城市 1 1 1 出发则路线为 1 → 2 → 3 → 8 → 9 1 \to 2 \to 3 \to 8 \to 9 1→2→3→8→9小 A \text A A 走的距离为 1 2 3 123 123小 B \text B B 走的距离为 1 1 2 112 112。在城市 1 1 1 时距离小 A \text A A 最近的城市是 2 2 2 和 6 6 6但是城市 2 2 2 的海拔更高视为与城市 1 1 1 第二近的城市所以小 A \text A A 最终选择城市 2 2 2走到 9 9 9 后小 A \text A A 只有城市 10 10 10 可以走没有第二选择可以选所以没法做出选择结束旅行
如果从城市 2 2 2 出发则路线为 2 → 6 → 7 2 \to 6 \to 7 2→6→7小 A \text A A 和小 B \text B B 走的距离分别为 2 , 4 2,4 2,4。
如果从城市 3 3 3 出发则路线为 3 → 8 → 9 3 \to 8 \to 9 3→8→9小 A \text A A 和小 B \text B B 走的距离分别为 2 , 1 2,1 2,1。
如果从城市 4 4 4 出发则路线为 4 → 6 → 7 4 \to 6 \to 7 4→6→7小 A \text A A 和小 B \text B B 走的距离分别为 2 , 4 2,4 2,4。
如果从城市 5 5 5 出发则路线为 5 → 7 → 8 5 \to 7 \to 8 5→7→8小 A \text A A 和小 B \text B B 走的距离分别为 5 , 1 5,1 5,1。
如果从城市 6 6 6 出发则路线为 6 → 8 → 9 6 \to 8 \to 9 6→8→9小 A \text A A 和小 B \text B B 走的距离分别为 5 , 1 5,1 5,1。
如果从城市 7 7 7 出发则路线为 7 → 9 → 10 7 \to 9 \to 10 7→9→10小 A \text A A 和小 B \text B B 走的距离分别为 2 , 1 2,1 2,1。
如果从城市 8 8 8 出发则路线为 8 → 10 8 \to 10 8→10小 A \text A A 和小 B \text B B 走的距离分别为 2 , 0 2,0 2,0。
如果从城市 9 9 9 出发则路线为 9 9 9小 A \text A A 和小 B \text B B 走的距离分别为 0 , 0 0,0 0,0旅行一开始就结束了。
如果从城市 10 10 10 出发则路线为 10 10 10小 A \text A A 和小 B \text B B 走的距离分别为 0 , 0 0,0 0,0。
从城市 2 2 2 或者城市 4 4 4 出发小 A \text A A 行驶的路程总数与小 B \text B B 行驶的路程总数的比值都最小但是城市 2 2 2 的海拔更高所以输出第一行为 2 2 2。
【数据范围与约定】
对于 30 % 30\% 30% 的数据有 1 ≤ n ≤ 20 , 1 ≤ m ≤ 20 1\le n \le 20,1\le m\le 20 1≤n≤20,1≤m≤20 对于 40 % 40\% 40% 的数据有 1 ≤ n ≤ 100 , 1 ≤ m ≤ 100 1\le n \le 100,1\le m\le 100 1≤n≤100,1≤m≤100 对于 50 % 50\% 50% 的数据有 1 ≤ n ≤ 100 , 1 ≤ m ≤ 1000 1\le n \le 100,1\le m\le 1000 1≤n≤100,1≤m≤1000 对于 70 % 70\% 70% 的数据有 1 ≤ n ≤ 1000 , 1 ≤ m ≤ 1 0 4 1\le n \le 1000,1\le m\le 10^4 1≤n≤1000,1≤m≤104 对于 100 % 100\% 100% 的数据 1 ≤ n , m ≤ 1 0 5 1\le n,m \le 10^5 1≤n,m≤105 − 1 0 9 ≤ h i ≤ 1 0 9 -10^9 \le h_i≤10^9 −109≤hi≤109 1 ≤ s i ≤ n 1 \le s_i \le n 1≤si≤n 0 ≤ x i ≤ 1 0 9 0 \le x_i \le 10^9 0≤xi≤109 数据保证 h i h_i hi 互不相同。
算法思想
根据题目描述本题要求的是选择一个城市 s s s 作为起点一直向东行驶并且最多行驶 x x x 公里就结束旅行时小 A \text{A} A 开车行驶的路程总数以及小 B \text B B 行驶的路程总数。
由于小 A \text{A} A和小 B \text{B} B一直向东行驶并且最多行驶 x x x 公里就结束旅行可以使用倍增法统计出小 A \text{A} A 和小 B \text B B 开车行驶的路程总数 l a la la和 l b lb lb。
状态表示 d a ( 0 , s , i ) da(0,s,i) da(0,s,i)表示从城市 s s s出发小 A \text{A} A先走两人轮流行驶了 2 i 2^i 2i次小 A \text{A} A行驶的总距离。 d a ( 1 , s , i ) da(1,s,i) da(1,s,i)表示从城市 s s s出发小 B \text{B} B先走两人轮流行驶了 2 i 2^i 2i次小 A \text{A} A行驶的总距离。 d b ( 0 , s , i ) db(0,s,i) db(0,s,i)表示从城市 s s s出发小 A \text{A} A先走两人轮流行驶了 2 i 2^i 2i次小 B \text{B} B行驶的总距离。 d b ( 1 , s , i ) db(1,s,i) db(1,s,i)表示从城市 s s s出发小 B \text{B} B先走两人轮流行驶了 2 i 2^i 2i次小 B \text{B} B行驶的总距离。
有了上述状态如何求从 s s s 出发最多行驶 x x x 公里时的 l a la la和 l b lb lb呢不妨设两人轮流行驶了 k k k次以二进制的方式分析假设 k ( 011010010 ) 2 k(011010010)_2 k(011010010)2那么 l a d a ( 0 , s , 7 ) d a ( 0 , s 1 , 6 ) d a ( 0 , s 2 , 4 ) d a ( 0 , s 3 , 1 ) l b d b ( 0 , s , 7 ) d b ( 0 , s 1 , 6 ) d b ( 0 , s 2 , 4 ) d b ( 0 , s 3 , 1 ) la da(0,s,7)da(0,s_1,6)da(0,s_2,4)da(0,s_3,1)\\ lb db(0,s,7)db(0,s_1,6)db(0,s_2,4)db(0,s_3,1) lada(0,s,7)da(0,s1,6)da(0,s2,4)da(0,s3,1)lbdb(0,s,7)db(0,s1,6)db(0,s2,4)db(0,s3,1)
其中 s 1 , s 2 , s 3 . . . s_1,s_2,s_3... s1,s2,s3...为中间经过的城市。要求解中间经过的城市还需要预处理 f ( 0 , s , i ) f(0,s,i) f(0,s,i)表示从城市 s s s出发小 A \text{A} A先走两人轮流行驶了 2 i 2^i 2i次到达的城市编号 f ( 1 , s , i ) f(1,s,i) f(1,s,i)表示从城市 s s s出发小 B \text{B} B先走两人轮流行驶了 2 i 2^i 2i次到达的城市编号
由于题目要求小 A \text{A} A和小 B \text{B} B的驾驶风格不同。因此还需要预处理出 g a ( i ) ga(i) ga(i)表示小 A \text{A} A从城市 s s s出发能够到达的城市编号 g b ( i ) gb(i) gb(i)表示小 B \text{B} B从城市 s s s出发能够到达的城市编号
下面再来考虑一些如何计算上述状态
状态计算
1、 先来看一下如何计算 g a ga ga和 g b gb gb
由于小 A \text{A} A总是沿着前进方向选择第二近的城市作为目的地那么就是求城市 s s s右边和它的海拔高度之差第 2 2 2小的城市小 B \text{B} B 总是沿着前进方向选择一个最近的城市作为目的地那么就是求城市 s s s右边和它的海拔高度之差最小的城市
即在 s s s右侧的城市中查找与 s s s高度之差的绝对值最小的两个城市其原理类似于博主的这篇文章——邻值查找。
为了快速查找目标可以使用set作为容器从后向前遍历每个城市
查找第 1 1 1个高度大于 h [ s ] h[s] h[s]的城市和第 2 2 2个高度大于 h [ s ] h[s] h[s]的城市查找第 1 1 1个高度小于 h [ s ] h[s] h[s]的城市和第 2 2 2个高度小于 h [ s ] h[s] h[s]的城市那么目标就在这 4 4 4个城市之间如下图所示。再将城市 s s s插入到set中。
2、再看如何计算 f ( 0 , s , i ) f(0,s,i) f(0,s,i)和 f ( 0 , s , i ) f(0,s,i) f(0,s,i)
当 i 0 i0 i0时表示从 s s s出发行驶 1 1 1次那么 f ( 0 , s , 0 ) g a ( s ) f(0,s,0) ga(s) f(0,s,0)ga(s) f ( 1 , s , 0 ) g b ( s ) f(1,s,0) gb(s) f(1,s,0)gb(s)当 i 1 i1 i1时表示从 s s s出发行驶 2 2 2次 第 1 1 1次小 A \text{A} A先驾驶从 s s s行驶到 f ( 0 , s , 0 ) f(0,s,0) f(0,s,0)第 2 2 2次换小 B \text{B} B驾驶从 f ( 0 , s , 0 ) f(0,s,0) f(0,s,0)行驶到了 f ( 1 , f ( 0 , s , 0 ) , 0 ) f(1,f(0,s,0),0) f(1,f(0,s,0),0) k k k表示由谁先驾驶 k 0 k0 k0表示小 A \text{A} A先驾驶 k 1 k1 k1表示小 B \text{B} B先驾驶那么 f ( k , s , 1 ) f ( 1 − k , f ( k , s , 0 ) , 0 ) f(k,s,1)f(1-k,f(k,s,0),0) f(k,s,1)f(1−k,f(k,s,0),0) 当 i 1 i1 i1时表示从 s s s出发行驶 2 i 2^i 2i次也可以分成两部分 第一部分 小 A \text{A} A先驾驶从 s s s行驶到 f ( 0 , s , i − 1 ) f(0,s,i-1) f(0,s,i−1)第二部分由于 i 1 i1 i1 2 i − 1 2^{i-1} 2i−1是偶数不换人还有由小 A \text{A} A先驾驶从 f ( 0 , s , i − 1 ) f(0,s,i-1) f(0,s,i−1)行驶到 f ( 0 , f ( 0 , s , i − 1 ) , i − 1 ) f(0,f(0,s,i-1),i-1) f(0,f(0,s,i−1),i−1)即 f ( k , s , i ) f ( k , f ( k , s , i − 1 ) , i − 1 ) f(k,s,i)f(k,f(k,s,i-1),i-1) f(k,s,i)f(k,f(k,s,i−1),i−1)
3、最后再计算 d a da da和 d b db db 当 i 0 i0 i0时即行驶 1 1 1次 d a ( 0 , s , 0 ) da(0,s,0) da(0,s,0)表示小 A \text{A} A先走行驶 1 1 1次会从城市 s s s到达 g a ( s ) ga(s) ga(s)那么 d a ( 0 , s , 0 ) d i s t ( s , g a ( s ) ) da(0,s,0)dist(s, ga(s)) da(0,s,0)dist(s,ga(s))即这两个城市海拔高度之差的绝对值如果小 B \text{B} B先走那么小 A \text{A} A行驶的距离为 0 0 0即 d a ( 1 , s , 0 ) 0 da(1,s,0)0 da(1,s,0)0同理 d b ( 1 , s , 0 ) d i s t ( s , g b ( s ) ) db(1,s,0)dist(s, gb(s)) db(1,s,0)dist(s,gb(s)) d b ( 0 , s , 0 ) 0 db(0,s,0)0 db(0,s,0)0 当 i 1 i1 i1时即行驶 2 2 2次可以分成两部分不妨用 k k k表示谁先行驶 k { 0 , 1 } k\{0,1\} k{0,1} 第一部分从 s s s出发行驶 1 1 1次走到 f ( k , s , 0 ) f(k,s,0) f(k,s,0)小 A \text{A} A行驶的距离 d a ( k , s , 0 ) da(k,s,0) da(k,s,0) 小 B \text{B} B行驶的距离为 d b ( k , s , 0 ) db(k,s,0) db(k,s,0)第二部分从 f ( k , s , 0 ) f(k,s,0) f(k,s,0)出发换人行驶 1 1 1次小 A \text{A} A行驶的距离 d a ( 1 − k , f ( k , s , 0 ) , 0 ) da(1-k,f(k,s,0),0) da(1−k,f(k,s,0),0) 小 B \text{B} B行驶的距离为 d b ( k , f ( k , s , 0 ) , 0 ) db(k,f(k,s,0),0) db(k,f(k,s,0),0)那么 d a ( k , s , 1 ) d a ( k , s , 0 ) d a ( 1 − k , f ( k , s , 0 ) , 0 ) da(k,s,1)da(k,s,0)da(1-k,f(k,s,0),0) da(k,s,1)da(k,s,0)da(1−k,f(k,s,0),0) d b ( k , s , 1 ) d b ( k , s , 0 ) d b ( 1 − k , f ( k , s , 0 ) , 0 ) db(k,s,1)db(k,s,0)db(1-k,f(k,s,0),0) db(k,s,1)db(k,s,0)db(1−k,f(k,s,0),0) 当 i 1 i1 i1时即行驶 2 i 2^i 2i次也可以分成两部分 k k k表示谁先行驶 k { 0 , 1 } k\{0,1\} k{0,1} d a ( k , s , i ) d a ( k , s , i − 1 ) d a ( k , f ( k , s , i − 1 ) , i − 1 ) da(k,s,i)da(k,s,i-1)da(k,f(k,s,i-1),i-1) da(k,s,i)da(k,s,i−1)da(k,f(k,s,i−1),i−1) d b ( k , s , i ) d b ( k , s , i − 1 ) d b ( 1 − k , f ( k , s , i − 1 ) , i − 1 ) db(k,s,i)db(k,s,i-1)db(1-k,f(k,s,i-1),i-1) db(k,s,i)db(k,s,i−1)db(1−k,f(k,s,i−1),i−1)
如下图所示
时间复杂度
预处理 g a , g b ga,gb ga,gb需要从后向前遍历每个城市 s s s查找与 s s s高度之差的绝对值最小的两个城市使用set容器查找的时间复杂度为 O ( l o g n ) O(logn) O(logn)总的时间复杂度为 O ( n l o g n ) O(nlogn) O(nlogn)通过倍增法预处理 f f f的时间复杂度为 O ( n l o g n ) O(nlogn) O(nlogn)通过倍增法预处理 d a , d b da,db da,db的时间复杂度为 O ( n l o g n ) O(nlogn) O(nlogn)第一问求对于给定的 x x x从哪个城市出发小 A \text A A 开车行驶的路程总数与小 B \text B B 行驶的路程总数的比值最小需要枚举每个城市作为起点求 l a la la和 l b lb lb时间复杂度为 O ( n l o g n ) O(nlogn) O(nlogn)第二问一共有 m m m个询问求在给定的 s s s 和 x x x 情况下求小 A \text A A 行驶的里程总数和小 B \text B B 行驶的里程总数时间复杂度为 O ( m l o g n ) O(mlogn) O(mlogn)
总的时间复杂度为 O ( n l o g n ) 1 0 5 × 17 O(nlogn)10^5\times17 O(nlogn)105×17
代码实现
#include iostream
#include set
using namespace std;
typedef long long LL;
typedef pairLL, int PLI;
const int N 1e5 10, M 17;
const LL INF 1e18;
int n, h[N];
int ga[N], gb[N]; //ga[i]表示小A从i出发能到达的城市
int f[2][N][M]; //f[0][s][i]表示从s出发小A先走轮流行驶2^i时到达的城市编号
int da[2][N][M], db[2][N][M];
void init_g()
{setPLI S;//防止查找越界插入4个边界S.insert({-INF, 0}), S.insert({-INF 1, 0});S.insert({INF, 0}), S.insert({INF 1, 0});PLI b[4]; //被选城市//从后向前遍历城市查找右侧第一个大于h[i]的位置for(int i n; i 0; i --){PLI t(h[i], i);auto it S.upper_bound(t);it ; //移动到右侧第二个大于h[i]的位置for(int k 0; k 4; k ) b[k] *it --;//从备选的4个备选城市中查找差值第1小和第2小的城市LL d1 INF, d2 INF;int p1, p2;for(int k 3; k 0; k --){LL d abs(h[i] - b[k].first);if(d d1) {d2 d1, d1 d;p2 p1, p1 b[k].second; }else if(d d2) {d2 d, p2 b[k].second;}}//小A选择第二近的城市作为目的地小B选择一个最近的城市作为目的地ga[i] p2, gb[i] p1;S.insert(t);}
}
void init_f()
{//初始状态从每个城市出发行驶1次能到达的城市for(int s 1; s n; s ) {f[0][s][0] ga[s], f[1][s][0] gb[s];}//状态计算for(int i 1; i M; i )for(int s 1; s n; s )for(int k 0; k 2; k ){if(i 1) //行驶2次f[k][s][i] f[1 - k][f[k][s][0]][0];else //行驶2^if[k][s][i] f[k][f[k][s][i - 1]][i - 1];}
}
//获取两个城市之间的距离
int get_dis(int a, int b)
{return abs(h[a] - h[b]);
}
void init_d()
{//初始状态计算从每个城市出发行驶1次能够走的额距离for(int s 1; s n; s ){da[0][s][0] get_dis(s, ga[s]);db[1][s][0] get_dis(s, gb[s]);}//状态计算for(int i 1; i M; i )for(int s 1; s n; s )for(int k 0; k 2; k ){if(i 1) //行驶2次{da[k][s][i] da[k][s][i - 1] da[1 - k][f[k][s][i - 1]][i - 1];db[k][s][i] db[k][s][i - 1] db[1 - k][f[k][s][i - 1]][i - 1];}else //行驶2^i次{da[k][s][i] da[k][s][i - 1] da[k][f[k][s][i - 1]][i - 1];db[k][s][i] db[k][s][i - 1] db[k][f[k][s][i - 1]][i - 1];}}
}
//计算从城市s出发行驶总距离不超过s时小A和小B各自走的总距离
void work(int s, int x, int la, int lb)
{la lb 0;//枚举行驶次数for(int i M - 1; i 0; i --){//如果能够到达城市并且总距离不超过xif(f[0][s][i] la lb da[0][s][i] db[0][s][i] x){la da[0][s][i], lb db[0][s][i];s f[0][s][i];//行驶到新的城市s}}
}
int main()
{scanf(%d, n);for(int i 1; i n; i ) scanf(%d, h[i]);//预处理状态init_g();init_f();init_d();//第一问int x;scanf(%d, x);int ans 0, max_h 0;double min_r INF;for(int s 1; s n; s ){int la, lb;work(s, x, la, lb);double r lb 0 ? INF : (double) la / lb;//取最小比值比值相同取海拔更高的城市if(r min_r || r min_r h[s] max_h){min_r r, max_h h[s], ans s;}}printf(%d\n, ans);//第二问int m;scanf(%d, m);while (m -- ){int s, x, la, lb;scanf(%d%d, s, x);work(s, x, la, lb);printf(%d %d\n, la, lb);}return 0;
}
