Submission #5547951


Source Code Expand

Copy
import java.util.*;

public class Main {
	static int mod = 1000000007;
  static int size = 200000;
	static long[] fac = new long[size];
	static long[] finv = new long[size];
	static long[] inv = new long[size];
  static int INF = Integer.MAX_VALUE;

 	public static void main(String[] args){
		Scanner scanner = new Scanner(System.in);
		int n = scanner.nextInt();
		int m = scanner.nextInt();
		int ans = 0;
		for(int x = 1; x <= n; x++){
			for(int y = 1; y <= m; y++){
				boolean flag = false;
				int count = 0;
				int tx = x;
				int ty = y;
				while(count < 1000){
					if(tx == 0 || ty == 0){
						flag = true;
						ans++;
						break;
					}
					if(tx < ty){
						tx = rev(tx);
						ty = ty;
						if(tx < ty){
							tx = tx;
							ty = ty - tx;
						}else{
							tx = tx-ty;
							ty = ty;
						}
					}else if(tx >= ty){
						tx = tx;
						ty = rev(ty);
						if(tx < ty){
							tx = tx;
							ty = ty - tx;
						}else{
							tx = tx - ty;
							ty = ty;
						}
					}
					count++;
				}
			}
		}
		System.out.println(n*m-ans);
		//System.out.println(rev(111));
	}
	public static int rev(int x){
		//xが一桁の場合
		if(x/10 == 0){
			return x;
		}else if(x/100 == 0){
			return (x%10)*10 + x/10;
		}else{
			return x/100 + (x-x%10-(x/100)*100) + 100 * (x%10);
		}
	}
  static class Pair implements Comparable<Pair>{
    int x, y;
    Pair(int a, int b){
        x = a;
        y = b;
    }
    @Override
    public boolean equals(Object o){
        if (this == o) return true;
        if (!(o instanceof Pair)) return false;
        Pair p = (Pair) o;
        return x == p.x && y == p.y;
    }
    @Override
    public int compareTo(Pair p){
        return x == p.x ? y - p.y : x - p.x; //xで昇順にソート
        //return (x == p.x ? y - p.y : x - p.x) * -1; //xで降順にソート
        //return y == p.y ? x - p.x : y - p.y;//yで昇順にソート
        //return (y == p.y ? x - p.x : y - p.y)*-1;//yで降順にソート
    }
  }
  //繰り返し二乗法
  public static long pow(long x, long n){
    long ans = 1;
    while(n > 0){
      if((n & 1) == 1){
        ans = ans * x;
        ans %= mod;
      }
      x = x * x % mod;
      n >>= 1;
    }
    return ans;
  }

  //fac, inv, finvテーブルの初期化、これ使う場合はinitComb()で初期化必要
	public static  void initComb(){
		fac[0] = finv[0] = inv[0] = fac[1] = finv[1] = inv[1] = 1;
		for (int i = 2; i < size; ++i) {
			fac[i] = fac[i - 1] * i % mod;
			inv[i] = mod - (mod / i) * inv[(int) (mod % i)] % mod;
			finv[i] = finv[i - 1] * inv[i] % mod;
		}
	}

	//nCk % mod
	public static long comb(int n, int k){
		return fac[n] * finv[k] % mod * finv[n - k] % mod;
	}

	//n! % mod
	public static long fact(int n){
		return fac[n];
	}

	//(n!)^-1 with % mod
	public static long finv(int n){
		return finv[n];
	}

  static class UnionFind {
    int[] parent;
    public UnionFind(int size) {
      parent = new int[size];
      Arrays.fill(parent, -1);
    }
    public boolean unite(int x, int y) {
      x = root(x);
      y = root(y);
      if (x != y) {
        if (parent[y] < parent[x]) {
          int tmp = y;
          y = x;
          x = tmp;
        }
        parent[x] += parent[y];
        parent[y] = x;
        return true;
      }
      return false;
    }
    public boolean same(int x, int y) {
      return root(x) == root(y);
    }
    public int root(int x) {
      return parent[x] < 0 ? x : (parent[x] = root(parent[x]));
    }
    public int size(int x) {
      return -parent[root(x)];
    }
  }
	public static int upperBound(long[] array, long value) {
			 int low = 0;
			 int high = array.length;
			 int mid;
			 while( low < high ) {
					 mid = ((high - low) >>> 1) + low; // (high + low) / 2
					 if( array[mid] <= value ) {
							 low = mid + 1;
					 } else {
							 high = mid;
					 }
			 }
			 return low;
	 }
	 public static final int lowerBound(final long[] arr, final long value) {
    int low = 0;
    int high = arr.length;
    int mid;
    while (low < high) {
        mid = ((high - low) >>> 1) + low;    //(low + high) / 2 (オーバーフロー対策)
        if (arr[mid] < value) {
            low = mid + 1;
        } else {
            high = mid;
        }
    }
    return low;
}
  //n,mの最大公約数
  public static int gcd(int n, int m){
    if(m > n) return gcd(m,n);
    if(m == 0) return n;
    return gcd(m, n%m);
  }
}

Submission Info

Submission Time
Task D - うほょじご
User rmkt
Language Java8 (OpenJDK 1.8.0)
Score 400
Code Size 4614 Byte
Status
Exec Time 516 ms
Memory 25940 KB

Test Cases

Set Name Score / Max Score Test Cases
Sample 0 / 0 s1.txt, s2.txt, s3.txt
All 400 / 400 01.txt, 02.txt, 03.txt, 04.txt, 05.txt, 06.txt, 07.txt, 08.txt, 09.txt, 10.txt, 11.txt, 12.txt, 13.txt, 14.txt, 15.txt, 16.txt, s1.txt, s2.txt, s3.txt
Case Name Status Exec Time Memory
01.txt 516 ms 24912 KB
02.txt 104 ms 22864 KB
03.txt 342 ms 21460 KB
04.txt 104 ms 24020 KB
05.txt 104 ms 24912 KB
06.txt 95 ms 25556 KB
07.txt 93 ms 23892 KB
08.txt 508 ms 24020 KB
09.txt 113 ms 25428 KB
10.txt 443 ms 23508 KB
11.txt 516 ms 25940 KB
12.txt 98 ms 23252 KB
13.txt 109 ms 25428 KB
14.txt 204 ms 25428 KB
15.txt 96 ms 23764 KB
16.txt 266 ms 23380 KB
s1.txt 92 ms 22740 KB
s2.txt 95 ms 23892 KB
s3.txt 125 ms 25940 KB