Better correct the memory usage by Java programs. You can simply decrease memory by 200 KB or just increase memory limits for some problems that can't be solved on Java or C#.

                Язык запрещен для данной задачи
                Language is not allowed for this problem

Edited by author 26.04.2013 17:32

hi

can you please show / send me some hint about test #2 ? (I think you can see the source code of my attempt)
p519446 at yandex.ru

TIA.

I create a struct STACK like this:
struct STACK
{
    int number;
    unsigned char before[3];
};

and keep arrays:
STACK LIST[100000+1];
int last[1000];

Apparently (3B+4B)*10^5 = 7*10^2 KB which is less than 750 :D
whats wrong with it? :/


how much memory does an empty cpp code consume?

#include <stdio.h>
#define MaxN 100000+252
#define MaxPop MaxN/2+1


struct pointer {
    int s;
    char o;
};

struct pointer GetPointer(int i)
{
    struct pointer p;
    p.s=i/250;
    p.o=i % 250;
    return p;

}

struct Stack {
    int V;
    struct pointer pred;
};
int GetAdress(struct pointer p) {
    return p.s*250+p.o;
}

int A[1001];
int MP;
struct Stack B[MaxN];


int Pop(int S)
{
    int E;
    E=B[A[S]].V;
    A[S]=GetAdress(B[A[S]].pred);
    return E;
}
int Push(int S, int E)
{
    int i=A[S];
    MP++;
    B[MP].V=E;
    B[MP].pred=GetPointer(i);
    A[S]=MP;
    return 0;
}
int main() {

    int N,i,j,E,k;
    int S;
    char command[10];
    scanf("%d",&N);


    MP=0;
    B[MP].V=0;
    B[MP].pred=GetPointer(0);
    for (i=1;i<1000;i++) A[i]=0;
    k=0;
    for (i=1;i<=N;i++) {

        scanf("%s",command);
        if (command[1] == 'U'){
            scanf("%d %d",&S,&E);
            Push(S,E);
        } else {
            scanf("%d",&S);
            k++;
            printf("%d\n",Pop(S));
        }
    }




    return 0;
}

Got AC. Used 2 arrays(bool and short for holding N's) + 2 arrays(bool and short) for top stack items and 1 int array for values managing 30 bit value storage instead of 32(B <= 1000000000). How can I improve the algo?

Edited by author 25.01.2013 12:42

If I run

public class Stacks {
    public static void main(String... args) {
        System.gc();
    }
}

It reports I exceed the memory limit with a usage of 4885 KB.

public class Stacks {
    public static void main(String... args) {
        System.gc();
    }
}

Reports 326 KB used.

How is the memory usage determined.  I assume you cannot have your managed memory trigger a GC which is a bit restrictive for Java.

How did you do that http://acm.timus.ru/status.aspx?space=1&num=1220&status=accepted&from=2371261&count=2 ???!  8-()

I use a block of continuous memory, divide the memory into Block(50 int).and each last one of Block is used to store the block number of previous Block in a same stack.moreover,I use two arrays to identify whether the Block is free and  to store offset in a Block respectively.Finally, I use an array[1000] to store the number of Block are being used in a stack.

Yeah! I did it! I spent about 4 hours to solve this problem =)

How to solve?
// nalgoritm.cpp : Defines the entry point for the console application.
//

//#include "stdafx.h"
//#include "conio.h"
#include "stdio.h"
short *A;
int *B;
int n,i;
    int last;
    int co;

void fun()
{
    int stack=A[i];
    for(int j=0;j<i;j++)
    {
        if(A[j]==stack&&B[j]!=(-1))
        {
        last=B[j];
        co=j;
        }
    }
    A[co]=(-1);
}

int main()
{
int j,nom,zn,k;
    char c;
    int element;
    i=k=0;
    scanf("%d",&n);
    A=new  short int[n];
    B=new  int[n];
    while(i<n){
j=0;
 scanf("%c",&c) ;
        while( c!=' ')
        {
         scanf("%c",&c);
           j++;
        }
        if(j==4)
        {
            scanf("%d",&nom);
        A[k]=nom;
        B[k]=(-1);
        k++;
        }
        else{
        scanf("%d %d",&nom,&zn);
        A[k]=nom;
        B[k]=zn;
        k++;
        }
        i++;
    }
    for(i=0;i<n;i++)
    {
        if(B[i]==(-1))
        {
            fun();
            printf("%d\n",last);

        }
    }
    //getch();
}

I always get WA#10 here is my solution

#include <iostream>
#include <vector>
#include <string>
#include <stack>
using namespace std;

int main(){
#ifndef ONLINE_JUDGE
    freopen("input.txt","rt",stdin);
    freopen("output.txt","wt",stdout);
#endif
    string operation;
    stack <long > znach[1002];

    short n;
    short int x;
    long  y;
    cin >>n;

    for (short i=1; i<=n; i++){

        cin >> operation;

        if(operation=="PUSH"){
            cin >> x;
            cin>>y;
            znach[x].push(y);
        }else{


            cin >>x;
            long z=znach[x].top();
            cout <<z<<endl;
            znach[x].pop();
    }

}
}
one who finds a mistake, please write back

T T..

I can't understand what kind of test can break this simple program. Any ideas?

If WA8, try test
100000
PUSH 1 1
PUSH 1 2
....
PUSH 1 99990
POP 1
...
POP 1
Right answer:
99990
...
99981

my simple test solution consist of only

            int N = int.Parse(Console.ReadLine());
            GC.Collect();

            Console.WriteLine("400");
            Console.WriteLine("200");
            Console.WriteLine("300");

and eats 1156 KB, MLE#1

New tests were added. 93 authors lost AC. If you have some good tests, please, send them to timus_support (at) acm.timus.ru.

It seems someone have suggested to hold a common memory segment for all stacks. Here is my way to solve with some details.

Allocate a large array - a common segment for all stacks, and define the size of a block.
int a[BLOCKS*BLOCK_SIZE];
Each block stores (BLOCK_SIZE-1) cells for the numbers and one cells to link it with the previous block for the stack.

Also it is useful to have a bit map reflecting if a particular block is occupied. Make functions find_free_block and release_block.
Also i was needed a couple of arrays of int[1000].

When the next stack grows above (BLOCK_SIZE-1)*k, the new block is occupied and the stack's memory becomes BLOCK_SIZE*(k+1). On the other hand, when i can release a block after POP i do this for memory reuse.

It was found experimetally at the price of 5 MLE attempts that acceptable parameters are:
BLOCKS = 3200; //number of blocks
BLOCK_SIZE = 50; //integers, not bytes

we can easily design 1000 stacks using a linked list，every node we 'll use a int to store its data，another int to store its father's index，we'll use 8 byte each node, about 800K,that will get MLE.

Then we can see the index of a node's father will always <=100000,we can just use 17 bit to store it,instead of a int(32 bit),zipped it and get AC~ :)

1)никаких локальных переменных в часто вызываемых методах -?кб
2)никаких объектов, кроме стандартного ввода-вывода -1500кб
3)свой вывод по байтам -300кб
4)данные в коллекциях примитивов
5)учитывать то, что максимум запросов будет 50000, т.е. в большом стеке начальные элементы можно затирать
6)ну и собственно сама суть решения - использовать модель памяти мс-дос - указатели в форме сегмет: смещение, тем самым уменьшается и их размер, и их количество