結果
問題 | No.362 門松ナンバー |
ユーザー |
![]() |
提出日時 | 2019-06-29 19:43:46 |
言語 | Java (openjdk 23) |
結果 |
WA
|
実行時間 | - |
コード長 | 5,065 bytes |
コンパイル時間 | 2,320 ms |
コンパイル使用メモリ | 78,924 KB |
実行使用メモリ | 67,544 KB |
最終ジャッジ日時 | 2024-07-02 05:39:22 |
合計ジャッジ時間 | 17,424 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 WA * 2 |
other | WA * 19 |
ソースコード
import java.util.*;public class Main {public static void main(String[] args) {Scanner sc = new Scanner(System.in);int t = sc.nextInt();long U = (long)Math.pow(10, 14);for(int i = 0; i < t; i++) {long k = sc.nextLong();long r = 0;long l = U;long ans = 0;while(l > r + 1) {long med = (r + l) / 2;long a = func(med);if(a > k) {l = med;} else {r = med;}ans = r;}System.out.println(ans);}}public static long func(long N) {String n = String.valueOf(N);int len = n.length();long[][][][][] dp = new long[len][4][10][10][2];if(len < 3) {return 0;} else {for(int i = 0; i < 10; i++) {for(int j = 0; j < 10; j++) {int p1 = 0;int p2 = 0;int p3 = 0;int d1 = Integer.parseInt(String.valueOf(n.charAt(1)));int d2 = Integer.parseInt(String.valueOf(n.charAt(2)));if(i > d1) {p1 = 1;} else if(i == d1) {if(j > d2) {p1 = 1;} else if(j == d2) {p2 = 1;} else {p3 = 1;}} else {p3 = 1;}int d0 = Integer.parseInt(String.valueOf(n.charAt(0)));if(p1 == 1) {for(int k = 0; k < d0; k++) {if(k == 0) {if(i == 0) {if(j == 0) dp[2][0][i][j][1]++;if(j != 0) dp[2][1][i][j][1]++;} else {if(i != j) dp[2][2][i][j][1]++;}} else {if(((k > i) && (i < j) && (k != j)) || ((k < i) && (i > j) && (k != j))) dp[2][3][i][j][1]++;}}}if(p2 == 1) {for(int k = 0; k <= d0; k++) {if(k == 0) {if(i == 0) {if(j == 0) dp[2][0][i][j][1]++;if(j != 0) dp[2][1][i][j][1]++;} else {if(i != j) dp[2][2][i][j][1]++;}} else if(k < d0) {if(((k > i) && (i < j) && (k != j)) || ((k < i) && (i > j) && (k != j))) dp[2][3][i][j][1]++;} else {if(((k > i) && (i < j) && (k != j)) || ((k < i) && (i > j) && (k != j))) dp[2][3][i][j][0]++;}}}if(p3 == 1) {for(int k = 0; k <= d0; k++) {if(k == 0) {if(i == 0) {if(j == 0) dp[2][0][i][j][1]++;if(j != 0) dp[2][1][i][j][1]++;} else {if(i != j) dp[2][2][i][j][1]++;}} else {if(((k > i) && (i < j) && (k != j)) || ((k < i) && (i > j) && (k != j))) dp[2][3][i][j][1]++;}}}}}for(int i = 1; i < len; i++) {int d = Integer.parseInt(String.valueOf(n.charAt(i)));// dp[i - 1][0][0][0][1]からの遷移dp[i][0][0][0][1] = dp[i - 1][0][0][0][1];for(int l = 1; l < 10; l++) {dp[i][1][0][l][1] += dp[i - 1][0][0][0][1];}// dp[i - 1][1][j][k][1]からの遷移for(int l = 1; l < 10; l++) {for(int j = 0; j < 10; j++) {for(int k = 0; k < 10; k++) {if(l != k) dp[i][2][k][l][1] += dp[i - 1][1][j][k][1];}}}// dp[i - 1][2][j][k][1]からの遷移for(int l = 1; l < 10; l++) {for(int j = 0; j < 10; j++) {for(int k = 0; k < 10; k++) {if(((j > k) && (k < l) && (l != j)) || ((j < k) && (k > l) && (l != j))) dp[i][3][k][l][1] += dp[i - 1][2][j][k][1];}}}// dp[i - 1][3][j][k][0]からの遷移for(int l = 1; l < 10; l++) {for(int j = 0; j < 10; j++) {for(int k = 0; k < 10; k++) {if(((j > k) && (k < l) && (l != j)) || ((j < k) && (k > l) && (l != j))) {if(l == d) {dp[i][3][k][l][0] += dp[i - 1][3][j][k][0];}if(l < d) {dp[i][3][k][l][1] += dp[i - 1][3][j][k][0];}}}}}// dp[i - 1][3][j][k][1]からの遷移for(int l = 1; l < 10; l++) {for(int j = 0; j < 10; j++) {for(int k = 0; k < 10; k++) {if(((j > k) && (k < l) && (l != j)) || ((j < k) && (k > l) && (l != j))) dp[i][3][k][l][1] += dp[i - 1][3][j][k][1];}}}}long ret = 0;for(int i = 0; i < 10; i++) {for(int j = 0; j < 10; j++) {for(int k = 0; k < 2; k++) {ret += dp[len - 1][3][i][j][k];}}}return ret;}}}