210 - Concurrency Simulator

Moderator: Board moderators

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

210 - Concurrency Simulator

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)

little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 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:
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)

little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm
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:
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

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

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

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

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

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

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]

Hao Hu
New poster
Posts: 5
Joined: Mon Jan 01, 2007 8:22 am
Location: Nanjing University, China
Contact:

210 - Concurrency Simulator

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?

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 Blocked[20000],h_b,t_b,idx;
bool locked;

void run()
{
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')
{
h_r--;
h_b++;
q[idx]-=t[3];
locked=false;
}
if(q[idx]<=0)
{
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;
}
while(h_r!=t_r)
{
run();
h_r++;
}
}
return 0;
}
``````
Solo Player

A1
Experienced poster
Posts: 173
Joined: Wed Jan 28, 2004 3:34 pm
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

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(){
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;
}
``````