396 - Top Dog

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

Moderator: Board moderators

Post Reply
_.B._
Experienced poster
Posts: 160
Joined: Sat Feb 07, 2004 7:50 pm
Location: Venezuela
Contact:

396 - Top Dog

Post by _.B._ »

Greetings!
I need help with this problem ( http://acm.uva.es/p/v3/396.html ).
I get the right output for the sample input, and TRIED to consider EVERYTHING this problem says :o
I'm getting WAs.
What did you have to consider to get this problem ACed??
Any critical I/O for this problem?

Thanks in advance! :wink:
_.

daveon
Experienced poster
Posts: 229
Joined: Tue Aug 31, 2004 2:41 am
Location: TORONTO, CANADA

Post by daveon »

Hey Bernardo,

I solved this problem a long time ago. Can't believe I can still understand it. First time was tough.

Try setting the maximum string length to 1000.
Other than that, if you can get the sample IO, you are very close to getting AC.

_.B._
Experienced poster
Posts: 160
Joined: Sat Feb 07, 2004 7:50 pm
Location: Venezuela
Contact:

Thanks.

Post by _.B._ »

Greetings!
Thanks again for the help, Daveon, but still WA :o
I think I'll re-code this problem whenever I find time for it.
Tedious problem :-?

Keep posting! :D
_.

Kevin
New poster
Posts: 7
Joined: Tue Oct 24, 2006 2:14 am

Post by Kevin »

I'll agree that this problem is tedious. Can anyone see the problem in my code or provide some test cases? I think I understand how they are doing multiple test cases.

This works on sample.

Code: Select all

#include <cstdio>
#include <cstring>
#include <string>
#include <map>
#include <vector>
#include <iostream>
#include <sstream>

using namespace std;

bool readline(string& line) {
  char buff[1024];
  if (!fgets(buff, 1024, stdin)) {
    return false;
  }
  for(char *p=buff; *p; ++p) {
    if (*p == '\r' || *p == '\n') {
      *p = 0;
      break;
    }
  }
  line = buff;
  return true;
}

struct col {
  string name;
  string type;
  int size;
};

int main() {
  int dn; 
  while(scanf(" %d ", &dn) == 1) {
    if (dn > 1) {
      printf("\n");
    }
    printf("%d\n", dn);
    vector<string> tbl;
    string line;
    while(readline(line) && line != "") {
      tbl.push_back(line);
    }
    map<string, vector<col> > m;
    while(readline(line) && line != "") {
      string t = line;
      m[t].clear();
      while(readline(line) && line != "#") {
	istringstream iss(line);
	string tp;
	m[t].push_back(col());
	iss >> m[t].back().name >> tp;
	if (tp == "VARCHAR") {
	  iss >> m[t].back().size;
	} else {
	  m[t].back().size = 0;
	}
	if (tp == "VARCHAR" ||
	    tp == "DATE") {
	  m[t].back().type = "CHAR";  
	} else {
	  m[t].back().type = "NUM";
	}	
      }
    }    
    map<string, vector<vector<string> > > n;
    while(readline(line) && line != "") {
      string t = line;
      while(readline(line) && line != "#") {
	n[t].push_back(vector<string>(m[t].size()));
	if (line == "<NULL") line = "";
	n[t].back()[0] = line;
	for(int i=1; i<m[t].size(); ++i) {
	  string x;
	  readline(x);
	  if (x == "<NULL>") x = "";
	  n[t].back()[i] = x;
	}
      }
    }
    for(vector<string>::iterator i=tbl.begin(); i!=tbl.end(); ++i) {
      if (m.find(*i) == m.end()) {
	printf("<TABLE NOT FOUND>\n");
      } else {
	printf("SELECT");
	for(vector<col>::iterator j=m[*i].begin(); 
	    j!=m[*i].end(); ++j) {
	  printf(" (%s) %s", j->type.c_str(), j->name.c_str());
	  if ((j+1) != m[*i].end()) {
	    printf(",");
	  }
	}
	printf(" FROM %s;\n", i->c_str());
      }
    }
    printf("\n");
    for(vector<string>::iterator i=tbl.begin(); i!=tbl.end(); ++i) {
      if (m.find(*i) != m.end()) {
	printf("%s(%d)(%d)\n", i->c_str(), m[*i].size(), n[*i].size()); 
	for(vector<vector<string> >::iterator j=n[*i].begin();
	    j!=n[*i].end(); ++j) {
	  vector<col>::iterator x=m[*i].begin();
	  for(vector<string>::iterator k=j->begin(); k!=j->end();
	      ++k, ++x) {
	    if (x->size > 64) {
	      printf("%s(%d) \"%s\"\n", x->name.c_str(),
		     x->size, k->c_str());
	    } else {
	      printf("%s \"%s\"\n", x->name.c_str(), k->c_str());
	    }
	  }
	}
      }
    }
  }
}

Dominik Michniewski
Guru
Posts: 834
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:

396 - P.E.

Post by Dominik Michniewski »

I solve this problem, but I got P.E. (so I assume, that problem is correctly solved and I must have mistake in output presentation).

I use following code to output data:

Code: Select all

void PrintSelects(TABLE *t)
{
	COLUMN *cc;

	while(t)
	{
		if(t->found != 1)
			printf("<TABLE NOT FOUND>\n");
		else
		{
			cc = t->c;
			printf("SELECT (%s) %s",((cc->type == NUM) ? "NUM" : "CHAR"),cc->name);
			cc = cc->next;
			while(cc)
			{
				printf(", (%s) %s",((cc->type == NUM) ? "NUM" : "CHAR"),cc->name);
				cc = cc->next;
			}
			printf(" FROM %s;\n",t->name);
		}
		t = t->next;
	}
	printf("\n");
}

void PrintData(TABLE *t)
{
	COLUMN *c,*r;

	while(t)
	{
		if(t->found)
		{
			printf("%s(%d)(%d)\n",t->name,t->cols,t->rows);
			r = t->r;
			c = t->c;
			while(r)
			{
				printf("%s",c->name);
				if(c->len > MAXDATA) printf("(%d)",c->len);
				printf(" \"%s\"\n",r->val);
				c = c->next;
				if(c == NULL) c = t->c;
				r = r->next;
			}
		}
		t = t->next;
	}
}
Is this correct ? Or could anyone shows me where am I wrong ?

Best regards
DM
If you really want to get Accepted, try to think about possible, and after that - about impossible ... and you'll get, what you want ....
Born from ashes - restarting counter of problems (800+ solved problems)

RainCT
New poster
Posts: 2
Joined: Sat Apr 03, 2010 1:29 am

Re: 396 -> Top Dog -> Top help!

Post by RainCT »

I'm also getting WA even though it works perfectly with the example input... Any idea?

Code: Select all

// -------------------------------------------------------------
//
// 396 - Top Dog
//
// http://uva.onlinejudge.org/index.php?option=onlinejudge&page=show_problem&problem=332
//
// By Siegfried Gevatter <siegfried@gevatter.com>
//
// -------------------------------------------------------------

#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <map>
#include <assert.h>
using namespace std;

typedef map<string, string> DataMap;
typedef vector<string> Names;
typedef vector<string> RowData;
typedef vector<RowData> Rows;

struct Column {
	string name;
	string type;
	unsigned short int size;
};
typedef vector<Column> Columns;

struct Table {
	string name;
	Columns columns;
};
typedef vector<Table> Tables;

// "Data type" to "generic data type" mapping
static DataMap datatypes;

string sql_statement(Table table) {
	Columns columns = table.columns;
	string sql = "SELECT ";
	int runs = 0;
	for (Columns::iterator it = columns.begin(); it != columns.end(); ++it) {
		if (runs++ > 0) sql += ", ";
		sql += "(" + datatypes[it->type] + ") " + it->name;
	}
	return sql + " FROM " + table.name + ";";
}

Table read_table(string name) {
	Table table;
	table.name = name;
	
	while (cin >> name and name != "#")  {
		Column column;
		column.name = name;
		string type;
		cin >> type;
		column.type = type;
		if (type == "VARCHAR") {
			unsigned short int size;
			cin >> size;
			column.size = size;
		}
		table.columns.push_back(column);
	}
		
	return table;
}

bool find_table(Table& table, const Tables& tables, string name) {
	for(Tables::const_iterator tb = tables.begin(); tb != tables.end(); ++tb) {
		if (tb->name == name) {
			table = *tb;
			return true;
		}
	}
	return false;
}

void process() {
	Tables tables;
	Names names;
	string name;
	
	// Read table names
	while (getline(cin, name) and name != "") {
		names.push_back(name);
	}
	
	// Read table information
	while (getline(cin, name) and name != "") {
		Table table = read_table(name);
		for(Names::iterator it = names.begin(); it != names.end(); ++it) {
			if (*it == name) {
				// We want this table, store it.
				tables.push_back(table);
				break;
			}
		}
		cin.ignore(1, '\n');
	}
	
	for(Names::iterator it = names.begin(); it != names.end(); ++it) {
		Table tb;
		if (find_table(tb, tables, *it)) cout << sql_statement(tb) << endl;
		else cout << "<TABLE NOT FOUND>" << endl;
	}
	cout << endl;
	
	for(Names::iterator it = names.begin(); it != names.end(); ++it) {
		Table tb;
		if (find_table(tb, tables, *it)) {
			int columns = tb.columns.size();
			
			cin >> name;
			assert(name == tb.name);
			cin.ignore(1, '\n');
			
			string data;
			Rows rows;
			while (getline(cin, data) and data != "#") {
				RowData rowdata;
				rowdata.push_back(data);
				for (int i = 1; i < columns; ++i) {
					getline(cin, data);
					if (data == "<NULL>") data = "";
					rowdata.push_back(data);
				}
				rows.push_back(rowdata);
			}
			
			cout << name << "(" << columns << ")(" << rows.size() << ")" << endl;
			for (Rows::iterator it = rows.begin(); it != rows.end(); ++it) {
				for (RowData::size_type i = 0; i < it->size(); ++i) {
					Column col = tb.columns[i];
					cout <<  col.name;
					if (col.type == "VARCHAR" and col.size > 64)
						cout << "(" << col.size << ")";
					cout << " \"" << (*it)[i] << '"' << endl;
				}
			}
		}
	}
}

int main() {
	// Populate the DataType-GenericDataType map
	datatypes["VARCHAR"] = "CHAR";
	datatypes["DATE"] = "CHAR";
	datatypes["INT"] = "NUM";
	datatypes["LONGINT"] = "NUM";
	
	// Do stuff
	int amount = 0;
	int n;
	while (cin >> n) {
		if (amount++ > 0) cout << endl;
		cin.ignore(1, '\n');
		cout << n << endl;
		process();
	}
	
	return 0;
}

Post Reply

Return to “Volume 3 (300-399)”