Page 1 of 2
440
Posted: Fri Nov 08, 2002 5:42 am
by littledump
My 440 works, i tested with all sample input, but it goes over the 10 seconds.
When i compile and run & i hit 0, the program wont terminate, but it wont let me type
If you wish to see my code, i will post it
Posted: Fri Nov 08, 2002 6:00 am
by littledump
actually i decided to post my code anyway. it executes really quick when i use it.
[cpp]
/*
*
* Solves #440 - Eeny Meeny Moo
*
*/
#include <iostream.h>
void main(void) {
int *cityOnNet, *cityOffNet;
int citiesOff, citiesOn, nextCity, numCities, m;
while(cin >> numCities != 0) {
cityOnNet = new int[numCities];
cityOffNet = new int[numCities];
m = 0;
do{
citiesOn = numCities;
for (int i = 0; i < numCities; i++){
cityOnNet = i+1;
cityOffNet = 0;
}
cityOffNet[0] = 1;
citiesOn--;
citiesOff=1;
nextCity=0;
for (int i = 1; i < numCities; i++){
nextCity+=m;
while(nextCity >= citiesOn){
nextCity -= citiesOn;
}
for (int j = 0; j < citiesOff; j++){
for (int k = 0; k < citiesOn; k++){
if (cityOffNet[j] == cityOnNet[k]){
for (int l = k; l < citiesOn; l++){
cityOnNet[l] = cityOnNet[l+1];
}
}
}
}
cityOffNet = cityOnNet[nextCity];
citiesOff++;
citiesOn--;
}
m++;
}while (cityOffNet[numCities-1] != 2);
cout << m;
delete [] cityOnNet;
delete [] cityOffNet;
}
}
[/cpp]
Posted: Fri Nov 08, 2002 12:32 pm
by Adil
shouldn't it be[cpp]while(cin >> numCities && numCities != 0) [/cpp]in stead of[cpp]while(cin >> numCities != 0) [/cpp]
?
Posted: Fri Nov 08, 2002 2:09 pm
by littledump
thanks
that now makes it terminate on my end
but when i submitted again, it still execeeds time
it gets stuck on input 5 it seems
this is not the fastest, but it might help
Posted: Fri Nov 08, 2002 4:07 pm
by kmhasan
I think you are making a O(n^4) implementation where O(n^3) does the job. And there are opportunities where you can break your search. My solution takes 1.871s which is of course not fast compared to others, but could help you, i guess. I did a simple simulation to find the smallest m value.
Here's my solution:
[cpp]
#include <iostream.h>
bool josephus(int m, int n) {
int *array = new int[n];
int i, j, count;
for (i=0;i<n;i++)
array=i+1;
array[0] = 0;
for (i=1,j=0;i<n;i++) {
count=0;
while (count<m) {
j++; if (j>=n) j=0;
if (array[j]!=0) count++;
}
array[j]=0;
if (i<n-1 && j==1) {
delete array;
return false;
}
}
delete array;
if (j==1) return true;
return false;
}
int main() {
int m,n;
while (true) {
cin>>n;
if (n==0) break;
for (m=1;!josephus(m,n);m++);
cout<<m<<endl;
}
return 0;
}[/cpp]
Posted: Fri Nov 08, 2002 5:20 pm
by littledump
but compiling and running my code on my pc, it runs extremely fast. evidently < 1 sec for all valid input 3<=n<=150. i do not understand why when it gets to input 5, at about 5 secs, it takes more than 5sec to solve it. There must be another problem?
Posted: Fri Nov 08, 2002 5:31 pm
by littledump
might the following have something to do with it
or should i say lack of the follow:
[cpp]
using namespace std;
[/cpp]
?
Posted: Fri Nov 08, 2002 6:47 pm
by kmhasan
Yes you are right. Your program does produce output in less than 1s. But that is for each test case. What I realized is that your solution can get TLE even if the judge input consists of 20 selected cases. The time limit given is for all test cases, not a single case.
You can generate one single input file that has all integers from 3..150 and try to see how much time your program takes for that.
There are many solutions that required 0sec for this problem, I guess most of them are using precomputed tables, you can try that one as well. I won't recommend it though.
Posted: Sat Nov 09, 2002 6:36 am
by littledump
i compiled using input from files
it took about 12 seconds to do all 147 valid inputs
why cant it do 5 in 10 seconds for the judge?
Posted: Sat Nov 09, 2002 6:49 am
by littledump
im also sending this in through the online submission page
any chance that could have anything to do with it?
most likely not i guess?
Posted: Sat Nov 09, 2002 7:09 pm
by littledump
well. i made one small change. i dont think it was significant enough to cut over 9 seconds off though, but i guess it was. it now runs in 1.709 seconds
heres my new code:
[cpp]/*
*
* Solves #440 - Eeny Meeny Moo
*
*/
#include <iostream>
using namespace std;
void main(void) {
int *cityOnNet, *cityOffNet;
int citiesOff, citiesOn, nextCity, numCities, m;
while(cin >> numCities && numCities !=0) {
cityOnNet = new int[numCities];
cityOffNet = new int[numCities];
m = 0;
do{
citiesOn = numCities;
for (int i = 0; i < numCities; i++){
cityOnNet = i+1;
cityOffNet = 0;
}
cityOffNet[0] = 1;
citiesOn--;
citiesOff=1;
nextCity=0;
for (int i = 1; i < numCities; i++){
nextCity+=m;
while(nextCity >= citiesOn){
nextCity -= citiesOn;
}
for (int j = 0; j < citiesOn; j++){
if (cityOffNet[i-1] == cityOnNet[j]){
for (int l = j; l < citiesOn; l++){
cityOnNet[l] = cityOnNet[l+1];
}
}
}
cityOffNet = cityOnNet[nextCity];
citiesOff++;
citiesOn--;
}
m++;
}while (cityOffNet[numCities-1] != 2);
cout << m <<endl;
delete [] cityOnNet;
delete [] cityOffNet;
}
}[/cpp]
440 TLE?
Posted: Tue Jan 28, 2003 8:08 am
by sami
[cpp]
why i am getting TLE?[/cpp]
Posted: Tue Jan 28, 2003 9:05 am
by Dominik Michniewski
I think, that's too litle informations to say why
Dominik
Posted: Sun Feb 02, 2003 4:28 pm
by sami
is there any speciality in its implementation or brute force is the solution..
Posted: Tue May 01, 2007 8:31 pm
by gates1
what's wrong in this, i getting WA
Code: Select all
var a:array[1..100] of shortint;
b:array[1..100] of byte;
i,j,u,z,k,n,r,l:longint;
begin
b[1]:=1;
repeat
inc(i);
readln(a[i]);
until a[i]=0;
n:=i-1;
for i:=1 to n do begin
r:=a[i];
j:=1;
repeat
inc(j);
l:=1;
k:=1;
for z:=2 to r do
b[z]:=0;
repeat
u:=0;
repeat
inc(l);
if l=r+1 then begin
l:=1;
repeat
inc(l);
until b[l]=0;
end;
if b[l]=0 then inc(u);
until u=j;
b[l]:=1;
inc(k);
until k=r;
until l=2;
a[i]:=j;
end;
for i:=1 to n do
writeln(a[i]);
readln;
end.