周练19.11.17

B - Consecutive Integers

Problem Statement

Snuke has N integers: 1,2,[ldots],N. He will choose K of them and give those to Takahashi.

How many ways are there to choose K consecutive integers?

Constraints

• All values in input are integers.
• 1≤K≤N≤50

Input

Input is given from Standard Input in the following format:

N K

Output

Print the answer.

Sample Input 1

3 2

Sample Output 1

2

There are two ways to choose two consecutive integers: (1,2) and (2,3).

Sample Input 2

13 3

Sample Output 2

11

AC

#include<iostream>
using namespace std;
int main()
{
	int n,k;
	while(cin>>n>>k)
	{
		cout<<(n-k)+1<<endl;
	}
	return 0;
}

C - ModSum

Problem Statement

For an integer N, we will choose a permutation {P1,P2,…,P**N} of {1,2,…,N}.

Then, for each i=1,2,…,N, let M**i be the remainder when i is divided by P**i.

Find the maximum possible value of M1+M2+[cdots]+M**N.

Constraints

• N is an integer satisfying 1≤N≤109.

Input

Input is given from Standard Input in the following format:

N

Output

Print the maximum possible value of M1+M2+[cdots]+M**N.

Sample Input 1

2

Sample Output 1

1

When the permutation {P1,P2}={2,1} is chosen, M1+M2=1+0=1.

Sample Input 2

13

Sample Output 2

78

Sample Input 3

1

Sample Output 3

0

AC

#include<iostream>
using namespace std;
int main(){
	long long int n;
	cin>>n;
	long long int sum = 0 ;
	for(long long int i=1;i<=n-1;i++)
	  sum+=i;
	cout<<sum<<endl;
	
	return 0;
}

F - Monsters Battle Royale

Problem Statement

There are N monsters, numbered 1,2,…,N.

Initially, the health of Monster i is A**i.

Below, a monster with at least 1 health is called alive.

Until there is only one alive monster, the following is repeated:

• A random alive monster attacks another random alive monster.
• As a result, the health of the monster attacked is reduced by the amount equal to the current health of the monster attacking.

Find the minimum possible final health of the last monster alive.

Constraints

• All values in input are integers.
• 2≤N≤105
• 1≤A*i*≤109

Input

Input is given from Standard Input in the following format:

N
A1 A2 … AN

Output

Print the minimum possible final health of the last monster alive.

Sample Input 1

4
2 10 8 40

Sample Output 1

2

When only the first monster keeps on attacking, the final health of the last monster will be 2, which is minimum.

Sample Input 2

4
5 13 8 1000000000

Sample Output 2

1

Sample Input 3

3
1000000000 1000000000 1000000000

Sample Output 3

1000000000

AC

#include <cstdio>
#include <algorithm>
using namespace std;

int a[(int)1e5 + 10];

int main() {
    int n;
    while(~scanf("%d", &n)) 
    {
	
		for (int i = 0; i < n; i++) {
	        scanf("%d", &a[i]);
	    }
	    int begin = 0;
	    int ans;
	    int flag = 0;
	    while (true) {
	        sort(a + begin, a + n);
	        while (a[begin] == 0) begin++;
	        if (begin == n - 1) break;
	        for (int i = begin + 1; i < n; i++) {
	            a[i] %= a[begin];
	            if (a[i] == 1) {
	                ans = 1;
	                flag = 1;
	                break;
	            }
	        }
	        if(flag)
	        	break;
	    }
	    if(!flag)
	    	ans = a[n-1];
	    printf("%d\n", ans);
	}
    return 0;
}

G - Powerful Discount Tickets

Problem Statement

Takahashi is going to buy N items one by one.

The price of the i-th item he buys is A**i yen (the currency of Japan).

He has M discount tickets, and he can use any number of them when buying an item.

If Y tickets are used when buying an item priced X yen, he can get the item for X/2^Y

(rounded down to the nearest integer) yen

What is the minimum amount of money required to buy all the items?

Constraints

• All values in input are integers.
• 1≤N,M≤105
• 1≤A*i*≤109

Input

Input is given from Standard Input in the following format:

N M
A1 A2 … AN

Output

Print the minimum amount of money required to buy all the items.

Sample Input 1

3 3
2 13 8

Sample Output 1

9

We can buy all the items for 9 yen, as follows:

• Buy the 1-st item for 2 yen without tickets.
• Buy the 2-nd item for 3 yen with 2 tickets.
• Buy the 3-rd item for 4 yen with 1 ticket.

Sample Input 2

4 4
1 9 3 5

Sample Output 2

6

Sample Input 3

1 100000
1000000000

Sample Output 3

0

We can buy the item priced 1000000000 yen for 0 yen with 100000 tickets.

Sample Input 4

10 1
1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000

Sample Output 4

9500000000

AC

#include<iostream>
#include<queue>
#include<algorithm>
using namespace std;
  
int main(){
	
	int m,n;  
	while(cin>>n>>m)
	{ 
		priority_queue<int>q;
		int t;
		for(int i=0;i<n;i++)
		{
			
			cin>>t;
			q.push(t);    
		}
		long long sum=0;
		
		while(m)
		{
			t=q.top()/2;
			q.pop();
			q.push(t);
			m--;
		}
		while(!q.empty())
		{
			sum+=q.top();
			q.pop();
		}
		cout<<sum<<endl; 
	}  
	return 0;
}

I - Lower

Problem Statement

There are N squares arranged in a row from left to right.

The height of the i-th square from the left is H**i.

You will land on a square of your choice, then repeat moving to the adjacent square on the right as long as the height of the next square is not greater than that of the current square.

Find the maximum number of times you can move.

Constraints

• All values in input are integers.
• 1≤N≤105
• 1≤H*i*≤109

Input

Input is given from Standard Input in the following format:

N
H1 H2 … HN

Output

Print the maximum number of times you can move.

Sample Input 1

5
10 4 8 7 3

Sample Output 1

2

By landing on the third square from the left, you can move to the right twice.

Sample Input 2

7
4 4 5 6 6 5 5

Sample Output 2

3

By landing on the fourth square from the left, you can move to the right three times.

Sample Input 3

4
1 2 3 4

Sample Output 3

0

AC

#include<iostream>
using namespace std;
int a[100000009];
int main()
{
	int t;
	while(cin>>t)
	{
		int con=0,num=0;
		for(int i=1;i<=t;++i)
		{
			cin>>a[i];
		}
		int k = a[1];
		for(int i =2;i<=t;++i)
		{
			if(k>=a[i])
			{
				num++;
				k=a[i];
			}
			if(k<a[i])
			{
				con = max(num,con);
				num = 0;
				k = a[i];
			}
		}
		con = max(con,num);
		cout<<con<<endl;
	}
}

M - AB Substrings

Problem Statement

Snuke has N strings. The i-th string is s**i.

Let us concatenate these strings into one string after arranging them in some order. Find the maximum possible number of occurrences of AB in the resulting string.

Constraints

• 1≤N≤104
• 2≤|s**i|≤10
• s**i consists of uppercase English letters.

Input

Input is given from Standard Input in the following format:

N
s1
\vdots
s_N

Output

Print the answer.

Sample Input 1

3
ABCA
XBAZ
BAD

Sample Output 1

2

For example, if we concatenate ABCA, BAD and XBAZ in this order, the resulting string ABCABADXBAZ has two occurrences of AB.

Sample Input 2

9
BEWPVCRWH
ZZNQYIJX
BAVREA
PA
HJMYITEOX
BCJHMRMNK
BP
QVFABZ
PRGKSPUNA

Sample Output 2

4

Sample Input 3

7
RABYBBE
JOZ
BMHQUVA
BPA
ISU
MCMABAOBHZ
SZMEHMA

Sample Output 3

4

AC

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
char a[1100];
int main()
{
	long long int t;
	while(cin>>t)
	{
		int head=0,tail=0,mid=0,con=0,ans=0;
		for(int i=0;i<t;++i)
		{
			scanf("%s",&a);
			int len = strlen(a);
			if(a[0]=='B'&&a[len-1]=='A')
				con++;
			if(a[0]=='B'&&a[len-1]!='A')
				head++;
			if(a[len-1]=='A'&&a[0]!='B')
				tail++;
			for(int j =1;j<len-1;++j)
			{
				if(a[j]=='B'&&a[j-1]=='A')
					ans++;
			}
		}
		int h=0,t=0;
		if(con)
		{
			ans = ans+con-1;
			if(head)
				t = 1;
			if(tail)
				h = 1;
		}
		head = head+h;
		tail = tail+t;
			
		ans = ans+min(head,tail);
		cout<<ans<<endl;
	}
	return 0;
}