A - Ice Tea Store

---

Time limit : 2sec / Memory limit : 256MB

Score : 300 points

Problem Statement

You've come to your favorite store Infinitesco to buy some ice tea.

The store sells ice tea in bottles of different volumes at different costs. Specifically, a 0.25-liter bottle costs Q yen, a 0.5-liter bottle costs H yen, a 1-liter bottle costs S yen, and a 2-liter bottle costs D yen. The store has an infinite supply of bottles of each type.

You want to buy exactly N liters of ice tea. How many yen do you have to spend?

Constraints

• 1≤Q,H,S,D≤108
• 1≤N≤109
• All input values are integers.

---

Input

Input is given from Standard Input in the following format:

Q H S DN

Output

Print the smallest number of yen you have to spend to buy exactly N liters of ice tea.

---

Sample Input 1

Copy

20 30 70 903

Sample Output 1

Copy

150

Buy one 2-liter bottle and two 0.5-liter bottles. You'll get 3 liters for 90+30+30=150 yen.

---

Sample Input 2

Copy

10000 1000 100 101

Sample Output 2

Copy

100

Even though a 2-liter bottle costs just 10 yen, you need only 1 liter. Thus, you have to buy a 1-liter bottle for 100 yen.

---

Sample Input 3

Copy

10 100 1000 100001

Sample Output 3

Copy

40

Now it's better to buy four 0.25-liter bottles for 10+10+10+10=40 yen.

---

Sample Input 4

Copy

12345678 87654321 12345678 87654321123456789

Sample Output 4

Copy

1524157763907942

---

贪心的问题，算是在背包吧，这个包不能满，所以wa了一发

AC代码

#include 
       
        using namespace std;int main(){    int q,h,s,d;    int n;    cin>>q>>h>>s>>d;    cin>>n;    q*=8,h*=4,s*=2;    int mi=min(q,h);    mi=min(mi,s);    int mi2=min(mi,d);    long long sum=1LL*n/2*mi2;    if(n&1)sum+=mi/2;    cout<
        
         <
        
       

B - Reverse and Compare

---

Time limit : 2sec / Memory limit : 256MB

Score : 500 points

Problem Statement

You have a string A=A1A2…An consisting of lowercase English letters.

You can choose any two indices i and j such that 1≤i≤j≤n and reverse substring AiAi+1…Aj.

You can perform this operation at most once.

How many different strings can you obtain?

Constraints

• 1≤|A|≤200,000
• A consists of lowercase English letters.

---

Input

Input is given from Standard Input in the following format:

A

Output

Print the number of different strings you can obtain by reversing any substring in A at most once.

---

Sample Input 1

Copy

aatt

Sample Output 1

Copy

5

You can obtain aatt (don't do anything), atat (reverse A[2..3]), atta (reverse A[2..4]), ttaa (reverse A[1..4]) and taat (reverse A[1..3]).

---

Sample Input 2

Copy

xxxxxxxxxx

Sample Output 2

Copy

1

Whatever substring you reverse, you'll always get xxxxxxxxxx.

---

Sample Input 3

Copy

abracadabra

Sample Output 3

Copy

44

---

一个字符串反转其中n个字符，问有多少种形式

#include 
         
          using namespace std;char s[200005];int a[256];int main(){    scanf("%s",s);    int l=strlen(s);    long long ans=1;    for(int i=0;i
         

 

#include 
         
          using namespace std;char s[200005];int main(){    scanf("%s",s);    long long ans=1;    int l=strlen(s);    sort(s,s+l);    for(int i=0;i