Codeforces Round #105 (Div. 2) (ABCDE题解)

2024-03-20 13:58

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

比赛链接:http://codeforces.com/contest/148

比较简单的一场,最长的一题也才写了30行多一点



A. Insomnia cure
time limit per test:2 seconds
memory limit per test:256 megabytes

«One dragon. Two dragon. Three dragon», — the princess was counting. She had trouble falling asleep, and she got bored of counting lambs when she was nine.

However, just counting dragons was boring as well, so she entertained herself at best she could. Tonight she imagined that all dragons were here to steal her, and she was fighting them off. Everyk-th dragon got punched in the face with a frying pan. Everyl-th dragon got his tail shut into the balcony door. Everym-th dragon got his paws trampled with sharp heels. Finally, she threatened everyn-th dragon to call her mom, and he withdrew in panic.

How many imaginary dragons suffered moral or physical damage tonight, if the princess counted a total ofd dragons?

Input

Input data contains integer numbers k, l, m, n and d, each number in a separate line (1 ≤ k, l, m, n ≤ 10,1 ≤ d ≤ 105).

Output

Output the number of damaged dragons.

Sample test(s)
Input
1
2
3
4
12
Output
12
Input
2
3
4
5
24
Output
17
Note

In the first case every first dragon got punched with a frying pan. Some of the dragons suffered from other reasons as well, but the pan alone would be enough.

In the second case dragons 1, 7, 11, 13, 17, 19 and 23 escaped unharmed.


题目大意:就是给四个数,和一个d,问1-d中有多少个数字不是那四个数的倍数


题目分析:爆搞


#include <cstdio>
#include <cstring>
int const MAX = 1e5;
bool has[MAX];int main()
{int a[4], d, cnt = 0;scanf("%d %d %d %d %d", &a[0], &a[1], &a[2], &a[3], &d);memset(has, false, sizeof(has));for(int i = 1; i <= d; i ++){for(int j = 0; j < 4; j++){if((i % a[j] == 0) && !has[i]){has[i] = true;cnt ++;}}}printf("%d\n", cnt);
}


B. Escape
time limit per test:2 seconds
memory limit per test:256 megabytes

The princess is going to escape the dragon's cave, and she needs to plan it carefully.

The princess runs at vp miles per hour, and the dragon flies atvd miles per hour. The dragon will discover the escape aftert hours and will chase the princess immediately. Looks like there's no chance to success, but the princess noticed that the dragon is very greedy and not too smart. To delay him, the princess decides to borrow a couple of bijous from his treasury. Once the dragon overtakes the princess, she will drop one bijou to distract him. In this case he will stop, pick up the item, return to the cave and spendf hours to straighten the things out in the treasury. Only after this will he resume the chase again from the very beginning.

The princess is going to run on the straight. The distance between the cave and the king's castle she's aiming for isc miles. How many bijous will she need to take from the treasury to be able to reach the castle? If the dragon overtakes the princess at exactly the same moment she has reached the castle, we assume that she reached the castle before the dragon reached her, and doesn't need an extra bijou to hold him off.

Input

The input data contains integers vp, vd, t, f andc, one per line (1 ≤ vp, vd ≤ 100,1 ≤ t, f ≤ 10, 1 ≤ c ≤ 1000).

Output

Output the minimal number of bijous required for the escape to succeed.

Sample test(s)
Input
1
2
1
1
10
Output
2
Input
1
2
1
1
8
Output
1
Note

In the first case one hour after the escape the dragon will discover it, and the princess will be 1 mile away from the cave. In two hours the dragon will overtake the princess 2 miles away from the cave, and she will need to drop the first bijou. Return to the cave and fixing the treasury will take the dragon two more hours; meanwhile the princess will be 4 miles away from the cave. Next time the dragon will overtake the princess 8 miles away from the cave, and she will need the second bijou, but after this she will reach the castle without any further trouble.

The second case is similar to the first one, but the second time the dragon overtakes the princess when she has reached the castle, and she won't need the second bijou.


题目大意:龙追公主,龙的速度为vd mile/h,公主速度为vp mile/h,龙在t小时后发现公主从老巢逃跑并开始追,一旦龙追上公主,公主可以丢个东西,这时候龙要拿着这个东西回老巢再用f小时研究它,然后重新出发开始追公主,龙的老巢和王宫相距c mile,问公主最少要准备多少个这样的东西才能安全回王宫,如果龙和公主同时到王宫,算公主已经安全到达


题目分析:完完全全的一个小模拟,根据题意模拟即可


#include <cstdio>int main()
{double vp, vd, t, f, c;int ans = 0;scanf("%lf %lf %lf %lf %lf", &vp, &vd, &t, &f, &c);if(vp >= vd) //公主比龙快,显然不需要多余的物品{printf("0\n");return 0;}double cur = 0, t1, t2; //cur表示当前公主跑了多远cur = t * vp;   //龙发现公主逃跑时,公主的位置t2 = cur / (vd - vp); //龙第一次追到公主花的时间cur += t2 * vp; //龙第一次追到公主的位置while(cur < c)  //一个循环表示龙追到公主一次{ans ++;     t1 = cur / vd + f;  //龙回去并研究完物品花的时间t1cur += t1 * vp;     //t1时间公主又跑了t1*vp milet2 = cur / (vd - vp);   //龙第i次追到公主的时间cur += t2 * vp;     //龙第i次追到公主时的位置}printf("%d\n",ans);
}



C. Terse princess
time limit per test:2 seconds
memory limit per test:256 megabytes

«Next please», — the princess called and cast an estimating glance at the next groom.

The princess intends to choose the most worthy groom, this is, the richest one. Whenever she sees a groom who is more rich than each of the previous ones, she says a measured «Oh...». Whenever the groom is richer than all previous ones added together, she exclaims «Wow!» (no «Oh...» in this case). At the sight of the first groom the princess stays calm and says nothing.

The fortune of each groom is described with an integer between 1 and 50000. You know that during the day the princess sawn grooms, said «Oh...» exactly a times and exclaimed «Wow!» exactly b times. Your task is to output a sequence ofn integers t1, t2, ..., tn, whereti describes the fortune ofi-th groom. If several sequences are possible, output any of them. If no sequence exists that would satisfy all the requirements, output a single number-1.

Input

The only line of input data contains three integer numbersn, a and b (1 ≤ n ≤ 100, 0 ≤ a, b ≤ 15, n > a + b), separated with single spaces.

Output

Output any sequence of integers t1, t2, ..., tn, whereti (1 ≤ ti ≤ 50000) is the fortune ofi-th groom, that satisfies the given constraints. If no sequence exists that would satisfy all the requirements, output a single number-1.

Sample test(s)
Input
10 2 3
Output
5 1 3 6 16 35 46 4 200 99
Input
5 0 0
Output
10 10 6 6 5
Note

Let's have a closer look at the answer for the first sample test.

  • The princess said «Oh...» (highlighted in bold): 5 1 36 16 35 46 4 200 99.
  • The princess exclaimed «Wow!» (highlighted in bold): 5 1 3 616 35 46 4 200 99.

题目大意:构造一个n个数的序列,满足公主叫了a次Oh和b次Wow,公主遇到一个数字,这个数字比前面的所有数字都大时她会叫Oh,公主遇到一个数字,这个数字比前面所有数字的和都大时,公主会叫Wow,叫Wow的话就不叫Oh了,构造的数字不能大于5万,如果不存在则输出-1


题目分析:首先明确一点,前两个数字,如果第二个比第一个大,这种情况公主会叫Wow,这题构造方法不唯一,最简单的应该是二进制法,举个例子比如b等于3这时候我们就可以构造0001,0010,0100,1000,0001+0010 = 0011正好比0100小1,同理0001+0010+0100 = 0111,正好比1000小1,又b最大为15,所以构造b的值最大到2^15=32768,然后构造a就方便了,直接往后依次加1即可,构造完a,b,剩下来的数全都等于构造a时的最后一个数即可


#include <cstdio>
int ans[105];int main()
{int a, b, n, cur = 1;scanf("%d %d %d", &n, &a, &b);ans[1] = 1;for(int i = 2; i <= n; i++){if(b){ans[i] = 1 << (i - 1);b --;}else if(a && i > 2){ans[i] = ans[i - 1] + 1;a --;}elseans[i] = ans[i - 1];   }if(a || b)printf("-1\n");else {for(int i = 1; i < n; i++)printf("%d ",ans[i]);printf("%d\n", ans[n]);}
}



D. Bag of mice
time limit per test:2 seconds
memory limit per test:256 megabytes

The dragon and the princess are arguing about what to do on the New Year's Eve. The dragon suggests flying to the mountains to watch fairies dancing in the moonlight, while the princess thinks they should just go to bed early. They are desperate to come to an amicable agreement, so they decide to leave this up to chance.

They take turns drawing a mouse from a bag which initially containsw white and b black mice. The person who is the first to draw a white mouse wins. After each mouse drawn by the dragon the rest of mice in the bag panic, and one of them jumps out of the bag itself (the princess draws her mice carefully and doesn't scare other mice).Princess draws first. What is the probability of the princess winning?

If there are no more mice in the bag and nobody has drawn a white mouse, the dragon wins. Mice which jump out of the bag themselves are not considered to be drawn (do not define the winner). Once a mouse has left the bag, it never returns to it. Every mouse is drawn from the bag with the same probability as every other one, and every mouse jumps out of the bag with the same probability as every other one.

Input

The only line of input data contains two integersw and b (0 ≤ w, b ≤ 1000).

Output

Output the probability of the princess winning. The answer is considered to be correct if its absolute or relative error does not exceed10 - 9.

Sample test(s)
Input
1 3
Output
0.500000000
Input
5 5
Output
0.658730159
Note

Let's go through the first sample. The probability of the princess drawing a white mouse on her first turn and winning right away is 1/4. The probability of the dragon drawing a black mouse and not winning on his first turn is 3/4 * 2/3 = 1/2. After this there are two mice left in the bag — one black and one white; one of them jumps out, and the other is drawn by the princess on her second turn. If the princess' mouse is white, she wins (probability is 1/2 * 1/2 = 1/4), otherwise nobody gets the white mouse, so according to the rule the dragon wins.



题目大意:公主和龙抓老鼠,老鼠有w只白的,b只黑的,先抓到白老鼠的赢,龙每次抓完一只老鼠后会多跑出去一只老鼠,一旦没有老鼠或者没人抓到白老鼠,则算公主输,公主和龙抓的老鼠是黑或白是等可能的,龙抓完跑掉的老鼠是黑或白也是等可能的,现在公主先抓,要求公主赢的概率


题目分析:比较好想的一道概率dp,dp[i][j]表示还剩i只白老鼠和j只黑老鼠时公主赢的概率,这里只需要推公主赢的情况即可,显然有三种情况公主会赢或者还有赢的可能

注意每一轮是按顺序执行的,即公主先抓,龙再抓,老鼠再跑,注意每次还剩多少

第一:公主抓到白老鼠  dp[i][j] += i / (i + j)

第二:公主和龙都抓到黑老鼠,跑出去的是黑老鼠  dp[i][j] = ( j / (i + j) ) * ( (j - 1) / (i + j - 1) * (j - 2) / (i + j - 2) ) * dp[i][j - 3] (减3是因为这种情况下需要至少三只黑老鼠)

第三:公主和龙都抓到黑老鼠,跑出去的是白老鼠  dp[i][j] = ( j / (i + j) ) * ( (j - 1) / (i + j - 1) * i / (i + j - 2) ) * dp[i - 1][j - 2]

注意初始化,没有白老鼠,dp[0][i] = 0,没有黑老鼠dp[i][0] = 1,一只老鼠都没有dp[0][0] = 0

最后答案是dp[w][b]


#include <cstdio>
#include <cstring>
int const MAX = 1005;
double dp[MAX][MAX];int main()
{int w, b;memset(dp, 0, sizeof(dp));scanf("%d %d", &w, &b);for(int i = 0; i <= b; i ++)dp[0][i] = 0;for(int i = 1; i <= w; i++)dp[i][0] = 1.0;for(int i = 1; i <= w; i++){for(int j = 1; j <= b; j++){dp[i][j] += (double) i / (i + j);if(j >= 2)dp[i][j] += (double) j / (i + j) * (double) (j - 1) / (i + j - 1) * (double) i / (i + j - 2) * dp[i - 1][j - 2];if(j >= 3)dp[i][j] += (double) j / (i + j) * (double) (j - 1) / (i + j - 1) * (double) (j - 2) / (i + j - 2) * dp[i][j - 3];}}printf("%.9f\n", dp[w][b]);
}



E. Porcelain
time limit per test:3 seconds
memory limit per test:256 megabytes

During her tantrums the princess usually smashes some collectable porcelain. Every furious shriek is accompanied with one item smashed.

The collection of porcelain is arranged neatly onn shelves. Within each shelf the items are placed in one row, so that one can access only the outermost items — the leftmost or the rightmost item, not the ones in the middle of the shelf. Once an item is taken, the next item on that side of the shelf can be accessed (see example). Once an item is taken, it can't be returned to the shelves.

You are given the values of all items. Your task is to find the maximal damage the princess' tantrum ofm shrieks can inflict on the collection of porcelain.

Input

The first line of input data contains two integersn (1 ≤ n ≤ 100) andm (1 ≤ m ≤ 10000). The nextn lines contain the values of the items on the shelves: the first number gives the number of items on this shelf (an integer between1 and 100, inclusive), followed by the values of the items (integers between1 and 100, inclusive), in the order in which they appear on the shelf (the first number corresponds to the leftmost item, the last one — to the rightmost one). The total number of items is guaranteed to be at least m.

Output

Output the maximal total value of a tantrum of m shrieks.

Sample test(s)
Input
2 3
3 3 7 2
3 4 1 5
Output
15
Input
1 3
4 4 3 1 2
Output
9
Note

In the first case there are two shelves, each with three items. To maximize the total value of the items chosen, one can take two items from the left side of the first shelf and one item from the right side of the second shelf.

In the second case there is only one shelf, so all three items are taken from it — two from the left side and one from the right side.


题目大意:给n层数字,一共要取m次,每次取数字只能从任意一层的最左或最右取

题目分析:预处理出每层取j (j <= m)个的最大值,之后就是个普通的多重背包问题


#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int sum[105], ma[105], dp[10005];int main()
{int n, m;scanf("%d %d", &n, &m);for(int i = 1; i <= n; i++){int num;scanf("%d", &num);for(int j = 1; j <= num; j++){int tmp;scanf("%d", &tmp);sum[j] = sum[j - 1] + tmp;  //计算前缀和}//预处理memset(ma, 0, sizeof(ma));for(int j = 0; j <= num; j++)for(int k = 0; k <= j; k++)ma[j] = max(ma[j], sum[k] + sum[num] - sum[num + k - j]);printf("\n");//多重背包for(int j = m; j >= 1; j--)for(int k = 1; k <= min(j, num); k ++)dp[j] = max(dp[j], dp[j - k] + ma[k]);}printf("%d\n", dp[m]);
}

这篇关于Codeforces Round #105 (Div. 2) (ABCDE题解)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



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

相关文章

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 Beta Round #47 C凸包 (最终写法)

题意慢慢看。 typedef long long LL ;int cmp(double x){if(fabs(x) < 1e-8) return 0 ;return x > 0 ? 1 : -1 ;}struct point{double x , y ;point(){}point(double _x , double _y):x(_x) , y(_y){}point op

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

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

C++ | Leetcode C++题解之第393题UTF-8编码验证

题目: 题解: class Solution {public:static const int MASK1 = 1 << 7;static const int MASK2 = (1 << 7) + (1 << 6);bool isValid(int num) {return (num & MASK2) == MASK1;}int getBytes(int num) {if ((num &

Codeforces 482B 线段树

求是否存在这样的n个数; m次操作,每次操作就是三个数 l ,r,val          a[l] & a[l+1] &......&a[r] = val 就是区间l---r上的与的值为val 。 也就是意味着区间[L , R] 每个数要执行 | val 操作  最后判断  a[l] & a[l+1] &......&a[r] 是否= val import ja

C语言 | Leetcode C语言题解之第393题UTF-8编码验证

题目: 题解: static const int MASK1 = 1 << 7;static const int MASK2 = (1 << 7) + (1 << 6);bool isValid(int num) {return (num & MASK2) == MASK1;}int getBytes(int num) {if ((num & MASK1) == 0) {return

C - Word Ladder题解

C - Word Ladder 题解 解题思路: 先输入两个字符串S 和t 然后在S和T中寻找有多少个字符不同的个数(也就是需要变换多少次) 开始替换时: tips: 字符串下标以0开始 我们定义两个变量a和b,用于记录当前遍历到的字符 首先是判断:如果这时a已经==b了,那么就跳过,不用管; 如果a大于b的话:那么我们就让s中的第i项替换成b,接着就直接输出S就行了。 这样

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

【秋招笔试】9.07米哈游秋招改编题-三语言题解

🍭 大家好这里是 春秋招笔试突围,一起备战大厂笔试 💻 ACM金牌团队🏅️ | 多次AK大厂笔试 | 大厂实习经历 ✨ 本系列打算持续跟新 春秋招笔试题 👏 感谢大家的订阅➕ 和 喜欢💗 和 手里的小花花🌸 ✨ 笔试合集传送们 -> 🧷春秋招笔试合集 🍒 本专栏已收集 100+ 套笔试题,笔试真题 会在第一时间跟新 🍄 题面描述等均已改编,如果和你笔试题看到的题面描述