首页 > ACM题库 > HDU-杭电 > HDU 3131-One…Two…Five![解题报告]HOJ
2014
03-03

HDU 3131-One…Two…Five![解题报告]HOJ

One…Two…Five!

问题描述 :


Sir Bedavere’s Bogus Division Solutions

The set of integers has rarely been a domain of error in everyday conversation. The king, however, is "three blind" and cannot visualize any number containing the digit ’3′ in its base 10 representation. He does intuitively sense the number between 2 and 4 and compensates for his blindness in the following manner: whenever he wants to state any number containing the digit ’3′, he will speak a series of numbers until they can all be combined (in the order given) via addition, subtraction, multiplication and division to produce the desired value which contains the digit ’3′. Mathematical operators work from left to right without any other regard for order of precedence (i.e. 6 + 7 * 11 = 143 –> a number with a ’3′).

For example, if the king says "1 2 5", then a knight will say ’3′ using the following logic:

1 2 5 = 1 * 2 � 5 = 2 � 5 = |2 � 5| = 3

Note that there are no negative numbers in optimistic Camelot. Every subtraction will produce a nonnegative result by what is called, in these enlightened times, the absolute value. All division is integer division, i.e. 7/5 = 1. Obviously, if the number zero appears as a divisor, then division will not be attempted.

The court, however, has a problem. Some of the computations produce more than 1 number containing the digit ’3′! You have been appointed to write a program which computes and displays the most frequently appearing number containing the digit ’3′. In the event of a tie, use the largest number.

输入:

The input will consist of an unspecified number of lines. Each line will contain at least 1 and at most 9 integers. Every number will be nonnegative and less than 100. A line with a single ‘#’ character will be the end of input.

输出:

The input will consist of an unspecified number of lines. Each line will contain at least 1 and at most 9 integers. Every number will be nonnegative and less than 100. A line with a single ‘#’ character will be the end of input.

样例输入:

1 2 5
1 1
6 5 1
#

样例输出:

3
No result
30

#pragma comment(linker,"/STACK:102400000,102400000")
#include <cctype>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <iostream>
#include <fstream>
#include <string>
#include <algorithm>
#include <functional>
#include <numeric>
#include <deque>
#include <list>
#include <map>
#include <queue>
#include <vector>
#include <set>
#include <stack>
#include <iterator>
#include <memory>
#include <utility>
#include <string>

using namespace std;

#define X first
#define Y second
#define mp make_pair
#define pb push_back
#define mset(a) memset(a,0,sizeof(a))
#define mmset(a) memset(a,-1,sizeof(a))
#define mcpy(a,b) memcpy(a,b,sizeof(a))
#define lowbit(a) ((a)&(-(a)))

typedef double lf;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<lf,lf> pdd;
typedef pair<int,pii> pip;
typedef pair<pii,int> ppi;
typedef vector<int> vi;
typedef vector<pii> vpii;

const int inf=1000000007;
const ll linf=1LL<<62;
const ull ulinf=1ULL<<63;
const lf eps=0.000001;
const lf pi=3.14159265358979323846;

template <class T> T abs(T a){return a>=0?a:-a;}
template <class T> T sqr(T a){return a*a;}
template <class T> T gcd(T a,T b){return b?gcd(b,a%b):a;}
template <class T> T mod(T a,T b){return (a%b+b)%b;}
ll powmod(ll a,ll b,ll c){if(b==0LL)return 1LL;ll ret=powmod(a,b>>1,c);ret=ret*ret%c;if(b&1LL)ret=ret*a%c;return ret;}
ll inv(ll a,ll b){return powmod(a,b-2LL,b);}
template <class T> void maxe(T &a,T b){if(a<b)a=b;}
template <class T> void mine(T &a,T b){if(a>b)a=b;}
int iszero(lf a){return abs(a)<=eps;}

template <class T> void geti(T &a){a=0;T b=1;char c=getchar();if(c=='-')b=-1;else a=c-48;while((c=getchar())!=' '&&c!='\n')a=a*10+c-48;a*=b;}

void fileio_in_out(){freopen(".in","r",stdin);freopen(".out","w",stdout);}
void fileio_txt(){freopen("input.txt","r",stdin);freopen("output.txt","w",stdout);}

//==================================================

#define DEBUG(X) 

const int N=222;
const int M=1111111;
const int K=9;

int test;
int n,m,k;
ll ans;
char s[N];
ll a[11];
int b[11];
map<ll,int> cnt;
ll stka[11];
int stkb[11];
int topa,topb;

int check(ll k)
{
    while(k)
    {
        if(k%10==3)
            return 1;
        k/=10;
    }
    return 0;
}

void work(int st)
{
    //printf("%d\n",st);
    ll t=a[1];
    for(int i=2;i<=n;i++)
    {
        b[i]=st&3;
        st>>=2;
        if(b[i]==0)
            t+=a[i];
        if(b[i]==1)
            t=abs(t-a[i]);
        if(b[i]==2)
            t*=a[i];
        if(b[i]==3)
        {
            if(a[i]==0)
                return;
            t/=a[i];
        }
        //printf("%d %I64d\n",b[i],t);
    }
    if(check(t))
        cnt[t]++;
}

int main()
{
    //fileio_in_out();
    //fileio_txt();
    //ios::sync_with_stdio(false);
    
    while(1)
    {
        gets(s);
        if(s[0]=='#')
            break;
        a[n=1]=0;
        for(int i=0;s[i];i++)
        {
            if(s[i]==' ')
                a[++n]=0;
            else
                a[n]=a[n]*10+s[i]-'0';
        }
        cnt.clear();
        int m=1<<((n-1)<<1);
        for(int i=0;i<m;i++)
            work(i);
        if(cnt.size())
        {
            k=0;
            for(map<ll,int>::iterator it=cnt.begin();it!=cnt.end();it++)
                if(it->Y>k||(it->Y==k&&it->X>ans))
                {
                    ans=it->X;
                    k=it->Y;
                }
            printf("%I64d\n",ans);
        }
        else
            puts("No result");
    }
    
    //system("pause");
    return 0;
}

  1. #include <stdio.h>
    int main(void)
    {
    int arr[] = {10,20,30,40,50,60};
    int *p=arr;
    printf("%d,%d,",*p++,*++p);
    printf("%d,%d,%d",*p,*p++,*++p);
    return 0;
    }

    为什么是 20,20,50,40,50. 我觉得的应该是 20,20,40,40,50 . 谁能解释下?

  2. 第二种想法,我想来好久,为啥需要一个newhead,发现是把最后一个节点一直返回到嘴上面这层函数。厉害,这道题之前没样子想过。

  3. Good task for the group. Hold it up for every yeara??s winner. This is a excellent oppotunity for a lot more enhancement. Indeed, obtaining far better and much better is constantly the crucial. Just like my pal suggests on the truth about ab muscles, he just keeps obtaining much better.

  4. int half(int *array,int len,int key)
    {
    int l=0,r=len;
    while(l<r)
    {
    int m=(l+r)>>1;
    if(key>array )l=m+1;
    else if(key<array )r=m;
    else return m;
    }
    return -1;
    }
    这种就能避免一些Bug
    l,m,r
    左边是l,m;右边就是m+1,r;