正文

codeforces 14A - Letter　&　codeforces 859B - Lazy Security Guard　-　[周赛水题]

IP云
IP云V管理员/6 阅读
08/18
提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

就像title说的，是昨天（2017/9/17）周赛的两道水题……

题目链接：http://codeforces.com/problemset/problem/14/A

time limit per test: 1 secondmemory limit per test: 64 megabytes

A boy Bob likes to draw. Not long ago he bought a rectangular graph (checked) sheet with n rows and m columns. Bob shaded some of the squares on the sheet. Having seen his masterpiece, he decided to share it with his elder brother, who lives in Flatland. Now Bob has to send his picture by post, but because of the world economic crisis and high oil prices, he wants to send his creation, but to spend as little money as possible. For each sent square of paper (no matter whether it is shaded or not) Bob has to pay 3.14 burles. Please, help Bob cut out of his masterpiece a rectangle of the minimum cost, that will contain all the shaded squares. The rectangle's sides should be parallel to the sheet's sides.

Input

The first line of the input data contains numbers n and m (1 ≤ n, m ≤ 50), n — amount of lines, and m — amount of columns on Bob's sheet. The following n lines contain m characters each. Character «.» stands for a non-shaded square on the sheet, and «*» — for a shaded square. It is guaranteed that Bob has shaded at least one square.

Output

Output the required rectangle of the minimum cost. Study the output data in the sample tests to understand the output format better.

Examples
input

6 7
.......
..***..
..*....
..***..
..*....
..***..

output

***
*..
***
*..
***

input

3 3
***
*.*
***

output

***
*.*
***

#include<cstdio>
int n,m;
int up,down,left,right;
char sheet[][];
int main()
{
scanf("%d%d",&n,&m);
left=m+, right=, up=n+, down=;
for(int i=;i<=n;i++)
{
scanf("%s",sheet[i]+);
for(int j=;j<=m;j++)
{
if(sheet[i][j]=='*')
{
if(j<left) left=j;
if(j>right) right=j;
if(i<up) up=i;
if(i>down) down=i;
}
}
}
for(int i=up;i<=down;i++)
{
for(int j=left;j<=right;j++) printf("%c",sheet[i][j]);
printf("\n");
}
}

题目链接：http://codeforces.com/problemset/problem/859/B

time limit per test: 2 secondsmemory limit per test: 256 megabytes

Your security guard friend recently got a new job at a new security company. The company requires him to patrol an area of the city encompassing exactly N city blocks, but they let him choose which blocks. That is, your friend must walk the perimeter of a region whose area is exactly N blocks. Your friend is quite lazy and would like your help to find the shortest possible route that meets the requirements. The city is laid out in a square grid pattern, and is large enough that for the sake of the problem it can be considered infinite.

Input

Input will consist of a single integer N (1 ≤ N ≤ 106), the number of city blocks that must be enclosed by the route.

Output

Print the minimum perimeter that can be achieved.

Examples
input

4

output

8

input

11

output

14

input

22

output

20

Note

Here are some possible shapes for the examples:

肯定首先要尽量做成一个大正方形，所以我们取int l = floor(sqrt(n))；

然后多出来的方块块怎么办嘞，肯定就是往大正方形的一条边上垒小方块，如果一条边垒满了， 就换条边垒（垒第二条边）；

显然，只要n>l*l，那就必然有一条边上要垒上一些个方块，那么就会比原来多两条单位边（即一个小正方形的一条边）；

如果第一条边垒满了，要垒第二条边了，那就又再多两条单位边；

而且，最多垒满两条边，不会再多；

#include<cstdio>
#include<cmath>
int n,l,ans;
int main()
{
scanf("%d",&n);
double tmp=sqrt(n);
l=(int)floor(tmp);
ans=*l;
if(n-l*l>l) ans+=;
else if(<n-l*l && n-l*l<=l) ans+=;
printf("%d\n",ans);
}

codeforces 14A - Letter&codeforces 859B - Lazy Security Guard-[周赛水题]的更多相关文章

  1. Codeforces 148D 一袋老鼠 Bag of mice &vert; 概率DP 水题

    除非特别忙,我接下来会尽可能翻译我做的每道CF题的题面! Codeforces 148D 一袋老鼠 Bag of mice | 概率DP 水题 题面 胡小兔和司公子都认为对方是垃圾. 为了决出谁才是垃 ...

  2. 【CF MEMSQL 3&period;0 B&period; Lazy Security Guard】

    time limit per test 2 seconds memory limit per test 256 megabytes input standard input output standa ...

  3. Codeforces Round &num;355 &lpar;Div&period; 2&rpar; A&period; Vanya and Fence 水题

    A. Vanya and Fence 题目连接: http://www.codeforces.com/contest/677/problem/A Description Vanya and his f ...

  4. Codeforces Testing Round &num;8 B&period; Sheldon and Ice Pieces 水题

    题目链接:http://codeforces.com/problemset/problem/328/B 水题~ #include <cstdio> #include <cstdlib ...

  5. Codeforces Round &num;290 &lpar;Div&period; 2&rpar; A&period; Fox And Snake 水题

    A. Fox And Snake 题目连接: http://codeforces.com/contest/510/problem/A Description Fox Ciel starts to le ...

  6. Codeforces Round &num;322 &lpar;Div&period; 2&rpar; A&period; Vasya the Hipster 水题

    A. Vasya the Hipster Time Limit: 1 Sec Memory Limit: 256 MB 题目连接 http://codeforces.com/contest/581/p ...

  7. Codeforces Round &num;373 &lpar;Div&period; 2&rpar; B&period; Anatoly and Cockroaches 水题

    B. Anatoly and Cockroaches 题目连接: http://codeforces.com/contest/719/problem/B Description Anatoly liv ...

  8. Codeforces Round &num;368 &lpar;Div&period; 2&rpar; A&period; Brain&&num;39&semi;s Photos 水题

    A. Brain's Photos 题目连接: http://www.codeforces.com/contest/707/problem/A Description Small, but very ...

  9. Codeforces Round &num;359 &lpar;Div&period; 2&rpar; A&period; Free Ice Cream 水题

    A. Free Ice Cream 题目连接: http://www.codeforces.com/contest/686/problem/A Description After their adve ...

随机推荐

  1. Key&sol;Value之王Memcached初探：三、Memcached解决Session的分布式存储场景的应用

    一.高可用的Session服务器场景简介 1.1 应用服务器的无状态特性 应用层服务器(这里一般指Web服务器)处理网站应用的业务逻辑,应用的一个最显著的特点是:应用的无状态性. PS:提到无状态特性 ...

  2. 解决 pathForResource 返回 nil的问题

    点击(此处)折叠或打开 NSString* path = [[NSBundle mainBundle] pathForResource:@"sample" ofType:@&quo ...

  3. bootrom启动流程【转】

    转自:http://blog.csdn.net/blueoceanindream/article/details/6851787 闲来无事,总结一下linux bootrom的启动流程: 环境:MIP ...

  4. apt-get &amp&semi;dpkg

    apt-get是ubuntu常用的软件安装工具.他可以很easy的从互联网上下载软件安装包,并实现安装. apt-get比较常用的命令如下: apt-get install packagename   ...

  5. springMVC servlet 静态资源加载

    问题描述 新手使用SpringMVC时市场会遇到静态资源无法加载在问题,如下图所示 问题原因 出现这种问题一般是在web.xml中的对spring的DispatcherServlet采用了如下配置,即 ...

  6. Java反射（Reflection）

    基本概念 在Java运行时环境中,对于任意一个类,能否知道这个类有哪些属性和方法?对于任意一个对象,能否调用它的任意一个方法? 答案是肯定的. 这种动态获取类的信息以及动态调用对象的方法的功能来自于J ...

  7. 【BZOJ2049】洞穴勘测（Link-Cut Tree）

    [BZOJ2049]洞穴勘测(Link-Cut Tree) 题面 题目描述 辉辉热衷于洞穴勘测. 某天,他按照地图来到了一片被标记为JSZX的洞穴群地区.经过初步勘测,辉辉发现这片区域由n个洞穴(分别 ...

  8. ADC0832的应用

    ADC0832是美国国家半导体公司生产的一种8位逐次比较型CMOS双通道A-D转换器,采用5V电源电压供电,模拟电压输入范围为0~5V,内部时钟250KHz时转换速度为32微秒. 仿真图为: 程序为: ...

  9. 对于coursera上三门北大网课的评测

    今年暑假开始就选了coursera上三门北大的网课——C++程序设计.算法基础.数据结构基础,它们属于一个项目的,上的话每个月249块钱,项目里包括这三门一共有七门课.因为一开始是三门课同时上的,数据 ...

  10. 【评分】BETA 版冲刺前准备

    [评分]BETA 版冲刺前准备 总结 本次作业较为简洁,计1分,按时提交计分,不提交不计分. 详细得分 组 短学号 名 分数 Boy Next Door 114 显东 1 Boy Next Door ...