icontofig | 发布于 2019-08-08 14:16:06 | 阅读量 297 | 二分
发布于 2019-08-08 14:16:06 | 二分

There is an array of length N consisting of non-negative integers. The array is sorted in non-decreasing order. Each number in the array appears exactly K times, except one element, which appears at least once, but less than K times. Your task is to identify that element.

This is an interactive problem. You are only given the integer N in the input. Both the array and the value of K are hidden. You are allowed to ask the judge the following queries: What is the value of the element at index i of the array? Identify the value of the element with frequency less than K by asking at most 60 such queries.

Input and Output

The first line of the input contains a single integer T denoting the number of test cases.

For each test case, you should start by reading a single line containing one integer N from the input.

You can interact with the judge using the standard input and output. There are two types of operations: to perform one operation, you should print to the standard output a line containing two space-separated integers type and val.

  • If type = 1, you are asking the judge a query for the value of the element of the array at index val. After printing this line, the judge will print to the standard input a line containing one integer corresponding to the value of the element at index val.
  • If type = 2, you are telling the judge that the element with frequency less than K is val. For each test case, you should perform this operation exactly once at the end. This is not counted towards the 60 queries.

 

Note

Don't forget to flush the standard output after printing each line. It can be done using fflush(stdout) in C/C++, System.out.flush() in Java and sys.out.flush() in Python.

If you ask more than 60 queries, your program will get the verdict Wrong Answer.

Constraints

  • 1 ≤ T ≤ 104
  • 3 ≤ N ≤ 105
  • 2 ≤ K ≤ N - 1
  • each element of the array lies between 1 and 109 inclusive

Example

Input / judge feedback	your output
1
3
						1 2
1
						1 3
5
						1 1
1
						2 5

Explanation

Example case 1: Suppose the array is [1, 1, 5]. Note that the value of K is 2, but it is hidden from you.

In the first query, you request the value of the 2nd element and the judge answers 1. Then you request the value of the 3rd element and the judge answers 5, then the value of the first element and the judge answers 1.

Now, you tell the judge that the answer is 5. You made a total of 3 queries.

题目大意

有一堆排好序的序列,其中除一个特殊的数外,其余的都出现了恰好k次。

但是你不知道k是多少,也不知道序列,只能通过向机器提问pos位置上是什么数字。

你要通过一系列询问得出特殊的数是多少。要求询问总数不能超过60次。

题解

生平第一次做人机交互题目。

其实这题蛮简单的。首先我们通过向机器询问1位置,通过二分整个序列下标并询问从而求出k的值,之后判断一下n位置和n-k是否相同,相同的话说明1位置的数就是哪个特殊的数,求出的k不是真正的k。然后我们判断一下n位置和n-k+1位置从而判断n位置的数会不会是特殊的数。

如果都不是,我们现在有k这个数,我们就可以再次二分,不过这次并不是二分序列下标,而是在1——n/k之间二分值mid,如果mid*k+1与(mid+1)*k不相同,则说明答案在1——mid*k+1中,否则就是在(mid+1)*k中。

如此二分就能保证一定不会超过60次询问。

代码

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5+5;
int T,n;
int mp[maxn];
int main(){
    scanf("%d",&T);
    while (T--){
        scanf("%d", &n);
        for (int i = 1; i <= n; ++i)
            mp[i] = -1;
        printf("1 1\n");
        fflush(stdout);
        scanf("%d", &mp[1]);
        printf("1 %d\n", n);
        fflush(stdout);
        scanf("%d", &mp[n]);
        int l = 1, r = n;
        int k = 0;
        while (l <= r){
            int mid = (l + r) >> 1;
            if (mp[mid] == -1){
                printf("1 %d\n",mid);
                fflush(stdout);
                scanf("%d",&mp[mid]);
            }
            if (mp[1] < mp[mid])
                r = mid - 1;
            else{
                k = max(k,mid);
                l = mid + 1;
            }
        }
        if (mp[n - k] == -1){
            printf("1 %d\n", n - k);
            fflush(stdout);
            scanf("%d", &mp[n - k]);
        }
        if (mp[n - k] == mp[n]){
            printf("2 %d\n", mp[1]);
            fflush(stdout);
            continue;
        }
        if (mp[n - k + 1] == -1){
            printf("1 %d\n", n - k + 1);
            fflush(stdout);
            scanf("%d", &mp[n - k + 1]);
        }
        if (mp[n - k + 1] != mp[n]){
            printf("2 %d\n", mp[n]);
            fflush(stdout);
            continue;
        }
        int ans = 2147483647;
        l = k+1,r = n-k;
        while (l <= r){
            int mid = (l + r) >> 1;
            if (mp[mid - (mid-1) % k] == -1){
                printf("1 %d\n",mid - (mid-1) % k);
                fflush(stdout);
                scanf("%d",&mp[mid - (mid-1) % k]);
            }
            if (mp[mid - (mid-1) % k + k - 1] == -1){
                printf("1 %d\n", mid - (mid-1) % k + k - 1);
                fflush(stdout);
                scanf("%d", &mp[mid - (mid-1) % k + k - 1]);
            }
            if (mp[mid - (mid-1) % k] == mp[mid - (mid-1) % k + k - 1]){
                l = mid + 1;
            }
            else{
                ans = mp[mid-(mid-1)%k];
                r = mid - 1;
            }
        }
        printf("2 %d\n",ans);
        fflush(stdout);
    }
    return 0;
}



内容更新于: 2019-08-08 14:16:12
链接地址: http://blog.leanote.com/post/icontofig/75824b79fc64

上一篇: 2019 Multi-University Training Contest 6 1002 Nonsense Time LIS(O(nlogn)版本)

下一篇: 2019 Multi-University Training Contest 6 1005 Snowy Smile 线段树维护最大子段和

297 人读过
立即登录, 发表评论.
没有帐号? 立即注册
0 条评论
文档导航