Codeforces 228 div2 A,B,C-布布扣-bubuko.com

全水题。。。。。

Fox Ciel is playing a game with numbers now.

Ciel has n positive integers: x1, x2, ..., xn. She can do the following operation as many times as needed: select two different indexes iand j such that xi > xj hold, and then apply assignment xi = xi - xj. The goal is to make the sum of all numbers as small as possible.

Please help Ciel to find this minimal sum.

Input

The first line contains an integer n (2?≤?n?≤?100). Then the second line contains n integers: x1, x2, ..., xn (1?≤?xi?≤?100).

Output

Output a single integer — the required minimal sum.

Sample test(s)

input
2
1 2

output
2

input
3
2 4 6

output
6

input
2
12 18

output
12

input
5
45 12 27 30 18

output
15

Note

In the first example the optimal way is to do the assignment: x2 = x2 - x1.

In the second example the optimal sequence of operations is: x3 = x3 - x2, x2 = x2 - x1.

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

int num[1200],n;

int gcd(int a,int b)
{
	return b==0?a:gcd(b,a%b);
}

int main()
{
	scanf("%d",&n);
	int a=-1;
	for(int i=0;i<n;i++) 
	{
		scanf("%d",&num[i]);
		if(a==-1) a=num[i];
		else a=gcd(a,num[i]);
	}
	printf("%d\n",a*n);
	return 0;
}

Fox Ciel has a board with n rows and n columns. So, the board consists of n?×?n cells. Each cell contains either a symbol ‘.‘, or a symbol ‘#‘.

A cross on the board is a connected set of exactly five cells of the board that looks like a cross. The picture below shows how it looks.

$bubuko.com,布布扣$

Ciel wants to draw several (may be zero) crosses on the board. Each cross must cover exactly five cells with symbols ‘#‘, and any cell with symbol ‘#‘ must belong to some cross. No two crosses can share a cell.

Please, tell Ciel if she can draw the crosses in the described way.

Input

The first line contains an integer n (3?≤?n?≤?100) — the size of the board.

Each of the next n lines describes one row of the board. The i-th line describes the i-th row of the board and consists of n characters. Each character is either a symbol ‘.‘, or a symbol ‘#‘.

Output

Output a single line with "YES" if Ciel can draw the crosses in the described way. Otherwise output a single line with "NO".

Sample test(s)

input
5
.#...
####.
.####
...#.
.....

output
YES

input
4
####
####
####
####

output
NO

input
6
.#....
####..
.####.
.#.##.
######
.#..#.

output
YES

input
6
.#..#.
######
.####.
.####.
######
.#..#.

output
NO

input
3
...
...
...

output
YES

Note

In example 1, you can draw two crosses. The picture below shows what they look like.

$bubuko.com,布布扣$

In example 2, the board contains 16 cells with ‘#‘, but each cross contains 5. Since 16 is not a multiple of 5, so it‘s impossible to cover all.

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

int n,nb;
char g[1000][1000];

bool ck(int x,int y)
{
	if((x>=0&&x<n)&&(y>=0&&y<n)) return true;
	return false;
}

void dfs(int x,int y)
{
	if(ck(x+1,y)&&ck(x+2,y)&&ck(x+1,y-1)&&ck(x+1,y+1))
	{
		if(g[x][y]==‘#‘&&g[x+1][y]==‘#‘&&g[x+1][y-1]==‘#‘&&g[x+1][y+1]==‘#‘&&g[x+2][y]==‘#‘)
		{
			g[x][y]=g[x+1][y]=g[x+1][y-1]=g[x+1][y+1]=g[x+2][y]=‘X‘;
			nb+=5;
		}
	}
}

int main()
{
	scanf("%d",&n);
	for(int i=0;i<n;i++)
	{
		scanf("%s",g[i]);
	}
	int jinghao=0;
	for(int i=0;i<n;i++)
	{
		for(int j=0;j<n;j++)
		{
			if(g[i][j]==‘#‘) jinghao++;
		}
	}
	if(jinghao%5) 
	{
		puts("NO"); return 0;
	}
	for(int i=0;i<n;i++)
	{
		for(int j=0;j<n;j++)
		{
			if(g[i][j]==‘#‘)
			{
				dfs(i,j);
			}
		}
	}
	if(nb!=jinghao)
	{
		puts("NO");
	}
	else
	{
		puts("YES");
	}
	return 0;
}

Fox Ciel has n boxes in her room. They have the same size and weight, but they might have different strength. The i-th box can hold at most xi boxes on its top (we‘ll call xi the strength of the box).

Since all the boxes have the same size, Ciel cannot put more than one box directly on the top of some box. For example, imagine Ciel has three boxes: the first has strength 2, the second has strength 1 and the third has strength 1. She cannot put the second and the third box simultaneously directly on the top of the first one. But she can put the second box directly on the top of the first one, and then the third box directly on the top of the second one. We will call such a construction of boxes a pile.

$bubuko.com,布布扣$

Fox Ciel wants to construct piles from all the boxes. Each pile will contain some boxes from top to bottom, and there cannot be more thanxi boxes on the top of i-th box. What is the minimal number of piles she needs to construct?

Input

The first line contains an integer n (1?≤?n?≤?100). The next line contains n integers x1,?x2,?...,?xn (0?≤?xi?≤?100).

Output

Output a single integer — the minimal possible number of piles.

Sample test(s)

input
3
0 0 10

output
2

input
5
0 1 2 3 4

output
1

input
4
0 0 0 0

output
4

input
9
0 1 0 2 0 1 1 2 10

output
3

Note

In example 1, one optimal way is to build 2 piles: the first pile contains boxes 1 and 3 (from top to bottom), the second pile contains only box 2.

$bubuko.com,布布扣$

In example 2, we can build only 1 pile that contains boxes 1, 2, 3, 4, 5 (from top to bottom).

$bubuko.com,布布扣$

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

int st[1000],n,ans=0;
int vis[1000];

int main()
{
	scanf("%d",&n);
	for(int i=0;i<n;i++) scanf("%d",st+i);
	sort(st,st+n);
	for(int i=0;i<n;i++)
	{
		if(vis[i]==0)
		{
			ans++;
			int strength=1;
			vis[i]=ans;
			for(int j=i+1;j<n;j++)
			{
				if(vis[j]) continue;
				if(st[j]>=strength)
				{
					vis[j]=ans;
					strength++;
				}
			} 
		}
	}
	printf("%d\n",ans);
	return 0;
}

Codeforces 228 div2 A,B,C

原文：http://blog.csdn.net/u012797220/article/details/18995983