Sunday, 21 June 2015

Code Forces Round #304A C++ Solution.

/*
  A. Soldier and Bananas
A soldier wants to buy w bananas in the shop. He has to pay k dollars for the first banana, 2k dollars for the second one and so on (in other words, he has to pay i·k dollars for the i-th banana).
He has n dollars. How many dollars does he have to borrow from his friend soldier to buy w bananas?
Input
The first line contains three positive integers k, n, w (1  ≤  k, w  ≤  10000 ≤ n ≤ 109), the cost of the first banana, initial number of dollars the soldier has and number of bananas he wants.
Output
Output one integer — the amount of dollars that the soldier must borrow from his friend. If he doesn't have to borrow money, output 0.
Sample test(s)
input
3 17 4
output
13

*/

#include<bits/stdc++.h>
using namespace std;
/*
    *
    * Prosen Ghosh
    * American International University - Bangladesh (AIUB)
    *
*/
int main()
{
    long long k,n,w,ans = 0;
    cin >> k >> n >> w;
    for(int i = 1; i <= w; i++){
        ans += i*k;
    }
    ans-=n;
    if(ans <= 0)cout << 0 << endl;
    else cout << ans << endl;
    return 0;
}

Saturday, 20 June 2015

Code Forces 492A C++ Solution.

/*
  A. Vanya and Cubes
Vanya got n cubes. He decided to build a pyramid from them. Vanya wants to build the pyramid as follows: the top level of the pyramid must consist of 1 cube, the second level must consist of 1 + 2 = 3 cubes, the third level must have 1 + 2 + 3 = 6 cubes, and so on. Thus, the i-th level of the pyramid must have 1 + 2 + ... + (i - 1) + i cubes.
Vanya wants to know what is the maximum height of the pyramid that he can make using the given cubes.
Input
The first line contains integer n (1 ≤ n ≤ 104) — the number of cubes given to Vanya.
Output
Print the maximum possible height of the pyramid in the single line.
Sample test(s)
input
1
output
1
input
25
output
4
Note
Illustration to the second sample:

*/

#include<iostream>
#include<cstring>
#include<cstdio>
#include<string>

using namespace std;
/*
    *
    * Prosen Ghosh
    * American International University - Bangladesh (AIUB)
    *
*/
int main(){

    int sum = 0,input,cnt = 0,ans = 0,next_sum = 0;
    cin >> input;
    if(input == 1){cout << 1 << endl;return 0;}
    for(int i = 1; i < input; i++){
        sum = 0;
        next_sum = 0;
        for(int j = 1; j <= i;j++){
            sum+=j;
            next_sum+=j+1;
        }
        ans+=sum;
        cnt++;
        if(ans+next_sum >= input||ans == input)break;
    }
    cout << cnt << endl;
    return 0;
}


Code Forces 492B C++ Solution.

/*
  B. Vanya and Lanterns
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output
Vanya walks late at night along a straight street of length l, lit by n lanterns. Consider the coordinate system with the beginning of the street corresponding to the point 0, and its end corresponding to the point l. Then the i-th lantern is at the point ai. The lantern lights all points of the street that are at the distance of at most d from it, where d is some positive number, common for all lanterns.
Vanya wonders: what is the minimum light radius d should the lanterns have to light the whole street?
Input
The first line contains two integers nl (1 ≤ n ≤ 10001 ≤ l ≤ 109) — the number of lanterns and the length of the street respectively.
The next line contains n integers ai (0 ≤ ai ≤ l). Multiple lanterns can be located at the same point. The lanterns may be located at the ends of the street.
Output
Print the minimum light radius d, needed to light the whole street. The answer will be considered correct if its absolute or relative error doesn't exceed 10 - 9.
Sample test(s)
input
7 15
15 5 3 7 9 14 0
output
2.5000000000
input
2 5
2 5
output
2.0000000000
Note
Consider the second sample. At d = 2 the first lantern will light the segment [0, 4] of the street, and the second lantern will light segment[3, 5]. Thus, the whole street will be lit.

*/


#include<iostream>
#include<cstring>
#include<cstdio>
#include<string>
#include<algorithm>

using namespace std;
/*
    *
    * Prosen Ghosh
    * American International University - Bangladesh (AIUB)
    *
*/
int main(){

    long long int n,l;
    double ar[1005],max_val = 0.0,val = 0.0;
    cin >> n >> l;
    for(long long int i = 0; i < n; i++){
        cin >> ar[i];
    }
    sort(ar,ar+n);
    for(long long int i = 0; i < n-1; i++){
        val = ar[i+1]-ar[i];
        if(val>max_val)max_val = val;
    }
    double val2 = 0.0,val3 = 0.0;
    val2 = ar[0]-0;
    max_val/=2;
    //*if(ar[n-1] > l)*/
    val3 = l - ar[n-1];
    if(val2 > max_val)max_val = val2;
    if(val3 > max_val)max_val = val3;
    printf("%.10f",max_val);
    return 0;
}

Code Forces 499A C++ Solution.

/*
A. Watching a movie

You have decided to watch the best moments of some movie. There are two buttons on your player:
  1. Watch the current minute of the movie. By pressing this button, you watch the current minute of the movie and the player automatically proceeds to the next minute of the movie.
  2. Skip exactly x minutes of the movie (x is some fixed positive integer). If the player is now at the t-th minute of the movie, then as a result of pressing this button, it proceeds to the minute (t + x).
Initially the movie is turned on in the player on the first minute, and you want to watch exactly n best moments of the movie, the i-th best moment starts at the li-th minute and ends at the ri-th minute (more formally, the i-th best moment consists of minutes: li, li + 1, ..., ri).
Determine, what is the minimum number of minutes of the movie you have to watch if you want to watch all the best moments?
Input
The first line contains two space-separated integers nx (1 ≤ n ≤ 501 ≤ x ≤ 105) — the number of the best moments of the movie and the value of x for the second button.
The following n lines contain the descriptions of the best moments of the movie, the i-th line of the description contains two integers separated by a space liri (1 ≤ li ≤ ri ≤ 105).
It is guaranteed that for all integers i from 2 to n the following condition holds: ri - 1 < li.
Output
Output a single number — the answer to the problem.
Sample test(s)
input
2 3
5 6
10 12
output
6
input
1 1
1 100000
output
100000
Note
In the first sample, the player was initially standing on the first minute. As the minutes from the 1-st to the 4-th one don't contain interesting moments, we press the second button. Now we can not press the second button and skip 3 more minutes, because some of them contain interesting moments. Therefore, we watch the movie from the 4-th to the 6-th minute, after that the current time is 7. Similarly, we again skip 3 minutes and then watch from the 10-th to the 12-th minute of the movie. In total, we watch 6 minutes of the movie.
In the second sample, the movie is very interesting, so you'll have to watch all 100000 minutes of the movie.

*/

#include<iostream>
#include<string>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
/*
    *
    * Prosen Ghosh
    * American International University - Bangladesh (AIUB)
    *
*/
int main(){

    int n,x,l[52],r[52],fm = 1;
    cin >> n >> x;
    for(int i = 0; i < n; i++){
        cin >> l[i] >> r[i];
    }
    int ans  = 0,cnt = 0;
    for(int i = 0; i < n; i++){
        while(fm+x <= l[i])fm+=x;
        if(fm <= l[i]){
            while((fm) <= r[i]){
            cnt++;
            fm++;
            }
        }
    }
    cout << cnt << endl;
    return 0;
}

Code Forces 500A C++ Solution.

/*
  A. New Year Transportation
New Year is coming in Line World! In this world, there are n cells numbered by integers from 1 to n, as a 1 × n board. People live in cells. However, it was hard to move between distinct cells, because of the difficulty of escaping the cell. People wanted to meet people who live in other cells.
So, user tncks0121 has made a transportation system to move between these cells, to celebrate the New Year. First, he thought of n - 1positive integers a1, a2, ..., an - 1. For every integer i where 1 ≤ i ≤ n - 1 the condition 1 ≤ ai ≤ n - i holds. Next, he made n - 1 portals, numbered by integers from 1 to n - 1. The i-th (1 ≤ i ≤ n - 1) portal connects cell i and cell (i + ai), and one can travel from cell i to cell(i + ai) using the i-th portal. Unfortunately, one cannot use the portal backwards, which means one cannot move from cell (i + ai) to celli using the i-th portal. It is easy to see that because of condition 1 ≤ ai ≤ n - i one can't leave the Line World using portals.
Currently, I am standing at cell 1, and I want to go to cell t. However, I don't know whether it is possible to go there. Please determine whether I can go to cell t by only using the construted transportation system.
Input
The first line contains two space-separated integers n (3 ≤ n ≤ 3 × 104) and t (2 ≤ t ≤ n) — the number of cells, and the index of the cell which I want to go to.
The second line contains n - 1 space-separated integers a1, a2, ..., an - 1 (1 ≤ ai ≤ n - i). It is guaranteed, that using the given transportation system, one cannot leave the Line World.
Output
If I can go to cell t using the transportation system, print "YES". Otherwise, print "NO".
Sample test(s)
input
8 4
1 2 1 2 1 2 1
output
YES
input
8 5
1 2 1 2 1 1 1
output
NO
Note
In the first sample, the visited cells are: 1, 2, 4; so we can successfully visit the cell 4.
In the second sample, the possible cells to visit are: 1, 2, 4, 6, 7, 8; so we can't visit the cell 5, which we want to visit.

*/


#include<iostream>
using namespace std;
/*
    *
    * Prosen Ghosh
    * American International University - Bangladesh (AIUB)
    *
*/
int main(){

    int n,t,ar[30010],flag = 0;
    cin >> n >> t;
    for(int i = 1; i < n; i++){
        cin >> ar[i];
    }
    for(int i = 1; i < n;){
        if((i+ar[i] == t)){flag = 1;i = (i+ar[i]);break;}
        else if(i+ar[i] > t)break;
        else {flag = 0;i = (i+ar[i]);}
    }
    if(flag)cout << "YES" << endl;
    else cout << "NO" <<endl;
    return 0;
}

Code Forces 501A C++ Solution.

/*
  A. Contest
Misha and Vasya participated in a Codeforces contest. Unfortunately, each of them solved only one problem, though successfully submitted it at the first attempt. Misha solved the problem that costs a points and Vasya solved the problem that costs b points. Besides, Misha submitted the problem c minutes after the contest started and Vasya submitted the problem d minutes after the contest started. As you know, on Codeforces the cost of a problem reduces as a round continues. That is, if you submit a problem that costs p points tminutes after the contest started, you get  points.
Misha and Vasya are having an argument trying to find out who got more points. Help them to find out the truth.
Input
The first line contains four integers abcd (250 ≤ a, b ≤ 35000 ≤ c, d ≤ 180).
It is guaranteed that numbers a and b are divisible by 250 (just like on any real Codeforces round).
Output
Output on a single line:
"Misha" (without the quotes), if Misha got more points than Vasya.
"Vasya" (without the quotes), if Vasya got more points than Misha.
"Tie" (without the quotes), if both of them got the same number of points.
Sample test(s)
input
500 1000 20 30
output
Vasya
input
1000 1000 1 1
output
Tie
input
1500 1000 176 177
output
Misha

*/

#include<iostream>
using namespace std;
/*
    *
    * Prosen Ghosh
    * American International University - Bangladesh (AIUB)
    *
*/
int main(){

    int a,b,c,d,m,v;
    cin >> a >> b >> c >> d;
    m = max((3*a)/10,a-(a/250)*c);
    v = max((3*b)/10,b-(b/250)*d);
    if(m == v){
        cout << "Tie" << endl;
    }
    else if(m > v){
        cout << "Misha" << endl;
    }
    else{
        cout << "Vasya" << endl;
    }
    return 0;
}