How to use dynamic programming to solve this problem? I used fibonacci.

Please, give me some tests!

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

int main(int argc, char *argv[])
{
  int a,k=-1,fact=1,term=1,i=0;
  char c;
  scanf("%d",&a);
  getchar();
  do{
     c=getchar();
     k++;
     }
  while(c==33);
  if(k>a) fact=-1;
  while(fact>0){
                term*=fact;
                fact=(a-i*k);
                i++;
                }



  if(k<=a) printf("%d",term);
  system("PAUSE");
  return 0;
}


Edited by author 01.07.2012 19:03

I always get WA on test 4,who can give me the testdata of test4.Help me!Thank you.

I keep getting WA2, but none of the threads posted here seem to help me: every example i found worked on my program, and i just can't see what's wrong with it. Can someone please tell me if they see anything that doesn't work within my program? Thank you in advance.
#define DM 8101
#define DN 901
#include <iostream>
#include <set>
#include <queue>
using namespace std;

int n, v, vp, s, sp, cf[DN][DM], dp[DN][DM];
multiset <int> ord;//ordering the elements
queue <int> q;//rebuild

void formare(int nrc, int car, int sum, int ptr)//no of digits, digit, sum, sumof squares
{
    if (nrc > 100 || (cf[sum][ptr] && cf[sum][ptr] <= nrc))
        return;
    cf[sum][ptr] = nrc;
    dp[sum][ptr] = car;
    for (int i = 9; i >= 1; --i)
        formare(nrc + 1, i, sum + i, ptr + i*i);
}

void realc(int s, int sp)
{
    if (!s || !sp || !dp[s][sp])
        return;
    q.push(dp[s][sp]);
    v+=dp[s][sp];
    vp+=dp[s][sp]*dp[s][sp];
    realc(s - dp[s][sp], sp - dp[s][sp]*dp[s][sp]);
}

int main()
{
    cin >> n;
    for (int i = 9; i >= 1; --i)
        formare(1, i, i, i*i);
    cf[0][0] = 1;
    dp[0][0] = 0;
    while (n--)
    {
        cin >> s >> sp;
        if (s > 900 || sp > 8100)
            cout << "No solution\n";
        else if (s == 0 && sp == 0)
            cout << "0\n";
        else
        {
            realc(s, sp);
            if (q.size() <= 100)
            {
                while (!q.empty())
                {
                    if (v == s && vp == sp)
                        ord.insert(q.front());
                    q.pop();
                }
                for (auto i:ord)
                    cout << i;
                ord.clear();
                if (v != s || vp != sp)
                    cout << "No solution";
                cout << '\n';
            }
            else
            {
                cout << "No solution\n";
                while (!q.empty())
                    q.pop();
            }
        }
        v = vp = 0;
    }
    return 0;
}

What is the test 19?
Help please!

Timus Sistem have:
Test1: n = 4
Test2: n = 2
Test3: n = 3

Right answers for n = 15
1 14 3 12 5 10 7 8 9 6 11 4 13 2 15
1 3 5 7 9 11 13 15 14 12 10 8 6 4 2

n = 16
1 15 3 13 5 11 7 9 8 10 6 12 4 14 2 16
1 3 5 7 9 11 13 15 16 14 12 10 8 6 4 2

Enjoy by problem)

It's just bruteforce!

it's cooooooool

Oh. My. God. JEBUS! I ACed it! Just use suffix array + Kasai and it will work out just fine. Trust me :)

But also here is what I collected about test 30 :
* Size of the string = 250000.
* All letters of English alphabet are being used.
* If we divide the string into heterogeneous and homogeneous regions, then the latter forms a majority. Moreover, longest homogeneous region = 396 and heterogeneous = 6.
* The amount of divergent adjacent characters is between 5000 and 10000.

Hope it helps :3

I submitted some algo which on my computer gives correct result for sample input given in problem statement and I got WA in test #1. Then I tried this code:

public class Problem_1285 {
    public static void main(String[] args) {
        System.out.println("1.00");
    }
}

...and got the same WA #1. What's going on???

There is a restiction for X and Y values: −10000.0 ≤ x, y ≤ 10000.0. Does .0 (sigle zero) means that only one digit after the decimal point is possible? Or if there any restriction for number of digits after the decimal point?

import java.math.*;
import java.util.*;

public class BigNumbers
{
   final int nmax=5005;

   public static BigInteger Px[], Py[], z[];
   public static int n;

   public static boolean Equal(BigInteger x1, BigInteger y1, BigInteger z1, BigInteger x2, BigInteger y2, BigInteger z2)
   {
      BigInteger A = (x1.multiply(z2)).subtract(x2.multiply(z1));
      BigInteger B = (y1.multiply(z2)).subtract(y2.multiply(z1));
      return (A.compareTo(BigInteger.ZERO)==0 && B.compareTo(BigInteger.ZERO)==0);
   }

   public static boolean Less(BigInteger x1, BigInteger y1, BigInteger z1, BigInteger x2, BigInteger y2, BigInteger z2)
   {
         if(Equal(x1,y1,z1,x2,y2,z2)) return false;

         if(y1.compareTo(BigInteger.ZERO)==0) return x1.compareTo(BigInteger.ZERO)==1;
         else
         {
            if(x1.compareTo(BigInteger.ZERO)==1)
            {
               if(x2.compareTo(BigInteger.ZERO)!=1) return true;
               BigInteger v=(y2.multiply(x1)).subtract(x2.multiply(y1));
               return v.compareTo(BigInteger.ZERO)==1;
            }
            else
            {
               if(x1.compareTo(BigInteger.ZERO)==0) return x2.compareTo(BigInteger.ZERO)==-1;
               else
               {
                  BigInteger v=(y2.multiply(x1)).subtract(x2.multiply(y1));
                  return (x2.compareTo(BigInteger.ZERO)==-1 && v.compareTo(BigInteger.ZERO)==1);
               }
            }
         }
   }

   public static boolean More(BigInteger x1, BigInteger y1, BigInteger z1, BigInteger x2, BigInteger y2, BigInteger z2)
   {
         return Less(x2,y2,z2,x1,y1,z1);
   }

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

      while(i<=j)
      {
         BigInteger xi,yi,zi,xj,yj,zj,xm,ym,zm;

         xm=(Px[m].multiply(z[n-1])).subtract(z[m].multiply(Px[n-1]));
         ym=(Py[m].multiply(z[n-1])).subtract(z[m].multiply(Py[n-1]));
         zm=z[m].multiply(z[n-1]);

         xi=(Px[i].multiply(z[n-1])).subtract(z[i].multiply(Px[n-1]));
         yi=(Py[i].multiply(z[n-1])).subtract(z[i].multiply(Py[n-1]));
         zi=z[i].multiply(z[n-1]);

         while(Less(xi,yi,zi,xm,ym,zm))
         {
            i++;
            if(i<=n)
            {
               xi=(Px[i].multiply(z[n-1])).subtract(z[i].multiply(Px[n-1]));
               yi=(Py[i].multiply(z[n-1])).subtract(z[i].multiply(Py[n-1]));
               zi=z[i].multiply(z[n-1]);
            }
         }

         xj=(Px[j].multiply(z[n-1])).subtract(z[j].multiply(Px[n-1]));
         yj=(Py[j].multiply(z[n-1])).subtract(z[j].multiply(Py[n-1]));
         zj=z[j].multiply(z[n-1]);
         while(More(xj,yj,zj,xm,ym,zm))
         {
            j--;
            if(j>=1)
            {
               xj=(Px[j].multiply(z[n-1])).subtract(z[j].multiply(Px[n-1]));
               yj=(Py[j].multiply(z[n-1])).subtract(z[j].multiply(Py[n-1]));
               zj=z[j].multiply(z[n-1]);
            }
         }

         if(i<=j)
         {
            BigInteger v;
            v=Px[i]; Px[i]=Px[j]; Px[j]=v;
            v=Py[i]; Py[i]=Py[j]; Py[j]=v;
            v=z[i]; z[i]=z[j]; z[j]=v;
            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();

      Px=new BigInteger[n+1];
      Py=new BigInteger[n+1];
      z=new BigInteger[n+1];

      for(int i=1;i<=n;i++)
      {
         Long x, y;
         x=sc.nextLong();
         y=sc.nextLong();
         Px[i]=BigInteger.valueOf(x);
         Py[i]=BigInteger.valueOf(y);
      }

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

      for(int i=1;i<=n-2;i++)
      {
         BigInteger v1=z[n-1].multiply(Py[i]);
         BigInteger v2=z[i].multiply(Py[n-1]);
         if(v1.compareTo(v2)==-1)
         {
            BigInteger v;
            v=Px[i]; Px[i]=Px[n-1]; Px[n-1]=v;
            v=Py[i]; Py[i]=Py[n-1]; Py[n-1]=v;
            v=z[i]; z[i]=z[n-1]; z[n-1]=v;
         }
      }

      QSort(1,n-2);

      Px[n-1]=Px[n-1].add(Px[n]);
      Py[n-1]=Py[n-1].add(Py[n]);

      int m = (n-1)/2;
      Px[m]=Px[m].add(Px[n]);
      Py[m]=Py[m].add(Py[n]);

      System.out.println(Px[n-1]+" "+Py[n-1]);
      System.out.println(Px[m]+" "+Py[m]);
      System.out.print(Px[n]+" "+Py[n]);
   }
}

input test 2 is:
1
1

Edited by author 06.02.2016 22:45

I just have implemented "Copy on Write" strategy suggested in other tread and it helped me pass through tests #9 and #10 where I got MLE/TLE earlier. But I cannot pass #19. I tried StreamTokenizer suggested by "Getting Stated" page, then I even implemented my own parser without any cheking for input errors just to speed up my solution. But still too slow!

There seems nothing can be done about algo itself: rollback/relearn fiddle with one variable, check prints, clone makes new entry in ArrayList<Clone> without actually doing anything. Only learn seems to be doing something: copying ProgramsList if it's needed, clearing abolished programs and adding new one. Not that much to find something excessive to remove.

But why it take so much time in test #19? How did 26 genii get their AC with Java? Is there some kind of trick or fundamental improvement to achive better time? I lost my mind searching solution. Please, help!

p.s. And sorry for bad English...

Update: I removed clearing ArrayList<Integer> in learn command, it waste memory a little and save time a little and made some cosmetic improvements. But still too slow!

Edited by author 21.12.2017 04:38

Can anyone help me please? I don't understand what is three prime number? :S

#include <iostream>

using namespace std;

int main()
{
    int a,b,c,d;
    cin>>a>>b>>c>>d;
        for (int i=0;a<c;i++)
        {
            a+=b;
            c=c-d;
        }
        cout<<a;
}


what's the problem??? help me please

program m;
var a:array[1..4000] of integer;
    p:array[1..4000] of integer;
    x:array[1..4000] of integer;
    n,s,i,j,k,f,m:integer;
    begin
    read(n);
    for i:=1 to n do
    read(a[i]);
    read(s);
    for j:=1 to s do
    read(p[j]);
    read(k);
    for f:=1 to k do
    read(x[f]);m:=0;
for i:=1 to n do
        for j:=1 to s do
          for f:=1 to k do
          begin
           if (a[i]=p[j]) and (p[j]=x[f]) and (x[f]=a[i]) then
         m:=m+1;
         end;
         write(m);
         end.

Until sample i thought, the problem is "how many such f exists" :D

P.S. This variation seems to be more interesting.

Edited by author 19.12.2017 20:41

What is test case?
Previously I had WA#4, but now my algorithm pass all tests discribed in those topic and fail with WA#7

Edited by author 27.11.2015 14:23

Edited by author 27.11.2015 14:23