Codeforces Round #379 (Div. 2) A B C D 水 二分 模拟

时间:2022-09-03 17:47:49
A. Anton and Danik
time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard output

Anton likes to play chess, and so does his friend Danik.

Once they have played n games in a row. For each game it's known who was the winner — Anton or Danik. None of the games ended with a tie.

Now Anton wonders, who won more games, he or Danik? Help him determine this.

Input

The first line of the input contains a single integer n (1 ≤ n ≤ 100 000) — the number of games played.

The second line contains a string s, consisting of n uppercase English letters 'A' and 'D' — the outcome of each of the games. The i-th character of the string is equal to 'A' if the Anton won the i-th game and 'D' if Danik won the i-th game.

Output

If Anton won more games than Danik, print "Anton" (without quotes) in the only line of the output.

If Danik won more games than Anton, print "Danik" (without quotes) in the only line of the output.

If Anton and Danik won the same number of games, print "Friendship" (without quotes).

Examples
Input
6
ADAAAA
Output
Anton
Input
7
DDDAADA
Output
Danik
Input
6
DADADA
Output
Friendship
Note

In the first sample, Anton won 6 games, while Danik — only 1. Hence, the answer is "Anton".

In the second sample, Anton won 3 games and Danik won 4 games, so the answer is "Danik".

In the third sample, both Anton and Danik won 3 games and the answer is "Friendship".

题意:水

题解:

 #include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<map>
#define __int64 ll
using namespace std;
int n;
char a;
int s=,b=;
int main()
{
scanf("%d",&n);
s=;
b=;
getchar();
for(int i=; i<=n; i++)
{
scanf("%c",&a);
if(a=='A')
s++;
else
b++;
}
if(s>b)
cout<<"Anton"<<endl;
if(s<b)
cout<<"Danik"<<endl;
if(s==b)
cout<<"Friendship"<<endl;
return ;
}
B. Anton and Digits
time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard output

Recently Anton found a box with digits in his room. There are k2 digits 2, k3 digits 3, k5 digits 5 and k6 digits 6.

Anton's favorite integers are 32 and 256. He decided to compose this integers from digits he has. He wants to make the sum of these integers as large as possible. Help him solve this task!

Each digit can be used no more than once, i.e. the composed integers should contain no more than k2 digits 2, k3 digits 3 and so on. Of course, unused digits are not counted in the sum.

Input

The only line of the input contains four integers k2, k3, k5 and k6 — the number of digits 2, 3, 5 and 6 respectively (0 ≤ k2, k3, k5, k6 ≤ 5·106).

Output

Print one integer — maximum possible sum of Anton's favorite integers that can be composed using digits from the box.

Examples
Input
5 1 3 4
Output
800
Input
1 1 1 1
Output
256
Note

In the first sample, there are five digits 2, one digit 3, three digits 5 and four digits 6. Anton can compose three integers 256 and one integer 32 to achieve the value 256 + 256 + 256 + 32 = 800. Note, that there is one unused integer 2 and one unused integer 6. They are not counted in the answer.

In the second sample, the optimal answer is to create on integer 256, thus the answer is 256.

题意:水

题解:

 #include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<map>
#define ll __int64
using namespace std;
ll a,b,c,d;
int main()
{
scanf("%I64d %I64d %I64d %I64d",&a,&b,&c,&d);
ll minx=;
minx=min(a,min(c,d));
ll ling=;
ll exm=max(ling,a-minx);
ll minx1=min(exm,b);
cout<<minx*+minx1*<<endl;
return ;
}
C. Anton and Making Potions
time limit per test

4 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

Anton is playing a very interesting computer game, but now he is stuck at one of the levels. To pass to the next level he has to prepare n potions.

Anton has a special kettle, that can prepare one potions in x seconds. Also, he knows spells of two types that can faster the process of preparing potions.

  1. Spells of this type speed up the preparation time of one potion. There are m spells of this type, the i-th of them costs bi manapoints and changes the preparation time of each potion to ai instead of x.
  2. Spells of this type immediately prepare some number of potions. There are k such spells, the i-th of them costs di manapoints and instantly create ci potions.

Anton can use no more than one spell of the first type and no more than one spell of the second type, and the total number of manapoints spent should not exceed s. Consider that all spells are used instantly and right before Anton starts to prepare potions.

Anton wants to get to the next level as fast as possible, so he is interested in the minimum number of time he needs to spent in order to prepare at least n potions.

Input

The first line of the input contains three integers n, m, k (1 ≤ n ≤ 2·109, 1 ≤ m, k ≤ 2·105) — the number of potions, Anton has to make, the number of spells of the first type and the number of spells of the second type.

The second line of the input contains two integers x and s (2 ≤ x ≤ 2·109, 1 ≤ s ≤ 2·109) — the initial number of seconds required to prepare one potion and the number of manapoints Anton can use.

The third line contains m integers ai (1 ≤ ai < x) — the number of seconds it will take to prepare one potion if the i-th spell of the first type is used.

The fourth line contains m integers bi (1 ≤ bi ≤ 2·109) — the number of manapoints to use the i-th spell of the first type.

There are k integers ci (1 ≤ ci ≤ n) in the fifth line — the number of potions that will be immediately created if the i-th spell of the second type is used. It's guaranteed that ci are not decreasing, i.e. ci ≤ cj if i < j.

The sixth line contains k integers di (1 ≤ di ≤ 2·109) — the number of manapoints required to use the i-th spell of the second type. It's guaranteed that di are not decreasing, i.e. di ≤ dj if i < j.

Output

Print one integer — the minimum time one has to spent in order to prepare n potions.

Examples
Input
20 3 2
10 99
2 4 3
20 10 40
4 15
10 80
Output
20
Input
20 3 2
10 99
2 4 3
200 100 400
4 15
100 800
Output
200
Note

In the first sample, the optimum answer is to use the second spell of the first type that costs 10 manapoints. Thus, the preparation time of each potion changes to 4 seconds. Also, Anton should use the second spell of the second type to instantly prepare 15 potions spending 80 manapoints. The total number of manapoints used is 10 + 80 = 90, and the preparation time is 4·5 = 20 seconds (15 potions were prepared instantly, and the remaining 5 will take 4 seconds each).

In the second sample, Anton can't use any of the spells, so he just prepares 20 potions, spending 10 seconds on each of them and the answer is 20·10 = 200.

题意:

题解:枚举第一种魔法 二分第二种魔法 取最优解

 #include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<map>
#define ll __int64
using namespace std;
ll n,m,k;
ll x,s;
struct node
{
ll w;
ll cost;
} N[],M[],zha[];
bool check(int xx,ll cc)
{
if(M[xx].cost<=cc)
return true;
else
return false;
}
int main()
{
scanf("%I64d %I64d %I64d",&n,&m,&k);
scanf("%I64d %I64d",&x,&s);
N[].w=x;
N[].cost=;
M[].w=;
M[].cost=;
for(int i=; i<=m; i++)
scanf("%I64d",&N[i].w);
for(int i=; i<=m; i++)
scanf("%I64d",&N[i].cost);
for(int i=; i<=k; i++)
scanf("%I64d",&M[i].w);
for(int i=; i<=k; i++)
scanf("%I64d",&M[i].cost);
ll ans=n*x;
for(int i=; i<=m; i++)
{
if((s-N[i].cost)>=){
int l=,r=k,mid;
int aaa=;
while(l<=r)
{
mid=(l+r)/;
if(check(mid,s-N[i].cost))
{
aaa=mid;
l=mid+;
}
else
{
r=mid-;
}
}
if(M[aaa].w>=n)
ans=;
else
ans=min(ans,N[i].w*(n-M[aaa].w));
}
}
printf("%I64d\n",ans);
return ;
}
D. Anton and Chess
time limit per test

4 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

Anton likes to play chess. Also, he likes to do programming. That is why he decided to write the program that plays chess. However, he finds the game on 8 to 8 board to too simple, he uses an infinite one instead.

The first task he faced is to check whether the king is in check. Anton doesn't know how to implement this so he asks you to help.

Consider that an infinite chess board contains one white king and the number of black pieces. There are only rooks, bishops and queens, as the other pieces are not supported yet. The white king is said to be in check if at least one black piece can reach the cell with the king in one move.

Help Anton and write the program that for the given position determines whether the white king is in check.

Remainder, on how do chess pieces move:

  • Bishop moves any number of cells diagonally, but it can't "leap" over the occupied cells.
  • Rook moves any number of cells horizontally or vertically, but it also can't "leap" over the occupied cells.
  • Queen is able to move any number of cells horizontally, vertically or diagonally, but it also can't "leap".
Input

The first line of the input contains a single integer n (1 ≤ n ≤ 500 000) — the number of black pieces.

The second line contains two integers x0 and y0 ( - 109 ≤ x0, y0 ≤ 109) — coordinates of the white king.

Then follow n lines, each of them contains a character and two integers xi and yi ( - 109 ≤ xi, yi ≤ 109) — type of the i-th piece and its position. Character 'B' stands for the bishop, 'R' for the rook and 'Q' for the queen. It's guaranteed that no two pieces occupy the same position.

Output

The only line of the output should contains "YES" (without quotes) if the white king is in check and "NO" (without quotes) otherwise.

Examples
Input
2
4 2
R 1 1
B 1 5
Output
YES
Input
2
4 2
R 3 3
B 1 5
Output
NO
Note

Picture for the first sample:

Codeforces Round #379 (Div. 2) A B C D 水 二分 模拟White king is in check, because the black bishop can reach the cell with the white king in one move. The answer is "YES".

Picture for the second sample:

Codeforces Round #379 (Div. 2) A B C D 水 二分 模拟Here bishop can't reach the cell with the white king, because his path is blocked by the rook, and the bishop cant "leap" over it. Rook can't reach the white king, because it can't move diagonally. Hence, the king is not in check and the answer is "NO".

题意:国际象棋中 判断king是否被check

题解:模拟 找的8个方向最近的棋子

 #include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<map>
#define ll __int64
using namespace std;
int n;
ll x,y;
ll xx[],yy[];
char a[];
int main()
{
scanf("%d",&n);
scanf("%I64d %I64d",&x,&y);
a[]='#';
for(int i=;i<=n;i++){
getchar();
scanf("%c %I64d %I64d",&a[i],&xx[i],&yy[i]);}
int s1=,s2=,s3=,s4=,s5=,s6=,s7=,s8=;
ll minx=1e10;
for(int i=;i<=n;i++)
{
if(xx[i]==x&&yy[i]>y){
if(minx>yy[i]){
s1=i;
minx=yy[i];
}
}
}
minx=-1e10;
for(int i=;i<=n;i++)
{
if(xx[i]==x&&yy[i]<y){
if(minx<yy[i]){
s2=i;
minx=yy[i];
}
}
}
minx=1e10;
for(int i=;i<=n;i++)
{
if(xx[i]>x&&yy[i]==y){
if(minx>xx[i]){
s3=i;
minx=xx[i];
}
}
}
minx=-1e10;
for(int i=;i<=n;i++)
{
if(xx[i]<x&&yy[i]==y){
if(minx<xx[i]){
s4=i;
minx=xx[i];
}
}
}
minx=1e10;
for(int i=;i<=n;i++)
{
if(xx[i]>x&&yy[i]>y&&(xx[i]-yy[i])==(x-y)){
if(minx>yy[i]){
s5=i;
minx=yy[i];
}
}
}
minx=-1e10;
for(int i=;i<=n;i++)
{
if(xx[i]<x&&yy[i]<y&&(xx[i]-yy[i])==(x-y)){
if(minx<yy[i]){
s6=i;
minx=yy[i];
}
}
}
minx=-1e10;
for(int i=;i<=n;i++)
{
if(xx[i]>x&&yy[i]<y&&(xx[i]+yy[i])==(x+y)){
if(minx<yy[i]){
s7=i;
minx=yy[i];
}
}
}
minx=1e10;
for(int i=;i<=n;i++)
{
if(xx[i]<x&&yy[i]>y&&(xx[i]+yy[i])==(x+y)){
if(minx>yy[i]){
s8=i;
minx=yy[i];
}
}
}
if((s1!=&&a[s1]!='B')||(s2!=&&a[s2]!='B')||(s3!=&&a[s3]!='B')
||(s4!=&&a[s4]!='B')||(s5!=&&a[s5]!='R')
||(s6!=&&a[s6]!='R')||(s7!=&&a[s7]!='R')||(s8!=&&a[s8]!='R'))
cout<<"YES"<<endl;
else
cout<<"NO"<<endl;
return ;
}

Codeforces Round #379 (Div. 2) A B C D 水 二分 模拟的更多相关文章

  1. Codeforces Round &num;379 &lpar;Div&period; 2&rpar; D&period; Anton and Chess 水题

    D. Anton and Chess 题目连接: http://codeforces.com/contest/734/problem/D Description Anton likes to play ...

  2. Codeforces Round &num;379 &lpar;Div&period; 2&rpar; B&period; Anton and Digits 水题

    B. Anton and Digits 题目连接: http://codeforces.com/contest/734/problem/B Description Recently Anton fou ...

  3. Codeforces Round &num;379 &lpar;Div&period; 2&rpar; A&period; Anton and Danik 水题

    A. Anton and Danik 题目连接: http://codeforces.com/contest/734/problem/A Description Anton likes to play ...

  4. Codeforces Round &num;379 &lpar;Div&period; 2&rpar; C&period; Anton and Making Potions —— 二分

    题目链接:http://codeforces.com/contest/734/problem/C C. Anton and Making Potions time limit per test 4 s ...

  5. Codeforces Round &num;379 &lpar;Div&period; 2&rpar; C&period; Anton and Making Potions 二分

    C. Anton and Making Potions time limit per test 4 seconds memory limit per test 256 megabytes input ...

  6. Codeforces Round &num;297 &lpar;Div&period; 2&rpar;A&period; Vitaliy and Pie 水题

    Codeforces Round #297 (Div. 2)A. Vitaliy and Pie Time Limit: 2 Sec  Memory Limit: 256 MBSubmit: xxx  ...

  7. Codeforces Round &num;396 &lpar;Div&period; 2&rpar; A B C D 水 trick dp 并查集

    A. Mahmoud and Longest Uncommon Subsequence time limit per test 2 seconds memory limit per test 256 ...

  8. Codeforces Round &num;379 &lpar;Div&period; 2&rpar; Analyses By Team&colon;Red &amp&semi; Black

    A.Anton and Danik Problems: 给你长度为N的,只含'A','D'的序列,统计并输出何者出现的较多,相同为"Friendship" Analysis: lu ...

  9. Codeforces Round &num;379 &lpar;Div&period; 2&rpar; E&period; Anton and Tree 缩点 直径

    E. Anton and Tree 题目连接: http://codeforces.com/contest/734/problem/E Description Anton is growing a t ...

随机推荐

  1. 消息队列 Kafka 的基本知识及 &period;NET Core 客户端

    前言 最新项目中要用到消息队列来做消息的传输,之所以选着 Kafka 是因为要配合其他 java 项目中,所以就对 Kafka 了解了一下,也算是做个笔记吧. 本篇不谈论 Kafka 和其他的一些消息 ...

  2. Linux下的删除命令

    Linux:rm Windows:del rm parameter: -f, --force    忽略不存在的文件,从不给出提示.-i, --interactive 进行交互式删除-r, -R, - ...

  3. MATLAB - 运算符

    1.关系运算符用来比较两个数之间的大小关系,在Matlab中的关系运算符包括: <  小于 <= 小于或等于 >        大于 >=      大于或等于 ==     ...

  4. Hadoop学习5--配置本地开发环境(Windows&plus;Eclipse)

    一.导入hadoop插件到eclipse 插件名称:hadoop-eclipse-plugin-2.7.0.jar 我是从网上下载的,还可以自己编译. 放到eclipse安装目录下的plugins文件 ...

  5. js设置datagriad的行移动

    //                    ,//                formatter: function(value,row,index){//                    ...

  6. R基础

    R的对象类型包括数值型(numeric),复数型(complex),逻辑型(logical),字符型(character)和原味型(raw),列表(list)递归结构:函数(function)和表达式 ...

  7. oracle的常见问题与解决

    刚接触oracle,在学习过程中遇到了很多的问题,本文章将会收藏我遇到的问题及如何解决. 错误一:ORA-28009:connection as sys should be as sysdba解决方法 ...

  8. apache和nginx原理上的不同之处

    今天群里提到面试时问到apache和nginx原理有什么不同,一时还真没想起,想到的只是他们的优缺点,便搜索了下.记录学习下.顺便记录下优缺点吧. 原理不同之处: 为什么Nginx的性能要比Apach ...

  9. 2018-4-5-MEMS

    微机电系统,研究生在学习纳米操作方面的知识的时候了解过一些,有时间的话写点东西温故知新.

  10. centos7学习笔记-安装配置apache

    我的邮箱地址:zytrenren@163.com欢迎大家交流学习纠错! 1.安装apache #yum install httpd 2.配置开机启动 systemctl enable httpd 3. ...