Reversion Count

點擊打開鏈接

Description:

There is a positive integer X, X's reversion count is Y. For example, X=123, Y=321; X=1234, Y=4321. Z=(X-Y)/9,?Judge if Z is made up of only one number(0,1,2...9), like Z=11,Z=111,Z=222,don't consider '+'and '-'.

Input:

Input contains of several test cases. Each test case only contains of a number X, L is the length of X. ( 2 <= L < 100)

Output:

Output “YES”or “NO”.

樣例輸入

10 13

樣例輸出

YES YES

題目來源

2018 ACM-ICPC 中國大學生程序設計競賽線上賽

解法一：

首先 一個數n與他反序數的差的絕對值，一定是9的倍數。證明如下：

設四位數 ABCD 他的反序數是DBCA

ABCD-DCBA=(1000*A+100*B+10*C+D)-(1000*D+100*C+10*B+A)

=(1000-1)*A+(100-10)*B-(100-10)*C-(1000-1)*D

=999*A+90*B-90*C-999*D

=(111*A+10*B-10*C-111*D)*9

再設五位數 ABCDE 他的反序數是 EDCBA

ABCDE-EDCBA=(10000*A+1000*B+100*C+10*D+E)-(10000*E+1000*D+100*C+10*B+A)

=9999*A+990*B+0*C-990*D-9999*E

=(1111*A+110*B-110*D-1111*E)*9

對于任一數都可以按此方法證明。

現在我們可以觀察到 要想使最后結果全由同一個數字組成就取決于 除第一位與最后一位 剩余所有對稱位置的數的值是否相等，若相等則一定是1，11，111，1111...的倍數，不等則一定不是。

如四位數ABCD， 111*A-111*D的結果一定是111的倍數，要使最后結果也是1,11,111,1111...的倍數那么10*B-10*C=10*(B-C)的結果一定要是0(你說B-C的結果可能是11的倍數（除0）？？？)

五位數 ABCDE， 1111*A-1111*E的結果一定是1111的倍數，注意觀察到 凡是有奇數位的數最中間的那個數最后一定被消掉了，對于ABCDE來說就是C最后被消掉了，所以最后一定要(110*B-110*D)=(B-D)*110的值為0

另外1到3位數可以直接輸出YES，因為他們的結果都是1位數

打表找規律代碼

#include<bits/stdc++.h> using namespace std; int rev(int x){int t = 0;int value = 0;while (x / 10){value = 10 * value + x % 10;x /= 10;}return value*10 + x; } int main() {int x,y,z;for(x=0;x<100000;x++){y=rev(x);z=(x-y)/9;printf("%d ",x);z=abs(z);if(z<90)printf("YES\n");else{set<int> s;s.clear();while(z){s.insert(z%10);z/=10;}if(s.size()==1)printf("YES\n");else printf("NO\n");}}return 0; } AC代碼
#include<stdio.h> #include<string.h>char str[110];int main() {while(~scanf("%s",str)){int l=strlen(str);if(l<=3){printf("YES\n");continue;}int flag=1;for(int i=1;i<=l/2-1;i++){if(str[i]!=str[l-1-i]) flag=0;}if(flag) printf("YES\n");else printf("NO\n");}return 0; } 解法二： 直接采用大數相加減然后模擬除法

JAVA

import java.math.BigInteger; import java.util.Scanner; import java.io.*; public class Main { public static void main(String args[]) { Scanner cin = new Scanner(System.in); while(cin.hasNext()) { BigInteger x,y,z,xx; x=cin.nextBigInteger(); xx=x; y=BigInteger.ZERO; z=BigInteger.ZERO; BigInteger n,k; n=BigInteger.ZERO; k=BigInteger.ZERO; while(x.compareTo(BigInteger.valueOf(0))!=0) { n=x.mod(BigInteger.valueOf(10)); y=y.multiply(BigInteger.valueOf(10)); y=y.add(n); x=x.divide(BigInteger.valueOf(10)); } z=xx.subtract(y); z=z.abs(); z=z.divide(BigInteger.valueOf(9)); n=z.mod(BigInteger.valueOf(10)); z=z.divide(BigInteger.valueOf(10)); k=n; // System.out.println(n); // System.out.println(k); int f=1; while(z.compareTo(BigInteger.valueOf(0))!=0) { n=z.mod(BigInteger.valueOf(10)); if(k.compareTo(n)!=0) { f=0; break; } z=z.divide(BigInteger.valueOf(10)); } if(f==1)System.out.println("YES"); else System.out.println("NO"); } } } C++

總結

以上是生活随笔為你收集整理的计蒜客 Reversion Count的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。