Discussion @ 1213. Cockroaches! @ Timus Online Judge

Pegasus Why the answer is Number_of_Compartments-1 [1] // Problem 1213. Cockroaches! 5 Dec 2012 07:37

Axmadjon Help in Java 1.7 // Problem 1213. Cockroaches! 5 Jun 2014 16:20

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.io.StreamTokenizer;
import java.util.Scanner;

public class Test {
    public static void main(String[] args) throws IOException {
        new Test().solve();
    }

    private static Scanner s = new Scanner(System.in);
    static int n = 0;

    void solve() throws IOException {

        String input = null;
        String[] strArray = new String[30];

        while (true) {
            input = getString();

            if (input.equals("#")) {
                break;
            } else {
                saveItToArray(strArray, input);
            }
        }

        checkOutIdentical(strArray);

        System.out.println(n - 1);
    }

    private static String getString() throws IOException {

        String input;

        input = s.nextLine();
        return (input);
    }

    void saveItToArray(String[] strArray, String input) {
        boolean isDash = false;
        for (int i = 0; i < input.length(); i++) {
            if (input.charAt(i) == '-') {
                strArray[n++] = input.substring(0, i);
                strArray[n++] = input.substring(i + 1, input.length());

                isDash = true;
                break;
            } else {
                isDash = false;
            }
        }

        if (!isDash) {
            strArray[n++] = input;
        }

    }

    void checkOutIdentical(String[] strArray) {
        int count = 0;
        count = n;
        for (int i = 1; i < count; i++) {
            for (int j = i - 1; j >= 0; j--) {
                if (!strArray[i].equals(" ") && !strArray[j].equals(" ")
                        && strArray[i].equals(strArray[j])) {
                    strArray[i] = " ";
                    n--;
                }
            }
        }
    }

}

Y.Y.M. The problem is simple.But you must care that if N(different compartments)=0 you should output 0 instead of -1 [7] // Problem 1213. Cockroaches! 22 Jun 2004 20:34

Magvay Re: The problem is simple.But you must care that if N(different compartments)=0 you should output 0 instead of -1 [1] // Problem 1213. Cockroaches! 5 Sep 2004 18:25

thanks a lot. I really didn't know what to do with test 13

Maigo Akisame (maigoakisame@yahoo.com.cn) It's not number of compartments=0. If you don't ignore the first line of input there'll be no this problem. // Problem 1213. Cockroaches! 26 Sep 2004 20:29

beststu Re: The problem is simple.But you must care that if N(different compartments)=0 you should output 0 instead of -1 [4] // Problem 1213. Cockroaches! 20 Feb 2006 10:57

Cockroaches!蟑螂
Time Limit: 1 second
Memory Limit: 1000K

It's well-known that the most tenacious of life species on the Earth are cockroaches. They live everywhere if only there in food. And as far as they are unpretentious in food you can find them absolutely everywhere.
众所周知地球上最顽强的生命种类是蟑螂，他们生活在有食物的任何地方。只要有食物，你就可以发现他们的影踪。

A little Lyosha studies at school on a Space station. During one of the school competitions his class has reached the final. A task of the final contest is to exterminate all the cockroaches in the cargo module within minimal time.
Lyosha 在太空站的学校学习。在学校的一项竞赛里，他们班已经到达接近尾声，其中一项任务是在最小的时间里消灭货物仓里的蟑螂。

Within the long history of the competitions a unified tactics was worked out. The tactics is as follows: a poison gas is let in one of the module compartments and after that the baffle that separates the compartment from one of the adjacent ones is opened. Cockroaches can't stand the smell of the gas and run to the other compartment. When there's no cockroaches in the treated compartment the baffle is closed. Afterwards analogously the next compartment is treated, and so on. The goal is to move all the cockroaches to the floodgate of the cargo module. Then the outward door is opened and all the cockroaches are engulfed by an open Space.
他们在长时间的竞赛里，已经形成了统一的战术。战术是这样的：把毒气放在一个厢房里，另外，打开闸门（隔开相邻厢房的门）。蟑螂不能忍受毒气的味道，会纷纷逃向隔壁的已打开的厢房，如此下去。目标是把所有的蟑螂赶向floodgate货物仓（的闸门）。

Lyosha is responsible for programming the control board of the baffles in his team. The baffles are opened slowly, so it's very important to make do with minimal number of baffle openings in order to win in the contest. Your task is to help Lyosha to compute this number.
Lyosha负责闸门的规划控制，闸门开得慢，所以这项工作对于竞赛的胜负是很重要的，要设法使到开最少的门。你的任务是帮助Lyosha 计算这个数。

Input
The first line contains a name of the floodgate compartment. Each of the next lines contains description of one of the baffles - the names of two compartments separated with a dash (-). The last line contains the only symbol "#". There are cockroaches in all the compartments of the module at first. It's possible to get to the floodgate from every compartment of the module passing several baffles. The total number of compartments doesn't exceed 30. The name of a compartment consists of no more than 20 Latin letters and digits. The large and the small letters should be distinguished.
首行为floodgate厢房名。以下每一行为两个厢房间的闸门名，两个厢房间用(-)隔开。最后一行只有“#”结束。开始时每个厢房都有蟑螂。每个厢房的蟑螂经过几个闸门后都能到达floodgate。厢房的数量不超过30个。厢房名不超过20个字母数字，区分大小写。

Output
Your program is to output the only number - the minimal amount of baffles that should be opened (and then closed) in order to move all the cockroaches to the floodgate.
输出最小的数字，即为了能把蟑螂赶到指定的floodgate,要开的门数（当然开完后又关上）

Sample Input
Gateway
Machinery-Gateway
Machinery-Control
Control-Central
Control-Engine
Central-Engine
Storage-Gateway
Storage-Waste
Central-Waste
#
Sample Output
6

dick19880328 Re: The problem is simple.But you must care that if N(different compartments)=0 you should output 0 instead of -1 [3] // Problem 1213. Cockroaches! 29 Aug 2007 07:22

thx anyway for translating it to Chinese

Skrebnev Re: The problem is simple.But you must care that if N(different compartments)=0 you should output 0 instead of -1 [2] // Problem 1213. Cockroaches! 26 Dec 2007 15:07

Thank, I have Got WA13) now AC

Pegasus Re: The problem is simple.But you must care that if N(different compartments)=0 you should output 0 instead of -1 [1] // Problem 1213. Cockroaches! 5 Dec 2012 07:40

I just want to know why the answer is Number_comparments - 1

adamant Re: The problem is simple.But you must care that if N(different compartments)=0 you should output 0 instead of -1 // Problem 1213. Cockroaches! 18 Dec 2013 15:25

Because you can make a tree from comparments and then open the baffles from the leaves to the root of tree using only n-1 baffle.

PrankMaN If you have WA #4 // Problem 1213. Cockroaches! 3 Aug 2013 03:05

fuch_prog_er #13 [2] // Problem 1213. Cockroaches! 11 Feb 2009 23:59

Ankerok Easy Answer (Russian) // Problem 1213. Cockroaches! 17 Apr 2012 20:36

SP2 For all Who used hash and got WA6 [1] // Problem 1213. Cockroaches! 25 Sep 2007 20:12

Varduhi Yeghiazaryan No subject // Problem 1213. Cockroaches! 18 Feb 2009 14:40

GodZilla Help me PLEASE !!!! [2] // Problem 1213. Cockroaches! 7 Nov 2002 02:52

Please help me !!!!
What's wrong in my code ????????????????????????

var a:array[1..100,1..100]of integer;
     nn:array[1..100]of string;
     s,s1:string;
     kol:integer;
     w:integer;
function find(s:string):integer;
var i:integer;
begin
for i:=1 to kol do
if nn[i]=s then
   begin
    find:=i;
    exit;
   end;
find:=kol+1;
end;
procedure init;
var k:integer;
    ch1,ch2,pp:integer;
begin
kol:=1;
{assign(input,'input.txt');
reset(input);}
readln(s);
nn[kol]:=s;
readln(s);
while s<>'#' do
   begin
    k:=pos('-',s);
    s1:=copy(s,1,k-1);
    delete(s,1,k);
    pp:=find(s1);
    if pp> kol then kol:=pp;
    nn[pp]:=s1;
    ch1:=pp;
    pp:=find(s);
    if pp> kol then kol:=pp;
    nn[pp]:=s;
    ch2:=pp;
    a[ch1,ch2]:=1;
    a[ch2,ch1]:=1;
    readln(s);
   end;
{close(input);}
end;
procedure solve;
var i,k,l,p:integer;
    ss,sp:set of 1..200;
    min,t,j:integer;
    ok:boolean;
begin
ss:=[1..kol];sp:=[];
for i:=1 to kol do
if a[1,i]<>0 then
   begin
    p:=i;
    break;
   end;
w:=1;
ss:=ss-[1,p];sp:=[1,p];
while ss<>[] do
begin
   for i:=1 to kol do
    begin
     ok:=false;
     if not(i in sp)then
      for j:=1 to kol do
       if (j in sp)and(a[i,j]<>0)then
        begin
         ss:=ss-[i,j];
         sp:=sp+[i,j];
         inc(w);
         break;
         ok:=true;
        end;
     if ok then break;
    end;
end;
end;
procedure outt;
begin
writeln(w);
end;
begin
init;
solve;
outt;
end.

GodZilla Sorry !!!!!! I got AC !!!!! [1] // Problem 1213. Cockroaches! 8 Nov 2002 19:06

> Please help me !!!!
> What's wrong in my code ????????????????????????
>
> var a:array[1..100,1..100]of integer;
>      nn:array[1..100]of string;
>      s,s1:string;
>      kol:integer;
>      w:integer;
> function find(s:string):integer;
> var i:integer;
> begin
> for i:=1 to kol do
>   if nn[i]=s then
>    begin
>     find:=i;
>     exit;
>    end;
> find:=kol+1;
> end;
> procedure init;
> var k:integer;
>     ch1,ch2,pp:integer;
> begin
> kol:=1;
> {assign(input,'input.txt');
> reset(input);}
>   readln(s);
>   nn[kol]:=s;
>   readln(s);
>   while s<>'#' do
>    begin
>     k:=pos('-',s);
>     s1:=copy(s,1,k-1);
>     delete(s,1,k);
>     pp:=find(s1);
>     if pp> kol then kol:=pp;
>     nn[pp]:=s1;
>     ch1:=pp;
>     pp:=find(s);
>     if pp> kol then kol:=pp;
>     nn[pp]:=s;
>     ch2:=pp;
>     a[ch1,ch2]:=1;
>     a[ch2,ch1]:=1;
>     readln(s);
>    end;
> {close(input);}
> end;
> procedure solve;
> var i,k,l,p:integer;
>     ss,sp:set of 1..200;
>     min,t,j:integer;
>     ok:boolean;
> begin
> ss:=[1..kol];sp:=[];
> for i:=1 to kol do
>   if a[1,i]<>0 then
>    begin
>     p:=i;
>     break;
>    end;
> w:=1;
> ss:=ss-[1,p];sp:=[1,p];
> while ss<>[] do
>   begin
>    for i:=1 to kol do
>     begin
>      ok:=false;
>      if not(i in sp)then
>       for j:=1 to kol do
>        if (j in sp)and(a[i,j]<>0)then
>         begin
>          ss:=ss-[i,j];
>          sp:=sp+[i,j];
>          inc(w);
>          break;
>          ok:=true;
>         end;
>      if ok then break;
>     end;
> end;
> end;
> procedure outt;
> begin
> writeln(w);
> end;
> begin
> init;
> solve;
> outt;
> end.

Sandello Re: Sorry !!!!!! I got AC !!!!! // Problem 1213. Cockroaches! 25 Jan 2009 16:30

Don't forget about min and max tests))

TheBeet This problem is very easy.But I don't know it has such a long text. [1] // Problem 1213. Cockroaches! 14 May 2004 10:34

ENick(TNU) Please,expl me my mistake-why WA2 // Problem 1213. Cockroaches! 30 Jun 2008 01:46

Hemisphere Got WA on test 9 any example? [1] // Problem 1213. Cockroaches! 30 Apr 2006 19:03

dracularKing why crash on this in java:while (input.equals("#")!=true) [3] // Problem 1213. Cockroaches! 27 Jun 2006 20:56

who can tell me

Vladimir Yakovlev (USU) Re: why crash on this in java:while (input.equals("#")!=true) [2] // Problem 1213. Cockroaches! 28 Jun 2006 00:48

Your program crashes on another line.

Didn't you try to run your program on sample input?

dracularKing Re: why crash on this in java:while (input.equals("#")!=true) [1] // Problem 1213. Cockroaches! 28 Jun 2006 09:42

i tried on my pc, i managed to have it runned through
i know that's all because im not familiar with the online java judge environment, but i just cannot get any feedback infomation from the email system, how does it come?

here's my codes, i really dont know where and how

import java.io.*;

public class Application
{
    public static void main(String[] args) throws IOException
    {
        new Application().run();
    }

    StreamTokenizer in;
    PrintWriter out;
    static int n = 0;

    void run() throws IOException
    {
        in = new StreamTokenizer(new BufferedReader(new InputStreamReader(
            System.in)));
        out = new PrintWriter(new OutputStreamWriter(System.out));
        solve();
        out.flush();
    }

    void solve() throws IOException
    {

        String input = null;
        String[] strArray = new String[30];

        while (true)
        {
            input = getString();

            if (input.equals("#"))
            {
                break;
            }
            else
            {
                saveItToArray(strArray, input);
            }
        }

        checkOutIdentical(strArray);

        System.out.println(n - 1);
    }

    private static String getString() throws IOException
    {
        BufferedReader keyboard =
            new BufferedReader(new InputStreamReader(System.in));
        String input;

        input = keyboard.readLine();
        return (input);
    }

    void saveItToArray(String[] strArray, String input)
    {
        boolean isDash = false;
        for (int i = 0; i < input.length(); i++)
        {
            if (input.charAt(i) == '-')
            {
                strArray[n++] = input.substring(0, i);
                strArray[n++] = input.substring(i + 1, input.length());

                isDash = true;
                break;
            }
            else
            {
                isDash = false;
            }
        }

        if (!isDash)
        {
            strArray[n++] = input;
        }

    }

    void checkOutIdentical(String[] strArray)
    {
        int count = 0;
        count = n;
        for (int i = 1; i < count; i++)
        {
            for (int j = i - 1; j >= 0; j--)
            {
                if (!strArray[i].equals(" ") && !strArray[j].equals(" ") &&
                    strArray[i].equals(strArray[j]))
                {
                    strArray[i] = " ";
                    n--;
                }
            }
        }
    }
}

Vladimir Yakovlev (USU) Re: why crash on this in java:while (input.equals("#")!=true) // Problem 1213. Cockroaches! 28 Jun 2006 12:13

getString() is wrong!!!
BufferedReader(new InputStreamReader(System.in)) reads whole input during the first run of getString(), but you use only first line of it

VladG There is very simple decision [1] // Problem 1213. Cockroaches! 29 Oct 2002 22:23

Failed Peter what does this problem mean? [1] // Problem 1213. Cockroaches! 28 Apr 2004 17:37

Nikolay Marinov Can someone give me a test where the answer is different from (diferent compartments - 1) [1] // Problem 1213. Cockroaches! 12 Jan 2003 12:46

Vlad Veselov Why answer is not equal to (amount of departments) - 1???Give some tests plz. [1] // Problem 1213. Cockroaches! 5 Jun 2003 20:45

Discussion of Problem 1213. Cockroaches!