How can I quickly build adjacency matrix befor using bfs for this problem. I have TLE#6,#10,#12 for this problem. Any algorithm please!

brute force is 20 lines AC.
how long code with formula?

Are there many possible answers?
For example in the test example my program gets the answer:

0000 (do nothing)
0111 (insert 1 at the end)
1010 (change the last 1 in 0; I suspect that this 1 was initially a 0 and now, due to the noisy line, it's a 1)
1101 (erase the last 1)

the total sum of positions is 20, which is a multiple of 5 = 4 + 1
Did I get something wrong? I not, which solution should I print? And is it possible not to have any solution?

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.util.StringTokenizer;


public class No1068 {
    public static void main(String[] args) throws Exception {
        BufferedReader rd=new BufferedReader(new InputStreamReader(System.in));
        PrintWriter wr=new PrintWriter(new OutputStreamWriter(System.out));
        StringTokenizer line =new StringTokenizer(rd.readLine());
        Integer n=Integer.parseInt(line.nextToken());

        if (n>0)
            wr.println((n*(n+1))/2);

            else
            {
                n=Math.abs(n);
                wr.println(1-(n*(n+1)/2));
            }
        wr.close();
        System.exit(0);



    }

}

How to solve this problem？I use trie tree and get MLE #2！！！！！！！！！！！

Edited by author 26.08.2012 09:02

Edited by author 26.08.2012 09:02

WHY?


type hlist=^list;

list=record
    data: longint;
    l,r: hlist;
    end;


var n,i:longint;
    a:array[1..3000] of longint;
    head: hlist;

procedure add(var v:hlist; x:longint);
    begin
    if v=nil then
        begin
        new(v);
        v^.data:=x;
        end
    else if x>v^.data then add(v^.r, x)
                     else add(v^.l, x);
    end;

procedure draw(var v:hlist);
        begin
        if not (v=nil) then
            begin
            draw(v^.r);
            draw(v^.l);
            write(v^.data,' ');
            dispose(v);
            end;
        end;
begin
readln(n);
for i:=n downto 1 do read(a[i]);
for i:=1 to n do add(head, a[i]);
draw(head);
end.

Should there be a teddy Hater in team of Holden?

Edited by author 31.10.2012 15:36

Could you give me case for test 14? Thank you!

each window light travels in both directions, or one?

1
2
0 2

Is answer of second child to himself means "circle" ?

Edited by author 01.11.2012 14:44

Edited by author 01.11.2012 14:45

am solutia
o vreti

Please, give some testdata

This is my code:


program num_1510;
type ar = array of longint;
var N,i,j,c,a:longint;
arr,arr2,arr3:ar; pow:boolean;
BEGIN
    read(N);
    setlength(arr,N+2);
    setlength(arr2,N+2);
    setlength(arr3,N+2);
    for i:=1 to N do
        read(arr[i]);
    arr2[1]:=arr[1];
    c:=1;
    for i:=1 to N do
        begin
            for j:=1 to N do
                begin
                    if arr2[j]=arr[i]
                        then
                            begin
                                pow:=false;
                                break;
                            end
                        else
                            begin
                                pow:=true;
                            end;
                end;
            if pow then begin arr2[c]:=arr[i]; c:=c+1; end;
        end;
    for i:=1 to N do
        begin
            for j:=1 to N do
                begin
                    if arr[i]=arr2[j] then c:=j;
                end;
            arr3[c]:=arr3[c]+1;
        end;
    a:=arr3[1];
    for i:=1 to N do
        begin
            if a>arr3[i+1]
            then a:=a
            else a:=arr3[i+1];
        end;
    for i:=1 to N do
        begin
            if a = arr3[i]
            then begin a:=i; break; end;
        end;
    write(arr2[a]);
END.



Please, help me:)

Edited by author 01.11.2012 00:53

var
  a,b,c,d:integer;
begin
  read(a,b,c,d);
  if   ((a-b=0)or(a-c=0)or(a-d=0))
    and((b-a=0)or(b-c=0)or(b-d=0))
    and((c-a=0)or(c-b=0)or(c-d=0))
    and((d-a=0)or(d-b=0)or(d-c=0)) then
    writeln('yes')
  else
    writeln('no');
end.

Test#11
4 10 4
2497

Out - 10 10 10 2

What's wrong?

Don't use int. Use long long.

Edited by author 31.10.2012 15:46

My program got Crash (assert), cause this test has some trash in the end.

Валят первым тестом, вроде работает
#include <stdio.h>
void main()
{
    int i=0,cash=0;
    char text[1000];
    gets(text);
    while(text[i]!=NULL && i<1001)
    {
        if (text[i]=='a' || text[i]=='d' || text[i]=='g' || text[i]=='j' || text[i]=='m' || text[i]=='p' || text[i]=='s' || text[i]=='v' || text[i]=='y' || text[i]=='.' || text[i]==' ') cash+=1;
        if (text[i]=='b' || text[i]=='e' || text[i]=='h' || text[i]=='k' || text[i]=='n' || text[i]=='q' || text[i]=='t' || text[i]=='w' || text[i]=='z' || text[i]==',') cash+=2;
        if (text[i]=='c' || text[i]=='f' || text[i]=='i' || text[i]=='l' || text[i]=='o' || text[i]=='r' || text[i]=='u' || text[i]=='x' || text[i]=='!' ) cash+=3;
        i++;
    }
    printf("%d",cash);
}

Edited by author 30.10.2012 18:58

Поясните пример, пожалуйста