try this test
2
abab
baa


answer:
ab
aa

I have used sieve theorem but i am still getting TLE! i need my code optimization .here is my code:

#include<iostream>
#include<cmath>
using namespace std;
#define TOTAL 163841
int main()
{

 int ara[TOTAL];

    for(int i=2; i<TOTAL; i++)
    {
        ara[i]=1;

    }
     int root = sqrt(TOTAL);

    for(int i=2; i<=root;i++)
    {
        for(int j=2; i*j<=TOTAL; j++) \\ Using  sieve theorem
        {
            ara[i*j]=0;
        }
    }
int T;
 int n;
cin >> T;
int r,k;
for(int l=1; l<=T; l++)
{

cin >> n;

if(n<=15000)
{
int ara2[n];
for(k=2,r=1;r<=n;k++)
{
    if(ara[k]==1)
    {
        ara2[r]=k; \\ copying the prime numbers to the ara2[]
        r++;
    }

}

cout << ara2[n] << "\n"; // cout the last num of ara2[]

}
}
return 0;
}

Edited by author 13.08.2017 12:49

There are at LEAST, 70 tests.

If you got TL you can try send same code and to get AC. When I delete 2 string (they are comments) i got AC.

my program as many others in net got AC but failed on test
3
1:00:00
12:59:58
12:59:59
Correct answer is 1:00:00 but not 13:00:00.

Can someone give me some hints about what #test 11 is?

1110 1119 -> 0

If i use double -> big error
If i use long long -> overflow
now i got Runtime error on java. Where I am wrong? I think my function Less is bad but I can't find mistake.

My code:
import java.math.*;
import java.util.*;

public class BigNumbers
{
   final int tmax=100;
   MathContext mc = new MathContext(tmax);

   final int nmax=5005;

   static int Pox[], Poy[], id[];
   static BigDecimal Px[], Py[];
   static int n, left;

   public static boolean Less(BigDecimal x1, BigDecimal y1, BigDecimal x2, BigDecimal y2)
   {
      return (y1.compareTo(BigDecimal.ZERO)!=-1) && (y2.compareTo(BigDecimal.ZERO)==1) &&
             ((y1.multiply(x2)).compareTo(x1.multiply(y2))==-1) ||
             (y1.compareTo(BigDecimal.ZERO)==-1) && ((y2.compareTo(BigDecimal.ZERO)!=-1)) ||
             ((x1.multiply(y2)).compareTo(x2.multiply(y1))==1);
   }

   public static BigDecimal modul2(BigDecimal x, BigDecimal y)
   {
         return (x.multiply(x)).add(y.multiply(y));
   }

   public static void QSort(int L, int R)
   {
      int m=(L+R)/2;
      int i=L;
      int j=R;

      while(i<=j)
      {
         while(Less(Px[i],Py[i],Px[m],Py[m])) i++;
         while(!Less(Px[j],Py[j],Px[m],Py[m]) && j!=m) j--;
         if(i<=j)
         {
            BigDecimal Y=Px[i];
            Px[i]=Px[j];
            Px[j]=Y;
            Y=Py[i];
            Py[i]=Py[j];
            Py[j]=Y;
            int y=id[i];
            id[i]=id[j];
            id[j]=y;
            i++;
            j--;
         }
      }
      if(L<j) QSort(L, j);
      if(i<R) QSort(i, R);
   }

   public static void main(String args[])
   {
      Scanner sc=new Scanner(System.in);

      n=sc.nextInt();

      Pox=new int[n+1];
      Poy=new int[n+1];
      id=new int[n+1];
      Px=new BigDecimal[n+1];
      Py=new BigDecimal[n+1];

      for(int i=1;i<=n;i++)
      {
         int x, y;
         x=sc.nextInt();
         y=sc.nextInt();
         Pox[i]=x;
         Poy[i]=y;
      }

      System.out.println(Pox[1]+" "+Poy[1]);

      for(int i=1;i<=n-1;i++)
      {
         BigDecimal x=BigDecimal.valueOf(Pox[i+1]-Pox[1]);
         BigDecimal y=BigDecimal.valueOf(Poy[i+1]-Poy[1]);
         Px[i]=x.divide(modul2(x,y));
         Py[i]=y.divide(modul2(x,y));
         id[i]=i+1;
      }

      left=1;
      for(int i=2;i<=n-1;i++)
         if(Px[left].compareTo(Px[i])==1 || Px[left].compareTo(Px[i])==0 &&
            Py[left].compareTo(Py[i])==1) left=i;

      System.out.println(Pox[id[left]]+" "+Poy[id[left]]);

      for(int i=1;i<=n-1;i++)
      {
         Px[i]=Px[i].subtract(Px[left]);
         Py[i]=Py[i].subtract(Py[left]);
      }

      for(int i=left;i<=n-2;i++)
      {
         Px[i]=Px[i+1];
         Py[i]=Py[i+1];
      }

      QSort(1,n-2);
      System.out.print(Pox[id[(n-1)/2]]+" "+Poy[id[(n-1)/2]]);
   }
}

Two Complex numbers are equivalent if they have the same moduli and there argument differ by a multiple of 2pi.how best can you solve this without encountering irrational numbers especially when you are dealing with nth root.

Edited by author 15.06.2013 20:16

#include <bits/stdc++.h>
using namespace std ;

#define DEBUG(x) cout << '>' << #x << ':' << x << endl;
#define mem(x,val) memset((x),(val),sizeof(x))
#define all(x) x.begin(),x.end()
#define pb push_back
#define mp make_pair
#define PI acos(-1.0)

const int INF = 1 << 29 ;
typedef long long ll ;

int N(int n  , int k ) {
    if(n == 1) return k<10?1:0 ;

    int sum = 0 ;
    for(int i = 0 ;i<= 9 && i<=k ; i++){
        sum+=N(n-1 , k-i) ;
    }
    return sum  ;
}

int main() {
    int n ,sum = 0 , temp  ;

    scanf("%d" ,&n) ;
    n/= 2 ;

    for(int i = 0 ; i<=n*9 ;i++){
        temp = N(n,i) ;
        sum+=(temp*temp) ;
    }

    printf("%d\n" , sum) ;

    return 0 ;
}

I have thought about something like lazy calculations model

#include<iostream>
#include <iomanip>
#include<vector>

int main(){
    long long num;
    std::vector<double> v;
    int count=0;
    while(std::cin>>num){
        if(num==0){
            v.push_back(num);
            }
    else{
    int i=0;
    double n=num/10;
    while(i<10000){
        n=n-(n*n-num)/(2*n);
        i++;
    }
    v.push_back(n);
    }

    }
    for(int i=v.size()-1;i>=0;i--)
        std::cout<<std::fixed<<std::setprecision(4)<<v[i]<<std::endl;
    return 0;
}

I was barely able to pass the TL by using the segment tree. That part probably works OK, but what causes troubles is the way I locate the array index by given content value (i.e. we want do delete 8, so I search for 8's index and replace it with 0). For that purpose I was using map from STL and wasn't able to come up with anything better (except some hash-like storage). What did you use for that purpose or could you avoid such situation at all?

Thanks.

It's a complete disaster! I just don't get it.
1)
Quote: "Exactly 1 mm of precipitations fall down on the pitch each minute"
Another quote: "You should output the average amount of precipitations (in millimeters) falling on the pitch in a minute."

So the reasonable question is: "Why the answer is just the area of the pitch without a small piece??" It shoud be less than one millimeter!
Ammount of precipitations is the height of the water column that arises from the surface in a particular period of time. Hence under the umbrellas the ammount equals to zero. And according to the statement the answer is (1 - area_covered_with_umbrellas / area_of_the_pitch).

2)
Quote: "All the water that has fallen on an umbrella streams down along the shortest way on the hemisphere."

So what? Does it mean that the water from the umbrella falls back on the pitch without changing the answer? Or, may be, it changes somehow the ammount of precipitations in the area near the umbrella... And if the umbrella is on the border of the pitch, than what ammount of water falls outside the pitch - area of spherical sector or area of its projection or area of spherical sector minus area of the layer falling out of the pitch?
BTW None of these variants didn't produce the answer given in the sample output.

I'd appreciate any information you could give me to remove an ambiguity.

I got WA4. Then i sorted answer by <length, int, int> and got AC.

[code deleted]

Edited by moderator 02.01.2020 18:17

I was trying to remove from the set first non-zero count money unit that is NOT LESS than ticket

But actually the task asks to remove just the FIRST non-zero count money unit

If act according to the former strategy you will receive WA20.

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

string per(int x)
{
int k(0),b(x);
string m;
if (x<10) {m+=char(x+'0');return m;}
while(x!=0)
{
 x=x/10;
 k++;
}
x=b;
b=k;
string s;
while(k>0)
{
 s+=char((x%10)+'0');
 x=(x-x%10)/10;
 k--;
}
for(int i=0;i<b;i++)
 m+=s[b-i-1];
return m;
}

int main()
{
int n,m,i,j,p,t(1);
char s[80];
string Y;
vector<int> v;
vector<int> w;
v.reserve(1);
w.reserve(1);
scanf("%d",&n);
scanf("%d",&m);

for(int d=0;d<n;d++)
{
 scanf("%s",s);
 if(s[0]=='l')
  {
  scanf("%d%d",&i,&j);
  if(j>m) continue;
  if(t<i) continue;
  v.push_back(j);w.push_back(i);
  p=w.size();
  for(int x=0;x<p;x++)
   if(w[x]==i && v[x]<0) {v.erase(v.begin()+x);w.erase(w.begin()+x);}
   }
 if(s[0]=='r'&& s[1]=='o')
  {
  scanf("%d",&i);
  p=w.size()-1;
  while(v[p]<0 || w[p]!=i)
   p--;
  v[p]-=1000000;}
 if(s[0]=='c'&& s[1]=='h')
{
 scanf("%d",&i);
 if(w.size()>0)
{
  for(int x=w.size()-1;x>=0;x--)
   if(w[x]==i && v[x]>0) {Y+=per(v[x]);if(d!=n-1)Y+="\n";break;}
   else
    if (x==0) {Y+="basic";if(d!=n-1)Y+="\n";}
    }
 else {Y+="basic";if(d!=n-1) Y+="\n";}

}
 if(s[0]=='r'&& s[1]=='e')
 {
  scanf("%d",&i);
  p=0;
  while(v[p]>0 || w[p]!=i)
   {
   p++;
   if(p>w.size()-1)
    break;
   }
  if(p>=0) v[p]+=1000000;
 }
 if(s[0]=='c'&& s[1]=='l')
{
 if(t<i) continue;
 t++;
 scanf("%d",&i);
 p=w.size();
 for(int x=0;x<p;x++)
  if(w[x]==i) {v.push_back(v[x]);w.push_back(t);}
}
}

cout<<Y;
}


I can't make up any new tests. Everything, I tried, works. If you have some ideas, please, help



Edited by author 01.08.2017 15:26

Edited by author 01.08.2017 15:28