2013
11-12

# Catch That Cow

Farmer John has been informed of the location of a fugitive cow and wants to catch her immediately. He starts at a point N (0 ≤ N ≤ 100,000) on a number line and the cow is at a point K (0 ≤ K ≤ 100,000) on the same number line. Farmer John has two modes of transportation: walking and teleporting.

* Walking: FJ can move from any point X to the points X - 1 or X + 1 in a single minute
* Teleporting: FJ can move from any point X to the point 2 × X in a single minute.

If the cow, unaware of its pursuit, does not move at all, how long does it take for Farmer John to retrieve it?

Line 1: Two space-separated integers: N and K

Line 1: The least amount of time, in minutes, it takes for Farmer John to catch the fugitive cow.

5 17

4

The fastest way for Farmer John to reach the fugitive cow is to move along the following path: 5-10-9-18-17, which takes 4 minutes.

解法一:
import java.io.BufferedInputStream;
import java.util.Scanner;

public class Main {

public static final int MAX = 200000;

public static void main(String[] args) {

Scanner scan = new Scanner(new BufferedInputStream(System.in));
if (scan.hasNext()) {
int n = scan.nextInt();
int k = scan.nextInt();
System.out.println(catchTheCow(n, k));
}
}

public static int catchTheCow(int n, int k) {
if (n == k) {
return 0;
}
boolean[] visited = new boolean[MAX + 5];
int[] minutes = new int[MAX + 5];
visited[n] = true;
while (!queue.isEmpty()) {
int current = queue.removeFirst();
for (int i = 0; i < 3; i++) {
int next = current;
if (i == 0) {
next++;
} else if (i == 1) {
next--;
} else if (i == 2) {
next <<= 1;
}
if (next < 0 || next > MAX) {
continue;
}
if (!visited[next]) {
visited[next] = true;
minutes[next] = minutes[current] + 1;
}
if (next == k) {
return minutes[k];
}
}
}

return 0;
}
}

import java.io.*;
public class Main
{
public static void main(String[] args) throws IOException
{
int a=Integer.parseInt(ss[0]);
int b=Integer.parseInt(ss[1]);
if(a>=b){
System.out.println(a-b);
System.exit(0);
}
int cnt=0;
if(a==0){
a++;
cnt++;
}
while(a< b)
{
a*=2;
cnt++;
}
if(a==b){
System.out.println(cnt);
System.exit(0);
}
a/=2;cnt--;
int g=(int) Math.pow(2,cnt);
int l=2*a-b;
int n=g*2;
int h=cnt+1+f(l,n);
int u=b-a;
int k=cnt+f(u,g);
System.out.println(Math.min(k,h));
}

public static int f(int l,int n)
{
if(n==0)return 0;
int h=l%n;
int a=f(n-h,n/2)+l/n+1;
int b=f(h,n/2)+l/n;
return Math.min(a, b);
}
}

1. 很高兴你会喜欢这个网站。目前还没有一个开发团队，网站是我一个人在维护，都是用的开源系统，也没有太多需要开发的部分，主要是内容整理。非常感谢你的关注。

2. #include <cstdio>
#include <cstring>

const int MAXSIZE=256;
//char store[MAXSIZE];
char str1[MAXSIZE];
/*
void init(char *store) {
int i;
store['A']=’V', store['B']=’W',store['C']=’X',store['D']=’Y',store['E']=’Z';
for(i=’F';i<=’Z';++i) store =i-5;
}
*/
int main() {
//freopen("input.txt","r",stdin);
//init(store);
char *p;
while(fgets(str1,MAXSIZE,stdin) && strcmp(str1,"STARTn")==0) {
if(p=fgets(str1,MAXSIZE,stdin)) {
for(;*p;++p) {
//*p=store[*p]
if(*p<’A’ || *p>’Z') continue;
if(*p>’E') *p=*p-5;
else *p=*p+21;
}
printf("%s",str1);
}
fgets(str1,MAXSIZE,stdin);
}
return 0;
}

3. 因为是要把从字符串s的start位到当前位在hash中重置，修改提交后能accept，但是不修改居然也能accept