Guys can anyone give any idea about how to solve this dynamically
.

Please help

#include <bits/stdc++.h>
using namespace std;
const int infInt = 1<<30;
vector<int>adj[100010];
pair<int,int> edges[100010];
int parent[100010],dist[100010];
map< pair<int,int> ,int> Map;
bool mark[100010];


void path(int u){
  if(parent[u]==u){
    cout<<edges[u].first<<" "<<edges[u].second;
    return;
  }
  path(parent[u]);
  cout<<" "<<edges[u].second;
}
int main(){
  int ant,curr,root,n;
  cin>>n;
  for(int i=0;i<n;i++){
    cin>>curr;
    if(i>0){
      edges[i].first=ant;
      edges[i].second=curr;
      adj[ant].push_back(curr);
      Map[make_pair(ant,curr)]=i;
    }

    if(i==0)
      root=curr;
    ant=curr;
  }
  if(root==curr){
    cout<<root<<endl;
    return 0;
  }
  queue<int> q;
  for(int i=1;i<n;i++){
    parent[i]=i;
    dist[i]=infInt;
    if(edges[i].first==root){
      q.push(i);
      dist[i]=0;
    }
    if(edges[i].second==curr)
      mark[i]=true;
  }

  while(!q.empty()){
    int u=q.front();
    q.pop();
    int x=edges[u].first;
    int y=edges[u].second;
    for(auto z: adj[y]){
      int v=Map[make_pair(y,z)];
      if(v>u and dist[v]>dist[u]+1){
        dist[v]=dist[u]+1;
        parent[v]=u;
        q.push(v);
      }
    }
  }
  int best=infInt,bestInd=-1;
  for(int i=1;i<n;i++){
    if(dist[i]<best and mark[i]){
      bestInd=i;
      best=dist[i];
    }
  }
  path(bestInd);
  cout<<endl;
  return 0;
}

Timus is online!
Hurra!

Can the coordinates be negative integers?

3 1 2 4
1 3 4 2
4 2 1 3
2 4 3 1
(4)

4 1 2 1
1 4 1 2
4 3 2 3
3 4 3 2
(2)

k=int(input())
a=[]
a.append(0)
a.append(1)
a.append(1)
a.append(2)
a.append(2)
s=0
for j in range(5,k+1):
 if j%2==1:
     for i in range(1,j//2+1):
         s+=a[i]
     a.append(s)

 else:
     for i in range(1,j//2):
         s+=a[i]
     s=s+a[j//2]-1
     a.append(s)
 s=0
print(a)

import java.math.BigInteger;
import java.util.Scanner;

public class bigKnum {

    public static void main(String args[]){
        Scanner in=new Scanner(System.in);
        int n=in.nextInt();
        int k=in.nextInt();

        BigInteger f1,f2,f3;
        f1=BigInteger.valueOf(k-1);
        f2=f1.multiply(BigInteger.valueOf(k));

        for(int i=2;i<n;i++)
        {
            f3=(f1.add(f2)).multiply(BigInteger.valueOf(k-1));
            f1=f2;
            f2=f3;

        }
        System.out.print(f2);

    }

}

That is my AC solve.
#include <stdio.h>
char a[1000005], b[1000005];
int Count, min;
int main()
{ scanf("%d", &Count);
  min=1;
  for (int i=1; i<=Count; i++)
    scanf("%d %d", &a[i], &b[i]);
// summing
  for (int i=Count; i>=0; i--)
    { int temp = a[i] + b[i];
      a[i] = temp%10;
      a[i-1] += temp/10;
    }
  if (a[0] == 1) min--;
  for (int i=min; i<=Count; i++)
    printf("%d", a[i]);
        return 0;
}

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]]);
   }
}