powered by simpleCommunicator - 2.0.61     © 2026 Programmizd 02
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Форумы / Java [игнор отключен] [закрыт для гостей] / Проблема с TopCoder-а
15 сообщений из 15, страница 1 из 1
Проблема с TopCoder-а
    #38340989
Фотография Vigoole
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Вот проблема с TopCoder-a, я ее сделал. Но за такое можно свобоно оторвать мне руки. Как мне избежать такой вложоности if/for, как по другому написать чтоб было понятно и другим ?
Проблема

Problem Statement

Sometimes when computer programs have a limited number of colors to use, they use a technique called dithering. Dithering is when you use a pattern made up of different colors such that when the colors are viewed together, they appear like another color. For example, you can use a checkerboard pattern of black and white pixels to achieve the illusion of gray.
You are writing a program to determine how much of the screen is covered by a certain dithered color. Given a computer screen where each pixel has a certain color, and a list of all the solid colors that make up the dithered color, return the number of pixels on the screen that are used to make up the dithered color. Each pixel will be represented by a character in screen. Each character in screen and in dithered will be an uppercase letter ('A'-'Z') representing a color.
Assume that any pixel which is a color contained in dithered is part of the dithered color.
Definition

Class:
ImageDithering
Method:
count
Parameters:
String, String[]
Returns:
int
Method signature:
int count(String dithered, String[] screen)
(be sure your method is public)


Constraints
-
dithered will contain between 2 and 26 upper case letters ('A'-'Z'), inclusive.
-
There will be no repeated characters in dithered.
-
screen will have between 1 and 50 elements, inclusive.
-
Each element of screen will contain between 1 and 50 upper case letters ('A'-'Z'), inclusive.
-
All elements of screen will contain the same number of characters.
Examples
0)

"BW"
{"AAAAAAAA",
"ABWBWBWA",
"AWBWBWBA",
"ABWBWBWA",
"AWBWBWBA",
"AAAAAAAA"}
Returns: 24
Here, our dithered color could consist of black (B) and white (W) pixels, composing a shade of gray. In the picture, there is a dithered gray square surrounded by another color (A).
1)


"BW"
{"BBBBBBBB",
"BBWBWBWB",
"BWBWBWBB",
"BBWBWBWB",
"BWBWBWBB",
"BBBBBBBB"}
Returns: 48
Here is the same picture, but with the outer color replaced with black pixels. Although in reality, the outer pixels do not form a dithered color, your algorithm should still assume they are part of the dithered pattern.
2)


"ACEGIKMOQSUWY"
{"ABCDEFGHIJKLMNOPQRSTUVWXYZABCDEFGHIJKLMNOPQRSTUVWX",
"ABCDEFGHIJKLMNOPQRSTUVWXYZABCDEFGHIJKLMNOPQRSTUVWX",
"ABCDEFGHIJKLMNOPQRSTUVWXYZABCDEFGHIJKLMNOPQRSTUVWX",
"ABCDEFGHIJKLMNOPQRSTUVWXYZABCDEFGHIJKLMNOPQRSTUVWX",
"ABCDEFGHIJKLMNOPQRSTUVWXYZABCDEFGHIJKLMNOPQRSTUVWX",
"ABCDEFGHIJKLMNOPQRSTUVWXYZABCDEFGHIJKLMNOPQRSTUVWX"}
Returns: 150
A picture of vertical stripes, every other stripe is considered part of the dithered color.
3)


"CA"
{"BBBBBBB",
"BBBBBBB",
"BBBBBBB"}
Returns: 0
The dithered color is not present.
4)


"DCBA"
{"ACBD"}
Returns: 4
The order of the colors doesn't matter.
This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2003, TopCoder, Inc. All rights reserved.


Мой код
Код: java
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
public class ImageDithering {

	public static int count(String dithered, String[] screen) {
		int answer = 0;
		if (dithered.length() >= 2 && dithered.length() <= 26)
			if (dithered.matches("[A-Z]*"))
				if (screen.length >= 1 && screen.length <= 50)
					for (int i = 0, j = screen[0].length(); i < screen.length; i++) {
						if (screen[i].matches("[A-Z]*")
								&& j == screen[i].length()) {
							if (screen[i].matches("["+dithered+"^[A-Z]]*")) {
								for (int k = 0; k < dithered.length(); k++) {
									for (int n = 0; n < screen[i].length(); n++) {
										if(dithered.charAt(k)==screen[i].charAt(n))
											answer++;
									}
								}
							}
						}
						else System.exit(1);
						
					}

		return answer;
	}

	public static void main(String[] args) {
		String tt = "BW";
		String[] strArray = { "AAAAAAAA", 
				      "ABWBWBWA", 
				      "AWBWBWBA", 
				      "ABWBWBWA",
				      "AWBWBWBA", 
				      "AAAAAAAA" };
		System.out.println(tt.length());
		System.out.println(ImageDithering.count(tt, strArray));

	}
}

...
Рейтинг: 0 / 0
Проблема с TopCoder-а
    #38340996
Фотография Blazkowicz
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Вы бы начали с табуляции. А то косоглазие сторо будет от восьми пробелов на отступ.
...
Рейтинг: 0 / 0
Проблема с TopCoder-а
    #38341009
Фотография Vigoole
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Табуляция нормальная но когда ставил код из эклипс тут по другому все выглядит, и какбудто нажимал 2 раза таб.
...
Рейтинг: 0 / 0
Проблема с TopCoder-а
    #38341043
Фотография Blazkowicz
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
VigooleТабуляция нормальная но когда ставил код из эклипс тут по другому все выглядит, и какбудто нажимал 2 раза таб.
Ну, дык перенастройте на 4.
...
Рейтинг: 0 / 0
Проблема с TopCoder-а
    #38341051
Фотография Blazkowicz
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Первые три блока - превалидация. Их лучше отделить от реализации логики.

Код: java
1.
2.
3.
4.
5.
6.
7.
if (!(dithered.length() >= 2 && dithered.length() <= 26)) return 0;
if (!(dithered.matches("[A-Z]*")))  return 0;
if (!(screen.length >= 1 && screen.length <= 50)) return 0;

for (int i = 0, j = screen[0].length(); i < screen.length; i++) {
  ...						
}



else System.exit(1); - тоже сильный ход.
...
Рейтинг: 0 / 0
Проблема с TopCoder-а
    #38341078
Фотография Blazkowicz
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
переменная i не нужна. enhanced for loop будет проще. Переменная j хранит длину, а не индекс вводит читателя в заблуждение.
...
Рейтинг: 0 / 0
Проблема с TopCoder-а
    #38341174
rfq
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
BlazkowiczПервые три блока - превалидация. Их лучше отделить от реализации логики.

Код: java
1.
2.
3.
4.
5.
6.
7.
if (!(dithered.length() >= 2 && dithered.length() <= 26)) return 0;
if (!(dithered.matches("[A-Z]*")))  return 0;
if (!(screen.length >= 1 && screen.length <= 50)) return 0;

for (int i = 0, j = screen[0].length(); i < screen.length; i++) {
  ...						
}



else System.exit(1); - тоже сильный ход.
Поддерживаю.
Аналогично меняется:,
Код: java
1.
2.
if (screen[i].matches("[A-Z]*") &&  j == screen[i].length()) System.exit(1);
if (screen[i].matches("["+dithered+"^[A-Z]]*")) continue;
...
Рейтинг: 0 / 0
Проблема с TopCoder-а
    #38341180
Фотография Vigoole
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Blazkowiczelse System.exit(1); - тоже сильный ход.
Недавно написал простую программку и выдавало какуюту ошибку в eclipse связано с JRE так нашол что можно обойти именно с этой команды.
Табуляция по умолчанию настроена на 4
Спс за ответы
...
Рейтинг: 0 / 0
Проблема с TopCoder-а
    #38341181
rfq
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
rfqАналогично меняется:,
Код: java
1.
2.
if (screen[i].matches("[A-Z]*") &&  j == screen[i].length()) System.exit(1);
if (screen[i].matches("["+dithered+"^[A-Z]]*")) continue;



Забыл обратить булевы значения условий.
...
Рейтинг: 0 / 0
Проблема с TopCoder-а
    #38341184
rfq
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
VigooleТабуляция по умолчанию настроена на 4
Спс за ответы
Это она в Эклипсе настроена на 4. В тексте ставится символ '\t', а здесь он считается за 8. Лучше избавьтесь от табуляций в тексте вообще, пишите одни пробелы - в Эклипсе есть такая опция.
...
Рейтинг: 0 / 0
Проблема с TopCoder-а
    #38341235
ivanra
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
А еще лучше попытаться сначала найти правильное решение, и потом заниматься украшательствами.
- судя по примеру №2 должны учитываться не только горизонтальные, но и вертикальные совпадения. Приведенное решение ищет только в строках
- судя по примеру №3 учитываются "разреженные" совпадения
вывод: Задача сформулирована небрежно, либо примеры неправильные.

Подозреваю, что можно обобщить на диагонали и ломанные.
Исходя из этого обобщения решение следующее:
- весь массив свалить в кучу
- убедиться что в этой куче есть все символы из шаблона (решается в один проход с помощью HashSet)
- в этом же проходе выкинуть все лишние символы
- посчитать результат
...
Рейтинг: 0 / 0
Проблема с TopCoder-а
    #38341371
Фотография Vigoole
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
ivanraА еще лучше попытаться сначала найти правильное решение, и потом заниматься украшательствами.
- судя по примеру №2 должны учитываться не только горизонтальные, но и вертикальные совпадения. Приведенное решение ищет только в строках
- судя по примеру №3 учитываются "разреженные" совпадения
вывод: Задача сформулирована небрежно , либо примеры неправильные.

Подозреваю , что можно обобщить на диагонали и ломанные.
Исходя из этого обобщения решение следующее:
- весь массив свалить в кучу
- убедиться что в этой куче есть все символы из шаблона (решается в один проход с помощью HashSet)
- в этом же проходе выкинуть все лишние символы
- посчитать результат

Обратите внимания в проблеме одномерный масив строк
...
Рейтинг: 0 / 0
Проблема с TopCoder-а
    #38341377
Фотография Blazkowicz
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
VigooleОбратите внимания в проблеме одномерный масив строк
Problem в данном контексте - "задача", а не "проблема"
...
Рейтинг: 0 / 0
Проблема с TopCoder-а
    #38341379
Фотография Blazkowicz
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
VigooleНедавно написал простую программку и выдавало какуюту ошибку в eclipse связано с JRE так нашол что можно обойти именно с этой команды.
Т.е. "не знаю что было, не знаю зачем сделал, но есть как есть"
...
Рейтинг: 0 / 0
Проблема с TopCoder-а
    #38341588
ivanra
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
По оформлению: ограничения (constraints) обычно не проверяются, это то, что "дано", на вход подаются данные уже удовлетворяющие перечисленным условиям. Понятно, что лишняя проверка не повредит, но в общем случае это лишний код:
Код: java
1.
2.
3.
4.
if (dithered.length() >= 2 && dithered.length() <= 26)
if (dithered.matches("[A-Z]*"))
if (screen.length >= 1 && screen.length <= 50)
if (screen[i].matches("[A-Z]*") && j == screen[i].length()) {


Но если очень хочется, то проверку можно вынести в отдельный метод.

По самому решению. Вот массив из 2 примера:
Код: java
1.
2.
3.
4.
5.
6.
BBBBBBBB
BBWBWBWB
BWBWBWBB
BBWBWBWB
BWBWBWBB
BBBBBBBB


Все 48 "пикселей" этого массива удовлетворяют шаблону BW, в том числе и угловые, отсюда и можно сделать вывод, что учитываются не только горизонтальные, но и вертикальные и диагональные совпадения (и даже ходы "конем"). То есть пиксели не должны стоять рядом, достаточно найти любое совпадение. Для примера, такой массив должен тоже дать в результате 48:
Код: java
1.
2.
3.
4.
5.
6.
WBBBBBBB
BBBBBBBB
BBBBBBBB
BBBBBBBB
BBBBBBBB
BBBBBBBB


Далее просто обобщаем на ломанные в случае с более длинными шаблонами. В конце концов, в условиях задачи нигде не сказано, что пиксели должны составлять линию, либо находиться на определенном расстоянии друг от друга.

Ну, и отсюда решение:
- проверить, что на экране есть все пиксели из шаблона, если это не так, результат 0.
- посчитать на экране те пиксели, которые имеются в шаблоне - это и есть ответ.
Я предложил решать с помощью множеств, но это для ленивых, более эффективный алгоритм можно написать с использованием целочисленных массивов.
...
Рейтинг: 0 / 0
15 сообщений из 15, страница 1 из 1
Форумы / Java [игнор отключен] [закрыт для гостей] / Проблема с TopCoder-а
Найденые пользователи ...
Разблокировать пользователей ...
Читали форум (0):
Пользователи онлайн (0):
x
x
Закрыть


Просмотр
0 / 0
Close
Debug Console [Select Text]