Description

The counter-terrorists found a time bomb in the dust. But this time the terrorists improve on the time bomb. The number sequence of the time bomb counts from 1 to N. If the current number sequence includes the sub-sequence “49”, the power of the blast would add one point.
Now the counter-terrorist knows the number N. They want to know the final points of the power. Can you help them?

Input

The first line of input consists of an integer $T (1 \leq T \leq 10000)$, indicating the number of test cases. For each test case, there will be an integer $N (1 \leq N \leq 2^{63}-1)$ as the description.

The input terminates by end of file marker.

Output

For each test case, output an integer indicating the final points of the power.

Sample Input

1
2
3
4

3
1
50
500

Sample Output

1
2
3

0
1
15

第3章　线性模型

3.1　基本形式

线性模型(linear model)试图学得一个通过属性的线性组合来进行预测的函数，即

一般用向量形式写成

w和b学得之后模型得以确定。许多功能强大的非线性模型(nonlinear model)可在线性模型的基础上通过引入层级结构或高维映射而得。由于w直观表达了各属性在预测中的重要性，因此线性模型有很好的可解释性(comprehensibility) or 可理解性(understandability)。

多元线性回归|第3天

Steps

通俗点讲就是有好多好多个X决定一个Y。

Datasets

Description

在一个果园里，多多已经将所有的果子打了下来，而且按果子的不同种类分成了不同的堆。多多决定把所有的果子合成一堆。

每一次合并，多多可以把两堆果子合并到一起，消耗的体力等于两堆果子的重量之和。可以看出，所有的果子经过 n-1次合并之后， 就只剩下一堆了。多多在合并果子时总共消耗的体力等于每次合并所耗体力之和。

因为还要花大力气把这些果子搬回家，所以多多在合并果子时要尽可能地节省体力。假定每个果子重量都为 1，并且已知果子的种类 数和每种果子的数目，你的任务是设计出合并的次序方案，使多多耗费的体力最少，并输出这个最小的体力耗费值。

例如有3种果子，数目依次为1，2，9。可以先将1 、2堆合并，新堆数目为3，耗费体力为3。接着，将新堆与原先的第三堆合并，又得到新的堆，数目为12 ，耗费体力为12。所以多多总共耗费体力=3+12=15。可以证明15为最小的体力耗费值。

Input

共两行。
第一行是一个整数$n(1\leq n\leq10000)$，表示果子的种类数。

第二行包含n个整数，用空格分隔，第i个整数$a_i(1\leq a_i\leq20000)$是第i种果子的数目。

Output

一个整数，也就是最小的体力耗费值。输入数据保证这个值小于$2^{31}$。

Sample Input

1
2

3 
1 2 9

Sample Output

1

15

简单线性回归模型|第2天

Steps

Datasets

数据预处理|第1天

Steps

Datasets

Description

在越来越讲究合作的时代，人们注意的更多的不是个人物的舞姿，而是集体的排列。

为了配合每年的倒计时，同学们决定排出——“数字舞蹈”。顾名思义就是所有人一起排成若干个数字，更为创新的是，每个人都是趴在地上，保证横竖。

现在给出数字及其要求摆出的大小，请你编程，模拟同学们的优美姿态。

Input

第一行为k。k表示要摆出数字的大小。

第二行为全部由数字组成的字符串，即要摆出的几个数字。

Output

按题目要求输出。

Sample Input

1
2

2
1234567890

Sample Output

1
2
3
4
5
6
7

   --   --        --   --   --   --   --   -- 
|    |    | |  | |    |       | |  | |  | |  |
|    |    | |  | |    |       | |  | |  | |  |
   --   --   --   --   --        --   --      
| |       |    |    | |  |    | |  |    | |  |
| |       |    |    | |  |    | |  |    | |  |
   --   --        --   --        --   --   --

Description

$2\times N$名编号为 $1\sim 2N$ 的选手共进行$R$轮比赛。每轮比赛开始前，以及所有比赛结束后，都会按照总分从高到低对选手进行一次排名。选手的总分为第一轮开始前的初始分数加上已参加过的所有比赛的得分和。总分相同的，约定编号较小的选手排名靠前。

每轮比赛的对阵安排与该轮比赛开始前的排名有关：第1名和第2名、第3名和第4名、……、第$2K-1$名和第$2K$名、…… 、第$2N-1$名和第$2N$名，各进行一场比赛。每场比赛胜者得1分，负者得0分。也就是说除了首轮以外，其它轮比赛的安排均不能事先确定，而是要取决于选手在之前比赛中的表现。

现给定每个选手的初始分数及其实力值，试计算在R轮比赛过后，排名第Q的选手编号是多少。我们假设选手的实力值两两不同，且每场比赛中实力值较高的总能获胜。

Input

第一行是三个正整数$N,R,Q$每两个数之间用一个空格隔开，表示有$2\times N$名选手、R轮比赛，以及我们关心的名次Q。

第二行是$2\times N$个非负整数$s1,s_2,\dots,s{2N},$每两个数之间用一个空格隔开，其中$si$表示编号为i的选手的初始分数。 第三行是$2\times N$个正整数$w_1,w_2,\dots,w{2N}$每两个数之间用一个空格隔开，其中$w_i$表示编号为i的选手的实力值。

Output

一个整数，即R轮比赛结束后，排名第Q的选手的编号。

Sample Input

1
2
3

2 4 2 
7 6 6 7 
10 5 20 15

Sample Output

1

1

§1　线性空间的定义与性质

定义1　设$V$是一个非空集合，$\mathbb{R}$为实数域。如果在$V$中定义了一个加法，即对于任意两个元素$\alpha,\beta\in V$，总有惟一的一个元素$\gamma\in V$与之对应，称为$\alpha$与$\beta$的和，记作$\gamma=\alpha+\beta$；在$V$中又定义了一个数的乘法(简称数乘)，即对于任一数$\lambda\in\mathbb{R}$与任意元素$\alpha\in V$，总有惟一的一个元素$\delta\in V$与之对应，称为$\lambda$与$\alpha$的数量乘积，记作$\delta=\lambda\alpha$，并且这两种运算满足以下八条运算规律(设$\alpha、\beta、\gamma\in V,\lambda、\mu\in\mathbb{R}$)：

(i)$\alpha+\beta=\beta+\alpha$；

(ii)$(\alpha+\beta)+\gamma=\alpha+(\beta+\gamma)$；

(iii)在$V$中存在零元素0，对任何$\alpha\in V$，都有$\alpha+0=\alpha$；

(iv)对任何$\alpha\in V$，都有$\alpha$的负元素$\beta\in V$，使$\alpha+\beta-0$；

(v)$1\alpha=\alpha$；

(vi)$\lambda(\mu\alpha)=(\lambda\mu)\alpha$；

(vii)$(\lambda+\mu)\alpha=\lambda\alpha+\mu\alpha$；

(viii)$\lambda(\alpha+\beta)=\lambda\alpha+\lambda\beta$；

那么就称$V$为(实数域$\mathbb{R}$上的)向量空间(或线性空间)，$V$中的元素不论其本来的性质如何，统称为(实)向量。

线性空间的性质：

1.零向量是惟一的.

2.任一向量的负向量是惟一的，$\alpha$的负向量记作$-\alpha$.

3.$0\alpha=0,(-1)\alpha=-\alpha,\lambda0=0.$

4.如果$\lambda\alpha=0$，则$\lambda=0$或$\alpha=0$.

定义2　设$V$是一个线性空间，$L$是$V$的一个非空子集，如果$L$对于$V$中所定义的加法和数乘两种运算也构成一个线性空间，则称$L$为$V$的子空间。

定理1　线性空间$V$的非空子集$L$构成子空间的充分必要条件是：$L$对于$V$中的线性运算封闭。

§2　维数、基与坐标

定义3　在线性空间$V​$中，如果存在n个向量$\alpha_1,\alpha_2,\dots,\alpha_n​$，满足：

(i)$\alpha_1,\alpha_2,\dots,\alpha_n$线性无关；

(ii)$V​$中任一向量$\alpha​$总可由$\alpha_1,\alpha_2,\dots,\alpha_n​$线性表示，

那么$\alpha_1,\alpha_2,\dots,\alpha_n​$就称为线性空间$V​$的一个基，n称为线性空间$V​$的维数。只含一个零向量的线性空间没有基，规定它的维数为0。维数为n的线性空间称为n维线性空间，记作$V_n​$。

定义4　设$\alpha_1,\alpha_2,\dots,\alpha_n​$是线性空间$V_n​$的一个基，对于任一向量$\alpha\in V_n​$，总有且仅有一组有序数$x_1,x_2,\dots,x_n​$使$\alpha=x_1\alpha_1+x_2\alpha_2+\dots+x_n\alpha_n,x_1,x_2,\dots,x_n​$这组有序数就称为向量$\alpha​$在$\alpha_1,\alpha_2,\dots,\alpha_n​$这个基中的坐标，并记作$\alpha=(x_1,x_2,\dots,x_n)^T​$。

设$V$与$U$是两个线性空间，如果在它们的向量之间有一一对应关系，且这个对应关系保持线性组合的对应，那么就说线性空间$V$与$U$同构。维数相等的线性空间都同构。

§1　向量的内积、长度及正交性

定义1　设有n维向量

令$[x,y]=x_1y_1+x_2y_2+\dots+x_ny_n$，称为向量$x$与$y$的内积。

内积具有下列性质：

(i)$[x,y]=[y,x]$；

(ii)$[\lambda x,y]=\lambda[x,y]$；

(iii)$[x+y,z]=[x,z]+[y,z]$；

(iv)当$x=0$时，$[x,x]=0$；当$x\neq0$时，$[x,x]>0$。

施瓦茨(Schwarz)不等式$[x,y]^2\leq[x,x][y,y]$。

定义2　令$||x||=\sqrt{[x,x]}=\sqrt{x_1^2+x_2^2+\dots+x_n^2},||x||$称为n维向量$x$的长度(或范数)。

向量的长度具有下述性质：

(i)非负性　当$x\neq0$时，$||x||>0$；当$x=0$时，$||x||=0$；

(ii)齐次性　$||\lambda x||=|\lambda|||x||$；

当$x\neq0、y\neq0$时，$\theta=arccos\frac{[x,y]}{||x||||y||}$称为n维向量$x$与$y$的夹角。当$[x,y]=0$时，称向量$x$与$y$正交。

定理1　若n维向量$a_1,a_2,\dots,a_r$是一组两两正交的非零向量，则$a_1,a_2,\dots,a_r$线性无关。

定义3　设n维向量$e_1,e_2,\dots,e_r$是向量空间$V(V\subseteq\mathbb{R^n})$的一个基，如果$e_1,e_2,\dots,e_r$两两正交，且都是单位向量，则称$e_1,e_2,\dots,e_r$是$V$的一个标准正交基。

设$e_1,e_2,\dots,e_r$是标准正交集，则任意向量$a$都能由$e_1,e_2,\dots,e_r$线性表示，设为$a=\lambda_1e_1+\lambda_2e_2+\dots+\lambda_re_r,$为求其中系数，可用$e_i^T$左乘上式，有$e_i^Ta=\lambda_ie_i^Te_i=\lambda_i,$即$\lambda_i=e_i^Ta=[a,e_i],$这就是向量在标准正交基中的坐标计算公式。

可以用施密特(Schmidt)正交化方法把一个基标准正交化，取：

然后把它们单位化，即：

就是$V$的一个标准正交基。

定义4　如果n阶矩阵$A$满足$A^TA=E(即A^{-1}=A^T),$那么称$A​$为正交矩阵，简称正交阵。

方阵为正交矩阵的充分必要条件是列向量都是单位向量，且两两正交。

因为$A^TA=E与AA^T=E$等价，所以上述结论对行向量亦成立。

正交矩阵具有以下性质：

(i)若$A$为正交矩阵，则$A^{-1}=A^T$也是正交矩阵，且$|A|=1或(-1)$；

(ii)若$A$和$B$都是正交矩阵，则$AB$也是正交矩阵。

定义5　若$P$为正交矩阵，则线性变换$y=Px$称为正交变换。

设$y=Px$为正交变换，则有$||y||=\sqrt{y^Ty}=\sqrt{x^TP^TPx}=sqrt{x^Tx}=||x||$。

说明经正交变换线段长度不变。