【53.57%】【codeforces 610C】Harmony Analysis
time limit per test3 seconds
memory limit per test256 megabytes
inputstandard input
outputstandard output
The semester is already ending, so Danil made an effort and decided to visit a lesson on harmony analysis to know how does the professor look like, at least. Danil was very bored on this lesson until the teacher gave the group a simple task: find 4 vectors in 4-dimensional space, such that every coordinate of every vector is 1 or - 1 and any two vectors are orthogonal. Just as a reminder, two vectors in n-dimensional space are considered to be orthogonal if and only if their scalar product is equal to zero, that is:
.
Danil quickly managed to come up with the solution for this problem and the teacher noticed that the problem can be solved in a more general case for 2k vectors in 2k-dimensinoal space. When Danil came home, he quickly came up with the solution for this problem. Can you cope with it?
Input
The only line of the input contains a single integer k (0 ≤ k ≤ 9).
Output
Print 2k lines consisting of 2k characters each. The j-th character of the i-th line must be equal to ’ * ’ if the j-th coordinate of the i-th vector is equal to - 1, and must be equal to ’ + ’ if it’s equal to + 1. It’s guaranteed that the answer always exists.
If there are many correct answers, print any.
Examples
input
2
output
++**
++
++++
+**+
Note
Consider all scalar products in example:
Vectors 1 and 2: ( + 1)·( + 1) + ( + 1)·( - 1) + ( - 1)·( + 1) + ( - 1)·( - 1) = 0
Vectors 1 and 3: ( + 1)·( + 1) + ( + 1)·( + 1) + ( - 1)·( + 1) + ( - 1)·( + 1) = 0
Vectors 1 and 4: ( + 1)·( + 1) + ( + 1)·( - 1) + ( - 1)·( - 1) + ( - 1)·( + 1) = 0
Vectors 2 and 3: ( + 1)·( + 1) + ( - 1)·( + 1) + ( + 1)·( + 1) + ( - 1)·( + 1) = 0
Vectors 2 and 4: ( + 1)·( + 1) + ( - 1)·( - 1) + ( + 1)·( - 1) + ( - 1)·( + 1) = 0
Vectors 3 and 4: ( + 1)·( + 1) + ( + 1)·( - 1) + ( + 1)·( - 1) + ( + 1)·( + 1) = 0
【题解】
规律题;
k和k-1的答案存在如下关系;
上图中的方框表示k-1时的答案;
把它按照上述方式复制3份,第4份则在原来的基础上取反;(用1表示+,0表示减);
比如样例输入
++**
+*+*
++++
+**+
//->
1100
1010
1111
1001
//->相同的3份取反的一份
1100 1100
1010 1010
1111 1111
1001 1001
1100 0011
1010 0101
1111 0000
1001 0110
/*而这正是k=3时的答案;右下角那个
上面两个方框是肯定满足的;
为了让下面两个方框在乘的时候也满足;
相当于左边取A,右边取它的相反数-A;这样一减就是0;
如果一个答案符合要求则全部取反还是能符合要求的;
所以右下角取反不会影响下面两个的答案正确性;
然后又能让上面两个方框的乘下面两个方框的向量的时候积为0;所以是符合要求的;
*/
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <set>
#include <map>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>
#include <vector>
#include <stack>
#include <string>
#define lson L,m,rt<<1
#define rson m+1,R,rt<<1|1
#define LL long long
using namespace std;
const int MAXN = 1000;
const int dx[5] = {0,1,-1,0,0};
const int dy[5] = {0,0,0,-1,1};
const double pi = acos(-1.0);
struct abc
{
int a[1000][1000];
};
int k;
abc ans[10];
void input_LL(LL &r)
{
r = 0;
char t = getchar();
while (!isdigit(t) && t!='-') t = getchar();
LL sign = 1;
if (t == '-')sign = -1;
while (!isdigit(t)) t = getchar();
while (isdigit(t)) r = r * 10 + t - '0', t = getchar();
r = r*sign;
}
void input_int(int &r)
{
r = 0;
char t = getchar();
while (!isdigit(t)&&t!='-') t = getchar();
int sign = 1;
if (t == '-')sign = -1;
while (!isdigit(t)) t = getchar();
while (isdigit(t)) r = r * 10 + t - '0', t = getchar();
r = r*sign;
}
int main()
{
// freopen("F:\\rush.txt","r",stdin);
ans[0].a[1][1] = 0;
for (k= 1;k <= 9;k++)
{
for (int i = 1;i <= 1<<(k-1);i++)
for (int j = 1;j <= 1<<(k-1);j++)
{
ans[k].a[i][j] = ans[k-1].a[i][j];
ans[k].a[i+(1<<(k-1))][j] = ans[k-1].a[i][j];
ans[k].a[i][j+(1<<(k-1))] = ans[k].a[i][j];
ans[k].a[i+(1<<(k-1))][j+(1<<(k-1))] = !ans[k].a[i][j];
}
}
input_int(k);
for (int i = 1;i <= 1<<k;i++)
{
for (int j = 1;j <= 1<<k;j++)
if (ans[k].a[i][j])
putchar('+');
else
putchar('*');
puts("");
}
return 0;
}
最新文章
- 3.27考试总结(hnoi难度)
- Nhibernate 一对一关系映射(主键映射)
- 【Scala 】Akka库
- 查看 usb info
- c语言输入输出
- GBin1插件推荐之马可波罗(Marco Polo),jQuery的自动补齐插件 - Autocomplete Plugin
- 创建区域Areas,添加TagHelper
- PSAM SAM
- 错误: 无法找到或可以不被加载到主类 Main
- 【Mysql基本知识整理】
- c/c++ 多线程 std::call_once的应用
- day23--面向对象之封装、继承、多态
- centos部署flask
- spring boot 添加整合ssl使得http变成https方法
- nested exception is com.svorx.core.dao.PersistenceException
- (转)Memcached 之 .NET(C#)实例分析
- 高手用的SourceInsight配置文件——仿Sublime风格【转】
- 设置CameraRollBrowseOptions的宽高
- xwork-2.1.2.jar与xwork-core-2.1.6.jar的区别是什么? 在线等待 先谢谢了
- ceph 测试
热门文章
- JavaScript实现,控制一个文本框只能输入正整数,如输入不符合条件则文本框全部字体标红
- Oracle使用——impdp导入数据时数据表已经存在
- hdu1848 sg打表
- Introduction to 3D Game Programming with DirectX 12 学习笔记之 --- 第七章:在Direct3D中绘制(二)
- char和achar互转
- JavaScript 验证API
- ELK之开心小爬爬
- ArcGIS下如何提取研究区域
- 2018-9-19-Roslyn-通过-Nuget-管理公司配置
- 基于 springMVC 的 RESTful HTTP API 实践(服务端)