AtCoder Grand Contest 019

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 D
N

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 90
3

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 10
1

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 10000
1

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 87654321
123456789

Sample Output 4

Copy

1524157763907942

---

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

AC代码

#include <bits/stdc++.h>
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<<sum<<endl;
    return 0;
}

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 <bits/stdc++.h>
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<l;i++)
    ans+=i-a[s[i]],a[s[i]]++;
    cout<<ans;
    return 0;
}

 

#include <bits/stdc++.h>
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<l;)
    {
        int t=upper_bound(s+i+1,s+l,s[i])-s;
        if(t==l)break;
        ans+=1LL*(t-i)*(l-t);
        i=t;
    }
    cout<<ans;
    retur