Форум программистов
 

Восстановите пароль или Зарегистрируйтесь на форуме, о проблемах и с заказом рекламы пишите сюда - alarforum@yandex.ru, проверяйте папку спам!

Вернуться   Форум программистов > IT форум > Помощь студентам
Регистрация

Восстановить пароль
Повторная активизация e-mail

Купить рекламу на форуме - 42 тыс руб за месяц

Ответ
 
Опции темы Поиск в этой теме
Старый 13.11.2012, 15:49   #1
Dessu
Новичок
Джуниор
 
Регистрация: 13.11.2012
Сообщений: 4
По умолчанию задача "Гонки" (паскаль\делфи)

Пожалуйста, помогите школьнику решить на делфи или переписать с явы

Гонки.

Имя входного файла: rally.in
Имя выходного файла: rally.out
Максимальное время работы на одном тесте: 2 секунды
Максимальный объем используемой памяти: 256 мегабайт
В области Х находится У городов. Некоторые пары городов соединены
проселочной дорогой с двусторонним движением. Начавшись в каком-то
городе, дорога не может закончиться в нем же. В этом году состояние
дорог позволило отделению ГИБДД области Х провести гонки под
лозунгом «Скажем НЕТ нарушениям скоростного режима». Было
решено, что круговая трасса должна состоять из четырех дорог, но не
может проходить через один город два раза. Естественно, свернуть
с одной дороги на другую можно только в городе. Организаторы
уже должны приступить к составлению отчета, и для этого требуется
посчитать количество различных трасс.
Формат входного файла В первой строке входного файла записаны
количество городов У (1 ≤ У ≤ 300) и количество дорог К. В каждой из
следующих m строк содержится два различных числа — номера городов,
соединенных соответствующей дорогой.
Формат выходного файла В выходной файл выведите одно число —
количество круговых трасс из четырех дорог, которые могут составить
организаторы.

Пример

rally.in
4 6
1 2
2 3
3 4
4 1
1 3
2 4

rally.out
3

Код на яве
Код:
import java.io.File;
import java.io.FileWriter;
import java.io.IOException;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.Scanner;

public class rally_ft implements Runnable {

	private Scanner in;
	private PrintWriter out;
	private int cread = 0;
	
	
	public void run() {
		out.close();
	}
	
	private rally_ft(String name) {
		try {
			in = new Scanner(new File(name + ".in"));
			out = new PrintWriter(new FileWriter(name + ".out"));	
			int n = in.nextInt();
			int m = in.nextInt();
			int[][] a = new int[n][n];
			for (int i = 0; i < m; i++) {
				int u = in.nextInt() - 1;
				int v = in.nextInt() - 1;
				a[u][v] += 1;
				a[v][u] += 1;
			}

			boolean bad = false;

			for (int i = 0; i < n; i++) {
				for (int j = i + 1; j < n; j++) {
					if (a[i][j] > 1) {
						System.err.println("Multiple edges between " + i + " " + j);
						bad = true;
					}
				}
			}
			assert(!bad);
			long ans = 0;

			int[][] b = new int[n][n];
			for (int i = 0; i < n; i++) {
				for (int j = 0; j < n; j++) {
					b[i][j] = 0;
					for (int k = 0; k < n; k++) {
						b[i][j] += a[i][k] * a[k][j];
					}
				}
			}

			for (int i = 0; i < n; i++) {
				for (int j = i + 1; j < n; j++) {
					ans += b[i][j] * (b[i][j] - 1);
				}
			}

			out.println(ans / 4);
			out.close();
		} catch (IOException e) {
			e.printStackTrace();
			System.exit(239);
		}
	}

	public static void main(String[] args) {
		(new Thread(new rally_ft("rally"))).start();
	}
}
Dessu вне форума Ответить с цитированием
Старый 13.11.2012, 16:22   #2
Abstraction
Старожил
 
Аватар для Abstraction
 
Регистрация: 25.10.2011
Сообщений: 3,178
По умолчанию

Возможно, будет проще, если Вы скажете, какую из строк приведённого кода (самой функции rally_ft внутри блока try, остальное несущественно) Вы не можете перевести на Delphi.
Abstraction вне форума Ответить с цитированием
Старый 13.11.2012, 16:31   #3
Dessu
Новичок
Джуниор
 
Регистрация: 13.11.2012
Сообщений: 4
По умолчанию

Какое исключение ловит try?

Последний раз редактировалось Dessu; 13.11.2012 в 16:36. Причина: тупость
Dessu вне форума Ответить с цитированием
Старый 13.11.2012, 16:34   #4
Dessu
Новичок
Джуниор
 
Регистрация: 13.11.2012
Сообщений: 4
По умолчанию

В принципе, я попробовал перевести и программа завелась, но показывает неверный ответ, а на яве - верный.

Код:
int[][] b = new int[n][n];
в этой строке создается двумерный массив?
Dessu вне форума Ответить с цитированием
Старый 13.11.2012, 16:38   #5
Abstraction
Старожил
 
Аватар для Abstraction
 
Регистрация: 25.10.2011
Сообщений: 3,178
По умолчанию

Цитата:
Мне нужен основной код решения задачи. Предположительно, он начинается с этих строк
Да. Это функция, принимающая аргумент типа "строка" (имя файла с данными). try{...}catch - синтаксическая конструкция для обработки исключительных ситуаций; в Delphi вроде есть какой-то её аналог, но пока это можно просто выкинуть. Дальше открываются два файла, на чтение и запись, и из первого читаются все пары (первый цикл).
Второй цикл, с System.err.println - проверка на отсутствие дублей в данных; по большому счёту не нужна. Третий (тройной) цикл - умножение матрицы инцидентности a на саму себя, с сохранением результата в новую матрицу b. Четвёртый цикл - сбор ответа, причём каждый путь оказывается посчитан 4 раза. out.println(ans / 4); выводит полученный ответ в выходной файл.

Цитата:
в этой строке создается двумерный массив?
Да. Размера n*n. Обратите внимание: в Java первый элемент массива размера n имеет индекс 0, а последний - n-1.
Abstraction вне форума Ответить с цитированием
Старый 13.11.2012, 16:45   #6
Dessu
Новичок
Джуниор
 
Регистрация: 13.11.2012
Сообщений: 4
По умолчанию

Огромное спасибо.
for(int i = 0; i < n; i++) - аналог for i:=0 to i=n do ?
Вроде бы, ничего сложного нет, но код в делфи выводит 0.5

Еще вопрос - первый цикл можно выбросить?

Последний раз редактировалось Stilet; 13.11.2012 в 18:16.
Dessu вне форума Ответить с цитированием
Ответ


Купить рекламу на форуме - 42 тыс руб за месяц



Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Игра "Гонки" polarity Общие вопросы Delphi 4 30.12.2011 17:00
на вход подаются сведения об учениках и оценках. Найти тех, кто сдал на "4" и "5" ( Паскаль ) weech Помощь студентам 1 18.11.2011 13:57
Тестовые задания при устройстве на работу. "Гонки кнопок", разные потоки. Casper-SC Свободное общение 4 12.11.2010 13:15
Паскаль.Программа "Верификация", "Кака бригадиру разделить заработанные деньги?".Сложные Valik102 Помощь студентам 11 23.06.2009 15:30
Почти готовые "гонки" Ulex Gamedev - cоздание игр: Unity, OpenGL, DirectX 11 20.09.2008 21:48