Олимпиадное программирование

Информация о пользователе

Привет, Гость! Войдите или зарегистрируйтесь.

Вы здесь » Олимпиадное программирование » Общий » Вода (Красноярск '07)

Вода (Красноярск '07)

Страница: 1

Сообщений 1 страница 6 из 6

1

  • Автор: Konstantin
  • Администратор
  • Зарегистрирован: 2007-11-07
  • Приглашений: 0
  • Сообщений: 34
  • Уважение: [+0/-0]
  • Позитив: [+0/-0]
  • Провел на форуме:
    5 часов 54 минуты
  • Последний визит:
    2008-01-05 19:17:25

Международная олимпиада АСМ по программированию
(четвертьфинал) 2007

Задача H
Вода

Входные данные читать из файла WATER.IN в текущем каталоге. Выходные данные писать  в стандартный поток вывода (на  дисплей). Исходный текст программы направлять на решение в файле WATER.CPP или WATER.DPR or WATER.JAVA
Ограничение по времени 5 секунд
Ограничение по памяти  64 Мбайта

Имеется три ведра, ёмкость которых известны и не равны. Самое большое ведро полное, остальные пусты. Требуется добиться, чтобы в самом большом ведре был заданный объем воды. За один шаг вода переливается из одного ведра в другое до тех пор, пока либо не закончится вода в ведре-источнике, либо не наполнится доверху вода в ведре-получателе.
Школьник Василий, чтобы занять себя, пытается решать эту задачу с разными входными данными, но не всегда находит решение. И даже если решение найдено, он хочет знать, является ли найденное решение оптимальным, а именно, используется ли минимальное количество шагов. Требуется написать программу, которая поможет Василию проверить его решение.

Входные данные:
Каждый тест приведён в отдельной строке, и содержит 4 натуральных числа, ёмкости вёдер b1, b2, b3 (1000 > b1 > b2 > b3 > 0), и требуемое количество воды в первом ведре t (b1 > t > 0). Признак окончания тестов – строка с данными b1 = b2 = b3 = t = 0, и этот тест не следует решать.

Пример входных данных:
10 8 4 4
10 8 4 5
0 0 0 0

Выходные данные:
Для каждого теста вывести либо минимальное количество переливаний, либо если задача не имеет решения, то слово IMPOSSIBLE (заглавными буквами).

Пример выходных данных:
3
IMPOSSIBLE

0

2

  • Автор: Konstantin
  • Администратор
  • Зарегистрирован: 2007-11-07
  • Приглашений: 0
  • Сообщений: 34
  • Уважение: [+0/-0]
  • Позитив: [+0/-0]
  • Провел на форуме:
    5 часов 54 минуты
  • Последний визит:
    2008-01-05 19:17:25

import java.io.FileReader;
import java.io.IOException;
import java.util.Scanner;

public class Task_H {

public static int state[][] = new int[1000000][4], ykr, ykw;
public static int b1, b2, b3;

public static boolean check(int[] input) {
    boolean res = true;
    for (int i=0; (i<ykw)&&res; i++) {
    res = !((state[i][0]==input[0])&&(state[i][1]==input[1])&&(state[i][2]==input[2]));   
    }
    return res;
}

public static int[] generate(int[] input, int a, int b) {
    int qua[] = {b1, b2, b3}, res[] = new int[4];
    for (int i=0; i<4; i++) res[i] = input[i];
    if (res[b]+res[a]>qua[b]) {
    res[a] -= (qua[b]-res[b]);
    res[b] = qua[b];
   
    } else {
    res[b] += res[a];
    res[a] = 0;
    }
    res[3]++;
    return res;
}

public static void main(String[] args) throws IOException {
    Scanner input = new Scanner(new FileReader("WATER.IN"));
    int t, temp[] = new int[4];
    int kombin[][] = {{0, 1},{0, 2},{1, 2},{1, 0},{2, 0},{2, 1}};
    b1 = input.nextInt();
    b2 = input.nextInt();
    b3 = input.nextInt();
    t = input.nextInt();
    while ((b1+b2+b3+t)!=0) {
    state[0] = new int[] {b1, 0, 0, 0};
    ykw=1;
    ykr=0;
    while ((ykr<ykw)&&(state[ykr][0]!=t)) {
        for (int i=0; i<6; i++) {
        temp = generate(state[ykr], kombin[i][0], kombin[i][1]);
        if (check(temp)) {
            state[ykw] = temp;
            ykw++;
        }
        }
        ykr++;
    }
    if (state[ykr][0]==t) {
        System.out.println(state[ykr][3]);
    } else {
        System.out.println("IMPOSSIBLE");
    }
    b1 = input.nextInt();
    b2 = input.nextInt();
    b3 = input.nextInt();
    t = input.nextInt();
    }
}

}

0

3

  • Автор: Konstantin
  • Администратор
  • Зарегистрирован: 2007-11-07
  • Приглашений: 0
  • Сообщений: 34
  • Уважение: [+0/-0]
  • Позитив: [+0/-0]
  • Провел на форуме:
    5 часов 54 минуты
  • Последний визит:
    2008-01-05 19:17:25

Идея решения:

Нужно генерировать все возможные состояния (т.е. количество воды в ведрах), пока не найдется решение (воды в первом ведре будет t).

Структуры данных:

state[i][A] - количество воды в A-м ведре в I-м состоянии
state[i][4] - количество переливаний, после которых получено данное состояние (не путать с I)

Алгоритм:

Заводим массив int state[][] = new int[1000000][4] . В этом массиве будут содержаться все генерируемые состояния.

Первой строкой в массиве будет начальное состояние (b1, 0, 0, 0), т.е. первое ведро заполнено, остальные пусты, достигнуто с помощью 0 переливаний

Ykr - номер читаемой из массива state[][] строки. Для этой строки на данной итерации мы генерируем все возможные состояния, в которые можно перейти с помощью метода generate.
Затем проверяем с помощью метода check, не была ли сгенерирована эта комбинация ранее (повторения нам не нужны, так можно и в бесконечный цикл уйти). Если не была - записываем ее в массив на ykw строку, ykw увеличиваем на единицу.

Описание методов:

public static int[] generate(int[] input, int a, int b)
generate(исходная строка, ведро-источник, ведро-приемник) - возвращает сгенерированное состояние

public static boolean check(int[] input)
check(проверяемая на повторение строка) - возвращает boolean

Примечание:

В предварительно заданном массиве int kombin[][] = {{0, 1},{0, 2},{1, 2},{1, 0},{2, 0},{2, 1}} содержатся все возможные комбинации операций (komib[i][0] - номер ведра-источника в i-ой комбинации, kombin[i][1] - номер ведра-приемника в i-ой комбинации), номера ведер начинаются с нуля

0

4

  • Автор: kir_const
  • Новичок
  • Зарегистрирован: 2007-11-11
  • Приглашений: 0
  • Сообщений: 4
  • Уважение: [+0/-0]
  • Позитив: [+0/-0]
  • Провел на форуме:
    45 минут
  • Последний визит:
    2007-11-12 21:49:54

Судя по ограничениям, организаторы такое решение и предполагали. Но решение может быть более эффективным. Во-первых, надо оценить количество состояний. Из условий задачи, понятно что хотя бы одно ведро либо полное либо пустое. Закодируем состояния, например так
0 - ведро А полное
1 - ведро А пустое
2 - ведро А не полное и не пустое, ведро Б полное
3 - ведро А не полное и не пустое, ведро Б пустое
4 - ведра А и Б не полные и непустые, ведро С полное
5 - ведра А и Б не полные и непустые, ведро С пустое
Для каждого из состояний объем воды в оставшихся двух ведрах известен и не превышает N. Тем
самым количество соcтояний не превышает 6N.
Их можно указанным способом закодировать, распихать в массивы и определять пройденное состояние за константное время. Поэтому можно довести объем воды, скажем до 1000000.

Можно попробовать не заниматься кодированием состояний, а написать класс на Java в котором хранить состояния ведер и использовать для хранения и поиска HashTable. Ей надо установить размер где нибудь в районе 15N  и просто помещать состояния туда. Такой прием поможет кучу аналогичных задач решить.

0

5

  • Автор: Konstantin
  • Администратор
  • Зарегистрирован: 2007-11-07
  • Приглашений: 0
  • Сообщений: 34
  • Уважение: [+0/-0]
  • Позитив: [+0/-0]
  • Провел на форуме:
    5 часов 54 минуты
  • Последний визит:
    2008-01-05 19:17:25

Появились вопросы:
Что такое N?
В первом случае будет ли осуществляться генерация состояний? Или состояние, подходящее под одно из шести описаний уже точно будет считаться возможным? Как в этом случае определить количество шагов?
Во втором случае мы просто заменим массив состояний HashTable'ом?

0

6

  • Автор: kir_const
  • Новичок
  • Зарегистрирован: 2007-11-11
  • Приглашений: 0
  • Сообщений: 4
  • Уважение: [+0/-0]
  • Позитив: [+0/-0]
  • Провел на форуме:
    45 минут
  • Последний визит:
    2007-11-12 21:49:54

Надо убрать этот цикл по поиску пройденных состояний. С этой целью надо либо сделать булевский массив индексом в котором будет код состояния, либо воспользоваться встроенным классом, который быстро осуществляет поиск - HashTable. N - я имел в виду суммарный объем воды.

0

Страница: 1

Вы здесь » Олимпиадное программирование » Общий » Вода (Красноярск '07)