A. Alphabet Animals

You are playing a game in which a group of players take turns saying animal names. The animal name you say when it is your turn must start with the same letter as the previously said animal ends with and it must not have been said previously in this round of the game. If there is no valid name or you cannot come up with one you are eliminated.

Given the last animal name said before your turn and a list of all names not yet used, can you make it through this turn? If so, can you make sure to eliminate the next player?

Input

The first line of input contains a single word, the animal that theprevious player just said. The next line contains a single integer n (0 ≤ n ≤ 10⁵), the number of valid unused animal names. Each of the following n lines contains one valid unused animal name.

All animal names (including the one the previous player said) are unique and consist of at least 1 and at most 20 lower case letters‘a’-‘z’.

Output

If there is any animal name you can play that eliminates the next player, output the first such name from the input list, followed by an exclamation mark. Otherwise, if there is any animal name that you can play, output the first such name. Otherwise, output a question mark (in this case you will just have to make up a fake name in the hope that the others will trust you that this is a real animal).

输出时每行末尾的多余空格，不影响答案正确性

样例输入1复制

pig
2
goat
toad

样例输出1复制

goat

样例输入2复制

dog
2
snake
emu

样例输出2复制

?

样例输入3复制

hare
3
bee
cat
eagle

样例输出3复制

eagle!

题意：

单词接龙，现在轮到你了，给出上一位玩家的单词和你可以用的单词，是否可能将下一位选手淘汰（接不了）

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int inf = 0x3f3f3f3f;
const double eps = 1e-15;
const double PI = acos(-1.0);
const int N = 1e5 + 10;

string s[N];
vector<int>vec;
int vis[30];

int main()
{
    int n;
    string pre;
    cin >> pre;
    int len = pre.size();
    memset(vis, 0, sizeof(vis));
    scanf("%d", &n);
    for(int i = 1; i <= n; ++i)
    {
        cin >> s[i];
        vis[s[i][0] - 'a']++;
        if(s[i][0] == pre[len - 1])
        {
            vec.push_back(i);
        }
    }
    int siz = vec.size();
    if(siz == 0)
    {
        cout<<"?"<<'\n';
        return 0;
    }
    int id = vec[0];
    bool flag = 0;
    for(int i = 0; i < siz; ++i)
    {
        int len = s[vec[i]].size();
//        cout<<s[vec[i]]<<'\n';
        vis[s[vec[i]][0] - 'a']--;
        if(!vis[s[vec[i]][len - 1] - 'a'])
        {
            id = vec[i];
            flag = 1;
            break;
        }
        vis[s[vec[i]][0] - 'a']++;
    }
    cout<<s[id];
    if(flag)
        cout<<"!";
    cout<<'\n';
    vec.clear();
    return 0;
}

B. Building Boundaries

Maarja wants to buy a rectangular piece of land and then construct three buildings on that land.

The boundaries of the buildings on the ground must have rectangularsizes a₁ × b₁, a₂ × b₂, and a₃ × b₃. They can touch each other but theymay not overlap. They can also be rotated as long as their sides arehorizontal and vertical.

What is the minimum area of land Maarja has to buy?

Input

The input consists of multiple test scenarios. The first line of inputcontains a single integer t (1 ≤ t ≤ 1000), the number of scenarios.Then follow the t scenarios. Each scenario consists of a single line,containing six integers a₁, b₁, a₂, b₂, a₃ and b₃(1 ≤ a₁, b₁, a₂, b₂, a₃, b₃ ≤ 10⁹).

Output

For each test scenario, output the minimum area of land such that Maarjacan construct the three buildings.

输出时每行末尾的多余空格，不影响答案正确性

样例输入复制

2
2 3 2 2 1 1
2 4 5 1 2 3

样例输出复制

12
21

题意：

给三个矩形，把他们放在一个矩形里面，求矩形最小占地面积

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const ll inf = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-12;
const double PI = acos(-1.0);
const int N = 455;

struct node
{
    ll x, y;
}s[3][2];

int main()
{
    int t;
    scanf("%d", &t);
    while(t--)
    {
        for(int i = 0; i < 3; ++i)
        {
            scanf("%lld%lld", &s[i][0].x, &s[i][0].y);
            s[i][1].x = s[i][0].y;
            s[i][1].y = s[i][0].x;
        }
        ll minn = inf;
        for(int i = 0; i < 3; ++i)
        {
            for(int j = i + 1; j < 3; ++j)
            {
                int k;
                for(int p = 0; p < 3; ++p)
                {
                    if(i != p && j != p)
                    {
                        k = p;
                        break;
                    }
                }
                for(int o = 0; o < 2; ++o)
                {
                    for(int p = 0; p < 2; ++p)
                    {
                        for(int q = 0; q < 2; ++q)
                        {
                            minn = min(minn, max(s[k][q].x, (s[i][o].x + s[j][p].x)) * (max(s[i][o].y, s[j][p].y) + s[k][q].y));
                            minn = min(minn, (s[i][o].x + max(s[j][p].x, s[k][q].x)) * max(s[i][o].y, s[j][p].y + s[k][q].y));
                            minn = min(minn, (s[i][o].x + s[j][p].x + s[k][q].x) * max(s[i][o].y, max(s[j][p].y, s[k][q].y)));
                        }
                    }
                }
            }
        }
        cout<<minn<<'\n';
    }
    return 0;
}

 C. Cocoa Coalition

Alice and Bob decide to share a chocolate bar, which is an n by m rectangular grid of chocolate cells. They decide that Alice should get (a < n ⋅ m) pieces and that Bob should get (b = n ⋅ m − a) pieces. To split the chocolate bar, they repeatedly take a singlepiece of chocolate and break it either horizontally or vertically,creating two smaller pieces of chocolate. See Figure 1for an example.

What is the minimum number of splits that Alice and Bob need to perform in order to split the n-by-m chocolate bar into two piles consisting of a and b chocolate cells?

Input

The input consists of a single line, containing the three integers n, m and a (1 ≤ n, m ≤ 10⁶, 1 ≤ a < n ⋅ m).

Output

Output the minimum number of splits needed to achieve the desireddivision of chocolate.

输出时每行末尾的多余空格，不影响答案正确性

样例输入1复制

3 10 9

样例输出1复制

1

样例输入2复制

10 10 71

样例输出2复制

3

题意：

在 n * m 块巧克力中切出 a 块巧克力，只能横着切或竖着切，问最少切几刀

思路：

（1）若 a % n == 0 || a % m == 0，一刀即可

（2）若 a 可以分解为两正数之积，且这两个数一个小于 n 并且一个小于 m ，切2刀

（3）其余情况都是3刀

注意：不一定是小块好切（比如 n = 4, m = 10, a = 13, 答案是切出27块来，切两刀），因此 a 和 n * m - a 要比较一下

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int inf = 0x3f3f3f3f;
const double eps = 1e-15;
const double PI = acos(-1.0);
const int N = 105;

ll n, m, a;

ll solve(ll a)
{
    ll ans;
    if(a % n == 0 || a % m == 0)
    {
        ans = 1;
    }
    else
    {
        bool flag = 0;
        for(ll i = 1; i <= sqrt(a); ++i)
        {
            if(a % i == 0)
            {
                if(a / i < n && i < m)
                {
                    flag = 1;
                    break;
                }
                if(a / i < m && i < n)
                {
                    flag = 1;
                    break;
                }
            }
        }
        if(flag)
            ans = 2;
        else
            ans = 3;
    }
    return ans;
}

int main()
{
    while(~scanf("%lld%lld%lld", &n, &m, &a))
    {
        cout<<min(solve(a),solve(n * m - a))<<'\n';
    }
    return 0;
}

 G. Hot Hike

In order to pass time during your vacation, you decided to go on a hike to visit a scenic lake up in the mountains. Hiking to the lake will take you a full day, then you will stay there for a day to rest and enjoy the scenery, and then spend another day hiking home, for a total of three days. However, the accursed weather this summer is ridiculously warm and sunny, and since severe dehydration is not at the top of your priority list you want to schedule the three-day trip during some days where the two hiking days are the least warm. In particular you want to minimize the maximum temperature during the two hiking days.

Given the current forecast of daily maximum temperatures during your vacation, what are the best days for your trip?

Input

The first line of input contains an integer n (3 ≤ n ≤ 50), the length of your vacation in days. Then follows a line containing n integers t1, t2, …, tn ( − 20 ≤ ti ≤ 40), where ti is the temperature forecast for the ith day of your vacation.

Output

Output two integers d and t, where d is the best day to start your trip, and t is the resulting maximum temperature during the two hiking days. If there are many choices of d that minimize the value of t, then output the smallest such d.

输出时每行末尾的多余空格，不影响答案正确性

样例输入1复制

5
23 27 31 28 30

样例输出1复制

2 28

样例输入2复制

4
30 20 20 30

样例输出2复制

1 30

签到

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int inf = 0x3f3f3f3f;
const double eps = 1e-15;
const double PI = acos(-1.0);
const int N = 55;

int t[N];

int main()
{
    int n;
    while(~scanf("%d", &n))
    {
        int id = 0;
        int minn = 50;
        for(int i = 1; i <= n; ++i)
        {
            scanf("%d", &t[i]);
            if(i >= 3)
            {
                int tmp = max(t[i - 2], t[i]);
                if(tmp < minn)
                {
                    minn = tmp;
                    id = i - 2;
                }
            }
        }
        cout<<id<<' '<<minn<<'\n';
    }
    return 0;
}