I do not trust that this problem can be solved during contest!
Because it demand big amount of tehnical work such
as grammar analysis, string manipulations and sorting.

What the fucking test is it? I failed on it many times, using every possible precision in calculations!

import java.util.Arrays;
import java.util.Scanner;

public class Timus1403 {

    /**
     * @param args
     */
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        int n = input.nextInt();
        Order[] order = new Order[n];
        int[] num = new int[100001];
        int[] ans = new int[100001];
        boolean[] used = new boolean[100001];
        Arrays.fill(used, false);
        for (int i = 0; i < order.length; i++) {
            int d = input.nextInt();
            int p = input.nextInt();
            order[i] = new Order(i + 1, d, p);
        }
        for (int i = 0; i < num.length; i++) {
            num[i] = i;
        }
        Arrays.sort(order);
        int count = 0;
        for (int i = 0; i < order.length; i++) {
            int j = order[i].deadline;
            if(num[j] > 0 && !used[num[j]]){
                count++;
                int x = num[j];
                ans[num[j]] = order[i].index;
                used[num[j]] = true;
                num[num[j]] = num[j] - 1;
                if(x == j){
                    continue;
                }
                num[order[i].deadline]--;

            }
        }
        System.out.println(count);
        for (int i = 0; i < used.length; i++) {
            if(used[i]){
                System.out.print(ans[i] + " ");
            }
        }


    }

}

class Order implements Comparable<Order>{
    public int index;
    public int deadline;
    public int price;

    public Order(int i, int d, int p){
        index = i;
        deadline = d;
        price = p;
    }

    @Override
    public String toString(){
        String ret = "";
        ret+= this.index + " " + this.deadline + " " + this.price;
        return ret;
    }

    public int compareTo(Order other) {
        return -(this.price - other.price);
    }

}

Edited by author 24.10.2010 08:20

   var
   s : integer;
   ch : char;

begin
   s := 0;
   while not eof do
     begin
       read(ch);
       case ch of
       '1', '5' : inc(s);
       '2', '4', '6', '9' : inc(s, 2);
       '3', '7' : inc(s, 3);
       '8' : inc(s, 4);
       end;
     end;
   writeLn(s);
end.
this ic gave me AC!!

   var
   s : integer;
   ch : char;
   a : array ['0'..'9'] of byte = (0, 1, 2, 3, 2, 1, 2, 3, 4, 2);

begin
   s := 0;
   while not eof do
     begin
       read(ch);
       s := s + a[ch];
     end;
   writeLn(s);
end.
and this WA#1!!!!
i don't know why, who can explain it to me!!
thanks!!

i think it will work out fine.
But just got WA1.
Can you help me ?
thx!






#include <cstdlib>
#include <iostream>

using namespace std;


int shu(int);


int main(int argc, char *argv[])
{
    int a[10],b=0,max=0,d=0;
    while (cin>>a[b])
    {if (a[b]==0) break;
     b++;}
     while (1)
     {if (a[d]==0) break;
      while (a[d]>=0)
      {if (shu(a[d])>max) max=shu(a[d]);
       a[d]--;}
       cout<<max<<endl;
       d++;}

    system("PAUSE");
    return EXIT_SUCCESS;
}

  int shu(int n)
  {int c;
   if (n==0) c=0;
   else if (n==1) c=1;
   else if (n%2==0) c=shu(n/2);
   else c=shu((n-1)/2)+shu((n-1)/2+1);}

Does the algorithm must have the minimal numbers of steps?

At first I got wa on test 12 19 ...
After this test I got ac
6
1 10
1 10
1 6
1 10
1 10
6 3
2
3 1
3 2

Edited by author 20.10.2010 14:21

Where i am wrong?


#include <iostream>
#include <cmath>
using namespace std;
int main ()
{
    double n,i,a,f,m;
    cin>>n;
    for (i=1;i<=n;i++)
    {
        cin>>a;
        m=sqrt (8*a-7);
        f=int (m);
        if (m==f) cout<<"1";
        else cout<<"0";
    }
}

My Email:sxcyd@126.com
Thank you!

Edited by author 23.10.2010 08:26

I used dp with two params.
dp[n][k] =(sum(i=0..n-1)max(dp[i][k+1], dp[n-i-1][k+1]))/n
k is number of salvos

ans =10 * dp[n][1];

Edited by author 23.10.2010 02:29

The statement says "The only line of the output should contain the Average LCP of T with 3 digits after decimal point. "
Is this with rounding or without? I'm using printf("%0.3lf") and keep on getting WA 35

My program got Fail (validator) on the first test.
P.S. I've checked that the first test is the first sample test and program which just outputs "33+88=121" also get Fail(validator). Please check the validator.

Edited by author 11.10.2010 19:57

#include<iostream>
using namespace std;
void main()
{
    int n,i=0,t,a[102]={-1};
    cin>>n;
    int num[1020]={-1};
    for(int j=1;j<=n;j++)
    {
        do
        {
            i++;
            cin>>num[i];
        }while(num[i]!=0);
        t=num[1];
        num[1]=0;
        for(int m=2;m<i;m++)
        {
            if(t<num[m])
                t=num[m];
            num[m]=0;
        }
        a[j]=t;
    }
    for(int j=1;j<=n;j++)
    {
        t=j;
        for(int m=1;m<=n;m++)
        {
            if(a[t]<a[m])
                t=m;
        }
        cout<<t<<" ";
        a[t]=-1;
    }
}

AAAAACCEPTED!!!!!
WHY?

beg for sample...

why wa#1 ???

#include <cstdlib>
#include <iostream>

using namespace std;

int a[2000],b[2000];
int c[2000][2000];
int en;

int sum(int k,int p)
{
  int top[4000];
  int i,j=0;
  int y=0,t;

  if (k > p)
   {
     for (i=k;i>=k-p;i--)
      b[i]=b[i-(k-p)];
     for (i=0;i<k-p;i++)
      b[i]=0;
     en=k;
   }
  else if (p > k)
   {
     for (i=p;i>=p-k;i--)
      a[i]=a[i-(p-k)];
     for (i=0;i<p-k;i++)
      a[i]=0;
     en=p;
   }
  else if (k == p) en=k;

  for (i=en-1;i>=0;i--)
   {
     t=a[i]+b[i]+y;
     if (t > 9)
      {
        t-=10;
        y=1;
        top[j]=t; j++;
      }
     else {top[j]=t; j++; y=0;}
   }
  if (y == 1) {top[j]=y; j++;}
  int l=0;
  for (i=j-1;i>=0;i--)
   {
    a[l]=top[i];
    l++;
   }
  return l;
}

int multi(int k,int p,int n)
{
  int tp[5000];
  int cv[4000];
  int y=0,v=0,vy,uz;
  int i,l=0,j,sy=0;

  for (i=0;i<=4000;i++) tp[i]=0;
  for (i=k-1;i>=0;i--)
   {
     v=(a[i]*p)+vy;
     if (v > 9)
      {
       vy=v / 10;
       v-=(vy*10);
      }
     else vy=0;
     cv[l]=v; l++;
     if (vy > 0) {cv[l]=vy; l++;}
     l+=sy;
     for (j=l-1;j>=sy;j--) cv[j]=cv[j-sy];
     for (j=0;j<sy;j++) cv[j]=0;
     for (j=0;j<l;j++)
      {
       uz=l-1;
       tp[j]+=cv[j]+y;
       if (tp[j] > 9)
        {
          tp[j]-=10;
          y=1;
        }
       else y=0;
      }
     for (j=0;j<l;j++) cv[j]=0;
     if (y == 1) { uz++; tp[uz]=y; }
     l=0; vy=0; sy++; y=0;
   }
  l=0;
  while (tp[uz] <= 0) uz--;
  for (j=uz;j>=0;j--)
   {
     c[n][l]=tp[j];
     l++;
   }
  return l;
}

int main()
{
    int n,k,i,j,u;
    int uz[2000];


    cin>>n>>k;
    c[0][0]=1; c[1][0]=k-1;
    uz[0]=1; uz[1]=1;
    for (i=2;i<=n;i++)
     {
       for (j=0;j<uz[i-1];j++) a[j]=c[i-1][j];
       for (j=0;j<uz[i-2];j++) b[j]=c[i-2][j];
       u=sum(uz[i-1],uz[i-2]);
       uz[i]=multi(u,k-1,i);
     }

    for (i=0;i<uz[n];i++)
     cout<<c[n][i];
    cout<<endl;

    return EXIT_SUCCESS;
}

During the OpenCup I've accepted the problem with complexity O(N*K^2), but here, on timus, only optimizations helped me to beat timelimit with this algo. At the same time, some people have AC-times 0.015 or something like that. Is it possible to solve the problem with more efficient algo?

I've seen a discussion that
gave a Hash Function .... as this:    x& 2^31
but As the writer say..the tests are too weak..got AC
Is there  any better Hash?...like ELF in string Hash..
touch me Please.

Edited by author 21.10.2010 13:37

Why does my program always get WA#1?
I have tried all the tests in the forum, and all of them are correct.
I think there is a very strange mistake in my program.

#include <stdio.h>
#define re(i, n) for (int i=0; i<n; i++)
#define rre(i, n) for (int i=n-1; i>=0; i--)
const int MAXN = 32;
int b, k;
long long c[MAXN][MAXN], res = 0;
void prp(void)
{
     re(i, MAXN) re(j, MAXN) if (i < j) c[i][j] = 0; else if (!j) c[i][j] = 1; else c[i][j] = c[i - 1][j - 1] * i / j;
}
long long xxx(long long v)
{
     int a[MAXN], len = 0;
     long long r0 = 0;
     while (v) {a[len++] = v % b; v /= b;}
     int k0 = k;
     rre(i, len) {
        int x = a[i];
        if (x >= 2) {r0 += c[i + 1][k0]; break;}
        if (x) {r0 += c[i][k0]; k0--;}
     }
     return r0;
}
int main(void)
{
    long long s, t;
    scanf("%lld%lld%d%d", &s, &t, &k, &b);
    prp();
    res = xxx(t + 1) - xxx(s);
    printf("%lld\n", res);
    return 0;
}


Edited by author 04.09.2010 20:07

In my pgm there's no '0'...
At least we can print(n-1) :)