[Java]伯俊16953号[A→B]Java
白俊16953号です.
https://www.acmicpc.net/problem/16953
質問する
2を掛けます. 1を数の一番右側に追加します. AからBまでの演算の最大値を求める.
入力
https://www.acmicpc.net/problem/16953
質問する
整数AをBに変えたいです.可能な演算は次の2つです.
入力
第1行は、A、B(1≦Aしゅつりょく
AをBに変換するために必要な演算の最大値に1を加算して出力します.作成できない場合は、-1を出力します.
入力例1 2 162
2 → 4 → 8 → 81 → 1624 42
100 40021
100 → 200 → 2001 → 4002 → 40021
サンプル出力1 5
-1
5
考える
DFS/BFSとGreedyアルゴリズムタイプの問題.
条件さえ理解すれば、問題は十分に解決できる.
これらの条件は問題で明確に説明されている.
AをBにする.
一番後ろに1を付けたり、2を掛けてBにしたりします.
アクション
私は逆に解いたのです
A->Bに行くのは問題ですが、通常迷路を解く場合、始点から終点までは難しく、終点から始点までは簡単です.
このような問題もB->Aとは逆の方が解決しやすい
したがって、BとAが異なる場合は、繰り返し続けます.
脱出条件がA=Bであれば自動脱出であり、例えばBより大きい場合はAである.
すなわち、BはAを超える.
この場合はもちろんAとBが違うのでcount = -1でいいです
各条件.
Bが偶数であれば2に分けられる.
一番後ろの数字が1の場合、1を削除します.
Bが奇数であれば、それを2に分けることはできないので、そのままcount=-1で中断すればよい.
BFSもあまり違いはありません.Queueを使用して実装します.
脱出条件をGreedyアルゴリズムで使用する条件にすればよい.
TMI
これはDFS/BFSの問題ですが、なぜいつも違う方法で解決しているのでしょうか.
大丈夫ですか.
コード#コード#
Greedy
import java.util.*;
import java.io.*;
public class Main {
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
long A = Long.parseLong(st.nextToken());
long B = Long.parseLong(st.nextToken());
int count = 1;
while(B != A) {
String str = Long.toString(B);
if(B % 2 == 0) {
B /= 2;
}
else if(str.charAt(str.length() -1) == '1') {
B = Long.parseLong( str.substring(0, str.length() - 1) );
}
else {
count = -1;
break;
}
if(B < A) {
count = -1;
break;
}
count ++;
}
System.out.println(count);
} // End of main
} // End of class
BFS
import java.util.*;
import java.io.*;
public class Main {
static Queue<Long> que = new LinkedList<>();
static long A, B;
static int count = 1;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
A = Long.parseLong(st.nextToken());
B = Long.parseLong(st.nextToken());
BFS();
System.out.println(count);
}
static void BFS() {
que.offer(B);
while( !que.isEmpty() ) {
long num = que.poll();
String str = Long.toString(num);
if(num == A) {
return;
}
else if(num < A) {
count = -1;
return;
}
if(num % 2 == 0) {
num /= 2;
que.offer(num);
count ++;
}
else if(str.charAt(str.length() -1) == '1') {
num = Long.parseLong( str.substring(0, str.length() - 1) );
que.offer(num);
count ++;
}
else {
count = -1;
return;
}
}
} // End of BFS
} // End of class
Reference
この問題について([Java]伯俊16953号[A→B]Java), 我々は、より多くの情報をここで見つけました
https://velog.io/@lifeisbeautiful/Java-백준-2606번-바이러스-자바-i3nvxuzy
テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol
しゅつりょく
AをBに変換するために必要な演算の最大値に1を加算して出力します.作成できない場合は、-1を出力します.
入力例1 2 162
2 → 4 → 8 → 81 → 1624 42
100 40021
100 → 200 → 2001 → 4002 → 40021
サンプル出力1 5
-1
5
考える
DFS/BFSとGreedyアルゴリズムタイプの問題.
条件さえ理解すれば、問題は十分に解決できる.
これらの条件は問題で明確に説明されている.
AをBにする.
一番後ろに1を付けたり、2を掛けてBにしたりします.
アクション
私は逆に解いたのです
A->Bに行くのは問題ですが、通常迷路を解く場合、始点から終点までは難しく、終点から始点までは簡単です.
このような問題もB->Aとは逆の方が解決しやすい
したがって、BとAが異なる場合は、繰り返し続けます.
脱出条件がA=Bであれば自動脱出であり、例えばBより大きい場合はAである.
すなわち、BはAを超える.
この場合はもちろんAとBが違うのでcount = -1でいいです
各条件.
2 1624 42100 40021サンプル出力1 5
-1
5
考える
DFS/BFSとGreedyアルゴリズムタイプの問題.
条件さえ理解すれば、問題は十分に解決できる.
これらの条件は問題で明確に説明されている.
AをBにする.
一番後ろに1を付けたり、2を掛けてBにしたりします.
アクション
私は逆に解いたのです
A->Bに行くのは問題ですが、通常迷路を解く場合、始点から終点までは難しく、終点から始点までは簡単です.
このような問題もB->Aとは逆の方が解決しやすい
したがって、BとAが異なる場合は、繰り返し続けます.
脱出条件がA=Bであれば自動脱出であり、例えばBより大きい場合はAである.
すなわち、BはAを超える.
この場合はもちろんAとBが違うのでcount = -1でいいです
各条件.
5-15DFS/BFSとGreedyアルゴリズムタイプの問題.
条件さえ理解すれば、問題は十分に解決できる.
これらの条件は問題で明確に説明されている.
AをBにする.
一番後ろに1を付けたり、2を掛けてBにしたりします.
アクション
私は逆に解いたのです
A->Bに行くのは問題ですが、通常迷路を解く場合、始点から終点までは難しく、終点から始点までは簡単です.
このような問題もB->Aとは逆の方が解決しやすい
したがって、
BとAが異なる場合は、繰り返し続けます.脱出条件が
A=Bであれば自動脱出であり、例えばBより大きい場合はAである.すなわち、
BはAを超える.この場合はもちろん
AとBが違うのでcount = -1でいいです各条件.
Bが偶数であれば2に分けられる.一番後ろの数字が1の場合、1を削除します.
Bが奇数であれば、それを2に分けることはできないので、そのままcount=-1で中断すればよい.脱出条件をGreedyアルゴリズムで使用する条件にすればよい.
TMI
これはDFS/BFSの問題ですが、なぜいつも違う方法で解決しているのでしょうか.
大丈夫ですか.
コード#コード#
Greedy
import java.util.*;
import java.io.*;
public class Main {
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
long A = Long.parseLong(st.nextToken());
long B = Long.parseLong(st.nextToken());
int count = 1;
while(B != A) {
String str = Long.toString(B);
if(B % 2 == 0) {
B /= 2;
}
else if(str.charAt(str.length() -1) == '1') {
B = Long.parseLong( str.substring(0, str.length() - 1) );
}
else {
count = -1;
break;
}
if(B < A) {
count = -1;
break;
}
count ++;
}
System.out.println(count);
} // End of main
} // End of class
BFS
import java.util.*;
import java.io.*;
public class Main {
static Queue<Long> que = new LinkedList<>();
static long A, B;
static int count = 1;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
A = Long.parseLong(st.nextToken());
B = Long.parseLong(st.nextToken());
BFS();
System.out.println(count);
}
static void BFS() {
que.offer(B);
while( !que.isEmpty() ) {
long num = que.poll();
String str = Long.toString(num);
if(num == A) {
return;
}
else if(num < A) {
count = -1;
return;
}
if(num % 2 == 0) {
num /= 2;
que.offer(num);
count ++;
}
else if(str.charAt(str.length() -1) == '1') {
num = Long.parseLong( str.substring(0, str.length() - 1) );
que.offer(num);
count ++;
}
else {
count = -1;
return;
}
}
} // End of BFS
} // End of class
import java.util.*;
import java.io.*;
public class Main {
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
long A = Long.parseLong(st.nextToken());
long B = Long.parseLong(st.nextToken());
int count = 1;
while(B != A) {
String str = Long.toString(B);
if(B % 2 == 0) {
B /= 2;
}
else if(str.charAt(str.length() -1) == '1') {
B = Long.parseLong( str.substring(0, str.length() - 1) );
}
else {
count = -1;
break;
}
if(B < A) {
count = -1;
break;
}
count ++;
}
System.out.println(count);
} // End of main
} // End of class
import java.util.*;
import java.io.*;
public class Main {
static Queue<Long> que = new LinkedList<>();
static long A, B;
static int count = 1;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
A = Long.parseLong(st.nextToken());
B = Long.parseLong(st.nextToken());
BFS();
System.out.println(count);
}
static void BFS() {
que.offer(B);
while( !que.isEmpty() ) {
long num = que.poll();
String str = Long.toString(num);
if(num == A) {
return;
}
else if(num < A) {
count = -1;
return;
}
if(num % 2 == 0) {
num /= 2;
que.offer(num);
count ++;
}
else if(str.charAt(str.length() -1) == '1') {
num = Long.parseLong( str.substring(0, str.length() - 1) );
que.offer(num);
count ++;
}
else {
count = -1;
return;
}
}
} // End of BFS
} // End of class
Reference
この問題について([Java]伯俊16953号[A→B]Java), 我々は、より多くの情報をここで見つけました https://velog.io/@lifeisbeautiful/Java-백준-2606번-바이러스-자바-i3nvxuzyテキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol