这几天刷CF水题感觉还好的几道题~

时间:2022-12-18 12:11:42
B. Queue at the Schooltime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

During the break the schoolchildren, boys and girls, formed a queue of n people in the canteen. Initially the children stood in the order they entered the canteen. However, after a while the boys started feeling awkward for standing in front of the girls in the queue and they started letting the girls move forward each second.

Let's describe the process more precisely. Let's say that the positions in the queue are sequentially numbered by integers from 1 to n, at that the person in the position number 1 is served first. Then, if at time x a boy stands on the i-th position and a girl stands on the (i + 1)-th position, then at time x + 1 the i-th position will have a girl and the (i + 1)-th position will have a boy. The time is given in seconds.

You've got the initial position of the children, at the initial moment of time. Determine the way the queue is going to look after t seconds.

Input

The first line contains two integers n and t (1 ≤ n, t ≤ 50), which represent the number of children in the queue and the time after which the queue will transform into the arrangement you need to find.

The next line contains string s, which represents the schoolchildren's initial arrangement. If the i-th position in the queue contains a boy, then the i-th character of string s equals "B", otherwise the i-th character equals "G".

Output

Print string a, which describes the arrangement after t seconds. If the i-th position has a boy after the needed time, then the i-th character a must equal "B", otherwise it must equal "G".

Sample test(s)input
5 1
BGGBG
output
GBGGB
input
5 2
BGGBG
output
GGBGB
input
4 1
GGGB
output
GGGB


题目的大意是给你一堆汉子妹子然后给定一个时间然后在这个时间内,如果汉子在妹子前面,汉子就得跟妹子换位置这道题首先得注意可以换位置的时间因为这关乎汉子能最后换到哪里去的问题接下来再搜索需要换位子的汉子,然后换成功一次后就得跳过该人 进入下一个人的判断 代码如下
#include<iostream>
#include<cstring>
using namespace std;

int main()
{ int n,t;
cin>>n>>t;
char str[105];
char s;
cin>>str;
int i,j;

for(j=0;j<t;j++)
{
for(i=0;i<n;i++)
{
if(str[i]=='B'&&str[i+1]=='G')
{
s=str[i];
str[i]=str[i+1];
str[i+1]=s;
i++;
}
}

}
cout<<str<<endl;
return 0;
}






A. Lucky Divisiontime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

Petya loves lucky numbers. Everybody knows that lucky numbers are positive integers whose decimal representation contains only the lucky digits 4 and 7. For example, numbers 477444 are lucky and 517467 are not.

Petya calls a number almost lucky if it could be evenly divided by some lucky number. Help him find out if the given number n is almost lucky.

Input

The single line contains an integer n (1 ≤ n ≤ 1000) — the number that needs to be checked.

Output

In the only line print "YES" (without the quotes), if number n is almost lucky. Otherwise, print "NO" (without the quotes).

Sample test(s)input
47
output
YES
input
16
output
YES
input
78
output
NO
Note

Note that all lucky numbers are almost lucky as any number is evenly divisible by itself.

In the first sample 47 is a lucky number. In the second sample 16 is divisible by 4.

唔这道题的大意是让你搜索一个范围的的接近幸运数,我们把只含4或7的数称之为幸运数,而接近幸运数指的一个能被幸运数整除的数字是故范围更大,这道题是纯暴力做法因为给定的范围很小,所以我很偷懒的直接把这个范围内的幸运数枚举了出来然后再将输入的数依次跟幸运数去取余如果等于0这个数就是接近幸运数,当然如果给定的范围很大则用循环找出这个大范围内的所有幸运数并存在数组里然后再用N去对这个数组里的数依次取余只要有一个为0那就是接近幸运数了 代码如下~

#include<iostream>using namespace std;int main(){    int n,m,t=0,c=0,a;    cin>>n;    {if(n%4==0||n%7==0||n%44==0||n%77==0||n%74==0||n%47==0||n%444==0||n%447==0||n%474==0||n%477==0||n%744==0||n%747==0||n%774==0||n%777==0)                cout<<"YES"<<endl;            else                cout<<"NO"<<endl;        }    return 0;}



A. Free Cashtime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

Valera runs a 24/7 fast food cafe. He magically learned that next day n people will visit his cafe. For each person we know the arrival time: the i-th person comes exactly at hi hours mi minutes. The cafe spends less than a minute to serve each client, but if a client comes in and sees that there is no free cash, than he doesn't want to wait and leaves the cafe immediately.

Valera is very greedy, so he wants to serve all n customers next day (and get more profit). However, for that he needs to ensure that at each moment of time the number of working cashes is no less than the number of clients in the cafe.

Help Valera count the minimum number of cashes to work at his cafe next day, so that they can serve all visitors.

Input

The first line contains a single integer n (1 ≤ n ≤ 105), that is the number of cafe visitors.

Each of the following n lines has two space-separated integers hi and mi (0 ≤ hi ≤ 23; 0 ≤ mi ≤ 59), representing the time when the i-th person comes into the cafe.

Note that the time is given in the chronological order. All time is given within one 24-hour period.

Output

Print a single integer — the minimum number of cashes, needed to serve all clients next day.

Sample test(s)input
48 08 108 108 45
output
2
input
30 1210 1122 22
output
1
Note

In the first sample it is not enough one cash to serve all clients, because two visitors will come into cafe in 8:10. Therefore, if there will be one cash in cafe, then one customer will be served by it, and another one will not wait and will go away.

In the second sample all visitors will come in different times, so it will be enough one cash.


唔 题目大意也很好理解 给出N个从小到大排好的时间,搜索出最大的相同的时间出现的次数那就是这个老板需要在这一天同时准备的最多的新盘子数

当然我们最好单独考虑一下如果N个时间全是一样的情况 那么直接输出N来就可以了(这个可以用标志变量标记一下)代码如下

#include<iostream>using namespace std;int main(){   int i,n,a[100000],b[100000],u=0;    cin>>n;    for(i=0;i<n;i++)    {        cin>>a[i]>>b[i];    }    for(i=0;i<n;i++)    {        if(a[i]!=b[i]||a[i]!=0)            u=1;    }    if(u==0)        cout<<n<<endl;    else    {         for(i=0;i<n;i++)             int t=1,max=1;        for(i=0;i<n;i++)     {        if(a[i]==a[i+1]&&b[i]==b[i+1])           {               t++;               if(max<t) max=t;           }           else            t=1;      }      cout<<max<<endl;    }    return 0;}



A. Amusing Joketime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

So, the New Year holidays are over. Santa Claus and his colleagues can take a rest and have guests at last. When two "New Year and Christmas Men" meet, thear assistants cut out of cardboard the letters from the guest's name and the host's name in honor of this event. Then the hung the letters above the main entrance. One night, when everyone went to bed, someone took all the letters of our characters' names. Then he may have shuffled the letters and put them in one pile in front of the door.

The next morning it was impossible to find the culprit who had made the disorder. But everybody wondered whether it is possible to restore the names of the host and his guests from the letters lying at the door? That is, we need to verify that there are no extra letters, and that nobody will need to cut more letters.

Help the "New Year and Christmas Men" and their friends to cope with this problem. You are given both inscriptions that hung over the front door the previous night, and a pile of letters that were found at the front door next morning.

Input

The input file consists of three lines: the first line contains the guest's name, the second line contains the name of the residence host and the third line contains letters in a pile that were found at the door in the morning. All lines are not empty and contain only uppercase Latin letters. The length of each line does not exceed 100.

Output

Print "YES" without the quotes, if the letters in the pile could be permuted to make the names of the "New Year and Christmas Men". Otherwise, print "NO" without the quotes.

Sample test(s)input
SANTACLAUSDEDMOROZSANTAMOROZDEDCLAUS
output
YES
input
PAPAINOELJOULUPUKKIJOULNAPAOILELUPUKKI
output
NO
input
BABBONATALEFATHERCHRISTMASBABCHRISTMASBONATALLEFATHER
output
NO
Note

In the first sample the letters written in the last line can be used to write the names and there won't be any extra letters left.

In the second sample letter "P" is missing from the pile and there's an extra letter "L".

In the third sample there's an extra letter "L".


这道题是一道对字符串处理的函数简单运用的题目其中掺杂这快速排序的概念 恩题目大意就是给你三段不长的字符串 然后看前两组字符串和在一起是否能构成第三串字符串 如果能则YES 否则NO,这道题思路很简单 首先将前两组字符串拼接起来 然后在前面分别求出字符串1和2的长度然后快速排出合成的新串 再将目标串排好序 最后判断新串和目标串是否相等就OK了 代码如下
#include<iostream>#include<cstring>#include<cstdlib>#include<algorithm>using namespace std;int main(){   char a[1005],b[1005],c[1005];    int len1,len2,len3;    int i;    cin>>a>>b>>c;    len1=strlen(a);    len2=strlen(b);    len3=strlen(c);    strcat(a,b);    sort(a,a+len1+len2);    sort(c,c+len3);    if(strcmp(a,c)==0)        cout<<"YES"<<endl;    else        cout<<"NO"<<endl;    return 0;}


B. Buttonstime limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard output

Manao is trying to open a rather challenging lock. The lock has n buttons on it and to open it, you should press the buttons in a certain order to open the lock. When you push some button, it either stays pressed into the lock (that means that you've guessed correctly and pushed the button that goes next in the sequence), or all pressed buttons return to the initial position. When all buttons are pressed into the lock at once, the lock opens.

Consider an example with three buttons. Let's say that the opening sequence is: {2, 3, 1}. If you first press buttons 1 or 3, the buttons unpress immediately. If you first press button 2, it stays pressed. If you press 1 after 2, all buttons unpress. If you press 3 after 2, buttons 3 and 2 stay pressed. As soon as you've got two pressed buttons, you only need to press button 1 to open the lock.

Manao doesn't know the opening sequence. But he is really smart and he is going to act in the optimal way. Calculate the number of times he's got to push a button in order to open the lock in the worst-case scenario.

Input

A single line contains integer n (1 ≤ n ≤ 2000) — the number of buttons the lock has.

Output

In a single line print the number of times Manao has to push a button in the worst-case scenario.

Sample test(s)input
2
output
3
input
3
output
7
Note

Consider the first test sample. Manao can fail his first push and push the wrong button. In this case he will already be able to guess the right one with his second push. And his third push will push the second right button. Thus, in the worst-case scenario he will only need 3 pushes.


这道题是一道简单的数学题,一开始把它理解为错排了后来认真看了一下发现与错排还是有区别的 大意是给你一串密码 然后问你最悲催的得按多少下那个键盘你才能过 注意每按错一个密码就得重新开始 而且还是一个一个的按。 唔这道题的数据是有规律的首先1对应1 2对应3 3对应7 我自己再模拟了4 5 6 分别为14 25 41乍看之下木有规律 但是不难发现 无论如何最后一次都是对的 都得按那最后一个正确的密码 所以可以把每个数先减去1 得到0 2 6 13 24 40 唔 这有啥规律呢 后一个减去前一个试试看呗 不难发现 出现了2 4 7 11 16 这些数 再减一次发现为2 3 4 5 成为了一个等差数列 是故如果把0 2 6 13 24 这些数设为a[i]那么a[i]-a[i-1](i从1开始)的差就是一个首项为2 公差为1的前N项数列的和的通项公式为(i*i+i)/2+1, 最后递归得到a[n-1]再加上1就是答案了 代码如下
#include<iostream>
using namespace std;

int main()
{ int a[100005];
int n;
cin>>n;
a[0]=0;
a[1]=2;
int i;
for(i=1;i<n;i++)
{
a[i]=((i*i)+i)/2+1+a[i-1];
}
cout<<a[n-1]+1<<endl;

return 0;
}