request for any optimizations possible for python solution: not it get TLE #42

import sys

#sys.stdin = open("smalltest.txt")
#sys.stdin = open("input.txt")

top = 0
stack = [0] * 2000020
input = sys.stdin.read().split()
operations = int(input[0])
ans = ""

for i in xrange(operations) :
    op = int(input[i+1])
    if op > 0 :
        stack[top] = op
        top += 1
    elif op < 0 :
        top -= 1
        ans += str(stack[top]) + "\n"
    else :
        if operations - i > top :
            l = max( 0, top - operations + i )
            cnt = top - l
            stack[top:top+cnt] = stack[l:top]
            top += cnt

sys.stdout.write( ans )

I think the problem is little unclear.
It does not mention if the centipede continues putting shoes with the same strategy for right foot, when it is so.


Edited by author 03.07.2013 19:21

Edited by author 03.07.2013 17:04

you must print n^2 and n.

You can solve it o(1) just precalc answers fir all test by brute forse, than put it to array.
Proffit

I did some tests. They imply that the program gives correct results, but the system says: "wrong answer".... Why?

screenshot: http://i077.radikal.ru/1102/59/2854393a1c43.jpg

Excuse me for my english

hi all;
here's a bit simpler algorithm than in the question:

if(x > 0 && y > 0) {

    for(i = 1; i <= x + y; ++i) {

        y = x * x + y;
        x = x * x + y;
        y = sqrt((double)x - y);
        x -= (2 * y * y);
    }

}
could anyone prove it to me how this scary algorithm is the one in O(1),
i mean the one that tests reminders and then swap (if necessary).
thank you.

Edited by author 17.02.2013 15:05

Edited by author 17.02.2013 15:05

#include <stdio.h>
#include<stdlib.h>

 int main()
{
 int arr[5],arr1[5],arr2[5],i,a=0,b=0,n,x=0,y=0;
 printf("Enter number");
 scanf("%d",&n);
 x=n+1;
 y=n-1;
 while(n>0)
 {
    for(i=5;i>=0;i--)
    {
      arr[i]=n%10;
      n=n/10;
    }
 }


 a=( arr[0]+arr[1]+arr[2]);
 b=(arr[3]+arr[4]+arr[5]);
 //  printf("%d%d",a,b);
   if((a-b==1)||(a-b==-1))
      {
           while(x>0)
         {
           for(i=5;i>=0;i--)
           {
               arr1[i]=x%10;
               x=x/10;
           }
         }
          while(y>0)
         {
           for(i=5;i>=0;i--)
           {
               arr2[i]=y%10;
               y=y/10;
           }
         }
       if ((arr1[0]+arr1[1]+arr1[2]==arr1[3]+arr1[4]+arr1[5])||(arr2[0]+arr2[1]+arr2[2]==arr2[3]+arr2[4]+arr2[5]))
       { printf("\nYes");}
        else
       { printf("\nNo");}
      }
      else
      {
          printf("No");
      }
    return 0;
}

i am doing (n%k)+(n/k) after putting restriction on k(k<=1000) and n(n>=1). but my answer is  said to be wrong.please help.

Edited by author 28.06.2013 19:30

Edited by author 28.06.2013 19:30

#include<iostream>
using namespace std;

short a[50001],b[50001];
int N,M,index_1_0,index_1_10,index_2_0,index_2_10;
bool f_0,f_10,t_0,t_10;
const int T=10000;

int main()
{
    cin>>N;
    for(int i=0;i<N;i++)
    {
        cin>>a[i];
        if(a[i]>=0&&!f_0)
        {
            index_1_0=i;
            f_0=true;
        }
        if(a[i]>=1000&&!f_10)
        {
            index_1_10=i;
            f_10=true;
        }
    }
    cin>>M;
    for(int i=0;i<M;i++)
    {
        cin>>b[i];
        if(b[i]<=0&&!t_0)
        {
            index_2_0=i;
            t_0=true;
        }
        if(b[i]<=1000&&!t_10)
        {
            index_2_10=i;
            f_10=true;
        }
    }
    for(int i=0;i<=index_1_0;i++)
    {
        for(int j=0;j<=index_2_10;j++)
        {
            if(a[i]+b[j]<1000)
            break;
            if(a[i]+b[j]==T)
            {
                cout<<"YES";
                return 0;
            }
        }
    }
    for(int i=index_1_0;i<=index_1_10;i++)
    {
        for(int j=index_2_10;j<=index_2_0;j++)
        {
            if(a[i]+b[j]<1000)
            break;
            if(a[i]+b[j]==T)
            {
                cout<<"YES";
                return 0;
            }
        }
    }
    for(int i=index_1_10;i<N;i++)
    {
        for(int j=index_2_0;j<M;j++)
        {
            if(a[i]+b[j]<1000)
            break;
            if(a[i]+b[j]==T)
            {
                cout<<"YES";
                return 0;
            }
        }
    }
    cout<<"NO";
    }

Edited by author 28.06.2013 11:46

Hi,
 Can someone please help with the type of test case 4.

Thanks.

Sorry, can anyone explain difference
between using i++ or ++i
in loop
for(int i=1;i<=n;++i)
or
for(int i=1;i<=n;i++)

i tried print "i" in loop, all the same

#include<stdio.h>
#include<stdio.h>

void plus(char *a,char *b,char *c)
{
    char *p1,*p2,*p3;
    p1=a+99;
    p2=b+99;
    p3=c+99;
    while(*p1!=0||*p2!=0)
    {
        *p3+=*p1+*p2-2*'0';
        if(*p3>'9')
        {
            *p3-=10;
            *(p3-1)+=1;
        }
        p1--;
        p2--;
        p3--;
    }
}
void multi(unsigned char *s,int k)
{
    unsigned char *p;
    p=s+99;
    while(*p!='0')
    {
        *p+=(*p-'0')*(k-1);
        p--;
    }
    p=s+99;
    while(*p!='0')
    {
        while(*p>'9')
        {
            *p-=10;
            *(p-1)+=1;
        }
        p--;
    }
}
void main()
{
    unsigned char a[101],b[101],c[101],d[101];
    int n,k,i,j;
    for(i=0;i<100;i++)
    {
        a[i]=b[i]=c[i]=d[i]='0';
    }
    scanf("%d %d",&n,&k);
    k-=1;
    a[100]='\0';
    b[100]='\0';
    c[100]='\0';
    a[99]=k+'0';
    b[99]=(k+k*k)%10+'0';
    b[98]=(k+k*k)/10+'0';
    for(i=1;i<n-1;i++)
    {
        strcpy(c,d);
        plus(a,b,c);
        multi(c,k);
        strcpy(a,b);
        strcpy(b,c);
    }

    i=0;
    while(*(b+i)=='0')
    {
        i++;
    }
    printf("%s",b+i);

}

If your code on pascal, don't use "CASE x oF"

it's got CE(Compilation error)

Consider for instance the first drawing : in my perception, the staircase has 4 steps because there are 4 horizontal levels. So the first step (ie the lower one) is made up with 4 blocks, the second with 3 blocks, the third one with 2 blocks and the fourth with 2 blocks again ; so the sizes of the steps are not in _strictly_ descending order (the sizes are 4 3 2 2).

So what does "size of a step" really mean? the number of blocks between two consecutive horizontal levels ?  the height from the ground of a given level? the height between two consécutive levels?

"descending order" : how do you count the steps? from right to left? from top to bottom?


The task is no more than finding the number of partitions of n into at least two distinct parts.

Edited by author 29.06.2013 04:27

here is my code. In my computer he got AC on test#1. But in timus that got WA#1

var
 a:array[0..500010] of longint;

procedure sort(l,r:longint);
var
 i,j,p,x:longint;
begin randomize;
 i:=l; j:=r; x:=a[random(r-l+1)+l];
 repeat
  while x>a[i] do inc(i);
  while x<a[j] do dec(j);
  if i<=j then
   begin
    p:=a[i];a[i]:=a[j];a[j]:=p;
    inc(i); dec(j);
   end;
 until i>j;
 if i<r then sort(i,r);
 if l<j then sort(l,j);
end;

var
 p,j,k,n,i,temp,have:longint;
begin
 readln(n);
 for i:=1 to n do
  readln(a[i]);
 sort(1,n);
 temp:=-1;
 for i:=1 to n do
  begin
   if a[i]=temp then begin inc(have); continue; end;
   if n mod 2=1 then k:=1 else k:=0;
   if have>=n div 2+k then begin writeln(temp); halt; end;
   have:=1;temp:=a[i];
  end;
 if n=1 then writeln(temp);
end.