210 - Concurrency Simulator

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

Moderator: Board moderators

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

210 - Concurrency Simulator

Post by Dominik Michniewski » Thu May 15, 2003 2:21 pm

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
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)

User avatar
little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

Post by little joey » Thu May 15, 2003 3:23 pm

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
Guru
Posts: 834
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:

Post by Dominik Michniewski » Fri May 16, 2003 7:57 am

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
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)

User avatar
little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

Post by little joey » Fri May 16, 2003 8:51 am

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
Guru
Posts: 834
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:

Post by Dominik Michniewski » Fri May 16, 2003 9:30 am

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
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)

junbin
Experienced poster
Posts: 174
Joined: Mon Dec 08, 2003 10:41 am

210 - Concurrency Simulator

Post by junbin » Wed Dec 24, 2003 10:53 am

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
New poster
Posts: 16
Joined: Mon Oct 27, 2003 10:10 am
Location: SiChuan, China

Re: 210 - Concurrency Simulator

Post by wiltord » Thu Dec 25, 2003 5:35 pm

junbin wrote: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. 8)
Last edited by wiltord on Fri Dec 26, 2003 4:55 am, edited 1 time in total.
my goal: master algorithms

junbin
Experienced poster
Posts: 174
Joined: Mon Dec 08, 2003 10:41 am

Post by junbin » Fri Dec 26, 2003 4:53 am

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
New poster
Posts: 10
Joined: Sat Jan 14, 2006 4:52 pm
Location: Lahore

Some clarificatiosn for Problem 210

Post by ahsanlatif » Wed Jan 18, 2006 2:35 pm

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
Guru
Posts: 834
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:

Post by Dominik Michniewski » Wed Jan 18, 2006 4:04 pm

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
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)

ahsanlatif
New poster
Posts: 10
Joined: Sat Jan 14, 2006 4:52 pm
Location: Lahore

Test cases for 210

Post by ahsanlatif » Wed Jan 18, 2006 5:38 pm

Can you provide with some inputs with outputs.
Last edited by ahsanlatif on Wed Jan 18, 2006 5:46 pm, edited 1 time in total.

ahsanlatif
New poster
Posts: 10
Joined: Sat Jan 14, 2006 4:52 pm
Location: Lahore

Code

Post by ahsanlatif » Wed Jan 18, 2006 5:42 pm

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
New poster
Posts: 5
Joined: Mon Jan 01, 2007 8:22 am
Location: Nanjing University, China
Contact:

210 - Concurrency Simulator

Post by Hao Hu » Thu Jan 25, 2007 11:30 am

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;
}
Solo Player

User avatar
A1
Experienced poster
Posts: 173
Joined: Wed Jan 28, 2004 3:34 pm
Location: Bangladesh

Post by A1 » Thu Jan 31, 2008 1:12 am

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
New poster
Posts: 1
Joined: Wed Jun 17, 2015 5:34 pm

Re: 210 - Concurrency Simulator

Post by samuelliyi » Wed Jun 17, 2015 5:45 pm

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

Post Reply

Return to “Volume 2 (200-299)”