Codeforces Round #202 (Div. 2) A,B

现在的位置: 首页 > 综合 > 正文

RSS

Codeforces Round #202 (Div. 2) A,B

2017年11月23日 ⁄ 综合 ⁄ 共 4196字 ⁄ 字号小中大 ⁄ 评论关闭

A. Cinema Line

time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

The new "Die Hard" movie has just been released! There are n people at the cinema box office standing in a huge line. Each of them has a single 100, 50 or 25 ruble bill. A "Die Hard" ticket costs 25 rubles. Can the booking clerk sell a ticket to each person and give the change if he initially has no money and sells the tickets strictly in the order people follow in the line?

Input

The first line contains integer n (1≤n≤105) — the number of people in the line. The next line contains n integers, each of them equals 25, 50 or 100 — the values of the bills the people have. The numbers are given in the order from the beginning of the line (at the box office) to the end of the line.

Output

Print "YES" (without the quotes) if the booking clerk can sell a ticket to each person and give the change. Otherwise print "NO".

Sample test(s)
input
4
25 25 50 50
output
YES
input
2
25 100
output
NO
input
4
50 50 25 25
output
NO

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

using namespace std;

int ershiwu,wushi,n,money;

int main()
{
    ershiwu=0,wushi=0;
    scanf("%d",&n);
    bool flag=true;
    while(n--)
    {
        scanf("%d",&money);
        if(money==25)
            ershiwu++;
        else if(money==50)
        {
            if(ershiwu-1>=0)
            {
                ershiwu--;
                wushi++;
            }
            else
            {
                flag=false; break;
            }
        }
        else if(money==100)
        {
            if(wushi>=1&&ershiwu>=1)
            {
                wushi--; ershiwu--;
            }
            else if(ershiwu>=3)
            {
                ershiwu-=3;
            }
            else
            {
                flag=false;break;
            }
        }
    }
    if(flag)
        puts("YES");
    else
        puts("NO");

return 0;
}

* This source code was highlighted by YcdoiT. ( style: Codeblocks )

B. Color the Fence

time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

Igor has fallen in love with Tanya. Now Igor wants to show his feelings and write a number on the fence opposite to Tanya's house. Igor thinks that the larger the number is, the more chance to win Tanya's heart he has.

Unfortunately, Igor could only get v liters of paint. He did the math and concluded that digit d requires ad liters of paint. Besides, Igor heard that Tanya doesn't like zeroes. That's why Igor won't use them in his number.

Help Igor find the maximum number he can write on the fence.

Input

The first line contains a positive integer v (0≤v≤106). The second line contains nine positive integers a1,a2,...,a9 (1≤ai≤105).

Output

Print the maximum number Igor can write on the fence. If he has too little paint for any digit (so, he cannot write anything), print -1.

Sample test(s)
input
5
5 4 3 2 1 2 3 4 5
output
55555
input
2
9 11 1 12 5 8 9 10 6
output
33
input
0
1 1 1 1 1 1 1 1 1
output
-1

先保证位数最大，然后使用余数尽量升级成大的数

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

using namespace std;

struct nim
{
    int valu;
    int cost;
    int deta;
}a[10];

bool cmp(nim a,nim b)
{
    if(a.cost!=b.cost)
    {
        return a.cost<b.cost;
    }
    else return a.valu>b.valu;
}

bool cmp2(nim a,nim b)
{
    if(a.valu!=b.valu)
    {
        return a.valu>b.valu;
    }
    else
    {
        return a.cost<b.cost;
    }
}

int number[12];

int main()
{
    int n;
    scanf("%d",&n);
    for(int i=0;i<9;i++)
    {
        a.valu=i+1;
        scanf("%d",&a.cost);
    }
    sort(a,a+9,cmp);

    if(n<a[0].cost)
    {
        puts("-1");
        return 0;
    }

    memset(number,0,sizeof(number));
    int number1=n/a[0].cost;
    int res=n%a[0].cost;
    number[a[0].valu]=number1;
    a[0].deta=0;
if(res!=0)
{
    for(int i=1;i<9;i++)
    {
        a.deta=a.cost-a[0].cost;
    }

    sort(a+1,a+9,cmp2);

    for(int i=1;i<9;i++)
    {
   //     printf("%d %d\n",a.valu,a.deta);
        if(a.valu>a[0].valu)
        while(res>=0)
        {
            if(res-a.deta<0) break;
            res-=a.deta;
            if(number[a[0].valu]-1>=0)
            {
                number[a[0].valu]--;
                number[a.valu]++;
            }
            else
            {
                break;
            }
        }
    }
}
    bool flag=false;
    for(int i=9;i>=1;i--)
    {
        while(number)
        {
            flag=true;
            printf("%d",i);
            number--;
        }
    }
    if(flag==false)
        printf("-1");
    putchar(10);
    return 0;
}

* This source code was highlighted by YcdoiT. ( style: Codeblocks )

【上篇】POJ 1947 Rebuilding Roads
【下篇】HDOJ 2929 Bigger is Better

作者: foggy

该日志由 foggy 于6年前发表在综合分类下，最后更新于 2017年11月23日.
转载请注明: Codeforces Round #202 (Div. 2) A,B | 学步园 +复制链接

抱歉!评论已关闭.

学步园

Codeforces Round #202 (Div. 2) A,B

作者: foggy

书签

最新文章New

本站推荐

返回首页