J 牛牛想要成为hacker

本文主要是介绍J 牛牛想要成为hacker，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

链接：https://ac.nowcoder.com/acm/contest/9982/J
来源：牛客网

在算法竞赛中"hack"一般指用一组测试数据触发程序的缺陷，从而导致本来通过题目的AC代码无法通过该测试数据。
一般情况见得比较多的是用hack数据导致别人WA掉，当然也有一些会导致原本的AC代码TLE和MLE。

牛牛在一些简单的练习题时遇到了这样一个问题。
给定一个大小为n的数组(1≤ai≤10^9)，然后请你判断数组元素是否能够从中选出三个组成一个三角形。

牛牛发现AC通过的代码中有这样一种暴力逻辑，该逻辑的伪代码如下。
FOR i = 1 … n
FOR j = i + 1 … n
FOR k = j + 1 … n
IF isTriangle(a[i],a[j],a[k])
print(“yes”)
EXIT
END IF
END FOR
END FOR
END FOR
print(“no”)
EXIT

其实就是三重循环枚举数组的三个元素，检查是否为三角形。这段代码很取巧的地方在于它存在一种“短路”逻辑，一旦发现存在三角形就立刻终止程序。
这样在随机数据下其实很容易发现三角形，所以如果数据纯随机，显然这就是一段AC代码。

牛牛当然知道这个代码很明显就存在缺陷，如果数据构造的好的话应该可以卡TLE，但是牛牛发现，他并不会构造出能够hack这个暴力算法的数据，所以他请你来帮他。

我们以这段程序调用isTriangle的次数作为时间复杂度的计算依据，请你构造数据hack这段暴力程序，使它TLE掉。
输入描述:
第一行输入一个正整数n(3≤n≤10^5)表示需要你构造的数组大小。
输出描述:
输出n个正整数，正整数的范围在[1,10^9] 之间，要求该暴力程序在运行过程中调用isTriangle函数的次数不得少于min(Cn3 ,n^2 ⌊log 2n⌋)
示例1
输入
3
输出
2 2 2
说明
当n=3时题目要求小w的程序调用isTriangle函数的次数不得少于1次，所以输出任意的3个正整数都能符合条件。
示例2
输入
10
输出
1 2 4 8 16 32 64 128 256 512
说明
由于任何三个数字都无法组成三角形，所以会扫描到最后一组，达到最大复杂度，一共调用了120次isTriangle函数。

思路
Cn,3 是跑满 n^2log2n 我们得考虑Cn,2 * num,num是斐波那契个数，我们带入1e5，求出27即可满足，后面全搞的比前面大最后一个斐波那契数就行，这样爆1e9，想到后面可以全都是1就可以了。

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+5;
const double esp=1e-6;
const ll mod=1e9+7;
int n,k;
ll qpow(ll a,ll b){ll ans=1,base=a;while(b){if(b&1) ans=ans*base;base=base*base;b>>=1;}return ans;
}
int a[N]={0,1,1};
bool check(int i,int j,int k){if(a[i]+a[j]<=a[k]) return false;if(a[i]+a[k]<=a[j]) return false;if(a[j]+a[k]<=a[i]) return false;return true;
}
ll cal(){ll cnt=0;for(int i=1;i<=n;i++){for(int j=i+1;j<=n;j++){for(int k=j+1;k<=n;k++){cnt++;if(check(i,j,k)){return cnt;}}}}return cnt;
}
void init(){for(int i=1;i<=N-2;i++) a[i]=1;a[1]=2,a[2]=3;for(int i=3;i<=40;i++){a[i]=a[i-2]+a[i-1];}
}
void solve(){scanf("%d",&n);for(int i=1;i<=n;i++){printf("%d ",a[i]);}cout<<endl<<cal();
}
int main(){int Case=1;init();//scanf("%d",&Case);while(Case--){solve();}return 0;
}