Interesting problems from a contest

[crisro996]

Hello there,

in my quest to learn more C++ I started solving some contest excercises and I came across one that seems fairly easy but involves some weird thinking(at least for me at my beginner level).

You have a cup/vase(w/e you want to call it) that is U-shaped.

4| |4
3| |3
2| |2
1\_ _/1
0 0

You insert n liquids. Each liquid comes with 3 pieces of information: volume(always even number), the place where you pour it from (left 'L' or rigth 'R') and the color (expressed in numbers).

So you get sth like this (example of what information you receive):

3
4 R (it has color 1 cause it's the first liquid)
4 L (color 2 cause it's the second)
2 R (and so on..)

I have one problem with this excercise: what's the easiest way (for me) to determine how each liquid falls in the cup?

When one is poured, it's simple half goes to the right and half to the left. But I find it hard to determine how I can easily do the same after the first liquid is poured. Can you please help me? Sorry if it's hard to understand, it's hard to explain.

By the way I use two arrays: one for left side and one for the right one.

[D80DSL3A]

What is to be calculated? Please post a link to the problem statement so I can read it myself.

[muratagenc]

assuming;
1. they do not blend,
2. they have the same unit mass.

so, let's say
1. 4R(1) poured, you got 2R(1), 2L(1)
2. 6L(2) poured, you have 10 in total, they should balance in 5R, 5L;
-- you now have 2R(1) 3R(2), 2L(1) 3L(2)
3. 2L(3) poured, you have 12 in total, balance is 6R, 6L
- 2R(1) 3R(2) 1R(3), 2L(1) 3L(2) 1L(3)
so on so forth..

I think...

ps: you should take care of the case when the vase is full.
ps2: where do you get these questions? I would like to be involved too. thnx.
ps3: not a hw right? ;)

[crisro996]

It's in romanian :) that's why I have problems explaining everything. The liquids indeed do not blend and have the same unit mass. I don't think muratagenc's solution is good I'll try something on paper later, maybe I figured it out eventually ^^.

Do you guys think I should do something like this:

Example:
3
4R(1)
4L(2)
2L(3)

We have 6L and 4R (Left from top:3-3-2-2-2-2 and right form top:1-1-1-1)
If we link the two sides I guess 2 units of liquid 2 will be pushed to the right side. So we get:
L from top: 3-3-2-2-2 and R from top:1-1-1-1-2

I'll start writing the code but do you guys think I am doing it right?The point of this cup/vase is that the liquids push each other to reach the same height on each side.

[kev82]

I think you mean a u-shaped tube rather than vase/cup. the problem is simple with a 2 ended datastructure such as a deque.

#include <iostream>
#include <deque>

int main() {
	std::deque<int> tube;
	int col = 1;

	while(true) {
		int num;
		std::string side;
		std::cin >> num >> side;
		if(!std::cin) break;
		for(int i=0;i!=num;++i) {
			if(side == "L") {
				tube.push_front(col);
			} else {
				tube.push_back(col);
			}
		}
		++col;
	}
	std::cout << std::endl;
	std::cout << std::endl;
	while(!tube.empty()) {
		std::cout << tube.front() << " " << tube.back() << std::endl;
		tube.pop_front();
		tube.pop_back();
	}
	std::cout << std::endl;
	return 0;
}

[crisro996]

Thank you kev82 you were right I meant tube. I finally solved it ^^