bzoj 1599: [Usaco2008 Oct]笨重的石子 (暴力)

2016-03-31 · 2 min read · brute force

1599: [Usaco2008 Oct]笨重的石子

Time Limit: 10 Sec Memory Limit: 162 MB Submit: 886 Solved: 614 [Submit][Status][Discuss]

Description

贝西喜欢棋盘游戏和角色扮演类游戏所以她说服Farmer John把她带到玩具店，在那里，她购买了三个不同的骰子，这三个质量均匀的骰子，分别有S1,S2,S3个面。(2 <= S1 <= 20; 2 <= S2 <= 20; 2 <= S3 <= 40). 贝西掷啊掷啊掷啊，想要知道出现几率最大的和是多少。问题给出三个骰子的面数，让你求出出现几率最大的和是多少。如果有很多种和出现的几率相同，那么就输出小的那一个。

Input

*第一行：三个由空格隔开的整数：s1,s2,s3

Output

*第一行：所要求的解

Sample Input

3 2 3

Sample Output

输出详解:

这里是所有可能的情况.

1 1 1 -> 3 1 2 1 -> 4 2 1 1 -> 4 2 2 1 -> 5 3 1 1 -> 5 3 2 1 -> 6

1 1 2 -> 4 1 2 2 -> 5 2 1 2 -> 5 2 2 2 -> 6 3 1 2 -> 6 3 2 2 -> 7

1 1 3 -> 5 1 2 3 -> 6 2 1 3 -> 6 2 2 3 -> 7 3 1 3 -> 7 3 2 3 -> 8

5和6出现的几率都是最大的，所以输出5.

暴力。。。

/* ***********************************************
Author :111qqz
Created Time :2016年03月31日 星期四 21时13分18秒
File Name :code/bzoj/1599.cpp
************************************************ */

 1#include <cstdio>
 2#include <cstring>
 3#include <iostream>
 4#include <algorithm>
 5#include <vector>
 6#include <queue>
 7#include <set>
 8#include <map>
 9#include <string>
10#include <cmath>
11#include <cstdlib>
12#include <ctime>
13#define fst first
14#define sec second
15#define lson l,m,rt<<1
16#define rson m+1,r,rt<<1|1
17#define ms(a,x) memset(a,x,sizeof(a))
18typedef long long LL;
19#define pi pair < int ,int >
20#define MP make_pair

 1using namespace std;
 2const double eps = 1E-8;
 3const int dx4[4]={1,0,0,-1};
 4const int dy4[4]={0,-1,1,0};
 5const int inf = 0x3f3f3f3f;
 6int s1,s2,s3;
 7double a[100];
 8int main()
 9{
10	#ifndef  ONLINE_JUDGE 
11	freopen("code/in.txt","r",stdin);
12  #endif
13	cin>>s1>>s2>>s3;
14	ms(a,0);
15	for ( int i = 1 ;i  <= s1 ; i++)
16	{
17	    for ( int j = 1 ; j <= s2 ; j++)
18	    {
19		for ( int k = 1 ; k <= s3 ; k++)
20		{
21		    a[i+j+k] += 1.0/s1+1.0/s2+1.0/s3;
22		}
23	    }
24	}

 1	double p = -1;
 2	int ans ;
 3	for ( int i = 3 ; i <= s1+s2+s3 ; i++)
 4	{
 5	    if (a[i]>p)
 6	    {
 7		p = a[i];
 8		ans = i ;
 9	    }
10	}

	cout<<ans<<endl;

1  #ifndef ONLINE_JUDGE  
2  fclose(stdin);
3  #endif
4    return 0;
5}