Я выполняю эту задачу программирования, которую можно найти на сайте www.interviewstreet.com (это первая задача стоимостью 30 баллов).
Когда я представил решение, мне вернули результат, в котором говорилось, что ответ был неправильным, потому что он прошел только 1/11 тестовых случаев. Тем не менее, я чувствую, что проверил различные случаи и не понимаю, что я делаю неправильно. Было бы полезно узнать, какими могут быть эти тестовые примеры, чтобы я мог протестировать свою программу.
Вот вопрос (между серыми линиями ниже):
Quadrant Queries (30 баллов)
На плоскости N точек. У i-й точки есть координаты (xi, yi). Выполните следующие запросы:
1) Отразить все точки между точками i и j, в том числе вдоль оси X. Этот запрос представлен как "X i j"
2) Отразить все точки между точками i и j, в том числе вдоль оси Y. Этот запрос представлен как "Y i j"
3) Подсчитайте, сколько точек между точками i и j, включая оба, лежат в каждом из 4 квадрантов. Этот запрос представлен как "C i j"
Вход:
Первая строка содержит N, количество точек. N строк.
В i-й строке записаны xi и yi, разделенные пробелом.
Следующая строка содержит Q количество запросов. Следующие Q строк содержат по одному запросу в каждой из приведенных выше форм.
Все индексы 1 проиндексированы.
Выход:
Выведите одну строку для каждого запроса типа «C i j». Соответствующая строка содержит 4 целых числа; количество точек, имеющих индексы в диапазоне [i..j] в 1-м, 2-м, 3-м и 4-м квадрантах соответственно.
Ограничения:
1 <= N <= 100000 <br />
1 <= Q <= 100000 <br />
Вы можете предположить, что ни одна точка не лежит на оси X или Y.
Все (xi, yi) поместятся в 32-разрядное целое число со знаком
Во всех запросах 1 <= i <= j <= N <br />
Пример ввода:
4
1 1
-1 1
-1 -1
1 -1
5
C 1 4
X 2 4
C 3 4
Y 1 2
C 1 3
Пример вывода:
1 1 1 1
1 1 0 0
0 2 0 1
Пояснение:
Когда запрос говорит «X i j», это означает, что берут все точки между индексами i и j, включая и отражая эти точки вдоль оси X. Здесь i и j не имеют ничего общего с координатами точек. Это показатели. i относится к точке i, а j относится к точке j
«C 1 4» просит вас «Рассмотреть набор точек, имеющих индекс в {1,2,3,4}. Среди этих пунктов, сколько из них находится в 1, 2, 3 и 4-м квадроциклах соответственно?
Ответ на это однозначно 1 1 1 1.
Далее мы отражаем точки между индексами '2 4' вдоль оси X. Итак, новые координаты:
1 1
-1 -1
-1 1
1 1
Теперь «C 3 4» - это «Рассмотрим множество точек, имеющих индекс в {3,4}. Среди этих пунктов, сколько из них находится в 1, 2, 3 и 4-м квадроциклах соответственно? Точка 3 лежит в квадранте 2, а точка 4 - в квадранте 1.
Таким образом, ответ 1 1 0 0
Я пишу код на PHP, а метод тестирования - с использованием STDIN и STDOUT.
Есть какие-нибудь идеи по поводу сложных тестовых случаев для тестирования моего кода? Я не понимаю, почему я провал 10/11 тестовых случаев.
Кроме того, вот мой код, если вам интересно:
// The global variable that will be changed
$points = array();
/******** Functions ********/
// This function returns the number of points in each quadrant.
function C($beg, $end) {
// $quad_count is a local array and not global as this gets reset for every C operation
$quad_count = array("I" => 0, "II" => 0, "III" => 0, "IV" => 0);
for($i=$beg; $i<$end+1; $i++) {
$quad = checkquad($i);
$quad_count[$quad]++;
}
return $quad_count["I"]." ".$quad_count["II"]." ".$quad_count["III"]." ".$quad_count["IV"];
}
// Reflecting over the x-axis means taking the negative value of y for all given points
function X($beg, $end) {
global $points;
for($i=$beg; $i<$end+1; $i++) {
$points[$i]["y"] = -1*($points[$i]["y"]);
}
}
// Reflecting over the y-axis means taking the negative value of x for all given points
function Y($beg, $end) {
global $points;
for($i=$beg; $i<$end+1; $i++) {
$points[$i]["x"] = -1*($points[$i]["x"]);
}
}
// Determines which quadrant a given point is in
function checkquad($i) {
global $points;
$x = $points[$i]["x"];
$y = $points[$i]["y"];
if ($x > 0) {
if ($y > 0) {
return "I";
} else {
return "IV";
}
} else {
if ($y > 0) {
return "II";
} else {
return "III";
}
}
}
// First, retrieve the number of points that will be provided. Make sure to check constraints.
$no_points = intval(fgets(STDIN));
if ($no_points > 100000) {
fwrite(STDOUT, "The number of points cannot be greater than 100,000!\n");
exit;
}
// Remember the points are 1 indexed so begin key from 1. Store all provided points in array format.
for($i=1; $i<$no_points+1; $i++) {
global $points;
list($x, $y) = explode(" ",fgets(STDIN)); // Get the string returned from the command line and convert to an array
$points[$i]["x"] = intval($x);
$points[$i]["y"] = intval($y);
}
// Retrieve the number of operations that will be provied. Make sure to check constraints.
$no_operations = intval(fgets(STDIN));
if($no_operations > 100000) {
fwrite(STDOUT, "The number of operations cannot be greater than 100,000!\n");
exit;
}
// Retrieve the operations, determine the type and send to the appropriate functions. Make sure i <= j.
for($i=0; $i<$no_operations; $i++) {
$operation = explode(" ",fgets(STDIN));
$type = $operation[0];
if($operation[1] > $operation[2]) {
fwrite(STDOUT, "Point j must be further in the sequence than point i!\n");
exit;
}
switch ($type) {
case "C":
$output[$i] = C($operation[1], $operation[2]);
break;
case "X":
X($operation[1], $operation[2]);
break;
case "Y":
Y($operation[1], $operation[2]);
break;
default:
$output[$i] = "Sorry, but we do not recognize this operation. Please try again!";
}
}
// Print the output as a string
foreach($output as $line) {
fwrite(STDOUT, $line."\n");
}
UPDATE:
Я наконец нашел тестовый случай, для которого моя программа не работает. Сейчас я пытаюсь определить, почему. Это хороший урок по тестированию с большими числами.
10
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
12
C 1 10
X 1 3
C 5 5
Y 2 10
C 10 10
C 1 10
X 1 3
C 5 5
Y 2 10
C 10 10
X 3 7
C 9 9
Я собираюсь проверить это правильно, инициализируя массив ошибок и определяя, какие операции вызывают проблему.