(UVA) Scarecrow - Solution
Link to the problem: https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=3836
Every time that a crop-growing spot that is not covered by a scarecrow is found, it is assumed that the next position will receive a scarecrow. If the crop-growing spot is in the last position, and there is no scarecrow related to this spot, it will receive a scarecrow itself. The approach used was Greedy.
import java.io.*;
import java.util.*;
class Main {
public static void process() throws NumberFormatException, IOException {
Scanner sc = new Scanner(System.in);
int numTests = sc.nextInt();
for (int i = 0; i < numTests; i++) {
int lengthField = sc.nextInt();
char[] field = new char[lengthField];
String line = sc.next();
for (int j = 0; j < lengthField; j++) {
field[j] = line.charAt(j);
}
int count = 0;
boolean onePoint = false;
for (int j = 0; j < lengthField; ) {
if (onePoint) {
count++;
onePoint = false;
j += 2;
continue;
}
if (field[j] == '.') {
onePoint = true;
if (j == lengthField-1) {
count++;
}
}
j++;
}
System.out.println("Case " + (i+1) + ": " + count);
}
return;
}
public static void main(String[] args) throws NumberFormatException, IOException {
Main m = new Main();
m.process();
System.exit(0);
}
}
Every time that a crop-growing spot that is not covered by a scarecrow is found, it is assumed that the next position will receive a scarecrow. If the crop-growing spot is in the last position, and there is no scarecrow related to this spot, it will receive a scarecrow itself. The approach used was Greedy.
import java.io.*;
import java.util.*;
class Main {
public static void process() throws NumberFormatException, IOException {
Scanner sc = new Scanner(System.in);
int numTests = sc.nextInt();
for (int i = 0; i < numTests; i++) {
int lengthField = sc.nextInt();
char[] field = new char[lengthField];
String line = sc.next();
for (int j = 0; j < lengthField; j++) {
field[j] = line.charAt(j);
}
int count = 0;
boolean onePoint = false;
for (int j = 0; j < lengthField; ) {
if (onePoint) {
count++;
onePoint = false;
j += 2;
continue;
}
if (field[j] == '.') {
onePoint = true;
if (j == lengthField-1) {
count++;
}
}
j++;
}
System.out.println("Case " + (i+1) + ": " + count);
}
return;
}
public static void main(String[] args) throws NumberFormatException, IOException {
Main m = new Main();
m.process();
System.exit(0);
}
}
Comments
Post a Comment