5 3 1 1 E RFRFRFRF 3 2 N FRRFLLFFRRFLL 0 3 W LLFFFLFLFL
1 1 E 3 3 N LOST 2 3 S
出處: UVa Online Judge - Mutant Flatworld Explorers
#include <iostream>
#include <map>
#include <vector>
using namespace std;
bool checkIsLost(int x, int y, int maxX, int maxY) {
return x < 0 || x > maxX || y < 0 || y > maxY;
}
int main() {
int maxX, maxY, x, y;
char ori;
string ins;
char oriArr[4] = {'E', 'N', 'W', 'S'};
int oriArrLen = 4;
map<char, int> oriIndexMap;
oriIndexMap['E'] = 0;
oriIndexMap['N'] = 1;
oriIndexMap['W'] = 2;
oriIndexMap['S'] = 3;
cin >> maxX >> maxY;
vector< vector<bool> > lostTable(maxX + 1, vector<bool>(maxY + 1, false));
while (cin >> x >> y >> ori >> ins) {
int oriIndex;
bool lost = false;
oriIndex = oriIndexMap[ori];
for (int i=0; i<ins.length(); i++) {
switch (ins[i]) {
case 'L':
oriIndex = (oriIndex + 1) % oriArrLen;
break;
case 'R':
if (oriIndex)
oriIndex--;
else
oriIndex = oriArrLen - 1;
break;
case 'F':
switch (oriIndex) {
case 0:
lost = checkIsLost(x + 1, y, maxX, maxY);
if (!lost)
x++;
break;
case 1:
lost = checkIsLost(x, y + 1, maxX, maxY);
if (!lost)
y++;
break;
case 2:
lost = checkIsLost(x - 1, y, maxX, maxY);
if (!lost)
x--;
break;
case 3:
lost = checkIsLost(x, y - 1, maxX, maxY);
if (!lost)
y--;
}
}
if (lost && !lostTable[x][y]) {
lostTable[x][y] = true;
break;
}
}
cout << x << " " << y << " " << oriArr[oriIndex];
if (lost)
cout << " " << "LOST\n";
else
cout << endl;
}
return 0;
}
1 2 3 4 5 6 7 8 9 5 10 5 20 10 5 10 20 10
BCG 30 CBG 50
#include <iostream>
#include <vector>
#include <map>
using namespace std;
int main() {
int start;
while (cin >> start) {
vector< vector<int> > binBottle(3, vector<int>(3, -1));
vector<string> comb(6, "");
map<string, int> getCount;
string minComb;
comb[0] = "BCG";
comb[1] = "BGC";
comb[2] = "CBG";
comb[3] = "CGB";
comb[4] = "GBC";
comb[5] = "GCB";
for (int i=0; i<binBottle.size(); i++) {
for (int j=0; j<binBottle[i].size(); j++) {
if (!i && !j)
binBottle[i][j] = start;
else
cin >> binBottle[i][j];
}
}
getCount[comb[0]] = binBottle[1][0] + binBottle[2][0] + binBottle[0][2] + binBottle[2][2] +
binBottle[0][1] + binBottle[1][1];
getCount[comb[1]] = binBottle[1][0] + binBottle[2][0] + binBottle[0][1] + binBottle[2][1] +
binBottle[0][2] + binBottle[1][2];
getCount[comb[2]] = binBottle[1][2] + binBottle[2][2] + binBottle[0][0] + binBottle[2][0] +
binBottle[0][1] + binBottle[1][1];
getCount[comb[3]] = binBottle[1][2] + binBottle[2][2] + binBottle[0][1] + binBottle[2][1] +
binBottle[0][0] + binBottle[1][0];
getCount[comb[4]] = binBottle[1][1] + binBottle[2][1] + binBottle[0][0] + binBottle[2][0] +
binBottle[0][2] + binBottle[1][2];
getCount[comb[5]] = binBottle[1][1] + binBottle[2][1] + binBottle[0][2] + binBottle[2][2] +
binBottle[0][0] + binBottle[1][0];
minComb = comb[0];
for (int i=1; i<comb.size(); i++) {
if (getCount[minComb] > getCount[comb[i]])
minComb = comb[i];
}
cout << minComb << " " << getCount[minComb] << endl;
}
return 0;
}
.png)
.png)
.png)
#include <stdio.h>
int binarySearch(int *, int, int);
int main() {
int arr[8] = {1, 2, 3, 4, 5, 6, 7, 8};
int arrLength = 8;
int findNum = 3;
int findIndex = binarySearch(arr, arrLength, findNum);
if (findIndex == -1)
printf("The number %d is not in the sequence\n", findNum);
else
printf("The number %d is at index %d\n", findNum, findIndex);
return 0;
}
int binarySearch(int *arr, int arrLength, int findNum) {
int low = 0;
int high = arrLength - 1;
while (low <= high) {
int mid = (low + high) / 2;
if (findNum > arr[mid])
low = mid + 1;
else if (findNum == arr[mid])
return mid;
else
high = mid - 1;
}
return -1;
}
public class BinarySearch {
public static void main(String[] args) {
int[] arr = {1, 2, 3, 4, 5, 6, 7, 8};
int findNum = 3;
int findIndex = binarySearch(arr, findNum);
if (findIndex == -1)
System.out.printf("The number %d is not in the sequence\n", findNum);
else
System.out.printf("The number %d is at index %d\n", findNum, findIndex);
}
private static int binarySearch(int[] arr, int findNum) {
int low = 0;
int high = arr.length - 1;
while (low <= high) {
int mid = (low + high) / 2;
if (findNum > arr[mid])
low = mid + 1;
else if (findNum == arr[mid])
return mid;
else
high = mid - 1;
}
return -1;
}
}
def binarySearch(arr, findNum):
low = 0
high = len(arr) - 1
while low <= high:
mid = (low + high) / 2
if findNum > arr[mid]:
low = mid + 1
elif findNum == arr[mid]:
return mid
else:
high = mid - 1
return -1
arr = [1, 2, 3, 4, 5, 6, 7, 8]
findNum = 3
findIndex = binarySearch(arr, findNum)
if findIndex == -1:
print "The number %d is not in the sequence" % (findNum)
else:
print "The number %d is at index %d" % (findNum, findIndex)
#include <stdio.h>
void mergeSort(int *, int, int);
void merge(int *, int, int, int);
int main() {
int arr[8] = {4, 6, 1, 9, 5, 3, 0, 2};
int dataNum = 8;
int i;
printf("before sorting: ");
for (i=0; i<dataNum; i++)
printf("%d " , arr[i]);
printf("\n");
mergeSort(arr, 0, dataNum - 1);
printf("after sorting: ");
for (i=0; i<dataNum; i++)
printf("%d " , arr[i]);
printf("\n");
return 0;
}
void mergeSort(int *arr, int low, int high) {
if (low < high) {
int mid = (low + high) / 2;
mergeSort(arr, low, mid);
mergeSort(arr, mid + 1, high);
merge(arr, low, mid, high);
}
}
void merge(int *arr, int low, int mid, int high) {
int leftIndex = low;
int rightIndex = mid + 1;
int tempArrLength = high - low + 1;
int tempArr[tempArrLength];
int tempIndex = 0;
while (leftIndex <= mid && rightIndex <= high) {
if (arr[leftIndex] <= arr[rightIndex]) {
tempArr[tempIndex] = arr[leftIndex];
leftIndex++;
}
else {
tempArr[tempIndex] = arr[rightIndex];
rightIndex++;
}
tempIndex++;
}
if (leftIndex > mid) {
while (rightIndex <= high) {
tempArr[tempIndex] = arr[rightIndex];
rightIndex++;
tempIndex++;
}
}
else {
while (leftIndex <= mid) {
tempArr[tempIndex] = arr[leftIndex];
leftIndex++;
tempIndex++;
}
}
leftIndex = low;
for (tempIndex=0; tempIndex<tempArrLength; tempIndex++) {
arr[leftIndex] = tempArr[tempIndex];
leftIndex++;
}
}
public class MergeSort {
public static void main(String[] args) {
int[] arr = {4, 6, 1, 9, 5, 3, 0, 2};
System.out.print("before sorting: ");
for (int num: arr)
System.out.printf("%d " , num);
System.out.println();
mergeSort(arr, 0, arr.length - 1);
System.out.print("after sorting: ");
for (int num: arr)
System.out.printf("%d " , num);
System.out.println();
}
private static void mergeSort(int[] arr, int low, int high) {
if (low < high) {
int mid = (low + high) / 2;
mergeSort(arr, low, mid);
mergeSort(arr, mid + 1, high);
merge(arr, low, mid, high);
}
}
private static void merge(int[] arr, int low, int mid, int high) {
int leftIndex = low;
int rightIndex = mid + 1;
int[] tempArr = new int[high - low + 1];
int tempIndex = 0;
while (leftIndex <= mid && rightIndex <= high) {
if (arr[leftIndex] <= arr[rightIndex]) {
tempArr[tempIndex] = arr[leftIndex];
leftIndex++;
}
else {
tempArr[tempIndex] = arr[rightIndex];
rightIndex++;
}
tempIndex++;
}
if (leftIndex > mid) {
while (rightIndex <= high) {
tempArr[tempIndex] = arr[rightIndex];
rightIndex++;
tempIndex++;
}
}
else {
while (leftIndex <= mid) {
tempArr[tempIndex] = arr[leftIndex];
leftIndex++;
tempIndex++;
}
}
leftIndex = low;
for (int temp: tempArr) {
arr[leftIndex] = temp;
leftIndex++;
}
}
}
def merge(arr, low, mid, high):
leftIndex = low
rightIndex = mid + 1
tempArr = []
while leftIndex <= mid and rightIndex <= high:
if arr[leftIndex] <= arr[rightIndex]:
tempArr.append(arr[leftIndex])
leftIndex += 1
else:
tempArr.append(arr[rightIndex])
rightIndex += 1
if leftIndex > mid:
while rightIndex <= high:
tempArr.append(arr[rightIndex])
rightIndex += 1
else:
while leftIndex <= mid:
tempArr.append(arr[leftIndex])
leftIndex += 1
leftIndex = low
for temp in tempArr:
arr[leftIndex] = temp
leftIndex += 1
def mergeSort(arr, low, high):
if low < high:
mid = (low + high) / 2
mergeSort(arr, low, mid)
mergeSort(arr, mid + 1, high)
merge(arr, low, mid, high)
arr = [4, 6, 1, 9, 5, 3, 0, 2]
print "before sorting:",
for num in arr:
print "%d" % (num),
print ""
mergeSort(arr, 0, len(arr) - 1)
print "after sorting:",
for num in arr:
print "%d" % (num),
print ""
#include <stdio.h>
void selSort(int *, int);
int main() {
int arr[8] = {3, 5, 9, 10, 8, 1, 12, 4};
int dataNum = 8;
int i;
printf("before sorting: ");
for (i=0; i<dataNum; i++)
printf("%d ", arr[i]);
printf("\n");
selSort(arr, dataNum);
printf("after sorting: ");
for (i=0; i<dataNum; i++)
printf("%d ", arr[i]);
printf("\n");
return 0;
}
void selSort(int *arr, int dataNum) {
int i, j;
for (i=0; i<dataNum; i++) {
int smallestIndex = i;
for (j=i+1; j<dataNum; j++) {
if (arr[smallestIndex] > arr[j])
smallestIndex = j;
}
if (smallestIndex != i) {
int temp = arr[smallestIndex];
arr[smallestIndex] = arr[i];
arr[i] = temp;
}
}
}
public class SelSort {
public static void main(String[] args) {
int[] arr = {3, 5, 9, 10, 8, 1, 12, 4};
System.out.print("before sorting: ");
for (int num: arr)
System.out.printf("%d ", num);
System.out.println();
selSort(arr);
System.out.print("after sorting: ");
for (int num: arr)
System.out.printf("%d ", num);
System.out.println();
}
private static void selSort(int[] arr) {
for (int i=0; i<arr.length; i++) {
int smallestIndex = i;
for (int j=i+1; j<arr.length; j++) {
if (arr[smallestIndex] > arr[j])
smallestIndex = j;
}
if (smallestIndex != i) {
int temp = arr[smallestIndex];
arr[smallestIndex] = arr[i];
arr[i] = temp;
}
}
}
}
def selSort(arr):
for i in range(len(arr)):
smallestIndex = i
for j in range(i + 1, len(arr)):
if arr[smallestIndex] > arr[j]:
smallestIndex = j
if smallestIndex != i:
temp = arr[smallestIndex]
arr[smallestIndex] = arr[i]
arr[i] = temp
arr = [3, 5, 9, 10, 8, 1, 12, 4]
print "before sorting:",
for num in arr:
print num,
print ""
selSort(arr)
print "after sorting:",
for num in arr:
print num,
print ""
as shown in the diagram below:![\begin{figure}
\centering
\setlength{\unitlength}{0.0125in} %
\begin{picture}
(2...
...raisebox{0pt}[0pt][0pt]{$\bullet
\bullet \bullet$ }}}
\end{picture}
\end{figure}](http://uva.onlinejudge.org/external/1/101img2.gif) |
where n is the number of blocks) should appear followed immediately by a colon. If there is at least a block on it, the colon must be followed by one space, followed by a list of blocks that appear stacked in that position with each block number separated from other block numbers by a space. Don't put any trailing spaces on a line.10 move 9 onto 1 move 8 over 1 move 7 over 1 move 6 over 1 pile 8 over 6 pile 8 over 5 move 2 over 1 move 4 over 9 quit
0: 0 1: 1 9 2 4 2: 3: 3 4: 5: 5 8 7 6 6: 7: 8: 9:
出處: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=3&page=show_problem&problem=37
#include <iostream>
#include <vector>
using namespace std;
void moveBackToOri(vector< vector<int> >& blocks, vector<int>& blockPos, int pos, int theBlock) {
while (blocks[pos].back() != theBlock) {
int last = blocks[pos].back();
blocks[pos].pop_back();
blocks[last].push_back(last);
blockPos[last] = last;
}
}
void pileBlocks(vector< vector<int> >& blocks, vector<int>& blockPos, int pos, int theBlock, vector<int>& temp) {
while (true) {
int last = blocks[pos].back();
blocks[pos].pop_back();
temp.push_back(last);
if (last == theBlock)
break;
}
}
int main() {
int blockNum;
cin >> blockNum;
vector< vector<int> > blocks(blockNum, vector<int>());
vector<int> blockPos(blockNum, -1);
for (int i=0; i<blocks.size(); i++) {
blocks[i].push_back(i);
blockPos[i] = i;
}
while (true) {
string action, where;
int fromBlock, toBlock;
int fromPos;
int toPos;
cin >> action;
if (action == "quit")
break;
cin >> fromBlock >> where >> toBlock;
fromPos = blockPos[fromBlock];
toPos = blockPos[toBlock];
if (fromPos != toPos) {
if (action == "move") {
if (where == "onto") {
moveBackToOri(blocks, blockPos, fromPos, fromBlock);
moveBackToOri(blocks, blockPos, toPos, toBlock);
blocks[fromPos].pop_back();
blocks[toPos].push_back(fromBlock);
blockPos[fromBlock] = toPos;
}
else {
moveBackToOri(blocks, blockPos, fromPos, fromBlock);
blocks[fromPos].pop_back();
blocks[toPos].push_back(fromBlock);
blockPos[fromBlock] = toPos;
}
}
else {
vector<int> temp;
if (where == "onto") {
pileBlocks(blocks, blockPos, fromPos, fromBlock, temp);
moveBackToOri(blocks, blockPos, toPos, toBlock);
while (!temp.empty()) {
int last = temp.back();
temp.pop_back();
blocks[toPos].push_back(last);
blockPos[last] = toPos;
}
}
else {
pileBlocks(blocks, blockPos, fromPos, fromBlock, temp);
while (!temp.empty()) {
int last = temp.back();
temp.pop_back();
blocks[toPos].push_back(last);
blockPos[last] = toPos;
}
}
}
}
}
for (int i=0; i<blocks.size(); i++) {
cout << i << ":";
for (int j=0; j<blocks[i].size(); j++)
cout << " " << blocks[i][j];
cout << endl;
}
return 0;
}
#include <iostream>
#include <vector>
using namespace std;
int main() {
int left, right, height, last;
int first = -1;
int nowHeight = 0;
vector<int> heightVec(10000, 0);
while (cin >> left >> height >> right) {
if (first == -1) {
first = left;
last = right;
}
if (right > last)
last = right;
for (int i=left; i<right; i++) {
if (height > heightVec[i])
heightVec[i] = height;
}
}
for (int i=first; i<=last; i++) {
if (heightVec[i] != nowHeight) {
cout << i << " " << heightVec[i];
if (i == last)
cout << endl;
else {
cout << " ";
nowHeight = heightVec[i];
}
}
}
return 0;
}