A. Elimination
time limit per test 1 second
memory limit per test 256 megabytes
input standard input
output standard output
The finalists of the "Russian Code Cup" competition in 2214 will be the participants who win in one of the elimination rounds.
The elimination rounds are divided into main and additional. Each of the main elimination rounds consists of c problems, the winners of the round are the first n people in the rating list. Each of the additional elimination rounds consists of d problems. The winner of the additional round is one person. Besides, kwinners of the past finals are invited to the finals without elimination.
As a result of all elimination rounds at least n·m people should go to the finals. You need to organize elimination rounds in such a way, that at least n·m people go to the finals, and the total amount of used problems in all rounds is as small as possible.
Input
The first line contains two integers c and d (1 ≤ c, d ≤ 100) — the number of problems in the main and additional rounds, correspondingly. The second line contains two integers n and m (1 ≤ n, m ≤ 100). Finally, the third line contains an integer k (1 ≤ k ≤ 100) — the number of the pre-chosen winners.
Output
In the first line, print a single integer — the minimum number of problems the jury needs to prepare.
Sample test(s)
input
1 10
7 2
1
output
2
input
2 2
2 1
2
output
0
[cpp
#include
#include
#include
#include
using namespace std;
int c,d,n,m,k,s;
int main()
{
cin>>c>>d>>n>>m>>k;
s=n*m-k;
if(s<=0)
{
puts("0"); return 0;
}
int ans=0;
if(c
{
int num_ma=s/n;
ans+=num_ma*c;
int resman=s%n;
ans+=min(resman*d,c);
}
else
{
ans=s*d;
}
cout<
return 0;
}
B. Crash
time limit per test 1 second
memory limit per test 256 megabytes
input standard input
output standard output
During the "Russian Code Cup" programming competition, the testing system stores all sent solutions for each participant. We know that many participants use random numbers in their programs and are often sent several solutions with the same source code to check.
Each participant is identified by some unique positive integer k, and each sent solution A is characterized by two numbers: x — the number of different solutions that are sent before the first solution identical to A, and k — the number of the participant, who is the author of the solution. Consequently, all identical solutions have the same x.
It is known that the data in the testing system are stored in the chronological order, that is, if the testing system has a solution with number x (x > 0) of the participant with number k, then the testing system has a solution with number x - 1 of the same participant stored somewhere before.
During the competition the checking system crashed, but then the data of the submissions of all participants have been restored. Now the jury wants to verify that the recovered data is in chronological order. Help the jury to do so.
Input
The first line of the input contains an integer n (1 ≤ n ≤ 105) — the number of solutions. Each of the following n lines contains two integers separated by space x and k (0 ≤ x ≤ 105; 1 ≤ k ≤ 105) — the number of previous unique solutions and the identifier of the participant.
Output
A single line of the output should con