CodeForse#204(Div.2)まとめA,B,C

3002 ワード

A題:
0または5からなる数列を与え、0または5からなる数のうち、90で割り切れる数の最大値を求める.
ACコード:
#include <stdio.h>
#include <stdlib.h>
#include <math.h>

int main() {
    int n;
    while(scanf("%d", &n)!=EOF) {
        int tmp, cnt0 = 0, cnt5 = 0;
        for(int i = 1; i <= n; i++) {
            scanf("%d", &tmp);
            if(tmp == 0)
                cnt0++;
            else
                cnt5++;
        }
        if(cnt0 == 0)
            printf("-1
"); else if(cnt5 < 9) printf("0
"); else { for(int i = 1; i <= (cnt5/9)*9; i++) printf("5"); for(int i = 1; i <= cnt0; i++) printf("0"); } puts(""); } return 0; }

B題:
等差数列の条件を満たす値と差を求める数列を与える.
ACコード:
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <vector>
using namespace std;
const int maxn=100100;
int flag[maxn]; 
int t[maxn];    
struct node
{
    int c; 
    int d;
    bool flag;
}D[maxn];

int main()
{
    int n,x,len=0;
    cin>>n;
    memset(D,0,sizeof(D));
    memset(flag,0,sizeof(flag));
    memset(t,0,sizeof(t));
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&x);
        if(!flag[x])
        {
            t[len++]=x;
            flag[x]=1;
            D[x].c=i;
            D[x].d=0;
            D[x].flag=false;
        }
        else
        {
            if(D[x].d==0)
            {
                D[x].d=i-D[x].c;
                D[x].c=i;
            }
            else
            {
                if(i-D[x].c==D[x].d)    D[x].c=i;
                else    D[x].flag=true;
            }
        }
    }
    sort(t,t+len);
    //cout<<len<<endl;
    int ans=0;
    for(int i=0;i<len;i++)
    {
        int xx=t[i];
        if(!D[xx].flag) ans++;
    }
    cout<<ans<<endl;
    for(int i=0;i<len;i++)
    {
        int xx=t[i];
        if(!D[xx].flag)
            printf("%d %d
",xx,D[xx].d); } return 0; }

C題:
N*2個の数字を与え、その中のN個を上方に、N個を下方に、最後に得られた得数と元の数との差の絶対値を最小にする.
小数点以下の数字を考えると、これらの数がゼロでない場合はabs(原数小数部加算-1*n)、0を1つ多くするとmin(abs(原数小数部加算-1*n)、abs(原数小数部加算-1*(n-1))
ACコード:
#include <stdio.h>
#include <math.h>
#include <stdlib.h>
#include <algorithm>

#define INF 0x7fffffff;

using namespace std;

int main() {
    int n;
    scanf("%d", &n);
    int x, len = 0, sum = 0;
    for(int i = 0; i < n*2; i++) {
        scanf("%*d.%d", &x);
        sum += x;
        if(x == 0)
            len++;
    }
    int ans = INF;
    for(int i = 0; i <= len; i++)
        ans = min(ans, abs(sum - (1000*n - 1000*i)));
    printf("%d.%03d
", ans/1000, ans%1000); return 0; }