Wednesday, April 30, 2014

Sereja And Mugs [ Codeforces.com Round #243 (Div. 2) Problem A ] [Java]

A. Sereja and Mugs
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output
Sereja showed an interesting game to his friends. The game goes like that. Initially, there is a table with an empty cup and n water mugs on it. Then all players take turns to move. During a move, a player takes a non-empty mug of water and pours all water from it into the cup. If the cup overfills, then we assume that this player lost.
As soon as Sereja's friends heard of the game, they wanted to play it. Sereja, on the other hand, wanted to find out whether his friends can play the game in such a way that there are no losers. You are given the volumes of all mugs and the cup. Also, you know that Sereja has (n - 1) friends. Determine if Sereja's friends can play the game so that nobody loses.
Input
The first line contains integers n and s (2 ≤ n ≤ 100; 1 ≤ s ≤ 1000) — the number of mugs and the volume of the cup. The next line contains n integers a1a2...an (1 ≤ ai ≤ 10). Number ai means the volume of the i-th mug.
Output
In a single line, print "YES" (without the quotes) if his friends can play in the described manner, and "NO" (without the quotes) otherwise.
Sample test(s)
input
3 4
1 1 1
output
YES
input
3 4
3 1 3
output
YES
input
3 4
4 4 4
output
NO

My Solution (Java) : 
→ Source
import java.util.Arrays;
import java.util.Scanner;

public class SerejaAndMugs {

    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt(); //no of players including Sereja
        int c = scan.nextInt(); //capacity of the cup

        int mugs[] = new int[n];
        for (int i = 0; i < n; ++i) {
            mugs[i] = scan.nextInt();
        }

        Arrays.sort(mugs);
        int t = 0;
        for (int i = 0; i < n - 1; ++i) {
            t += mugs[i];
            if (mugs[i] <= c && t <= c) {
                continue;
            } else {
                System.out.println("NO");
                System.exit(0);
            }
        }
        System.out.println("YES");
    }
}

Monday, April 28, 2014

Data Recovery (A) : CodeForces.com

A. Data Recovery
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output
Not so long ago company R2 bought company R1 and consequently, all its developments in the field of multicore processors. Now the R2 laboratory is testing one of the R1 processors.
The testing goes in n steps, at each step the processor gets some instructions, and then its temperature is measured. The head engineer in R2 is keeping a report record on the work of the processor: he writes down the minimum and the maximum measured temperature in his notebook. His assistant had to write down all temperatures into his notebook, but (for unknown reasons) he recorded only m.
The next day, the engineer's assistant filed in a report with all the m temperatures. However, the chief engineer doubts that the assistant wrote down everything correctly (naturally, the chief engineer doesn't doubt his notes). So he asked you to help him. Given numbers n,mminmax and the list of m temperatures determine whether you can upgrade the set of m temperatures to the set of ntemperatures (that is add n - m temperatures), so that the minimum temperature was min and the maximum one was max.
Input
The first line contains four integers n, m, min, max (1 ≤ m < n ≤ 100; 1 ≤ min < max ≤ 100). The second line contains m space-separated integers ti (1 ≤ ti ≤ 100) — the temperatures reported by the assistant.
Note, that the reported temperatures, and the temperatures you want to add can contain equal temperatures.
Output
If the data is consistent, print 'Correct' (without the quotes). Otherwise, print 'Incorrect' (without the quotes).

Sample test(s)
input
2 1 1 2
1
output
Correct
input
3 1 1 3
2
output
Correct
input
2 1 1 3
2
output
Incorrect
Note
In the first test sample one of the possible initial configurations of temperatures is [1, 2].
In the second test sample one of the possible initial configurations of temperatures is [2, 1, 3].
In the third test sample it is impossible to add one temperature to obtain the minimum equal to 1 and the maximum equal to 3.
My solution:
import java.util.LinkedList;
import java.util.List;
import java.util.Scanner;

public class DataRecovery {

    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        int m = scan.nextInt();
        int min = scan.nextInt();
        int max = scan.nextInt();
        List<Integer> list = new LinkedList<Integer>();
        int temperatures = 0;
        for (int i = 0; i < m; ++i) {
            temperatures = scan.nextInt();
            list.add(temperatures);
        }
        int flag = 0;
        for (int i = 0; i < list.size(); ++i) {

            if (list.get(i) == min) {
                flag++;
            }
            if (list.get(i) == max) {
                flag++;
            }
            if(list.get(i)>max||list.get(i)<min){
                System.out.println("Incorrect");
                System.exit(0);
            }
        }
        if (m <= n - 2) {
            System.out.println("Correct");
        }
        if (m == n - 1) {
            if (flag>=1) {
                System.out.println("Correct");
            } else if (flag == 0) {
                System.out.println("Incorrect");
            }
        }
    }
}

Friday, April 25, 2014

Mashmokh and Lights [Problem 415A Codeforces.com] : C++ Solution

A. Mashmokh and Lights
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output
Mashmokh works in a factory. At the end of each day he must turn off all of the lights.
The lights on the factory are indexed from 1 to n. There are n buttons in Mashmokh's room indexed from 1 to n as well. If Mashmokh pushes button with index i, then each light with index not less than i that is still turned on turns off.
Mashmokh is not very clever. So instead of pushing the first button he pushes some of the buttons randomly each night. He pushed mdistinct buttons b1, b2, ..., bm (the buttons were pushed consecutively in the given order) this night. Now he wants to know for each light the index of the button that turned this light off. Please note that the index of button bi is actually bi, not i.
Please, help Mashmokh, print these indices.
Input
The first line of the input contains two space-separated integers n and m (1 ≤ n, m ≤ 100), the number of the factory lights and the pushed buttons respectively. The next line contains m distinct space-separated integers b1, b2, ..., bm (1 ≤ bi ≤ n).
It is guaranteed that all lights will be turned off after pushing all buttons.
Output
Output n space-separated integers where the i-th number is index of the button that turns the i-th light off.
Sample test(s)
input
5 4
4 3 1 2
output
1 1 3 4 4 
input
5 5
5 4 3 2 1
output
1 2 3 4 5 
Note
In the first sample, after pressing button number 4, lights 4 and 5 are turned off and lights 1, 2 and 3 are still on. Then after pressing button number 3, light number 3 is turned off as well. Pressing button number 1 turns off lights number 1 and 2 as well so pressing button number 2 in the end has no effect. Thus button number 4 turned lights 4 and 5 off, button number 3 turned light 3 off and button number 1 turned light 1 and 2 off.

My Solution ( C++ ) :
→ Source
#include <iostream>
#include <vector>

using namespace std;

int main(){
    int n=0;//no of lights
    cin>>n;
    int *lights = new int[n+1];
    for(int i =1;i<=n;++i){
        lights[i]=-1;
    }

    int p = 0;//no of pressed buttons
    cin>>p;

    vector<int> vec(p);
    int press=-1;
    for(int i=0;i<p;++i){
        cin>>press;
        vec.push_back(press);
    }

    for(auto &it:vec){
        for(int i =it;i<=n&&lights[i]==-1;++i){
            lights[i]=it;
        }
    }
    for(int i=1;i<=n;++i){
        cout<<lights[i]<<" ";
    }
    return 0;
}

Pasha and Hamster [codeforces.com, Problem A, Div 2] [C++]

A. Pasha and Hamsters
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output
Pasha has two hamsters: Arthur and Alexander. Pasha put n apples in front of them. Pasha knows which apples Arthur likes. Similarly, Pasha knows which apples Alexander likes. Pasha doesn't want any conflict between the hamsters (as they may like the same apple), so he decided to distribute the apples between the hamsters on his own. He is going to give some apples to Arthur and some apples to Alexander. It doesn't matter how many apples each hamster gets but it is important that each hamster gets only the apples he likes. It is possible that somebody doesn't get any apples.
Help Pasha distribute all the apples between the hamsters. Note that Pasha wants to distribute all the apples, not just some of them.
Input
The first line contains integers nab (1 ≤ n ≤ 100; 1 ≤ a, b ≤ n) — the number of apples Pasha has, the number of apples Arthur likes and the number of apples Alexander likes, correspondingly.
The next line contains a distinct integers — the numbers of the apples Arthur likes. The next line contains b distinct integers — the numbers of the apples Alexander likes.
Assume that the apples are numbered from 1 to n. The input is such that the answer exists.
Output
Print n characters, each of them equals either 1 or 2. If the i-h character equals 1, then the i-th apple should be given to Arthur, otherwise it should be given to Alexander. If there are multiple correct answers, you are allowed to print any of them.
Sample test(s)

input
4 2 3
1 2
2 3 4
output
1 1 2 2
input
5 5 2
3 4 1 2 5
2 3
output
1 1 1 1 1


My Solution (C++):

#include <iostream>
#include <vector>

using namespace std;

int main()
{
    int n=0; //no of apples
    cin>>n;
    int a=0; //no of apples arthur likes
    cin>>a;
    int b=0;    //no of apples alexander likes
    cin>>b;

    vector<int> aLikes;
    vector<int> bLikes;
    int *apples = new int[n+1];

    for(int i =1;i<=n;++i)
    apples[i]=0;

    int get=0;
    for(int i =0;i<a;++i){
        cin>>get;
        aLikes.push_back(get);
    }
    for(int i=0;i<b;++i){
        cin>>get;
        bLikes.push_back(get);
    }

    for(int i =1;i<=n;++i){
        for(auto &it:aLikes){
            if(it == i){
                cout<<"1 ";
                apples[i]=1;
                break;
            }
        }

        for(auto &it:bLikes){
            if(it == i && apples[i]!=1){
                cout<<"2 ";
                apples[i]=1;
                break;
            }
        }
    }
    return 0;
}

Deceitful War (Google Code Jam 2014 Qualification Round Problem D) Solution

Problem

Naomi and Ken sometimes play games together. Before they play, each of them gets Nidentical-looking blocks of wood with masses between 0.0kg and 1.0kg (exclusive). All of the blocks have different weights. There are lots of games they could play with those blocks, but they usually play something they call War. Here is how War works:
  1. Each player weighs each of his or her own blocks, so each player knows the weights of all of his or her own blocks, but not the weights of the other player's blocks.
  2. They repeat the following process N times:
    1. Naomi chooses one of her own blocks, with mass ChosenNaomi.
    2. Naomi tells Ken the mass of the block she chose.
    3. Ken chooses one of his own blocks, with mass ChosenKen.
    4. They each put their block on one side of a balance scale, and the person whose block is heavier gets one point.
    5. Both blocks are destroyed in a fire.
Naomi has realized three things about War. First, she has realized that she loses a lot. Second, she has realized that there is a unique strategy that Ken can follow to maximize his points without assuming anything about Naomi's strategy, and that Ken always uses it. Third, she has realized that she hates to lose. Naomi has decided that instead of playing War, she will play a game she calls Deceitful War. The great thing about Deceitful War is that Ken will think they're playing War!
Here is how Deceitful War works, with differences between Deceitful War and War in bold:
  1. Each player weighs each of his or her own blocks. Naomi also weighs Ken's blocks while he isn't looking, so Naomi knows the weights of all blocks and Ken only knows the weights of his own blocks.
  2. They repeat the following process N times:
    1. Naomi chooses one of her own blocks, with mass ChosenNaomi.
    2. Naomi tells Ken a number, ToldNaomi, between 0.0kg and 1.0kg exclusive. Ken, who thinks they're playing War, thinks the number Naomi just told him is ChosenNaomi.
    3. Ken chooses one of his own blocks, with mass ChosenKen.
    4. They each put their block on one side of a balance scale, and the person whose block is heavier gets one point.
    5. Both blocks are destroyed in a fire.
Naomi doesn't want Ken to know that she isn't playing War; so when she is choosing which block to play, and what mass to tell Ken, she must make sure that the balance scale won't reveal that ChosenNaomi ≠ ToldNaomi. In other words, she must make decisions so that:
  • ChosenNaomi > ChosenKen if, and only if, ToldNaomi > ChosenKen, and
  • ToldNaomi is not equal to the mass of any of Ken's blocks, because he knows that isn't possible.
It might seem like Naomi won't win any extra points by being deceitful, because Ken might discover that she wasn't playing War; but Naomi knows Ken thinks both players are playing War, and she knows what he knows, and she knows Ken will always follow his unique optimal strategy for War, so she can always predict what he will play.
You'll be given the masses of the blocks Naomi and Ken started with. Naomi will play Deceitful War optimally to gain the maximum number of points. Ken will play War optimally to gain the maximum number of points assuming that both players are playing War. What will Naomi's score be? What would it have been if she had played War optimally instead?

Examples

If each player has a single block left, where Naomi has 0.5kg and Ken has 0.6kg, then Ken is guaranteed to score the point. Naomi can't say her number is ≥ 0.6kg, or Ken will know she isn't playing War when the balance scale shows his block was heavier.
If each player has two blocks left, where Naomi has [0.7kg, 0.2kg] and Ken has [0.8kg, 0.3kg], then Naomi could choose her 0.2kg block, and deceive Ken by telling him that she chose a block that was 0.6kg. Ken assumes Naomi is telling the truth (as in how the War game works) and will play his 0.8kg block to score a point. Ken was just deceived, but he will never realize it because the balance scale shows that his 0.8kg block is, like he expected, heavier than the block Naomi played. Now Naomi can play her 0.7kg block, tell Ken it is 0.7kg, and score a point. If Naomi had played War instead of Deceitful War, then Ken would have scored two points and Naomi would have scored zero.

Input

The first line of the input gives the number of test cases, TT test cases follow. Each test case starts with a line containing a single integer N, the number of blocks each player has. Next follows a line containing N space-separated real numbers: the masses of Naomi's blocks, in kg. Finally there will be a line containing N space-separated real numbers: the masses of Ken's blocks, in kg.
Each of the masses given to Ken and Naomi will be represented as a 0, followed by a decimal point, followed by 1-5 digits. Even though all the numbers in the input have 1-5 digits after the decimal point, Ken and Naomi don't know that; so Naomi can still tell Ken that she played a block with mass 0.5000001kg, and Ken has no reason not to believe her.

Output

For each test case, output one line containing "Case #xy z", where x is the test case number (starting from 1), y is the number of points Naomi will score if she plays Deceitful War optimally, and z is the number of points Naomi will score if she plays War optimally.

Limits

1 ≤ T ≤ 50. All the masses given to Ken and Naomi are distinct, and between 0.0 and 1.0 exclusive.

Small dataset

1 ≤ N ≤ 10.

Large dataset

1 ≤ N ≤ 1000.

Sample

Input   
4
1
0.5
0.6
2
0.7 0.2
0.8 0.3
3
0.5 0.1 0.9
0.6 0.4 0.3
9
0.186 0.389 0.907 0.832 0.959 0.557 0.300 0.992 0.899
0.916 0.728 0.271 0.520 0.700 0.521 0.215 0.341 0.458


Output   
Case #1: 0 0
Case #2: 1 0
Case #3: 2 1
Case #4: 8 4
My solution to this problem ( C++ ):

#include <iostream>
#include <algorithm>
#include <vector>
#include <fstream>

using namespace std;

int main()
{
    ifstream input("D-large-practice.in");
    ofstream output("output2.out");
 int nCases=0;
 input>>nCases;

 for(int i =0;i<nCases;++i)
 {
  int nBlocks=0;
  input>>nBlocks;

  vector<float> nVec;
  vector<float> kVec;
  vector<float>::iterator itN = nVec.begin();


  for(int j=0;j<nBlocks;++j)
  {
   float push;
   input>>push;
   nVec.push_back(push);
  }

  for(int j=0;j<nBlocks;++j)
  {
   float push;
   input>>push;
   kVec.push_back(push);
  }

  vector<float>::iterator itK = kVec.begin();
  int nPoints=0;
  int mark=-1;

 //if Naomi plays Decietful war
  sort(nVec.begin(), nVec.end());
  sort(kVec.begin(), kVec.end());
  int nPointsDW=0;
  int k =0;
  for(int i =0;i<nVec.size();++i)
  {
            for(int j = k;j<kVec.size();++j)
            {
                if(nVec[i]>kVec[j])
                {
                  k++;
                  nPointsDW++;
                  break;
                }
            }
        }

        //if naomi plays War
  reverse(nVec.begin(), nVec.end());
  for(unsigned int i=0;i<nVec.size();++i)
  {
   mark=-1;
   for(unsigned int j=0;j<kVec.size();++j)
   {
    if(nVec[i]<kVec[j])
    {
     mark = 1;
     break;
    }
    itK++;
   }

   if(mark==-1)
   {
    nPoints++;
   }
   else
   {
    kVec.erase(itK);
   }
   itK=kVec.begin();
  }
  output<<"Case #"<<i+1<<": "<<nPointsDW<<" "<<nPoints<<endl;
 }
 return 0;
}