Codeforce 214 Div 2 B.Hometask

2024-06-12 03:58
文章标签 div 214 codeforce hometask

本文主要是介绍Codeforce 214 Div 2 B.Hometask,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

题目描述:

Description

Furik loves math lessons very much, so he doesn't attend them, unlike Rubik. But now Furik wants to get a good mark for math. For that Ms. Ivanova, his math teacher, gave him a new task. Furik solved the task immediately. Can you?

You are given a set of digits, your task is to find the maximum integer that you can make from these digits. The made number must be divisible by 2, 3, 5 without a residue. It is permitted to use not all digits from the set, it is forbidden to use leading zeroes.

Each digit is allowed to occur in the number the same number of times it occurs in the set.

Input

A single line contains a single integer n(1 ≤ n ≤ 100000) — the number of digits in the set. The second line contains n digits, the digits are separated by a single space.

Output

On a single line print the answer to the problem. If such number does not exist, then you should print -1.

Sample Input

Input
1
0
Output
0
Input
11
3 4 5 4 5 3 5 3 4 4 0
Output
5554443330
Input
8
3 2 5 1 5 2 2 3
Output
-1

就是给你n个数,让你求由这n个数组成的,能被2,3,5整除的的最大的数。


思路:

这道题本来是用来练手速的,没想到一做就是一个下午。最后还是看了BMan的代码才勉强AC的,不过看了BMan的代码之后,真的学到了很多的东西!例如,学到了CF里面有一个ONLINE_JUDGE的宏变量,可以利用条件编译来方便测设与提交!最重要的是学到了一个思路,那就是预处理的优美之处!

具体做法是:因为答案要能被3整除,所以各位数之和必须为3的倍数!如果是,直接输出;否则的话有两种可能:

1. sum % 3 == 1 这种情况只需在数列中找到一个num[i] % 3 == 1 的数去掉就可以咯,如果没有就找两个num[] % 3 == 2 去掉就可以了!

2..sum % 3 == 2,这种情况跟上一种是基本一致的,就不在赘述了!


这个题目有一个易错点,就是在判断前导0,BMan给出了一个很强大的做法,具体的做法请看代码实现:

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <string>
#include <algorithm>
#include <vector>
#define N 1000010using namespace std;void debug()
{
#ifdef ONLINE_JUDGE
#elsefreopen( "in.txt", "r", stdin );
#endif // JUDGE_ONLINE
}int main()
{debug();//freopen( "in.txt", "r", stdin );int n;while( scanf( "%d", &n ) != EOF ){int num[N] = {0};int vis[N];int sum = 0;memset( vis, 0, sizeof( vis ) );for( int i = 0; i < n; i++ ){scanf( "%d", &num[i] );sum += num[i];}sort( num, num + n, greater<int>() );if( sum % 3 == 1 ){for( int i = n-1; i >= 0; i-- ){if( num[i] % 3 == 1 ){vis[i] = 1;sum -= num[i];break;}}int two = 0;if( sum % 3 == 1 )//说明找不到num[i] % 3 == 1 的num{for( int i = n-1; i >= 0; i-- ){if( num[i] % 3 == 2 ){vis[i] = 1;if( ++two >= 2 ){break;}}}if( two != 2 ){printf( "-1\n" );continue;}}}if( sum % 3 == 2 ){for( int i = n-1; i >= 0; i-- ){if( num[i] % 3 == 2 ){vis[i] = 1;sum -= num[i];break;}}int one = 0;if( sum % 3 == 2 ){for( int i = n-1; i >= 0; i-- ){if( num[i] % 3 == 1 ){vis[i] = 1;if( ++one >= 2 ){break;}}}if( one != 2 ){printf( "-1\n" );continue;}}}int cnt = 0;for( int i = 0; i < n; i++ ){if( !vis[i] ){num[cnt++] = num[i];}}n = cnt;if( n == 0 || num[n-1] != 0 ){printf( "-1" );}else{int i = 0;while( i < n - 1 && num[i] == 0 )//判断前导0,如果一开始num[0]就等于0的话,由于已经进行了降序的排序,所以后面一定是0,这样的话与后面的代码结合就能够保证
//前导0的只输出一个0{i++;}for( ; i < n; i++ ){printf( "%d", num[i] );}}putchar( 10 );}return 0;
}

通过今天的学习,我发现学习大神们的代码对提升自己的编码能力是有着很大的帮助的!要多看别人的代码!!!

One Day One Step!

 

这篇关于Codeforce 214 Div 2 B.Hometask的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1053129

相关文章

Codeforces Round #240 (Div. 2) E分治算法探究1

Codeforces Round #240 (Div. 2) E  http://codeforces.com/contest/415/problem/E 2^n个数,每次操作将其分成2^q份,对于每一份内部的数进行翻转(逆序),每次操作完后输出操作后新序列的逆序对数。 图一:  划分子问题。 图二: 分而治之,=>  合并 。 图三: 回溯:

Codeforces Round #261 (Div. 2)小记

A  XX注意最后输出满足条件,我也不知道为什么写的这么长。 #define X first#define Y secondvector<pair<int , int> > a ;int can(pair<int , int> c){return -1000 <= c.X && c.X <= 1000&& -1000 <= c.Y && c.Y <= 1000 ;}int m

Codeforces Round #113 (Div. 2) B 判断多边形是否在凸包内

题目点击打开链接 凸多边形A, 多边形B, 判断B是否严格在A内。  注意AB有重点 。  将A,B上的点合在一起求凸包,如果凸包上的点是B的某个点,则B肯定不在A内。 或者说B上的某点在凸包的边上则也说明B不严格在A里面。 这个处理有个巧妙的方法,只需在求凸包的时候, <=  改成< 也就是说凸包一条边上的所有点都重复点都记录在凸包里面了。 另外不能去重点。 int

CSS实现DIV三角形

本文内容收集来自网络 #triangle-up {width: 0;height: 0;border-left: 50px solid transparent;border-right: 50px solid transparent;border-bottom: 100px solid red;} #triangle-down {width: 0;height: 0;bor

创建一个大的DIV,里面的包含两个DIV是可以自由移动

创建一个大的DIV,里面的包含两个DIV是可以自由移动 <body>         <div style="position: relative; background:#DDF8CF;line-height: 50px"> <div style="text-align: center; width: 100%;padding-top: 0px;"><h3>定&nbsp;位&nbsp;

Codeforces Round 971 (Div. 4) (A~G1)

A、B题太简单,不做解释 C 对于 x y 两个方向,每一个方向至少需要 x / k 向上取整的步数,取最大值。 由于 x 方向先移动,假如 x 方向需要的步数多于 y 方向的步数,那么最后 y 方向的那一步就不需要了,答案减 1 代码 #include <iostream>#include <algorithm>#include <vector>#include <string>

CF#271 (Div. 2) D.(dp)

D. Flowers time limit per test 1.5 seconds memory limit per test 256 megabytes input standard input output standard output 题目链接: http://codeforces.com/contest/474/problem/D We s

CF #278 (Div. 2) B.(暴力枚举+推导公式+数学构造)

B. Candy Boxes time limit per test 1 second memory limit per test 256 megabytes input standard input output standard output 题目链接: http://codeforces.com/contest/488/problem/B There

CF#278 (Div. 2) A.(暴力枚举)

A. Giga Tower time limit per test 1 second memory limit per test 256 megabytes input standard input output standard output 题目链接: http://codeforces.com/contest/488/problem/A Giga To

CF #283 (Div. 2) B.(字符串好多坑)

题目链接:http://codeforces.com/contest/496/problem/B 解题思路: 首先明确可以暴力,写一个add函数和shift函数。然后给一个循环值cnt,做cnt次循环即可,每次取两种情况的最小值入字符串数组,最后排下序,输出最小的字符串。 这个cnt很不好控制,我也是WA了几次才估计出来的······· 接下来说说奇葩的数据: Input: 1