11111 - Generalized Matrioshkas

All about problems in Volume 111. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

User avatar
Christian Schuster
Learning poster
Posts: 63
Joined: Thu Apr 04, 2002 2:00 am

Post by Christian Schuster » Mon Nov 13, 2006 2:55 am

A hint for the C people getting TLE:

sscanf() on long input strings is extremely slow, because the glibc implementation of this function scans the string for the terminating \0 character. Using strtok() or something like that is much faster in this problem.

Aklovo
New poster
Posts: 1
Joined: Thu Nov 03, 2011 2:00 am

Re: 11111 - Generalized Matrioshkas

Post by Aklovo » Thu Nov 03, 2011 2:05 am

Someone knows why Im getting Runtime Error?? >.<!

Code: Select all

#include <iostream>
#include <sstream>
#include <vector>
#include <stack>
#include <cstdlib>

using namespace std;

int main()
{
	string line;
	
	while(getline(cin,line))
	{
		stack<double> pila;
		vector<double> vec;
		unsigned ptr = vec.size();
		bool flag = false;
		
		stringstream ss(line);
		
		string temp;
		
		while(ss >> temp)
		{
			bool neg = false;
			
			if(temp[0] == '-') {
				temp.erase(0,1);
				neg = true;
			}
			
			double num = atof(temp.c_str());

			if(neg) {
				
				pila.push(num);

				if(ptr == vec.size()) {
					vec.push_back(num);
				} else {
					vec[ptr] += num;
				}
				++ptr;
				
			} else {
				
				if(ptr > 0)
					--ptr;
				
				if(pila.top() == num) {
					pila.pop
					();
				} else {
					flag = true;
					break;
				}
			}

		}
		
		
		
		if(!flag)
		{
			if(!pila.empty()) { 
				flag = true;
			} else {
			
				for(unsigned i=0 ; i<vec.size()-1 ; i++)
				{
					if(vec[i] <= vec[i+1]){
						flag = true;
						break;
					}
				}	
			
			}
		}
		
		if(flag)
			cout << ":-( Try again." << endl;
		else
			cout << ":-) Matrioshka!" << endl;
	}
}

I use big variables remove the sign before process and nothing can someone help me? Thx!

ljacs
New poster
Posts: 5
Joined: Wed Sep 05, 2012 5:53 am

Re: 11111 - Generalized Matrioshkas

Post by ljacs » Sun Oct 07, 2012 12:24 am

Hello there! I don't know why I get WA for this problem. I've covered sample input/output and it all seems right to me >.<
Could anyone please give me some critical input or figure out my code's problem?
Thank you :)

Edit:
Figured out the problem. For those who are getting WA, here are the previous problems of my code:
1) Do not output for a blank line between two consecutive test cases.
2) Don't forget to check if there is a matrioshka which was opened but was not closed.
3) Beware of multiple spaces between numbers.

Code: Select all

Accepted.

Avenger
New poster
Posts: 1
Joined: Wed Jan 09, 2013 7:07 pm

Re: 11111 - Generalized Matrioshkas

Post by Avenger » Wed Jan 09, 2013 7:12 pm

I have AC, but then I figured out that I didnt consider this case

Code: Select all

-9 9 -9 9
for that my code gives

Code: Select all

:-) Matrioshka!

hipanda
New poster
Posts: 1
Joined: Wed May 07, 2014 2:45 am

Re: 11111 - Generalized Matrioshkas

Post by hipanda » Wed May 07, 2014 3:05 am

I was getting WA, I tried all previous posted test cases and my program was getting those test cases right. Then due to my implementation, this test case helped me:

-9 -1 1 9 -9 -7 7 -1 1 9

It's a valid doll, but my program was mistakenly printing "try again" for this case. Hope this helps some people in my situation.

Post Reply

Return to “Volume 111 (11100-11199)”