CF151A - SoftDrinking

题目描述

This winter is so cold in Nvodsk! A group of n friends decided to buy k bottles of a soft drink called “Take-It-Light” to warm up a bit. Each bottle has l milliliters of the drink. Also they bought c limes and cut each of them into d slices. After that they found p grams of salt.

To make a toast, each friend needs nl milliliters of the drink, a slice of lime and np grams of salt. The friends want to make as many toasts as they can, provided they all drink the same amount. How many toasts can each friend make?

输入

The first and only line contains positive integers n, k, l, c, d, p, nl, np, not exceeding 1000 and no less than 1. The numbers are separated by exactly one space.

输出

Print a single integer — the number of toasts each friend can make.

样例

Input

1
3 4 5 10 8 100 3 1

Output

1
2

Input

1
5 100 10 1 19 90 4 3

Output

1
3

Input

1
10 1000 1000 25 23 1 50 1

Output

1
0

注意

A comment to the first sample:

Overall the friends have 4 * 5 = 20 milliliters of the drink, it is enough to make 20 / 3 = 6 toasts. The limes are enough for 10 * 8 = 80 toasts and the salt is enough for 100 / 1 = 100 toasts. However, there are 3 friends in the group, so the answer is min(6, 80, 100) / 3 = 2.

解题思路

题目大意:n个朋友有k瓶l毫升的饮料、c个橙子切成d片、p克盐。

每个人敬酒需要nl毫升饮料、1片橙子、和np克盐。

在每个人喝酒量相同情况下,问他们最多能喝多少杯酒。

根据注意中的提示,答案是min(k * l / nl, c * d, p / np) / n。

AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include <iostream>

using namespace std;

int n, k, l, c, d, p, nl, np;

int main()
{
cin >> n >> k >> l >> c >> d >> p >> nl >> np;

cout << min(k * l / nl, min(c * d, p / np)) / n << endl;

return 0;
}

CF151B - Phone Numbers

题目描述

Winters are just damn freezing cold in Nvodsk! That’s why a group of n friends prefers to take a taxi, order a pizza and call girls. The phone numbers in the city consist of three pairs of digits (for example, 12-34-56). Each friend has a phonebook of size si (that’s the number of phone numbers). We know that taxi numbers consist of six identical digits (for example, 22-22-22), the numbers of pizza deliveries should necessarily be decreasing sequences of six different digits (for example, 98-73-21), all other numbers are the girls’ numbers.

You are given your friends’ phone books. Calculate which friend is best to go to when you are interested in each of those things (who has maximal number of phone numbers of each type).

If the phone book of one person contains some number two times, you should count it twice. That is, each number should be taken into consideration the number of times it occurs in the phone book.

输入

The first line contains an integer n (1 ≤ n ≤ 100) — the number of friends.

Then follow n data blocks that describe each friend’s phone books. Each block is presented in the following form: first goes the line that contains integer si and string namei (0 ≤ si ≤ 100) — the number of phone numbers in the phone book of the i-th friend and the name of the i-th friend. The name is a non-empty sequence of uppercase and lowercase Latin letters, containing no more than 20 characters. Next si lines contain numbers as “XX-XX-XX”, where X is arbitrary digits from 0 to 9.

输出

In the first line print the phrase “If you want to call a taxi, you should call: “. Then print names of all friends whose phone books contain maximal number of taxi phone numbers.

In the second line print the phrase “If you want to order a pizza, you should call: “. Then print names of all friends who have maximal number of pizza phone numbers.

In the third line print the phrase “If you want to go to a cafe with a wonderful girl, you should call: “. Then print names of all friends who have maximal number of girls’ phone numbers.

Print the names in the order in which they are given in the input data. Separate two consecutive names with a comma and a space. Each line should end with exactly one point. For clarifications concerning the output form, see sample tests. It is necessary that you follow the output form strictly. Extra spaces are not allowed.

样例

Input

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
4
2 Fedorov
22-22-22
98-76-54
3 Melnikov
75-19-09
23-45-67
99-99-98
7 Rogulenko
22-22-22
11-11-11
33-33-33
44-44-44
55-55-55
66-66-66
95-43-21
3 Kaluzhin
11-11-11
99-99-99
98-65-32

Output

1
2
3
If you want to call a taxi, you should call: Rogulenko.
If you want to order a pizza, you should call: Fedorov, Rogulenko, Kaluzhin.
If you want to go to a cafe with a wonderful girl, you should call: Melnikov.

Input

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
3
5 Gleb
66-66-66
55-55-55
01-01-01
65-43-21
12-34-56
3 Serega
55-55-55
87-65-43
65-55-21
5 Melnik
12-42-12
87-73-01
36-04-12
88-12-22
82-11-43

Output

1
2
3
If you want to call a taxi, you should call: Gleb.
If you want to order a pizza, you should call: Gleb, Serega.
If you want to go to a cafe with a wonderful girl, you should call: Melnik.

Input

1
2
3
4
5
6
7
8
9
10
11
3
3 Kulczynski
22-22-22
65-43-21
98-12-00
4 Pachocki
11-11-11
11-11-11
11-11-11
98-76-54
0 Smietanka

Output

1
2
3
If you want to call a taxi, you should call: Pachocki.
If you want to order a pizza, you should call: Kulczynski, Pachocki.
If you want to go to a cafe with a wonderful girl, you should call: Kulczynski.

注意

In the first sample you are given four friends. Fedorov’s phone book contains one taxi number and one pizza delivery number, Melnikov’s phone book only has 3 numbers of girls, Rogulenko’s one has 6 taxi numbers and one pizza delivery number, Kaluzhin’s one contains 2 taxi numbers and one pizza delivery number.

Thus, if you need to order a taxi, you should obviously call Rogulenko, if you need to order a pizza you should call anybody of the following: Rogulenko, Fedorov, Kaluzhin (each of them has one number). Melnikov has maximal number of phone numbers of girls.

解题思路

模拟题,使用结构体,直接按题目要求读入,然后判断输入的号码属于哪种类型。

最后判断每种类型哪个人出现次数最多,按格式要求输出即可。

AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
#include <iostream>

using namespace std;

struct People
{
string name;
int taxi;
int pizza;
int girl;
};

int query(string& str)
{
if (str[0] == str[1] && str[1] == str[3] && str[3] == str[4] && str[4] == str[6] && str[6] == str[7]) return 0;
else if (str[0] > str[1] && str[1] > str[3] && str[3] > str[4] && str[4] > str[6] && str[6] > str[7]) return 1;
else return 2;
}

int n, m;
People people[100];
string ans[3];

int main()
{
cin >> n;
for (int i = 0; i < n; i++)
{
cin >> m;
cin >> people[i].name;

for (int j = 0; j < m; j++)
{
string tmp;

cin >> tmp;
if (query(tmp) == 0) people[i].taxi++;
else if(query(tmp) == 1) people[i].pizza++;
else if (query(tmp) == 2) people[i].girl++;
}
}

string taxi[100], pizza[100], girl[100];
int cnt_taxi = 0, cnt_pizza = 0, cnt_girl = 0;
int max_taxi = -1, max_pizza = -1, max_girl = -1;

for (int i = 0; i < n; i++)
{
if (people[i].taxi > max_taxi) max_taxi = people[i].taxi;
if (people[i].pizza > max_pizza) max_pizza = people[i].pizza;
if (people[i].girl > max_girl) max_girl = people[i].girl;
}

for (int i = 0; i < n; i++)
{
if (people[i].taxi >= max_taxi) taxi[cnt_taxi++] = people[i].name;
if (people[i].pizza >= max_pizza) pizza[cnt_pizza++] = people[i].name;
if (people[i].girl >= max_girl) girl[cnt_girl++] = people[i].name;
}

cout << "If you want to call a taxi, you should call: ";
if (cnt_taxi == 1) cout << taxi[0];
else
{
cout << taxi[0];
for (int i = 1; i < cnt_taxi; i++) cout << ", " << taxi[i];
}
cout << '.' << endl;

cout << "If you want to order a pizza, you should call: ";
if (cnt_pizza == 1) cout << pizza[0];
else
{
cout << pizza[0];
for (int i = 1; i < cnt_pizza; i++) cout << ", " << pizza[i];
}
cout << '.' << endl;

cout << "If you want to go to a cafe with a wonderful girl, you should call: ";
if (cnt_girl == 1) cout << girl[0];
else
{
cout << girl[0];
for (int i = 1; i < cnt_girl; i++) cout << ", " << girl[i];
}
cout << '.' << endl;

return 0;
}

CF151C - Win or Freeze

题目描述

You can’t possibly imagine how cold our friends are this winter in Nvodsk! Two of them play the following game to warm up: initially a piece of paper has an integer q. During a move a player should write any integer number that is a non-trivial divisor of the last written number. Then he should run this number of circles around the hotel. Let us remind you that a number’s divisor is called non-trivial if it is different from one and from the divided number itself.

The first person who can’t make a move wins as he continues to lie in his warm bed under three blankets while the other one keeps running. Determine which player wins considering that both players play optimally. If the first player wins, print any winning first move.

输入

The first line contains the only integer q (1 ≤ q ≤ 1013).

Please do not use the %lld specificator to read or write 64-bit integers in С++. It is preferred to use the cin, cout streams or the %I64d specificator.

输出

In the first line print the number of the winning player (1 or 2). If the first player wins then the second line should contain another integer — his first move (if the first player can’t even make the first move, print 0). If there are multiple solutions, print any of them.

样例

Input

1
6

Output

1
2

Input

1
30

Output

1
2
1
6

Input

1
1

Output

1
2
1
0

注意

Number 6 has only two non-trivial divisors: 2 and 3. It is impossible to make a move after the numbers 2 and 3 are written, so both of them are winning, thus, number 6 is the losing number. A player can make a move and write number 6 after number 30; 6, as we know, is a losing number. Thus, this move will bring us the victory.

解题思路

题目很难理解,题意是给定一个数字,每个人轮流对数字进行操作。

如果你操作后这个数字对方无法操作,则对方获胜。

操作:将这个数字除以n,n∈(1, n);

如果你能将数字分解为两个素数的乘积,则你就获胜了。

因为对手操作后,剩余的数字是素数,你无法再对数字进行操作。

情况1:给出的数不能操作,即给出素数,则1直接获胜。

情况2:给出的数可以分解为2个素数,则2获胜。

情况3:给出的数可以分解为2个以上的素数,则1获胜。

考点其实是质因数分解。注意判断到3个质因数以上跳出循环,否则会超时。

AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <iostream>
#include <vector>

using namespace std;

int main()
{
long long q;
vector<long long> quality;

cin >> q;

for (long long i = 2; i <= q / i; i++)
{
while (q % i == 0)
{
quality.push_back(i);
q /= i;
if (quality.size() >= 3) break;
}
if (quality.size() >= 3) break;
}

if (q > 1 && quality.size() < 3) quality.push_back(q);

if (quality.size() == 2) cout << "2" << endl;
else if (quality.size() > 2) cout << "1" << endl << quality[0] * quality[1] << endl;
else cout << 1 << endl << 0 << endl;

return 0;
}

CF151D - Quantity of Strings

题目描述

Just in case somebody missed it: this winter is totally cold in Nvodsk! It is so cold that one gets funny thoughts. For example, let’s say there are strings with the length exactly n, based on the alphabet of size m. Any its substring with length equal to k is a palindrome. How many such strings exist? Your task is to find their quantity modulo 1000000007 (109 + 7). Be careful and don’t miss a string or two!

Let us remind you that a string is a palindrome if it can be read the same way in either direction, from the left to the right and from the right to the left.

输入

The first and only line contains three integers: n, m and k (1 ≤ n, m, k ≤ 2000).

输出

Print a single integer — the number of strings of the described type modulo 1000000007 (109 + 7).

样例

Input

1
1 1 1

Output

1
1

Input

1
5 2 4

Output

1
2

注意

In the first sample only one string is valid: “a” (let’s denote the only letter of our alphabet as “a”).

In the second sample (if we denote the alphabet letters as “a” and “b”) the following strings are valid: “aaaaa” and “bbbbb”.

解题思路

给m种字符,要求组成长度为n的字符串,并且任意长度为k的字串都是回文。

分情况讨论:

  1. k < n && k % 2 == 0,只能是相同的字符。
  2. k == n && k % 2 == 1,考虑左边或右边,一边的每个位可以是任意字符。
  3. k > n || k == 1,每个位都能是任意字符。
  4. n为奇数,每个字符都能有1或2种字符。
  5. n为偶数,只能由1种字符。

AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include <iostream>

using namespace std;

typedef long long ll;

const int mod = 1000000007;

ll quick(ll a, ll b)
{
ll ans = 1;

while (b)
{
if (b & 1) ans = ans * a % mod;
a = a * a % mod;
b >>= 1;
}

return ans;
}

int main()
{
ll n, m, k;

cin >> n >> m >> k;

if (k > n || k == 1)
cout << quick(m, n) << endl;
else if (k == n)
cout << quick(m, (n + 1) / 2) << endl;
else if (k % 2 == 1)
cout << quick(m, 2) << endl;
else
cout << m << endl;

return 0;
}