210 - Concurrency Simulator

[Dominik Michniewski]

I tried to solve this problem, but I got WA. So I have a few questions to people, who solved this problem.
1. Is this possible, that statement is in more than one line ? i.e.
print
a ?
2. Is this possible, that inside a program code exist empty line ? i.e.
print a

print b ?
I ask, because of sentence "Blanks appearing in a statement should be ignored".
So if both of this question are false, could someone tell me some IO ?
I think, that I create this simulator in the proper way, but I can't got Acc.

Best regards
DM

[little joey]

Answer to both questions: No. My program would certainly crash if that was the case, but it got AC.

My own testdata was:

Code: Select all

1

10 1 1 1 1 1 1
a = 4
print a
lock
b = 9
print b
unlock
print b
end
a = 3
print a
lock
b = 8
print b 
unlock
print b
end
b = 5
a = 17
print a
print b
lock
b = 21
print b
unlock
print b
end
lock
z=26
y=25
x=24
print x
printy
printz
unlock
end
k=7
lock
k=9
k=10
printk
printk
unlock
end
k=7
lock
k=9
k=10
printk
printk
unlock
end
end
k=7
lock
k=9
k=10
printk
printk
unlock
end
k=7
lock
k=9
k=10
printk
printk
unlock
end
k=7
lock
k=9
k=10
printk
printk
unlock
end

but I don't remember all the specifics of this problem.

[Dominik Michniewski]

I've got this output:

Code: Select all

1: 3
2: 3
3: 17
3: 5
4: 24
4: 25
4: 26
5: 10
5: 10
6: 10
6: 10
8: 10
8: 10
9: 10
9: 10
10: 10
10: 10
1: 9
1: 9
2: 8
2: 8
3: 21
3: 21

Is this s correct ? Could you check it ? Checking by hand ten programs is very frustrating ...

Best regards
DM

[little joey]

Yes, your output is correct. Sorry for not having more difficult cases, but it has been a while since I solved it, and don't remember all the specifics.

[Dominik Michniewski]

Could you send me your EXE forthis problem (Win EXE file) ?
I try to find differences without disturbing you )

Best regards
DM

PS. My mail is Dominik.Michniewski@interia.pl

[junbin]

I've tried solving this question using simple parsing methods.. but I keep getting WA.

Is there any tricky inputs anyone can share with me or any sample data sets they have?

Also, I have a question.

Let's say there are 2 programs A and B. A is in the ready queue, B is in the blocked queue. A then executes an unlock statement. If A still has at least 1 time unit left, does A continue to run or is B allowed to run immediately?

[wiltord]

A is in the ready queue....A then executes an unlock statement.

Hi, junbin. I think you don't really understand the states of a program.
In this problem, a program may be in three states, running(being processed by cpu),waiting(in the ready queue),blocked(in the blocked queue). So,if A is in the ready queue, A can't execute an unlock statement.

The programs in the ready queue is waiting for its own time quantum to come,or we say they are waiting for cpu. The programs in the blocked queue is waiting for the variable to be unlocked,or we say they are sleeping,only the excution of unlock statement by a running program can wake up the first program of this queue.

Now,return to your question,if A is a running program, A excutes unlock,the A will continue to excute untill its time quantum is passed.

I also got wrong answer, my problem is

When an unlock is executed, any program at the head of the blocked queue is moved to the head of the ready queue.

I didn't move the program at the head of the block to the head to the ready,but to tail.Hope it can help you.

[junbin]

Thanks for your reply.. however, I've already got my code AC'ed.. :p

I have no idea what was wrong.. I simply rewrote the whole program from scratch and it was AC immediately. :p

[ahsanlatif]

Hi,
I am getting WA for the prob 210. I want to clarify some points reagrding the statements structure. I am assuming that particular statements will always be like this:

For "print" statement:
----------------------
print variable //Note that there is single space between var-name and print instruction

For "assignment" statement:
---------------------------
variable = val //where 0<=val<=100 and there are spaces(single) on both sides of = sign

For "lock" statement:
---------------------
lock

For "unlock" statement:
-----------------------
unlock

For "end" statement:
--------------------
end


Kindly note that I am assuming that there are no space character(blanks) before and after above statements.That is to say following input is not valid:
<space><space>print b<space>
Only one statement exists per line.
There is no blank line in the input.

Can you tell me if the above mentioned assumptions are correct. Also if anyone has some input for this problem, Share here.

[Dominik Michniewski]

1. It's a multiply input program
2. I don't know nothing about number of spaces in input - it's good if your program can skip more than 1 space in a row Empty lines my program probably skip if they exist in program body.
3. My program reads input without paying attension on unecessary blanks. So I assumed, that input is correct (follow specification).

Best regards
DM

[ahsanlatif]

Can you provide with some inputs with outputs.

[ahsanlatif]

Here is my code.
I am sure about the execution portion but not about the input. I have tested it for more than one cases. But input is like the specified in the statement. (getType function)
Can you tell me what is the problem:

Code: Select all

[code]#include <iostream>
#include <queue>

using namespace std;

struct Statement{
	char type;
	char LHS,RHS;

};

struct Program{
	char ip;
	char len;
	Statement stmt[25];
};

int stmtcost[5];
int quantum;
Program progs[10];
int progcount;
queue<int> Ques[2];
char variables[26];

int executeStmt(Statement st,int prognum,int & lockStatus){
	switch(st.type){
		case 0:
			variables[st.LHS]=st.RHS;
		break;

		case 1:
			cout<<prognum+1<<": "<<(int)variables[st.LHS]<<endl;
		break;

		case 2:
			if(lockStatus)return 1;
			lockStatus=1;
		break;

		case 3:
			lockStatus=0;
		break;

	}
	return 0;
}

void simulateEnv(){
	int nextQ=0;
	int prognum;
	int quantumT;
	int placeinBlk;
	int lockStatus=0,tempLoc;

	for(nextQ=0;nextQ<progcount;nextQ++)
		Ques[0].push(nextQ);

	nextQ=0;
	while(!Ques[0].empty()||!Ques[1].empty()){
		if(Ques[nextQ].empty()){
			nextQ^=1;
			continue;
		}
		prognum=Ques[nextQ].front();
		Ques[nextQ].pop();

		quantumT=quantum;
		tempLoc=lockStatus;

		while(quantumT>0){
			if(progs[prognum].ip>=progs[prognum].len)break;
			

			if((placeinBlk=executeStmt(progs[prognum].stmt[progs[prognum].ip],prognum,lockStatus))==1)
				break;

			quantumT-=stmtcost[progs[prognum].stmt[progs[prognum].ip].type];
			progs[prognum].ip++;

		}
		if(tempLoc==1&&lockStatus==0)
			nextQ=1;
		else
			nextQ=0;

		if(progs[prognum].ip>=progs[prognum].len)
			continue;
		else if(placeinBlk)
			Ques[1].push(prognum);
		else
			Ques[0].push(prognum);
	}
}

///////////////////
int getType(char * inputStmt, Statement & st){
	
	if(inputStmt[2]=='='){
		st.type=0;
		st.LHS=inputStmt[0]-'a';
		st.RHS=0;
		inputStmt+=4;
		while(*inputStmt)
			st.RHS=st.RHS*10+(*inputStmt++-'0');
	}
	else if(inputStmt[0]=='p'){
		st.type=1;
		st.LHS=inputStmt[6]-'a';
	}
	else if(inputStmt[0]=='l'){
		st.type=2;
	}
	else if(inputStmt[0]=='u'){
		st.type=3;
	}
	else if(inputStmt[0]=='e')
		st.type=4;
	return st.type;
}

/////////////////////


int main(){

	int casecount=0;
	int prognum,stmtnum;
	char inputStmt[10];
	
	cin>>casecount;


	while(casecount){
		cin>>progcount;
		for(prognum=0;prognum<5;prognum++)
			cin>>stmtcost[prognum];
		for(prognum=0;prognum<26;prognum++)
			variables[prognum]=0;

		cin>>quantum;
		cin.ignore(5,'\n');
		for(prognum=0;prognum<progcount;prognum++){
			stmtnum=0;
			while(1){
				cin.getline(inputStmt,9);
				if(getType(inputStmt,progs[prognum].stmt[stmtnum])==4){
					progs[prognum].len=stmtnum;
					progs[prognum].ip=0;
					break;
				}
				stmtnum++;
			}
		}
		simulateEnv();
		casecount--;
		if(casecount)
		cout<<endl;
	}
	return 0;
}

[/code]
Thanx in Advance.

[Hao Hu]

Hi, I tried this problem today but got WA.

I thought I implemented the rules of concurrency simulation described well, and I've already searched this forum for help / tricky parts as well as test datas generated by others. But I still can't find my problem is. I think it works well.

So would you please kindly spare some minutes on my code and see where my problem lies?

Thanks a million in advance

Code: Select all

/*
Author: Hao Hu (Ikki)
Problem: Concurrency Simulator
Source: 1991 acm/icpc World Finals Problem C
Date: Jan 25, 2007
*/

#include<stdio.h>
#include<string.h>

char tmp[100];
int var[26],t[5],np,tq;
int num[15],q[15],to[15];
char prog[15][30][100];
int Ready[20000],h_r,t_r;
int Blocked[20000],h_b,t_b,idx;
bool locked;

void run()
{
	idx=Ready[h_r];
	for(int i=to[idx];i<num[idx];i++)
	{
		if(prog[idx][i][0]=='e'&&prog[idx][i][1]=='n')
		{
			q[idx]-=t[4];
			return;
		}
		if(prog[idx][i][1]=='=')
		{
			char ch; int xx;
			sscanf(prog[idx][i],"%c=%d",&ch,&xx);
			var[ch-'a']=xx;
			q[idx]-=t[0];
		}
		if(prog[idx][i][0]=='p'&&prog[idx][i][1]=='r')
		{
			printf("%d: %d\n",idx+1,var[prog[idx][i][5]-'a']);
			q[idx]-=t[1];
		}
		if(prog[idx][i][0]=='l'&&prog[idx][i][1]=='o')
		{
			if(locked)
			{
				Blocked[t_b++]=idx;
				q[idx]=tq;
				to[idx]=i;
				return;
			}
			else
			{
				locked=true;
				q[idx]-=t[2];
			}
		}
		if(prog[idx][i][0]=='u'&&prog[idx][i][1]=='n')
		{
			Ready[h_r]=Blocked[h_b];
			h_r--;
			h_b++;
			q[idx]-=t[3];
			locked=false;
		}
		if(q[idx]<=0)
		{
			Ready[t_r++]=idx;
			q[idx]=tq;
			to[idx]=i+1;
			return;
		}
	}
}

int main()
{
//	freopen("new_in.txt","r",stdin);
	int test,no=0;
	scanf("%d",&test);
	getchar();
	while(test--)
	{
		if(no!=0) printf("\n");
		no++;
		memset(num,0,sizeof(num));
		memset(var,0,sizeof(var));
		gets(tmp);
		scanf("%d%d%d%d%d%d%d",&np,&t[0],&t[1],&t[2],&t[3],&t[4],&tq);
		locked=false;
		h_r=t_r=h_b=t_b=10000;
		for(int i=0;i<np;i++)
		{
			q[i]=tq;
			while(1)
			{
				gets(tmp);
				int len=0,sz=strlen(tmp);
				for(int j=0;j<sz;j++)
					if(tmp[j]!=' ')
						prog[i][num[i]][len++]=tmp[j];
				prog[i][num[i]][len]='\0';
				num[i]++;
				if(prog[i][num[i]-1][0]=='e'&&prog[i][num[i]-1][1]=='n')
					break;
			}
		}
		for(int i=0;i<np;i++)
		{
			to[i]=0;
			Ready[t_r++]=i;
		}
		while(h_r!=t_r)
		{
			run();
			h_r++;
		}
	}
	return 0;
}

[A1]

hope you already solved it
if not, then you can try this input output:

Code: Select all

1

3 1 1 1 1 1 3
a = 5
print a
end
b = 7
lock
print a
print b
unlock
c = 10
print a
end
print a
print b
lock
print c
unlock
end

-------------------output-------------
1: 5
2: 5
3: 5
3: 7
2: 7
3: 10
2: 5

[samuelliyi]

hi guys,i've been trying to solve this problem for some time,but keep getting WAs, and i've try to use UA's debug functionality to test for some input, which all seem OK,so I could not figure out where my code fails,could anyone please help me ,here's the code:

Code: Select all

#include<stdio.h>
#include<string>
#include<vector>
#include<map>
#include<deque>
#include<queue>
#include<iostream>
#include<sstream>
using namespace std;
//vector<program> a;
map<string,int> dict;
vector<queue<string> > lines;
vector<int> is_finished;
   int case_id,program_id;
   int t1,t2,t3,t4,t5,t;
void simulate_program();

int main(){
   //read the case number
   cin>>case_id;
   string line;
   while(case_id--){
       lines.clear();
       is_finished.clear();
        //ignore blank line
        //read time info for the case
        cin>>program_id>>t1>>t2>>t3>>t4>>t5>>t;
        //getline(cin,line);
        cin.ignore(256,'\n');
        while(program_id--){
                is_finished.push_back(0);
                queue<string> program;
                getline(cin,line);
               while(line!="end"){
                    program.push(line);
                    getline(cin,line);
                }
                program.push(line);
                lines.push_back(program);
        }
//        for(vector<queue<string> >::iterator it=lines.begin();it!=lines.end();it++){
//            while(!it->empty()){
//                cout<<it->front()<<endl;
//                it->pop();
//            }
//        }
        simulate_program();
        if(case_id>1){
            putchar('\n');
        }

   }
   return 0;
}
void simulate_program(){
    int is_locked=0,index;
    deque<int> primary_queue;
    queue<int> block_queue;
    for(unsigned int i=0;i<lines.size();i++){
        primary_queue.push_back(i);
    }
    while(!primary_queue.empty()){
            index=primary_queue.front();
            primary_queue.pop_front();
            int slice=0;
            while(slice<t){
                string l=lines[index].front();
                stringstream istr(l);
                string p1,p2;
                int p3;
                istr>>p1>>p2;
                if(p1=="print"){
                        cout<<index+1<<": "<<dict[p2]<<endl;
                        slice+=t2;
                }
                else if(p1=="lock"){
                        slice+=t3;
                        if(is_locked){
                            block_queue.push(index);
                            is_finished[index]=1;
                            break;
                        }
                        else{
                            is_locked=1;
                        }
                }
                else if(p1=="unlock"){
                    slice+=t4;
                    is_locked=0;
                    if(!block_queue.empty()){
                        int i=block_queue.front();
                        block_queue.pop();
                        primary_queue.push_front(i);
                        is_finished[i]=0;
                    }
                }
                else if(p1=="end"){
                    is_finished[index]=1;
                    break;
                }
                else{
                    slice+=t1;
                    istr>>p3;
                    dict[p1]=p3;
                }
                lines[index].pop();

            }
              if(!is_finished[index]){
                    primary_queue.push_back(index);
                }
    }
    return;
}

thanks in advance