Firstly in timus backtracking set cover problem
helped to get Ac.

I have AC

Edited by author 10.11.2007 01:29

The problem task in Russian isn't equal to the problem task in English. The English text have following sentence: "You have to put the fence in the minimum number of squares so that the goat will be able to visit exactly K squares." It means that our region built could contain only K squares and something else, for example halves squares (as in example). But in the problem task in Russian this sentence is as follows:
"Требуется, поставив минимальное число секций, предоставить козлу участок ровно из K квадратов."
It means that the region contains only K squares and nothing else.

I think that this sentence should be rewritten as follows:
"Требуется, поставив минимальное число секций, предоставить козлу возможность посетить ровно K квадратов."


And something else.

English sentence contains phrase: "to put the fence in the minimum number of squares". But how should we count number of squares if the fence is put on the bound of two squares?!!

it gives error (Crash) . how can i solve it? can you give me hint? thanks

import java.io.*;

class Courier{
    static PrintWriter p=new PrintWriter(System.out);
    static int f;
    static final int k=-'0';
    int mat[][],dp[],max;
    short N,a[],l[],sa,sl;
    boolean ok;

    static int nextInt() throws IOException{
        int t=0;
        for (f=System.in.read(); f<'0' || f>'9'; f=System.in.read());
        for (;f>='0' && f<='9'; t*=10,t+=f+k,f=System.in.read());
        return t;
    }

    Courier() throws IOException{
        N=(short)nextInt();
        mat=new int[N+1][3];
        short i=1;
        for (;i<=N; mat[i][0]=nextInt(),mat[i][1]=nextInt(),mat[i][2]=i++);
        a=new short[N];
        l=new short[N];
        dp=new int[N+1];
        qsort((short) 1,N);
        for (i=1;i<=N; i++){
            if (mat[i][0]>=1){
                a[sa++]=(short) mat[i][2];
                nadji(2,i,mat[i][1]);
                sa--;
            }
        }
        for (p.println(sl),i=0; i<sl; p.print(l[i++]),p.print(' '));
        p.flush();
    }

    void nadji(int k,short p, int s){
        if (k==N+1){
            if (s>max) for (sl=0,max=s; sl<sa; l[sl]=a[sl++]);
            ok=N==sl;
            return;
        }
        if (s<dp[k]) return;
        dp[k]=s;
        short i=(short) (p+1);
        for (;i<=N; i++){
            if (mat[i][0]>=k){
                a[sa++]=(short) mat[i][2];
                nadji(k+1,i,s+mat[i][1]);
                sa--;
                if (ok) return;
            }
        }
        if (s>max) for (max=s,sl=0; sl<sa; l[sl]=a[sl++]);
    }

    void qsort(short a, short b){
        short i=a,j=b,m=(short) ((i+j)>>1);
        int[] t;
        for (;i<j;){
            for (;mat[i][0]<mat[m][0] || (mat[i][0]==mat[m][0] && mat[i][1]<mat[m][1]); i++);
            for (;mat[m][0]<mat[j][0] || (mat[m][0]==mat[j][0] && mat[m][1]<mat[j][1]); j--);
            if (i<=j){
                if (i<j){
                    t=mat[i];
                    mat[i]=mat[j];
                    mat[j]=t;
                }
                i++;
                j--;
            }
        }
        if (i<b) qsort(i,b);
        if (a<j) qsort(a,j);
    }

}

public class Timus1403 {
    public static void main(String[] args) throws IOException{
        new Courier();
    }
}

hello

I built NONdeterministic finite automation and have AC in 0.5 sec. But I think that DFA will be much more effective.

Can anyone suggest a genuine method of solving this problem. i.e. not a method such as

    if(n==1) printf("14");
    else if(n==2) printf("155");
    else
    {
        printf("1575");
        for(i=3;i<n;i++)
        printf("0");
    }

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
string a;
int k;
int array[9096], n, bucket[9096], lbucket[9096], h = 0;
void scan(){
    cin >> k >> a;
    a += a.substr(0, k - 1);
    n = a.size();
}
bool f(int x, int y){
    if ( !h )
        return a[x] < a[y];
    if ( bucket[x] < bucket[y] ) return 1;
    if ( bucket[y] < bucket[x] ) return 0;
    int bx, by;
    if ( x + h >= n ) bx = n - (x + h) - 1;
    else bx = bucket[x + h];
    if ( y + h >= n ) by = n - (y + h) - 1;
    else by = bucket[y + h];
    return bx < by;
}
bool makebuckets(){
    int br = 0;
    for ( int i = 0; i < n; ++i ){
        if ( i > 0 )
            if ( f(array[i], array[i - 1]) || f(array[i - 1], array[i]) )
                ++br;
        lbucket[array[i]] = br;
    }
    for ( int i = 0; i < n; ++i )
        bucket[i] = lbucket[i];
    ++br;
    return (br == n);
}
void buildsuffixarray(){
    for ( int i = 0; i < n; ++i )
        array[i] = i;
    sort (array, array + n, f);
    if ( makebuckets() ) return;
    for ( h = 1;; h *= 2 ){
        sort(array, array + n, f);
        if ( makebuckets() ) break;
    }
}
int findnext(int st, int i){
    ++i;
    for (i; i < n; ++i)
        if ( array[i] >= st && array[i] < st + k ) return i;
    return -1;
}
int rez(int t){
    int p = findnext(t, -1), d, result = (k + 1) * k / 2;
    d = findnext(t, p);
    int br = 0;
    while ( d > 0 ){
        int j = 0;
        while ( a[array[p] + j] == a[array[d] + j] && array[p] + j < t + k && array[d] + j < t + k ) ++j;
        result -= j;
        p = d;
        d = findnext(t, d);
        ++br;
    }
    if ( br != k - 1 ) while(1);
    return result;
}
void solve(){
    buildsuffixarray();
    cout << rez(0);
    for ( int i = 1; i < n - k + 1; ++i )
        cout << " " << rez(i);
    cout << endl;
}
int main(){
    scan();
    solve();
}

I am getting mad... no idea where my code is wrong... The idea is right

I have check all of the datas in 'DISCUSS',every one is true
But I got WA on Testdata26
Any one can tell me what 26 is?
Thanks!
My email:caoyuan9642@163.com

input
1
-999 999

Output must be same like input.

Edited by author 01.10.2009 17:02

Some tests:

20 10 2050
mon........3...10...17...24...31
tue........4...11...18...25.....
wed........5...12...19...26.....
thu........6...13..[20]..27.....
fri........7...14...21...28.....
sat...1....8...15...22...29.....
sun...2....9...16...23...30.....
//////////////////////////////
4 7 1890
mon........7...14...21...28
tue...1....8...15...22...29
wed...2....9...16...23...30
thu...3...10...17...24...31
fri.[.4]..11...18...25.....
sat...5...12...19...26.....
sun...6...13...20...27.....
/////////////////////////////
'.' it's ' '

Good luck!

Edited by author 01.10.2009 06:11

Some tests:

20 10 2050
mon        3   10   17   24   31
tue        4   11   18   25
wed        5   12   19   26
thu        6   13  [20]  27
fri        7   14   21   28
sat   1    8   15   22   29
sun   2    9   16   23   30
//////////////////////////////
4 7 1890
mon        7   14   21   28
tue   1    8   15   22   29
wed   2    9   16   23   30
thu   3   10   17   24   31
fri [ 4]  11   18   25
sat   5   12   19   26
sun   6   13   20   27

Good luck!

My C# Algorithm, error on Test 5 "Time limit exceeded". Help me make it faster. My email dark4ai@gmail.com

using System;
using System.Collections.Generic;

namespace timus1002
{
    public class Word
    {
        public int wordscount = 0;
        public int[] strs;
    }
    class Program
    {
        public static Dictionary<char, char[]> rules = new Dictionary<char, char[]>(10);
        public static string[] strings = new string[16];
        static bool TestWord(string word, string number)
        {
            if (number.Length < word.Length)
                return false;

            for (int i = 0; i < word.Length; i++)
                if (Array.IndexOf<char>(rules[number[i]],word[i])==-1)
                    return false;
            return true;
        }
        static Word TestNumber(string number, string[] dictionary, int min, int[] stros)
        {
            Word[] words = new Word[dictionary.Length];
            int m = dictionary.Length + 1;
            int mi = -1;
            for (int i = 0; i < dictionary.Length;i++)
            {
                int[] resu = new int[stros.Length + 1];
                for (int f = 0; f < resu.Length - 1; f++)
                    resu[f] = stros[f];
                resu[resu.Length - 1] = i;
                if (TestWord(dictionary[i], number))
                {
                    if (dictionary[i].Length == number.Length)
                    {
                        Word result = new Word();
                        result.strs = resu;
                        result.wordscount = min + 1;
                        words[i] = result;
                    }
                    else
                    {
                        words[i] = TestNumber(number.Substring(dictionary[i].Length), dictionary, min + 1, resu);
                    }
                    if (words[i] != null && words[i].wordscount < m)
                    {
                        m = words[i].wordscount;
                        mi = i;
                    }
                }
            }
            if (mi >= 0)
                return words[mi];
            return null;
        }
        static void Main(string[] args)
        {
            rules.Add('0', new char[]{ 'o', 'q', 'z' });
            rules.Add('1', new char[]{ 'i', 'j' });
            rules.Add('2', new char[]{ 'a', 'b', 'c' });
            rules.Add('3', new char[]{ 'd', 'e', 'f' });
            rules.Add('4', new char[]{ 'g', 'h'});
            rules.Add('5', new char[]{ 'k', 'l'});
            rules.Add('6', new char[]{ 'm', 'n'});
            rules.Add('7', new char[]{ 'p', 'r', 's' });
            rules.Add('8', new char[]{ 't', 'u', 'v' });
            rules.Add('9', new char[]{ 'w', 'x', 'y' });
            string end;
            while (true)
            {
                end = Console.ReadLine();
                if (end.Length != 2 && end != "-1")
                {
                    int numbers = int.Parse(Console.ReadLine());
                    string[] dictionary = new string[numbers];
                    for (int i = 0; i < numbers; i++)
                        dictionary[i] = Console.ReadLine();
                    Word res = TestNumber(end, dictionary, 0, new int[0]);
                    if (res == null)
                        Console.WriteLine("No solution.");
                    else
                    {
                        string result = dictionary[res.strs[0]];
                        for(int k =1;k<res.strs.Length;k++)
                            result+=" "+dictionary[res.strs[k]];
                        Console.WriteLine(result);
                    }
                }
                else break;
            }
            Console.Read();
        }
    }
}

0,
2,
12,
60,
320,
1950,
13692,
109592,
986400,
9864090,
108505100,
1302061332,
16926797472,
236975164790,
3554627472060,
56874039553200,
966858672404672,
17403456103284402,
330665665962403980,
6613313319248079980,
138879579704209680000

I used O(k) algo and kept WA 14. I must have tried a thousand ways to deal with it but it doesn't work. Finally, I found out a special way. Here it is: you found out when -2x^2+(a-b+2i)x+bi-i^2 has max value --suppose it to be when "x=m". Then, round it by (int)(m+0.5000000001) (that works for sure). Here, the tricky way is to scan from "m-10" to "m+10" and find when "y" is the biggest. I finally got ac with this. Hope this can help you somehow.

Edited by author 29.09.2009 04:47

Edited by author 29.09.2009 04:48

my code:
#include "stdio.h"
#include "iostream.h"
#include "math.h"
int main()
{
    long a[100001],i;
    a[0]=0;
    a[1]=1;
    for(i=2;i<100001;i++)
    {
        if(i%2==0)
        {
            a[i]=a[i/2];
        }
        else
        {
            a[i]=a[i/2]+a[i/2+1];
        }
    }
    int t[10];
    i=0;
    while(true)
    {
        cin>>t[i];
        if(t[i]==0)
            break;
        i++;
    }
    i=0;
    long max;
    while(t[i]!=0)
    {
        for(int j=0;j<t[i]+1;j++)
        {
            if(a[j]>max)
            {
                max=a[j];
            }
        }
        cout<<max<<"\n";
        max=-1;
        i++;
    }
    return 0;
}

program p1008_image_encoding;
const
  ele:array[1..4]of char=('R','T','L','B');

var
  b,v:array[0..11,0..11]of boolean;
  e,e1,xx,yy,h,num,swap,i,j,s,t:longint;
  x,y:array[1..10]of longint;
  a:array[0..11,1..2]of longint;
  ret,k:string;

begin
  readln(ret);
  if pos(' ',ret)=0
    then begin
    val(ret,num);
    readln(x[1],y[1]);
    b[x[1],y[1]]:=true;
    for i:=2 to num do begin
      readln(x[i],y[i]);
      b[x[i],y[i]]:=true;
      end;
    {for i:=1 to num-1 do
      for j:=i+1 to num do
      if (x[i]>x[j])or((x[i]=x[j])and(y[i]>y[j])) then begin
        swap:=x[i];x[i]:=x[j];x[j]:=swap;
        swap:=y[i];y[i]:=y[j];y[j]:=swap;
        end;}
    writeln(x[1],' ',y[1]);
    for i:=1 to num do
      if not v[x[i],y[i]] then begin
      v[x[i],y[i]]:=true;
      e:=1;e1:=1;h:=1;
      a[1,1]:=x[i];a[1,2]:=y[i];
      while true do begin
        for j:=h to e do begin
        if (a[j,1]+1<=10)and(b[a[j,1]+1,a[j,2]])and(not v[a[j,1]+1,a[j,2]])
          then begin
          inc(e1);a[e1,1]:=a[j,1]+1;a[e1,2]:=a[j,2];
          v[a[j,1]+1,a[j,2]]:=true;write('R');
          end;
        if (a[j,2]+1<=10)and(b[a[j,1],a[j,2]+1])and(not v[a[j,1],a[j,2]+1])
          then begin
          inc(e1);a[e1,2]:=a[j,2]+1;a[e1,1]:=a[j,1];
          v[a[j,1],a[j,2]+1]:=true;write('T');
          end;
        if (a[j,1]-1>0)and(b[a[j,1]-1,a[j,2]])and(not v[a[j,1]-1,a[j,2]])
          then begin
          inc(e1);a[e1,1]:=a[j,1]-1;a[e1,2]:=a[j,2];
          v[a[j,1]-1,a[j,2]]:=true;write('L');
          end;
        if (a[j,2]-1>0)and(b[a[j,1],a[j,2]-1])and(not v[a[j,1],a[j,2]-1])
          then begin
          inc(e1);a[e1,1]:=a[j,1];a[e1,2]:=a[j,2]-1;
          v[a[j,1],a[j,2]-1]:=true;write('B');
          end;
        if j<>num then writeln(',') else writeln('.');
        end;
        if e1=e then break;
        h:=e+1;e:=e1;
      end;
    end;
  end
  else begin
     k:=copy(ret,1,pos(' ',ret)-1);
     val(k,s);
     delete(ret,1,pos(' ',ret));
     val(ret,t);
     x[1]:=s;y[1]:=t;
     num:=1;
     xx:=x[1];yy:=y[1];
     h:=1;e:=1;e1:=1;
     while ret<>'.' do begin
       for j:=h to e do begin
       readln(ret);
       for i:=1 to 4 do
         if pos(ele[i],ret)<>0 then begin
           inc(num);
           case i of
           1:begin x[num]:=x[j]+1; y[num]:=y[j]; end;
           2:begin x[num]:=x[j]; y[num]:=y[j]+1; end;
           3:begin x[num]:=x[j]-1; y[num]:=y[j]; end;
           4:begin x[num]:=x[j]; y[num]:=y[j]-1; end;
           end;
         end;
       end;
       h:=e+1;e:=num
       end;
     for i:=1 to num-1 do
       for j:=i+1 to num do
       if (x[i]>x[j])or((x[i]=x[j])and(y[i]>y[j]))
         then begin
         swap:=x[i];x[i]:=x[j];x[j]:=swap;
         swap:=y[i];y[i]:=y[j];y[j]:=swap;
         end;
    writeln(num);
    for i:=1 to num do writeln(x[i],' ',y[i]);
  end;
end.

please help me


Edited by author 28.09.2009 20:32