Page 31 of 43
101-Block Problem--- Time Limit Exceeding
Posted: Wed Sep 13, 2006 7:31 pm
by mudda_steven
Iam a newbie and
Iam unable to minimize this code........this is as far as i can go to reduce the complexity of the problem....could u guys please tell me a way in which i can reduce the Time limit.....
Code: Select all
#include<iostream>
#include<string.h>
using namespace std;
class Block
{
public:
int value;
int next;
int prev;
Block()
{
value = 0;
next = -1;
prev = -1;
}
Block(int val)
{
value = val;
next = -1;
prev = -1;
}
};
class Operation
{
public:
static Block block[25];
int temp,t,temp1;
Operation()
{
}
static void MakeBlocks()
{
for(int i=0;i<25;i++)
{
block[i].value = i;
}
}
int check(int a,int b)
{
for(t=block[a].value;t != -1;t=block[t].next)
{
if(t==b)
return 0;
}
for(t=block[a].value;t != -1;t=block[t].prev)
{
if(t==b)
return 0;
}
return 1;
}
void Moveofx(int a)
{
temp = block[a].next;
while(temp != -1)
{
temp1 = block[temp].next;
block[temp].next = -1;
block[temp].prev = -1;
temp = temp1;
}
}
void MoveToEnd(int a)
{
temp = block[a].value;
while(block[temp].next != -1)
{
temp = block[temp].next;
}
}
void MoveOnto(int a,int b)
{
int temp3,temp4;
Moveofx(a);
Moveofx(b);
temp = block[a].prev;
if(temp != -1)
block[temp].next = -1;
block[a].next = -1;
block[a].prev = b;
block[b].next = a;
}
void MoveOver(int a,int b)
{
Moveofx(a);
temp = block[a].prev;
if(temp != -1)
block[temp].next = -1;
block[a].next = -1;
MoveToEnd(b);
block[a].prev = block[temp].value;
block[temp].next = block[a].value;
}
void PileOnto(int a,int b)
{
Moveofx(b);
temp = block[a].prev;
if(temp != -1)
block[temp].next = -1;
block[a].prev = b;
block[b].next = a;
}
void PileOver(int a,int b)
{
MoveToEnd(b);
temp1 = block[a].prev;
if(temp1 != -1)
block[temp1].next = -1;
block[a].prev = b;
block[temp].next = a;
}
void Display(int n)
{
for(int i=0;i<n;i++)
{
temp = i;
if(block[temp].prev != -1)
{
cout<<temp<<": "<<endl;
}
else
if((block[temp].next == -1 ))
{
cout<<temp<<": "<<block[temp].value<<endl;
}
else
{
cout<<temp<<":";
for(;temp !=-1;temp = block[temp].next)
{
cout<<" "<<block[temp].value;
}
cout<<endl;
}
}
}
};
Block Operation::block[25];
int main()
{
int n;
char command[10],oper[10];
int a,b,i;
Operation op = Operation();
Operation::MakeBlocks();
while(cin>>n)
{
for(;;)
{
cin>>command;
if(strcmp(command,"quit")==0)
{
op.Display(n);
break;
}
cin>>a;
cin>>oper;
cin>>b;
if(op.check(a,b) == 0)
continue;
if(strcmp(command,"move")==0)
{
if(strcmp(oper,"onto") ==0)
{
op.MoveOnto(a,b);
}
else
{
op.MoveOver(a,b);
}
}
if(strcmp(command,"pile")==0)
{
if(strcmp(oper,"onto") ==0)
{
op.PileOnto(a,b);
}
else
{
op.PileOver(a,b);
}
}
}
}
}
Thanks
Posted: Sat Nov 04, 2006 7:38 am
by yoshiro aoki
I only looked quickly at your code, so maybe my advice is not the best possible. Of course you can profile the code to find more about where time is spent.
Maybe a hash table would allow quicker determination of where blocks are? I can have an array, 0 - 24, representing blocks. The value of the array elements could be the stack a particular block is in. So, such lookups are in constant time complexity. Will that help you?
I think I will try this problem. It looks very interesting!
I hope you can speed up your code and get an accept if you have not already.
Have a nice weekend,
-yoshiro (mark) aoki
Posted: Sat Nov 04, 2006 6:29 pm
by yoshiro aoki
Help me with 101 (TLE)
Posted: Sun Nov 19, 2006 6:04 am
by blodstone
Can someone help me with my program? The judge keep sending me a TLE but I still don't know where is the problem.
Code: Select all
#include <iostream>
#include <list>
#include <sstream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
using namespace std;
int search(list<int> arr[],int n, int target){
list<int>::iterator pos;
for (int i=0;i<n;i++){
pos = find(arr[i].begin(), arr[i].end(), target);
if(pos!=arr[i].end())
return i;
}
return 0;
}
int main(){
freopen("input.in","r",stdin);
freopen("output.out","w",stdout);
int n;
bool first = true;
string word1,word2;
int x,y;
list<int> arr[25];
while(cin >> n){
if (!first) cout << endl;
first = false;
for(int i=0;i<n;i++){
arr[i].push_back(i);
}
while(true){
cin >> word1; if (word1=="quit") break;
cin >> x >> word2 >> y;
if(word1=="move"){
if(word2=="onto"){
int tx = search(arr,n,x);
int tmp,tmp2;
while (arr[tx].back()!=x){
tmp = arr[tx].back();
arr[tmp].push_back(tmp);
arr[tx].pop_back();
}
tmp2 = arr[tx].back();
arr[tx].pop_back();
tx = search(arr,n,y);
while (arr[tx].back()!=y){
tmp = arr[tx].back();
arr[tmp].push_back(tmp);
arr[tx].pop_back();
}
arr[tx].push_back(tmp2);
}
else{
int tx = search(arr,n,x);
int tmp;
while (arr[tx].back()!=x){
tmp = arr[tx].back();
arr[tmp].push_back(tmp);
arr[tx].pop_back();
}
tmp = arr[tx].back();
arr[tx].pop_back();
tx = search(arr,n,y);
arr[tx].push_back(tmp);
}
} else if(word1=="pile"){
if(word2=="onto"){
int tx = search(arr,n,x);
int tmp;
list<int> smtr;
while (arr[tx].back()!=x){
tmp = arr[tx].back();
smtr.push_back(tmp);
arr[tx].pop_back();
}
tmp = arr[tx].back();
smtr.push_back(tmp);
arr[tx].pop_back();
tx = search(arr,n,y);
while (arr[tx].back()!=y){
tmp = arr[tx].back();
arr[tmp].push_back(tmp);
arr[tx].pop_back();
}
while(!smtr.empty()){
int temp = smtr.back();
arr[tx].push_back(temp);
smtr.pop_back();
}
}
else{
int tx = search(arr,n,x);
int tmp;
list<int> smtr;
while (arr[tx].back()!=x){
tmp = arr[tx].back();
smtr.push_back(tmp);
arr[tx].pop_back();
}
tmp = arr[tx].back();
smtr.push_back(tmp);
arr[tx].pop_back();
tx = search(arr,n,y);
while(!smtr.empty()){
int temp = smtr.back();
arr[tx].push_back(temp);
smtr.pop_back();
}
}
}
}
for(int i=0;i<n;i++){
cout << i << ":";
while (!arr[i].empty()){
cout << " " << arr[i].front() ;
arr[i].pop_front();
}
cout << endl;
}
}
return 0;
}
I used this test case, and it ran fine. Can someone provide me another test case? so I can test my program. Thx in advance
Code: Select all
10
move 9 onto 1
quit
11
move 9 onto 1
move 8 over 1
move 7 over 1
move 6 over 1
pile 8 over 6
pile 8 over 5
move 2 over 1
move 4 over 9
quit
24
move 23 onto 1
move 9 over 1
move 22 onto 2
pile 20 over 15
move 16 onto 15
move 22 onto 2
move 11 over 2
move 22 onto 23
move 17 over 15
pile 16 over 23
move 2 over 15
move 3 over 15
move 4 over 15
move 5 over 15
move 6 over 15
move 7 over 15
move 8 over 15
pile 3 onto 22
move 21 onto 9
move 22 over 9
quit
Posted: Wed Nov 22, 2006 11:25 pm
by jeffrey
for the 24-block example input you gave, I got
Code: Select all
0: 0
1: 1 23
2:
3: 3
4: 4
5: 5
6: 6
7: 7
8: 8
9: 9 21 22
10: 10
11: 11
12: 12
13: 13
14: 14
15: 15 2
16: 16
17: 17
18: 18
19: 19
20: 20
21:
22: 22
23:
The submission server is down so I don't know if my program is correct, but does that output match yours?
Things to watch out for is that there are no spaces on the end of a line, and that your output doesn't end with \r or \n.
101... runtime error on the server but not locally using gcc
Posted: Thu Nov 23, 2006 6:44 pm
by jeffrey
I'm running gcc 4.0.1. I've also tried gcc 3.4.2. Running in a cygwin or mac os x environment, I do
c++ -o 101 101.cpp
cat input | ./101
This gives me the desired result. However, upon submitting the source to the judge I always get a runtime error. I've tried copying the text to the submission page and also uploading the file. Any ideas about how I can fix this? It seems to me that since the judge is running linux, they're running gcc and the results should be the same. I would search the forum but the forum search is broken. At least "runtime error" gives no results.
Posted: Thu Nov 23, 2006 7:06 pm
by jeffrey
the howto says
Crash - Runtime Error (RE): Your program failed during the execution (segmentation fault, floating point exception...). The exact cause is reported to the user.
But where is it reported? I got no email and my status page doesn't say anything that I can see.
ACM101 WA "C"
Posted: Mon Dec 04, 2006 5:44 am
by scan33scan33
I got a lot of WAs for this problem.
And test for a lot of cases and got them right.
So......help me please!
or give me some samples, thx.
code removed
Re: ACM101 WA "C"
Posted: Mon Dec 04, 2006 5:58 am
by scan33scan33
[quote="scan33scan33"]I got a lot of WAs for this problem.
And test for a lot of cases and got them right.
So......help me please!
or give me some samples, thx.
I got an AC use C compiler...................
I previously chose C++........
sorry for asking....
Re: ACM101 WA "C"
Posted: Mon Dec 04, 2006 6:11 am
by helloneo
scan33scan33 wrote:
I got an AC use C compiler...................
I previously chose C++........
sorry for asking....
Congratulation..~!
If you got AC, then remove your code..
101: understand the problem
Posted: Fri Dec 15, 2006 10:40 am
by dddolphin
HI, I have problem understanding the process. Let me put my understanding to the following example:
the sample output from the webpage is:
0: 0//an space before first zero and also second 0??
1: 1 9 2 4
2:
3: 3
4:
5: 5 8 7 6
6:
7:
8:
9://if there is a '\n' here, does it matter?
if I continue to
move 7 onto 9, result would be:
0: 0
1: 1 9 7
2: 2
3: 3
4: 4
5: 5 8
6: 6
7:
8:
9:
Or, if I
move 7 over 9, result would be:
0: 0
1: 1 9 2 4 7
2:
3: 3
4:
5: 5 8
6: 6
7:
8:
9:
Or, if I
pile 7 onto 9, result would be:
0: 0
1: 1 9 7 6
2: 2
3: 3
4: 4
5: 5 8
6:
7:
8:
9:
Or, if
pile 7 over 9, result would be:
0: 0
1: 1 9 2 4 7 6
2:
3: 3
4:
5: 5 8
6:
7:
8:
9:
Anyone can help?
Posted: Fri Dec 15, 2006 2:34 pm
by helloneo
There are a lot of threads on this problem..
You have to search first..
If you need to post, use one of the old one to post instead of creating new one..
Check this out..
http://online-judge.uva.es/board/viewtopic.php?t=4019
Solved--Thanks
Posted: Fri Dec 15, 2006 4:19 pm
by dddolphin
the above processing is correct.
but still encounter presentation error
q101 where is my wrong
Posted: Fri Dec 15, 2006 6:24 pm
by ilms
this is my code
Code: Select all
#include <iostream>
#include <string>
#include <cstdlib>
using namespace std;
class bb{
private:
int box[25][25];
int box_in[25];
public:
int use_box;
void re_set();
void re_put(int index);
void put(int fb,int tb);
void put_all(int fb,int tb);
void show();
};
bb sbox;
int main(){
string da,db;
int ia,ib;
re_start:
cin>>ia;
sbox.use_box=ia;
sbox.re_set();
re_run:
cin>>da;
if(da=="quit"){
err_go:
sbox.show();
goto re_start;
}else if(cin>>ia>>db>>ib){
if(ia!=ib){
if(da=="move"){
if(db=="onto"){
sbox.re_put(ia);
sbox.re_put(ib);
sbox.put(ia,ib);
}
if(db=="over"){
sbox.re_put(ia);
sbox.put(ia,ib);
}
}else if(da=="pile"){
if(db=="onto"){
sbox.re_put(ib);
sbox.put_all(ia,ib);
}
if(db=="over"){
sbox.put_all(ia,ib);
}
}
}
goto re_run;
}
return 0;
}
void bb::re_set(){
int ax,ay;
for(ax=0;ax<25;ax++)
for(ay=0;ay<25;ay++){
box[ax][ay]=ax;
box_in[ax]=1;
}
}
void bb::re_put(int index){
int ax,ay,ac,ad,ae;
for(ax=0;ax<use_box;ax++)
for(ay=0;ay<box_in[ax];ay++)
if(box[ax][ay]==index){
ad=box_in[ax];
for(ac=ay+1;ac<ad;ac++){
box_in[ax]--;
ae=box[ax][ac];
box[ae][box_in[ae]]=ae;
box_in[ae]++;
}
return;
}
}
void bb::put(int fb,int tb){
int ax,ay,ac,ad;
for(ax=0;ax<use_box;ax++)
for(ay=0;ay<box_in[ax];ay++)
if(box[ax][ay]==fb){
box_in[ax]--;
for(ac=ay;ac<use_box;ac++){
box[ax][ac]=box[ax][ac+1];
}
for(ax=0;ax<use_box;ax++){
ad=box_in[ax];
for(ay=0;ay<ad;ay++)
if(box[ax][ay]==tb){
box[ax][box_in[ax]]=fb;
box_in[ax]++;
}
}
return;
}
}
void bb::put_all(int fb,int tb){
int ax,ay,ac,ad,ae;
for(ax=0;ax<use_box;ax++)
for(ay=0;ay<box_in[ax];ay++)
if(box[ax][ay]==fb)
for(ac=0;ac<use_box;ac++)
for(ad=0;ad<box_in[ac];ad++)
if(box[ac][ad]==tb){
ae=box_in[ax];
for(ad=ay;ad<ae;ad++){
box[ac][box_in[ac]]=box[ax][ad];
box_in[ax]--;
box_in[ac]++;
}
return;
}
}
void bb::show(){
int ax,ay;
for(ax=0;ax<use_box;ax++){
cout<<ax<<":";
for(ay=0;ay<box_in[ax];ay++){
cout<<" "<<box[ax][ay];
}
cout<<endl;
}
}
i send my code to server.
the server show message "Output Limit Exceeded".
where is my worng??
101 why pe
Posted: Sat Dec 16, 2006 12:12 pm
by SHAHADAT
cut