暑假集训D20 2023.8.15

A.Access Denied

题意:给出系统密码比对的程序和每条指令所耗费的时间,你需要通过程序返回的执行时间来破解出正确的密码.

\(\operatorname{Solution}\)

bool CheckPassword(string pwd1, string pwd2) {
    if (pwd1.Length != pwd2.Length) {
        return false;
    }
    for (int i = 0; i < pwd1.Length; i++) {
        if (pwd1[i] != pwd2[i]) {
            return false;
        }
    }
    return true;
}

检查密码的程序如上所示.可以先猜长度再猜每个字符.长度错误会耗费 \(5ms\) .直到返回的时间不是 \(5ms\) 说明长度猜对了.
然后猜每个字符.根据判断的程序.首先判断长度花费了 \(4ms\).
然后每次 \(for\) 循环都要花费 \(5ms\) (赋值或i++花费 \(1ms\) ,比较花费 \(3ms\) ,for分支花费 \(1ms\) )
进入循环后,判断字符时,如果不等于则花费 \(5ms+4ms\) ,如果相等花费 \(5ms+5ms\) ,不妨假设前 \(k\) 个字符相等,第 \(k+1\) 个字符不等,那么花费时间就是 \(4+9*k+10ms\).
每次枚举每个位置的字母即可.返回的时间 \(x\) ,代表下标在 \(x/9-1\) 上的字母出错了,枚举即可.

#include<bits/stdc++.h>

using namespace std;
#define  pb push_back
vector<char> p;
int check(string t)
{
	cout<<t<<endl;
	string str;
	cin>>str;
	cin>>str;
	if(str=="GRANTED")
	{
		exit(0);
	}
	int x;
	scanf(" (%d",&x);
	// cout<<"x:"<<x<<endl;
	cin>>str;
	return (x/9) -1;
}
int main()
{
	string s = "a";
	int len =1;
	for(int i= 'a';i<='z';i++)
		p.pb(i);
	for(int i= 'A';i<='Z';i++)
		p.pb(i);
	for(int i= '0';i<='9';i++)
		p.pb(i);
	// for(char j:p)
	// {
	// 	cout<<j<<endl;
	// }
	int x;
	while(1)
	{
		cout<<s<<endl;
		string str;
		cin>>str;
		// cout<<str<<' ';
		cin>>str;
		// cout<<str<<' ';

		if(str=="GRANTED")exit(0);
		
		scanf(" (%d",&x);
		// cout<<x<<' ';
		cin>>str;
		// cout<<str<<'\n';

		if(x!=5)break;
		len++;
		s+="a";
	}
	// cout<<len<<endl;
	int i = x/9 - 1;
	// cout<<i<<endl;
	for(;i<len;)
	{
		for(char j :p)
		{
			// cout<<"j:"<<j<<endl;
			s[i] = (char)j;
			int temp = check(s);
			// cout<<"temp:"<<temp<<endl;
			if(temp!=i)
			{
				i = temp;
				break;
			}
		}
	}

	return 0;
}