摘要：地址年校招全國統一模擬筆試第三場編程題集合變換次數牛牛想對一個數做若干次變換，直到這個數只剩下一位數字。牛牛可以進行的操作是將數組中的任意一個數改為這個數的兩倍。

地址：2017年校招全國統一模擬筆試(第三場)編程題集合

牛牛想對一個數做若干次變換，直到這個數只剩下一位數字。
變換的規則是：將這個數變成 所有位數上的數字的乘積。比如285經過一次變換后轉化成285=80.
問題是，要做多少次變換，使得這個數變成個位數。
輸入描述:
輸入一個整數。小于等于2,000,000,000。

輸出描述:
輸出一個整數，表示變換次數。

輸入例子1:

285

輸出例子1:

2

var readline = require("readline");
const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout
});

rl.on("line", function(line) {
  var times = 0;
  var str = line.trim();
  calc(str);
  console.log(times);
  function calc(str){
    if(str.length === 1){
      return times;
    } else {
      times++;
      calc(str.split("").map(Number).reduce(function(a, b){
        return a * b;
      }, 1) + "");
    }
  }
});

給出一個區間[a, b]，計算區間內“神奇數”的個數。
神奇數的定義：存在不同位置的兩個數位，組成一個兩位數（且不含前導0），且這個兩位數為質數。
比如：153，可以使用數字3和數字1組成13，13是質數，滿足神奇數。同樣153可以找到31和53也為質數，只要找到一個質數即滿足神奇數。
輸入描述:
輸入為兩個整數a和b，代表[a, b]區間 (1 ≤ a ≤ b ≤ 10000)。

輸出描述:
輸出為一個整數，表示區間內滿足條件的整數個數

輸入例子1:

11 20

輸出例子1:

6

var readline = require("readline");
const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout
});

rl.on("line", function(line) {
  var num = line.trim().split(" ").map(Number);
  var count = 0;
  for(var i = num[0]; i <= num[1]; i++){
    if(isMagicNum(i)){
      count++;
    }
  }
  console.log(count);

  function isMagicNum(num){
    arr = ("" + num).split("");
    var len = arr.length;
    for(var i = 0; i < arr.length; i++){
      for(var j = 0; j < arr.length; j++){
        if(i !== j && arr[j] !== "0" && arr[i] !== "0"){
          if(isPrime(parseInt(arr[i] + arr[j]))){
            return true;
          } else if(isPrime(parseInt(arr[j] + arr[i]))){
            return true;
          }
        }
      }
    }
    return false;
  }

  function isPrime(num){
    if((num & 1) === 0) return num === 2;
    var limit = Math.sqrt(num);
    for(var i = 3; i <= limit; i += 2){
      if(num % i === 0) return false;
    }
    return true;
  }

});

牛牛手里有一個字符串A，羊羊的手里有一個字符串B，B的長度大于等于A，所以牛牛想把A串變得和B串一樣長，這樣羊羊就愿意和牛牛一起玩了。
而且A的長度增加到和B串一樣長的時候，對應的每一位相等的越多，羊羊就越喜歡。比如"abc"和"abd"對應相等的位數為2，為前兩位。
牛牛可以在A的開頭或者結尾添加任意字符，使得長度和B一樣。現在問牛牛對A串添加完字符之后，不相等的位數最少有多少位？
輸入描述:
第一行為字符串A，第二行為字符串B，A的場地小于等于B的長度，B的長度小于等于50.字符均為小寫字母。

輸出描述:
輸出一個整數表示A串添加完字符之后，不相等的位數最少有多少位？

輸入例子1:

abe
cabc

輸出例子1:

1

var readline = require("readline");
const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout
});
var currLine = 0;
var strA, strB;
rl.on("line", function(line) {
  if(currLine === 0){
    strA = line.trim();
    currLine++;
  } else {
    strB = line.trim();
    if(strA.length === strB.length){
      console.log(getDiffLen(strA, strB));
    } else {
      console.log(strA.length - maxCommonSubStrLen(strA, strB))
    }
    currLine = 0, strA = strB = "";
  }

  function maxCommonSubStrLen(a, b){
    var maxLen = 0, len = 0;
    var lenA = a.length, lenB = b.length;
    var temp;
    for(var i = 0; i < lenB - lenA + 1; i++){
      temp = b.slice(i, i + lenA);
      len = getCommonLen(a, temp);
      maxLen = len < maxLen ? maxLen : len;
    }
    return maxLen;
  }
  function getDiffLen(a, b){
    if(a.length !== b.length) throw new Error("Two parameters in "getDiffLen" should be same length.");
    var arrA = a.split("");
    var arrB = b.split("");
    var num = 0;
    arrA.forEach(function(item, index){
      if(item !== arrB[index]){
        num++;
      }
    });
    return num;
  }
  function getCommonLen(a, b){
    if(a.length !== b.length) throw new Error("Two parameters in "getDiffLen" should be same length.");
    return a.length - getDiffLen(a, b);
  }
});

牛牛有一個數組，里面的數可能不相等，現在他想把數組變為：所有的數都相等。問是否可行。
牛牛可以進行的操作是：將數組中的任意一個數改為這個數的兩倍。
這個操作的使用次數不限，也可以不使用，并且可以對同一個位置使用多次。

輸入描述:
輸入一個正整數N (N <= 50)
接下來一行輸入N個正整數，每個數均小于等于1e9.

輸出描述:
假如經過若干次操作可以使得N個數都相等，那么輸出"YES", 否則輸出"NO"

輸入例子1:

2
1 2

輸出例子1:

YES

var readline = require("readline");
const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout
});
var currLine = 0;
var len, nums;
rl.on("line", function(line) {
  if(currLine === 0){
    len = parseInt(line);
    currLine++;
  } else {
    nums = line.trim().split(" ").map(Number);
    console.log(yesorno(nums));
    len = currLine = 0, nums = null;

    function yesorno(arr){
      var flag = null, temp;
      for(var i = 0; i < len; i++){
        temp = nums[i];
        while((temp & 1) === 0){
          temp /= 2;
        }
        if(flag){
          if(temp === flag) {
            continue;
          } else {
            return "NO";
          }
        } else {
          flag = temp;
        }
      }
      return "YES"
    }
  }
});

牛牛定義排序子序列為一個數組中一段連續的子序列,并且這段子序列是非遞增或者非遞減排序的。牛牛有一個長度為n的整數數組A,他現在有一個任務是把數組A分為若干段排序子序列,牛牛想知道他最少可以把這個數組分為幾段排序子序列.
如樣例所示,牛牛可以把數組A劃分為[1,2,3]和[2,2,1]兩個排序子序列,至少需要劃分為2個排序子序列,所以輸出2

輸入描述:
輸入的第一行為一個正整數n(1 ≤ n ≤ 10^5)

第二行包括n個整數A_i(1 ≤ A_i ≤ 10^9),表示數組A的每個數字。

輸出描述:
輸出一個整數表示牛牛可以將A最少劃分為多少段排序子序列

輸入例子1:

6
1 2 3 2 2 1

輸出例子1:

2

var readline = require("readline");
const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout
});
var currLine = 0;
var len, nums;
rl.on("line", function(line) {
  if(currLine === 0){
    len = parseInt(line);
    currLine++;
  } else {
    nums = line.trim().split(" ").map(Number);
    var count = 1;
    var isAsc = null;
    for(var i = 1, j = 0; i < len; i++){
      if(nums[i] < nums[i - 1]){
        if(isAsc === null) isAsc = true;
        else if(!isAsc) {
          count++;
          isAsc = null;
        }
      } else if(nums[i] > nums[i - 1]){
        if(isAsc === null) isAsc = false;
        else if(isAsc){
          count++;
          isAsc = null;
        }
      }
    }
    console.log(count);
    len = currLine = 0, nums = null;
  }
});

牛牛舉辦了一次編程比賽,參加比賽的有3*n個選手,每個選手都有一個水平值a_i.現在要將這些選手進行組隊,一共組成n個隊伍,即每個隊伍3人.牛牛發現隊伍的水平值等于該隊伍隊員中第二高水平值。
例如:
一個隊伍三個隊員的水平值分別是3,3,3.那么隊伍的水平值是3
一個隊伍三個隊員的水平值分別是3,2,3.那么隊伍的水平值是3
一個隊伍三個隊員的水平值分別是1,5,2.那么隊伍的水平值是2
為了讓比賽更有看點,牛牛想安排隊伍使所有隊伍的水平值總和最大。
如樣例所示:
如果牛牛把6個隊員劃分到兩個隊伍
如果方案為:
team1:{1,2,5}, team2:{5,5,8}, 這時候水平值總和為7.
而如果方案為:
team1:{2,5,8}, team2:{1,5,5}, 這時候水平值總和為10.
沒有比總和為10更大的方案,所以輸出10.

輸入描述:
輸入的第一行為一個正整數n(1 ≤ n ≤ 10^5)
第二行包括3*n個整數a_i(1 ≤ a_i ≤ 10^9),表示每個參賽選手的水平值.

輸出描述:
輸出一個整數表示所有隊伍的水平值總和最大值.

輸入例子1:

2
5 2 8 5 1 5

輸出例子1:

10

var readline = require("readline");
const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout
});
var currLine = 0;
var group, nums;
rl.on("line", function(line) {
  if(currLine === 0){
    group = parseInt(line);
    currLine++;
  } else {
    nums = line.trim().split(" ").map(Number).sort(function(a, b){
      return b - a;
    });
    var len = nums.length;
    var ans = 0;
    for(var i = 1; i < len - group; i += 2){
      ans += nums[i];
    }
    console.log(ans);
    group = currLine = 0, nums = null;
  }
});

牛牛現在有一個n個數組成的數列,牛牛現在想取一個連續的子序列,并且這個子序列還必須得滿足:最多只改變一個數,就可以使得這個連續的子序列是一個嚴格上升的子序列,牛牛想知道這個連續子序列最長的長度是多少。
輸入描述:
輸入包括兩行,第一行包括一個整數n(1 ≤ n ≤ 10^5),即數列的長度;
第二行n個整數a_i, 表示數列中的每個數(1 ≤ a_i ≤ 10^9),以空格分割。

輸出描述:
輸出一個整數,表示最長的長度。

輸入例子1:

6
7 2 3 1 5 6

輸出例子1:

5

var readline = require("readline");
var quantity = 0, len = 0;
var max = 0, temp = 0, flag = 0;
const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout
});
var currLine = 0;
var len, nums;
rl.on("line", function(line) {
  if(currLine === 0){
    len = parseInt(line);
    currLine++;
  } else {
    nums = line.trim().split(" ").map(Number);
    var ans = 1;
    var pre = [0], post = [0];

    nums.shift(Infinity);
    nums.push(Infinity);
    for(var i = 1; i <= len; i++){
      pre[i] = nums[i - 1] < nums[i] ? pre[i - 1] + 1 : 1;
    }
    for(var i = len; i > 0; i--){
      post[i] = nums[i] < nums[i + 1] ? post[i+1] + 1 : 1;
    }

    for (var i = 1; i <= len; i++){
      if (nums[i + 1] - nums[i - 1] >= 2) ans = Math.max(ans, pre[i - 1] + post[i + 1] + 1);
    }
    console.log(ans);
    len = currLine = 0, nums = null;
  }
});

小牛牛是牛牛王國的將軍,為了訓練出精銳的部隊,他會對新兵進行訓練。部隊進入了n個新兵,每個新兵有一個戰斗力值和潛力值,當兩個新兵進行決斗時,總是戰斗力值高的獲勝。獲勝的新兵的戰斗力值就會變成對手的潛力值 + 自己的戰斗力值 - 對手的戰斗力值。敗者將會被淘汰。若兩者戰斗力值一樣,則會同歸于盡,雙雙被淘汰(除了考察的那個新兵之外，其他新兵之間不會發生戰斗) 。小牛牛想知道通過互相決斗之后新兵中戰斗力值+潛力值最高的一個可能達到多少,你能幫助小牛牛將軍求出來嗎?

輸入描述:
輸入包括n+1行,第一行包括一個整數n(1 ≤ n ≤ 10^5);
接下來的n行,每行兩個整數x和y(1 ≤ x,y ≤ 10^9)

輸出描述:
輸出一個整數,表示新兵中戰斗力值+潛力值最高的一個能達到多少。

示例輸入

2
1 2
2 1

示例輸出

4

var readline = require("readline");
const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout
});
var quantity = 0, len = 0;
var sum = 0, temp = 0, flag = 0;
rl.on("line", function(line) {
  if(quantity === 0){
    quantity = len = parseInt(line);
  } else {
    var input = line.trim().split(" ").map(Number);
    if(input[0] >= input[1]){
      temp = input[0] + input[1];
      flag = flag > temp ? flag : temp;
    } else {
      temp = 2 * input[0];
      flag = flag > temp ? flag : temp;
      sum += input[1] - input[0];
    }
    quantity--;
    if(quantity === 0){
      console.log(sum + flag);
    }
  }
});