Round#251
June 5, 2014
##A. Devu, the Singer and Churu, the Joker
Devu is a renowned classical singer. He is invited to many big functions/festivals. Recently he was invited to “All World Classical Singing Festival”. Other than Devu, comedian Churu was also invited.
Devu has provided organizers a list of the songs and required time for singing them. He will sing n songs, ith song will take ti minutes exactly.
The Comedian, Churu will crack jokes. All his jokes are of 5 minutes exactly.
People have mainly come to listen Devu. But you know that he needs rest of 10 minutes after each song. On the other hand, Churu being a very active person, doesn’t need any rest.
You as one of the organizers should make an optimal sсhedule for the event. For some reasons you must follow the conditions:
The duration of the event must be no more than d minutes; Devu must complete all his songs; With satisfying the two previous conditions the number of jokes cracked by Churu should be as many as possible. If it is not possible to find a way to conduct all the songs of the Devu, output -1. Otherwise find out maximum number of jokes that Churu can crack in the grand event.
Input The first line contains two space separated integers n, d (1 ≤ n ≤ 100; 1 ≤ d ≤ 10000). The second line contains n space-separated integers: t1, t2, …, tn (1 ≤ ti ≤ 100).
Output If there is no way to conduct all the songs of Devu, output -1. Otherwise output the maximum number of jokes that Churu can crack in the grand event.
Sample test(s) input 3 30 2 2 1 output 5 input 3 20 2 1 1 output -1 Note Consider the first example. The duration of the event is 30 minutes. There could be maximum 5 jokes in the following way:
First Churu cracks a joke in 5 minutes. Then Devu performs the first song for 2 minutes. Then Churu cracks 2 jokes in 10 minutes. Now Devu performs second song for 2 minutes. Then Churu cracks 2 jokes in 10 minutes. Now finally Devu will perform his last song in 1 minutes. Total time spent is 5 + 2 + 10 + 2 + 10 + 1 = 30 minutes.
Consider the second example. There is no way of organizing Devu’s all songs. Hence the answer is -1.
It is easy and I wrote in python:
n, d = map(int, input().split())
t = list(map(int, input().split()))
sum_time = (n - 1) * 10 + sum(t)
if sum_time > d:
print(-1)
else:
res_time = d - sum_time
cnt = res_time / 5 + (n - 1) * 2
print(int(cnt))
Devu is a dumb guy, his learning curve is very slow. You are supposed to teach him n subjects, the ith subject has ci chapters. When you teach him, you are supposed to teach all the chapters of a subject continuously.
Let us say that his initial per chapter learning power of a subject is x hours. In other words he can learn a chapter of a particular subject in x hours.
Well Devu is not complete dumb, there is a good thing about him too. If you teach him a subject, then time required to teach any chapter of the next subject will require exactly 1 hour less than previously required (see the examples to understand it more clearly). Note that his per chapter learning power can not be less than 1 hour.
You can teach him the n subjects in any possible order. Find out minimum amount of time (in hours) Devu will take to understand all the subjects and you will be free to do some enjoying task rather than teaching a dumb guy.
Please be careful that answer might not fit in 32 bit data type.
Input The first line will contain two space separated integers n, x (1 ≤ n, x ≤ 105). The next line will contain n space separated integers: c1, c2, …, cn (1 ≤ ci ≤ 105).
Output Output a single integer representing the answer to the problem.
Sample test(s) input 2 3 4 1 output 11 input 4 2 5 1 2 1 output 10 input 3 3 1 1 1 output 6 Note Look at the first example. Consider the order of subjects: 1, 2. When you teach Devu the first subject, it will take him 3 hours per chapter, so it will take 12 hours to teach first subject. After teaching first subject, his per chapter learning time will be 2 hours. Now teaching him second subject will take 2 × 1 = 2 hours. Hence you will need to spend 12 + 2 = 14 hours.
Consider the order of subjects: 2, 1. When you teach Devu the second subject, then it will take him 3 hours per chapter, so it will take 3 × 1 = 3 hours to teach the second subject. After teaching the second subject, his per chapter learning time will be 2 hours. Now teaching him the first subject will take 2 × 4 = 8 hours. Hence you will need to spend 11 hours.
So overall, minimum of both the cases is 11 hours.
Look at the third example. The order in this example doesn’t matter. When you teach Devu the first subject, it will take him 3 hours per chapter. When you teach Devu the second subject, it will take him 2 hours per chapter. When you teach Devu the third subject, it will take him 1 hours per chapter. In total it takes 6 hours.
Note the sentence lease be careful that answer might not fit in 32 bit data type.! I got wrong answer when I treat the answer as int. However, this is not all. I got pretest accepted but I got wrong answer after the contest! This is because when I convert a value multiplied by two values of int to a long long int I made a mistake. Because when two ints are multiplied, the result is int. If the result is overflowed, it is vain to convert that value to long long int. So we should first convert each int to long long int then multiply them.
This is my c++ code:
c++
/*
* =====================================================================================
* Filename : DumbGuy.cpp
* Description : dumb guy
* Version : 0.1
* Created : 06/04/14 23:54
* Author : Liu Xue Yang (LXY), liuxueyang457@163.com
* Motto : Suicide is Painless
* =====================================================================================
*/
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cstring>
#include <string>
#include <iostream>
using namespace std;
/*
* === FUNCTION ======================================================================
* Name: main
* =====================================================================================
*/
int c[100005];
int
main ( int argc, char *argv[] )
{
int n;
// long long x;
int x;
#ifndef ONLINE_JUDGE
freopen("DumbGuy.txt", "r", stdin);
#endif
while ( cin>>n>>x ) {
memset(c, 0, sizeof(c));
for ( int i = 0; i < n; ++i ) {
cin>>c[i];
}
sort(c, c + n);
long long int sum = 0;
for ( int i = 0; i < n; ++i ) {
if ( x > 1 ) {
// sum += (long long)((x--) * c[i]); /* error! */
// sum = sum + (long long)(x--) * (long long)(c[i]); /* correct */
// sum = sum + (long long)((x--) * c[i]); /* error */
sum += (long long)(x--) * (long long)(c[i]); /* correct */
}
else {
// sum += (long long)(c[i]);
sum = sum + (long long)(c[i]);
}
}
cout<<sum<<endl;
}
return EXIT_SUCCESS;
} /* ---------- end of function main ---------- */
It should be better if I wrote in python3 =_=:
n, x = map(int, input().split())
c = list(map(int, input().split()))
c.sort()
r_sum = 0
for i in c:
if x > 1:
r_sum += i * x
x -= 1
else:
r_sum += i
print(r_sum)
##C. Devu and Partitioning of the Array
Devu being a small kid, likes to play a lot, but he only likes to play with arrays. While playing he came up with an interesting question which he could not solve, can you please solve it for him?
Given an array consisting of distinct integers. Is it possible to partition the whole array into k disjoint non-empty parts such that p of the parts have even sum (each of them must have even sum) and remaining k - p have odd sum? (note that parts need not to be continuous).
If it is possible to partition the array, also give any possible way of valid partitioning.
Input The first line will contain three space separated integers n, k, p (1 ≤ k ≤ n ≤ 105; 0 ≤ p ≤ k). The next line will contain n space-separated distinct integers representing the content of array a: a1, a2, …, an (1 ≤ ai ≤ 109).
Output In the first line print “YES” (without the quotes) if it is possible to partition the array in the required way. Otherwise print “NO” (without the quotes).
If the required partition exists, print k lines after the first line. The ith of them should contain the content of the ith part. Print the content of the part in the line in the following way: firstly print the number of elements of the part, then print all the elements of the part in arbitrary order. There must be exactly p parts with even sum, each of the remaining k - p parts must have odd sum.
As there can be multiple partitions, you are allowed to print any valid partition.
Sample test(s) input 5 5 3 2 6 10 5 9 output YES 1 9 1 5 1 10 1 6 1 2 input 5 5 3 7 14 2 9 5 output NO input 5 3 1 1 2 3 7 5 output YES 3 5 1 3 1 7 1 2
While, I got wrong answer two times in the contest. Maybe it is not very difficult for this implementation problem. But I have to be careful and find an easy way to solve it.
/*
* =====================================================================================
* Filename : PartitionOfArray.cpp
* Description : partition
* Version : 0.1
* Created : 06/05/14 00:25
* Author : Liu Xue Yang (LXY), liuxueyang457@163.com
* Motto : Suicide is Painless
* =====================================================================================
*/
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <iostream>
#include <algorithm>
#include <string>
#include <cstring>
using namespace std;
/*
* === FUNCTION ======================================================================
* Name: main
* =====================================================================================
*/
vector<int> ans[100005];
int
main ( int argc, char *argv[] )
{
#ifndef ONLINE_JUDGE
freopen("PartitionOfArray.txt", "r", stdin);
#endif
int n, k, p;
while ( cin >> n >> k >> p ) {
vector<int> odd, even;
odd.clear();
even.clear();
int tmp;
for ( int i = 0; i < n; ++i ) {
cin >> tmp;
if ( tmp & 1 ) {
odd.push_back(tmp);
}
else {
even.push_back(tmp);
}
}
int n_even = p, n_odd = k - p;
// odd is not enough
if ( odd.size() < n_odd ) {
printf ( "NO\n" );
continue;
}
// number of odd's parity is not match
else if ( (odd.size() - n_odd) & 1 ) {
printf ( "NO\n" );
continue;
}
// even number is not enough
else if ( (even.size() + (odd.size() - n_odd) / 2) < n_even ) {
printf ( "NO\n" );
continue;
}
else {
printf ( "YES\n" );
int j, h, z;
for ( j = 0; j < k; ++j )
ans[j].clear();
// add n_odd odd numbers
for ( j = 0, h = 0; j < n_odd; ++j, ++h ) {
ans[h].push_back(odd[j]);
}
// add as much as even numbers
for ( z = 0; z < even.size() && h < k; ++h, ++z ) {
ans[h].push_back(even[z]);
}
if ( h == k ) {
// remaining even numbers
for ( ; z < even.size(); ++z )
ans[0].push_back(even[z]);
// remaining odd numbers
for ( ; j + 1 < odd.size(); j+=2 ) {
ans[0].push_back(odd[j]);
ans[0].push_back(odd[j+1]);
}
}
else {
// we should add those odd numbers to serve as even sets
for ( ; j + 1< odd.size() && h < k; ++h, j += 2 ) {
ans[h].push_back(odd[j]);
ans[h].push_back(odd[j+1]);
}
// because there must not be any even numbers, we just add odd numbers
for ( ; j + 1 < odd.size(); j+=2 ) {
ans[0].push_back(odd[j]);
ans[0].push_back(odd[j+1]);
}
}
for ( z = 0; z < k; ++z ) {
printf ( "%ld", ans[z].size() );
for ( j = 0; j < ans[z].size(); ++j ) {
printf ( " %d", ans[z][j] );
}
printf ( "\n" );
}
}
}
return EXIT_SUCCESS;
} /* ---------- end of function main ---------- */
Devu and his brother love each other a lot. As they are super geeks, they only like to play with arrays. They are given two arrays a and b by their father. The array a is given to Devu and b to his brother.
As Devu is really a naughty kid, he wants the minimum value of his array a should be at least as much as the maximum value of his brother’s array b.
Now you have to help Devu in achieving this condition. You can perform multiple operations on the arrays. In a single operation, you are allowed to decrease or increase any element of any of the arrays by 1. Note that you are allowed to apply the operation on any index of the array multiple times.
You need to find minimum number of operations required to satisfy Devu’s condition so that the brothers can play peacefully without fighting.
Input The first line contains two space-separated integers n, m (1 ≤ n, m ≤ 105). The second line will contain n space-separated integers representing content of the array a (1 ≤ ai ≤ 109). The third line will contain m space-separated integers representing content of the array b (1 ≤ bi ≤ 109).
Output You need to output a single integer representing the minimum number of operations needed to satisfy Devu’s condition.
Sample test(s) input 2 2 2 3 3 5 output 3 input 3 2 1 2 3 3 4 output 4 input 3 2 4 5 6 1 2 output 0 Note In example 1, you can increase a1 by 1 and decrease b2 by 1 and then again decrease b2 by 1. Now array a will be [3; 3] and array b will also be [3; 3]. Here minimum element of a is at least as large as maximum element of b. So minimum number of operations needed to satisfy Devu’s condition are 3.
In example 3, you don’t need to do any operation, Devu’s condition is already satisfied.
This solution is amazing!
/*
* =====================================================================================
* Filename : Brother.cpp
* Description : smart solution
* Version : 0.1
* Created : 06/07/14 21:51
* Author : Liu Xue Yang (LXY), liuxueyang457@163.com
* Motto : Suicide is Painless
* =====================================================================================
*/
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
#include <cstdlib>
using namespace std;
/*
* === FUNCTION ======================================================================
* Name: main
* =====================================================================================
*/
int
main ( int argc, char *argv[] )
{
int n, m;
#ifndef ONLINE_JUDGE
freopen("Brother.txt", "r", stdin);
#endif
vector<int> a, b;
while ( cin >> n >> m ) {
int i, tmp;
a.clear();
b.clear();
for (i = 0; i < n; ++i) {
cin >> tmp;
a.push_back(tmp);
}
for (i = 0; i < m; ++i) {
cin >> tmp;
b.push_back(tmp);
}
sort(a.begin(), a.end());
sort(b.begin(), b.end(), greater<int>());
long long int res = 0;
for (i = 0; i < min(n, m) && a[i] < b[i]; ++i)
res += (b[i] - a[i]);
cout << res << endl;
}
return EXIT_SUCCESS;
} /* ---------- end of function main ---------- */