首页 > 试题广场 >

艰难的抉择

[编程题]艰难的抉择

热度指数：2332 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

给出一个含有n个数字的序列a₁,a₂,a₃,...a_n，可以进行以下操作：

一次操作定义为对这个序列的每个数字进行以下两种改变之一：

1.a_i ÷ 2

2.a_i × 3

每一次的操作中，必须保证至少有一个数字是第1种改变；并且经过每次操作后，每一个数字都必须是整数。

牛牛得知，每进行一次操作，他就可以得到一颗西瓜糖，但是由于孱弱的数学功底，他不知道何时该对某一个数字进行第一种还是第二种改变，这使得他十分纠结，于是他找来了睿智的你，希望你帮他计算出，他最多可以得到多少颗西瓜糖。

输入描述:

第一行：一个整数n，表示序列中数字的个数，1 <= n <= 10000；
第二行：n个数字，每个数字a_i满足1 <= a_i <= 10⁹。

输出描述:

一个整数，表示最多可以得到的西瓜糖的颗数。

示例1

输入

2
1 4

输出

示例2

输入

4
3 3 5 9

输出

算法知识视频讲解

Demon=)

//所有数字的2的因子数量之和
import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        int x[] = new int[n];
        for (int i = 0; i < n; i++)
            x[i] = scan.nextInt();
        int count = 0;
        for(int i=0;i<n;i++) {
            while(x[i]%2==0) {
                x[i]/=2;
                count+=1;
            }
        }
        System.out.println(count);
    }
}

发表于 2018-07-26 09:00:33 回复(0)

风起莫扬

//所有偶数的2幂相加
import java.util.Scanner;
public class Main{
    public static int cnt = 0;
    
    public static void numberOfSugar(int[] a, int b){
        for(int i = 0; i < b; i++){
            while(a[i]%2 == 0){
                a[i] = a[i] / 2;
                cnt++;
            }
        }
    }
    public static void main(String[] args){
        Scanner input = new Scanner(System.in);
        
        String d = input.nextLine();//读取输入转换时间长
        String s = input.nextLine();      int c = Integer.parseInt(d);
        String[] arr = s.split(" ");
        int[] num = new int[c];
        
        for(int i = 0; i < c; i++){
            num[i] = Integer.parseInt(arr[i]);
        }
        
        numberOfSugar(num, c);
        System.out.println(cnt);
    }
}

编辑于 2018-08-10 21:48:45 回复(0)

WAK

每次都必须有一个数除2，乘3不影响被2整除的次数，所以求出所有的数能被2整除的次数，加起来就是结果。

   #include<bits/stdc++.h>
 using namespace std;
 int chu(int x){
     int num = 0;
     while(x>=1&&x%2==0){
         x = x/2;
         num++;
     }
     return num;
 }
 int main(){
     int n;
     while(cin>>n){
         int num = 0;
         for(int i = 0;i<n;i++){
             int x;
             cin>>x;
             num+=chu(x);
         }
         cout<<num<<endl;
     }
     return 0;
 }
 
  

编辑于 2018-07-20 20:02:01 回复(0)

牛客300425056号

#include <stdio.h> int main() { int i,n,a,sum=0; scanf("%d",&n); for (i=1;i<=n;i++) { scanf("%d",&a); while (a%2==0) { a/=2; sum++; } } printf("%d",sum); return 0; }</stdio.h>

发表于 2018-07-27 17:18:21 回复(0)

cqu后起之秀


	#include<iostream>



	using namespacestd;



	int main(){



	    int n,m,cnt=0;



	    cin>>n;



	    while(cin>>m){



	        while(m%2==0){



	            cnt++;



	            m/=2;



	        }



	    }



	    cout<<cnt<<endl;



	}

发表于 2018-08-30 22:21:56 回复(3)

zhzhong6

package main

import "fmt"

func main() {
	var n, i, r int
	fmt.Scan(&n)

	for n > 0 {
		n--
		fmt.Scan(&i)
		for i%2==0{
			r++
			i=i/2
		}
	}
  fmt.Println(r)
}

发表于 2020-09-10 17:24:33 回复(0)

88_Rising

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

/*
*
* 给出一个含有n个数字的序列a1,a2,a3,...an，可以进行以下操作：
一次操作定义为对这个序列的每个数字进行以下两种改变之一：
1.ai ÷ 2
2.ai × 3
每一次的操作中，必须保证至少有一个数字是第1种改变；并且经过每次操作后，每一个数字都必须是整数。
牛牛得知，每进行一次操作，他就可以得到一颗西瓜糖，但是由于孱弱的数学功底，
* 他不知道何时该对某一个数字进行第一种还是第二种改变，这使得他十分纠结，于是他找来了睿智的你，希望你帮他计算出，他最多可以得到多少颗西瓜糖。
* */
public class Chosen {
    public static void main(String[] args) throws IOException {

        BufferedReader bufferedReader=new BufferedReader(new InputStreamReader(System.in));
        int size=Integer.parseInt(bufferedReader.readLine());
        String[] nums=bufferedReader.readLine().split(" ");
        int[] array=new int[size];
        int count=0;
        for(int i=0;i<size;i++){
            array[i]=Integer.parseInt(nums[i]);
            while(array[i]%2==0){
                count++;
                array[i]/=2;
            }
        }
        System.out.println(count);
    }
}

发表于 2020-08-17 11:33:02 回复(0)

YoungAndTao

n=int(input())

s=input()

x=list(map(int,s.split()))

i=0

count=0

while(i<n):

if(x[i]%2==0):

count+=1

x[i]/=2

else:

i+=1

print(count)

发表于 2019-02-20 18:34:05 回复(0)

‘黎落冰释

include<stdio.h>

int main(){
int i[10000];
int n,s,count=0,sum=0,sun;
int c=0;
scanf("%d",&n);
for( ;count<n;count++)
scanf("%d", &i[count]);
for( ;c<n;c++){
if(i[c]%2==0){
s=0;
sun=i[c];
while(!s){
s=sun%2;
if(sun%2==0){
s=0;
sum++;
sun=sun/2;
}
else
s=1;
}
}
}
printf("%d",sum);
return 0;

}

发表于 2018-09-23 12:50:28 回复(0)

lamia

所有偶数的二次幂相加

#include <bits/stdc++.h>
// #define TEST_INSTANCE
#ifdef TEST_INSTANCE
#include <gtest/gtest.h>
static int fast = []() {std::ios_base::sync_with_stdio(0); std::cin.tie(0); std::cout.tie(0); return 0; }();
#endif


class Solution {
public:
  Solution(void): c_(0) {}
  void add(size_t x) {
    while(this->isEven(x)) {}
  }

  bool isEven(size_t &n) {
    if(1 == n % 2) return false;
    n >>= 1; ++this->c_; return true;
  }

  size_t go(void) {
    #ifndef TEST_INSTANCE
    std::cout << this->c_ << "\n";
    #endif
    return this->c_;
  }
protected:
  size_t c_;
}; 

/****************** TEST ******************/
#ifdef TEST_INSTANCE
TEST(SolutionTest, test1) {
  auto p = new Solution;
  size_t N = 2;
  std::vector<size_t> xs = {
    1, 4, 
  };
  size_t out = 2;
  for(auto &x: xs) p->add(x);
  EXPECT_EQ(p->go(), out);
  delete p;
}

TEST(SolutionTest, test2) {
  auto p = new Solution;
  size_t N = 4;
  std::vector<size_t> xs = {
    3, 3, 5, 9, 
  };
  size_t out = 0;
  for(auto &x: xs) p->add(x);
  EXPECT_EQ(p->go(), out);
  delete p;
}

TEST(SolutionTest, test3) {
  auto p = new Solution;
  size_t N = 4;
  std::vector<size_t> xs = {
    5, 2, 16, 3, 
  };
  size_t out = 5;
  for(auto &x: xs) p->add(x);
  EXPECT_EQ(p->go(), out);
  delete p;
}
#endif
/****************** TEST ******************/

int main(int argc, char **argv) {
#ifdef TEST_INSTANCE
  testing::InitGoogleTest(&argc, argv);
  return RUN_ALL_TESTS();;
#else
  size_t N, x;
  auto p = new Solution;
  while(std::cin >> N) {
    for(size_t i = 0; i < N; ++i) {std::cin >> x; p->add(x);}
    p->go();
  }
#endif
}

编辑于 2018-08-30 15:24:10 回复(4)

skyscrapering

直接考虑偶数的个数以及2的幂

   importsys  
   n =sys.stdin.readline().strip('\n')  
   t =sys.stdin.readline().strip('\n')  
   t =list(map(int,t.split()))  
   cnt =0  
   foritem int:  
       ifitem %2==1:  
           continue  
       whileitem %2==0:  
           cnt +=1  
           item =int( item /2)  
   print(cnt)  

发表于 2018-08-25 16:44:25 回复(0)

jachy


	#include<bits/stdc++.h>



	using namespace std;



	 



	int main(){



	    int n;



	    cin >> n;



	    int arr[n];



	    int count = 0;



	    for(int i = 0; i < n ; i++){



	        cin >> arr[i];



	        while(arr[i] % 2 == 0){



	            arr[i] /= 2;



	            count++;



	        }



	    }



	    cout << count << endl;



	    return 0;



	}

发表于 2018-08-07 11:31:49 回复(0)

蓝色明月


	n =input()



	s =raw_input().split(' ')



	r =0



	fori inrange(n):



	    s[i] =int(s[i])



	    whiles[i] %2==0:



	        s[i] =s[i] /2



	        r +=1



	printr

发表于 2018-08-03 12:28:31 回复(0)

Python

kimihi

from math import log
 
listNum = input()
listInfo = input().split()
list2 = []
for i in listInfo:
    i = int(i)
    if i%2 == 0:
        list2.append(i)
if len(list2) == 0:
    print("0")
else:
    a = 0
    for j in list2:
        result = j & (j-1)
        if result != 0:
            while True:
                if j%2 == 0:
                    a=a+1
                    j=j//2 
                else:
                    break
        else:
            c = log(j,2)          
            a = a + int(c)
    print(a)

编辑于 2018-07-30 20:29:45 回复(0)

mylu

第一次做，感觉想不出来，好沮丧，还得多练，见多视广。

发表于 2018-07-30 20:01:14 回复(0)

吾生有你

import java.util.*;
public class Main{
    public static void main(String[] args){
        Scanner input=new Scanner(System.in);
        while(input.hasNext()){
            int n=input.nextInt();
            int[] a=new int[n];
            int count=0;
            for(int i=0; i<n; i++){
                a[i]=input.nextInt();
                if(a[i]%2==0){
                    while(a[i]%2==0){
                        a[i]/=2;
                        count++;
                    }
                }
            }
            System.out.println(count);
        }
    }
}

发表于 2018-07-26 11:13:30 回复(0)

伊涅斯塔

  所有2的因子数量和就是答案 
  
 
  #include<iostream> 
  #include<string.h> 
  #include<stdio.h> 
    
  usingnamespacestd; 
    
  intGetTimes(inta) { 
      ints = 0; 
      while(a % 2 == 0) { 
          a /= 2; 
          s++; 
      } 
      returns; 
  } 
    
  intmain() 
  { 
      intT; 
      cin >> T; 
      int*arr = newint[T]; 
    
      intsum = 0; 
      for(inti = 0; i < T; i++) { 
          cin >> arr[i]; 
          sum += GetTimes(arr[i]); 
      } 
    
      cout << sum << endl; 
    
      delete[] arr; 
      return0; 
  } 

发表于 2018-07-23 16:00:15 回复(2)

Roee

将数列中所有数字2的幂次加起来就是答案。

#include<iostream>
using namespace std;
int last(int x){
    int z = 0;
    while(x%2==0){
        x/=2;
        z++;
    }
    return z;
}
int main(){
    ios::sync_with_stdio(false);
    int a, n, r = 0;
    cin >> n;
    for(int i=0;i<n;i++){
        cin >> a;
        r += last(a);
    }
    cout<<r<<endl;
}

发表于 2018-07-21 23:43:08 回复(0)

wbq9224

python版 ac代码：

import sys

n = int(sys.stdin.readline().strip())
nums = list(map(int, sys.stdin.readline().strip().split()))
count = 0
for i in range(len(nums)):
    temp = nums[i]
    while temp & 1 == 0:
        temp = temp >> 1
        count += 1
print(count)

发表于 2018-07-21 10:02:50 回复(0)

提交观点

问题信息

C++工程师 golang工程师 iOS工程师安卓工程师运维工程师前端工程师算法工程师测试工程师 PHP工程师贪心模拟 2018 数学 Java工程师牛客

来自：【2018】牛客模考（...

上传者：小小

难度：

19条回答 76收藏 6443浏览

通过挑战的用户

Mario20...

2022-02-15 13:21:03
Fallen丶...

2021-09-16 20:07:54
C.C.K.

2021-07-06 10:59:10
牛客29525...

2021-06-28 10:47:56
Philche...

2021-06-22 19:16:58