冬天到了，小伙伴们都懒得出去吃饭了，纷纷打电话叫起了外卖。送外卖的小哥想找出一条最短的路径，小区门口进来，送完外卖又回到小区门口。
整个小区是一个由m*n个边长为1的正方形组成的矩形，各幢公寓楼分布于正方型的顶点上，小区门口位于左上角。每幢楼与相邻的八个方向的楼之间都有道路。
下图为m=2，n=3的小区地图，并且外卖小哥要经过的最短路径为6。
[编程题]送外卖
#include<stdio.h>
#include<string.h>
#define N 100
int main()
{
char m[N],n[N];
while(scanf("%s %s",m,n)!=-1)
{
int i,j,L[N];
int len1=strlen(m);
int len2=strlen(n);
memset(L,0,sizeof(L));
for(i=0;i<len1;i++)
for(j=0;j<len2;j++)
L[i+j]+=(m[len1-i-1]-'0')*(n[len2-j-1]-'0');//乘运算
for(i=0;i<len1+len2;i++)
if(L[i]>=10)
{
L[i+1]+=L[i]/10;//进位
L[i]%=10;//取余
}
while(L[i]==0)//去零
i--;
while(i>=0)
printf("%d",L[i--]);
if(m[len1-1]%2==0||n[len2-1]%2==0)
printf(".00\n");
else
printf(".41\n");
}
return 0;
}
编辑于 2020-04-13 21:21:17
回复(0)
思路：
注意点：
- m或n为偶数时，f(m,n)=m*n;
- m和n都为奇数时，f(m,n)=m*n-1+根号2;
代码：
import java.util.*;
import java.text.DecimalFormat;
import java.math.*;
public class Main {
public static void main(String[] args) {
Scanner cin = new Scanner(System.in);
while (cin.hasNext()) {
BigDecimal m = cin.nextBigDecimal();
BigDecimal n = cin.nextBigDecimal();
System.out.println(songwaimai(m, n));
}
}
public static String songwaimai(BigDecimal m, BigDecimal n) {
BigDecimal row = m;
BigDecimal line = n;
BigDecimal count = null;
if (row.divideAndRemainder(new BigDecimal("2"))[1].compareTo(BigDecimal.ZERO) == 0
|| line.divideAndRemainder(new BigDecimal("2"))[1].compareTo(BigDecimal.ZERO) == 0) {
count = row.multiply(line);
} else {
count = row.multiply(line).add(new BigDecimal("0.41"));
}
DecimalFormat dcmFmt = new DecimalFormat("0.00");
return dcmFmt.format(count);
}
}
注意点：
- 输入：多组数据
- 精度：m (2≤n≤2^128) 和n (2≤r≤2^128)
编辑于 2015-04-03 17:24:53
回复(0)
最优路径证明见一楼
由于输入整数m (2≤n≤2^128^) 和n (2≤r≤2^128^)范围非常大，因此我们需要手动写一个大数乘法器。没办法，C艹库少。。。
我采用的是万进制，逢万进一。
输入的是数值字符串，比如"12345601230009"，然后转换成int数组intsNum[4, 9, 123, 3456, 12],intsNum[0]表示数组的长度，intsNum[1]=9表示数值字符串中的第一段“0999”，intsNum[2]=123，表示数组中的第二段0123，intsNum[3]=3456，表示数组中的第三段3456，intsNum[4]=12，表示数组中的第四段12
#include <iostream>
(720)#include <string.h>
#include <string>
using namespace std;
//将两个数组相乘，并且结果存放子啊num3
//数组示例[4，123，0，1234，9]，4表示长度，真正表示是的值为 ‘9 1234 0000 0123’
void bigNumMutli(int* num1, int* num2, int* num3, int maxLen) {
memset(num3, 0, maxLen);
//1、对num1、num2进行相乘
for (int i = 1; i <= num2[0]; ++i) {
for (int j = 1; j <= num1[0]; ++j) {
//num1的第j位 与 num2的第i位相乘，应该放在num3的 第i + j - 1位上，画一个多位数相乘算术式可知
num3[i + j - 1] += num1[i] * num2[j];
if (num3[i + j - 1] > 9999) {
//num3[i + j - 1] 逢万进位
num3[i + j] += num3[i + j - 1] / 10000;
num3[i + j - 1] %= 10000;
}
}
}
//2、检查num3是否有进位，注意长度为m、n位的两个数相乘结果长度不会超过 m + n
//初始化num3的长度为 num1、num2之和
num3[0] = num1[0] + num2[0];
for (int i = 1; i < num3[0]; ++i) {
if (num3[i] > 10000) {
num3[i + 1] += num3[i] / 10000;
num3[i] %= 10000;
}
}
//如果最高位为0，说明结果小于
if (num3[num3[0]] == 0) {
num3[0] -= 1;
}
}
//将数字字符串转成int数组，比如"12304560001",转换结果为[3, 1, 456, 123]
void strToInts(string num, int* numInts, int maxLen) {
memset(numInts, 0, maxLen);
for (int i = (int)num.size() - 1; i >= 0; ) {
int tempNum = 0, j = 0, weight = 1;
//取出四位转成整形
while (i >= 0 && j++ < 4) {
tempNum += (num[i--] - '0') * weight;
weight *= 10;
}
numInts[++numInts[0]] = tempNum;
}
}
//将int数组转换会字符串类型
string intsToStr(int* numInts) {
if (numInts[0] == 0) {
return "0";
}
//最高位不需要补零
string resStr = to_string(numInts[numInts[0]]);
//注意访问顺序，是从高->低
for (int i = numInts[0] - 1; i >= 1; --i) {
string tempStr = "";
//中间不足四位需要补零
if (numInts[i] < 1000) {
tempStr += '0';
}
if (numInts[i] < 100) {
tempStr += '0';
}
if (numInts[i] < 10) {
tempStr += '0';
}
tempStr += to_string(numInts[i]);
resStr.append(tempStr);
}
return resStr;
}
string mutli(string num1, string num2) {
int intsNum1[101] = { 0 }, intsNum2[101] = { 0 }, intsSum[101] = { 0 };
strToInts(num1, intsNum1, 101);
strToInts(num2, intsNum2, 101);
bigNumMutli(intsNum1, intsNum2, intsSum, 101);
return intsToStr(intsSum);
}
int main() {
string a, b;
//scanf返回值为正确输入数据的变量个数，当一个变量都没有成功获取数据时，此时返回-1
while (cin >> a >> b) {
string tempRes = mutli(a, b);
if ((a[a.size() - 1] - '0') % 2 == 0 || (b[b.size() - 1] - '0') % 2 == 0) {
tempRes += ".00";
} else {
//注意：√2 - 1 = 0.41
tempRes += ".41";
}
cout << tempRes << endl;
}
return 0;
}
————————————————
版权声明：本文为CSDN博主「hestyle」的原创文章，遵循 CC 4.0 BY 版权协议，转载请附上原文出处链接及本声明。
原文链接：https://hestyle.blog.csdn.net/article/details/104706905
编辑于 2020-03-07 10:06:48
回复(0)
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int main()
{
char m[100], n[100];
while(~scanf("%s %s", m, n))
{
int result[100] = {0};
int len_m = strlen(m), len_n = strlen(n);
int re = 100;
int count = 0;
int loc = 99;
for(int i = len_m - 1; i >= 0; i--)
{
re--;
loc = re;
for(int j = len_n - 1; j >= 0; j--)
{
result[loc] = result[loc] + (m[i] - '0') * (n[j] - '0') + count;
count = result[loc] / 10;
result[loc] = result[loc] % 10;
loc--;
}
if(count)
result[loc] = count;
count = 0;
}
int l = 0;
while(result[l++] == 0);
for(int k = l - 1; k < 100; k++)
{
printf("%d", result[k]);
}
if((m[len_m-1] % 2 == 0) || (n[len_n-1] % 2 == 0))
printf(".00\n");
else
printf(".41\n");
}
}
编辑于 2020-03-03 21:57:10
回复(0)
根据输入长度判断应选用的数据类型，10以内选int，19以内选long,其余选BigInteger
import java.math.BigInteger;
import java.util.Scanner;
/**
* @author MemoryC
* */
public class Main {
public static void main(String[] args) {
Scanner scanner=new Scanner(System.in);
while(scanner.hasNext()) {
String ms=scanner.next();
String ns=scanner.next();
if(ms.trim().length()==0||ns.trim().length()==0){
continue;
}
if(ms.length()<10&&ns.length()<10&&(ms.length()+ns.length()<10)){
int m=Integer.parseInt(ms);
int n=Integer.parseInt(ns);
float r=m*n;
if( (m&0x01)==1&&(n&0x01)==1){
r+=0.41f;
}
System.out.printf("%.2f\n",r);
}else if(ms.length()<19&&ns.length()<19&&(ms.length()+ns.length()<19)){
long m=Long.parseLong(ms);
long n=Long.parseLong(ns);
float r=m*n;
if( (m&0x01)==1&&(n&0x01)==1){
r+=0.41f;
}
System.out.printf("%.2f\n",r);
}else{
BigInteger m=new BigInteger(ms);
BigInteger n=new BigInteger(ns);
String r=m.multiply(n).toString();
if(((m.toString().charAt(m.toString().length()-1))-'0')%2!=0&&((n.toString().charAt(n.toString().length()-1))-'0')%2!=0){
r+=".41";
}else{
r+=".00";
}
System.out.println(r);
}
}
scanner.close();
}
} 测试通过
编辑于 2019-03-09 22:49:13
回复(0)
//高精度乘法+1楼的公式
#include <stdio.h>
#include <string.h>
#include <math.h>
int main()
{ int a[40],b[40],c[80];
char s[40],ss[40];
int len ,lenn;
while(scanf("%s%s",s,ss)!=EOF)
{ len = strlen(s); lenn = strlen(ss);
memset(a,0,sizeof(a)); //清零数组
memset(b,0,sizeof(b));
for (int i = 0 ; i < len ; i++) a[len - i - 1] = s[i] - '0';//将字符串转化为数组
for (int i = 0 ; i < lenn ; i++) b[lenn - i - 1] = ss[i] - '0';
memset(c,0,sizeof(c)); //清零
for (int i = 0 ; i < len ; i++)
for (int j = 0 ; j < lenn ; j++)
c[i + j] += a[i] * b[j]; //运算（这个就有一点复杂了）
int l = len + lenn - 1; //l是结果的最高位数
for (int i = 0 ; i < l ;i++)
{ c[i + 1] += c[i] / 10; //保证每一位的数都只有一位，并进位
c[i] %= 10; }
if (c[l] > 0) l++; //保证最高位数是对的
while (c[l - 1] >= 10) {
c[l] = c[l - 1] / 10;
c[l - 1] %= 10;
l++; }
while (c[l - 1] == 0 && l > 1) l--; //while去零法
if((s[len-1]-'0')%2==0||(ss[lenn-1]-'0')%2==0)
{ for (int i = l - 1; i >= 0 ; i--) //输出结果
printf("%d",c[i]); printf(".00\n"); }
else { for (int i = l - 1; i >= 0 ; i--)
printf("%d",c[i]); printf(".41\n");
}
}
return 0;
}
编辑于 2019-03-06 10:54:38
回复(0)
try: while True: m, n = list(map(int, input().split())) if m%2 == 0 or n%2 == 0: print(str(m*n)+'.00') else: print(str(m*n)+'.41') except: pass
发表于 2018-12-01 10:11:47
回复(0)
思路：使用 vector 模拟大数乘法。 #include <iostream>
#include <iomanip>
#include <math.h>
#include <vector>
#include <string>
#include <sstream>
using namespace std;
vector<int> Multi(const vector<int> &a, const vector<int> &b)
{
vector<int> answer(a.size() + b.size());
int answerSize = answer.size();
for (int i = b.size()-1; i >= 0; i--)
{
answerSize = answer.size() - 1 - (b.size() - 1 - i);
for (int j = a.size() - 1; j >= 0; j--)
{
int temp = a[j] * b[i];
if (answer[answerSize] + temp < 10)
answer[answerSize--] += temp;
else
{
answer[answerSize-1] += (answer[answerSize] + temp) / 10;
answer[answerSize] = (answer[answerSize] + temp) % 10;
answerSize--;
}
}
}
return answer;
}
int main()
{
string m, n;
while (cin >> m >> n)
{
vector<int> a, b;
for (int i = 0; i < m.size(); i++)
{
a.push_back(m[i] - '0');
}
for (int i = 0; i < n.size(); i++)
{
b.push_back(n[i] - '0');
}
if (a[a.size() - 1] % 2 != 0 && b[b.size() - 1] % 2 != 0)
{
vector<int> temp = Multi(a, b);
bool check = (temp[0] == 0 )? true : false;
for (int i = 0; i < temp.size(); i++)
{
if (check)
{
check = false;
continue;
}
cout << temp[i];
}
cout << ".41"<< endl;
}
else
{
vector<int> temp = Multi(a, b);
bool check = (temp[0] == 0) ? true : false;
for (int i = 0; i < temp.size(); i++)
{
if (check)
{
check = false;
continue;
}
cout << temp[i];
}
cout << ".00" << endl;
}
}
system("pause");
}
发表于 2018-08-13 13:03:25
回复(0)
#include<iostream>
#include<iomanip>
using namespace std;
string add(string x, string y)
{
string ans;
int up=0, now=0, a, b;
int i=x.length()-1, j=y.length()-1;
while(i >= 0 || j >= 0)
{
if(i >= 0) a = x[i] - '0';
else a = 0;
if(j >= 0) b = y[j] - '0';
else b = 0;
now = (up + a + b) % 10;
up = (up + a + b) / 10;
ans.push_back('0' + now);
--i; --j;
}
if(up) ans.push_back('0' + up);
for(int i=0; i<ans.length()/2; i++)
{
swap(ans[i], ans[ans.length()-i-1]);
}
return ans;
}
string mul(string x, string y)
{
string ans;
ans.push_back('0');
for(int i=y.length()-1; i>=0; --i)
{
for(int j=0; j<y[i]-'0'; ++j)
{
ans = add(ans, x);
}
x.push_back('0');
}
return ans;
}
int main()
{
string m, n, ans;
while(cin >> m >> n)
{
ans.clear();
ans = mul(m, n);
if((m[m.length()-1]-'0') * (n[n.length()-1]-'0') % 2 == 0)
{
cout << ans << ".00" << endl;
}
else
{
cout << ans << ".41" << endl;
}
}
return 0;
}
#include<iomanip>
using namespace std;
string add(string x, string y)
{
string ans;
int up=0, now=0, a, b;
int i=x.length()-1, j=y.length()-1;
while(i >= 0 || j >= 0)
{
if(i >= 0) a = x[i] - '0';
else a = 0;
if(j >= 0) b = y[j] - '0';
else b = 0;
now = (up + a + b) % 10;
up = (up + a + b) / 10;
ans.push_back('0' + now);
--i; --j;
}
if(up) ans.push_back('0' + up);
for(int i=0; i<ans.length()/2; i++)
{
swap(ans[i], ans[ans.length()-i-1]);
}
return ans;
}
string mul(string x, string y)
{
string ans;
ans.push_back('0');
for(int i=y.length()-1; i>=0; --i)
{
for(int j=0; j<y[i]-'0'; ++j)
{
ans = add(ans, x);
}
x.push_back('0');
}
return ans;
}
int main()
{
string m, n, ans;
while(cin >> m >> n)
{
ans.clear();
ans = mul(m, n);
if((m[m.length()-1]-'0') * (n[n.length()-1]-'0') % 2 == 0)
{
cout << ans << ".00" << endl;
}
else
{
cout << ans << ".41" << endl;
}
}
return 0;
}
发表于 2018-06-26 15:01:38
回复(0)
#include <stdio.h>
#include <string>
#include <iostream>
using namespace std;
string sadd( string a, string b)
{
int idxa = a.length() - 1;
int idxb = b.length() - 1;
string rlt = "";
int carry = 0, rem;
while (idxa>=0 && idxb>= 0)
{
rem = (int)(a[idxa--] - '0') + (int)(b[idxb--] - '0') + carry;
carry = rem / 10;
rem %= 10;
rlt = (char)(rem + '0') + rlt;
}
while (idxa>=0)
{
rem = (int)(a[idxa--] - '0') + carry;
carry = rem / 10;
rem %= 10;
rlt = (char)(rem + '0') + rlt;
}
while (idxb>=0)
{
rem = (int)(b[idxb--] - '0') + carry;
carry = rem / 10;
rem %= 10;
rlt = (char)(rem + '0') + rlt;
}
if (carry)
{
rlt = (char)(carry + '0') + rlt;
}
return rlt;
}
string splu(string a, string b)
{
int idxa = a.length() - 1;
int idxa0 = a.length();
int idxb0 = b.length();
string rlt;
int i = 0;
while (idxa0--)
{
int j = i;
int idxb = b.length() - 1;
int rem,carry = 0;
string rlt1 = "";
while (idxb >= 0)
{
rem = (int)(a[idxa0] - '0') * (int)(b[idxb--] - '0') + carry;
carry = rem / 10;
rem %= 10;
rlt1 = (char)(rem + '0') + rlt1;
}
if (carry > 0)
{
rlt1 = (char)(carry + '0') + rlt1;
}
while (j--)
{
string temp = "0";
rlt1 = rlt1 + temp;
}
i++;
rlt = sadd(rlt,rlt1);
}
return rlt;
}
int main()
{
string a,b,c;
int idxa,idxb;
while (cin>> a >> b)
{
c = splu(a,b);
idxa = a.length() - 1;
idxb = b.length() - 1;
if (a[idxa] % 2 != 0 && b[idxb] % 2 != 0)
{
std::cout<<c+".41"<<std::endl;
}
else
{
std::cout<<c+".00"<<std::endl;
}
}
return 0;
}
发表于 2017-08-22 17:06:54
回复(0)
变式的大数乘法，我的天！
#include<stdio.h>
#include<math.h>
#include<string.h>
int main()
{
char m[100],n[100];
int ans[100],ls=0,t=0,i,j,ln,lm;
while(~scanf("%s%s",m,n))
{
memset(ans,0,sizeof(ans));
ls=0;
t=0;
lm=strlen(m);
ln=strlen(n);
for(i=lm-1;i>=0;i--)
{
ls=t;
for(j=ln-1;j>=0;j--)
{
ans[ls]+=(m[i]-'0')*(n[j]-'0');
ls++;
}
t++;
}
for(i=0;i<ls-1;i++)
{
ans[i+1]=ans[i+1]+ans[i]/10;
ans[i]%=10;
}
//printf("ls=%d\n",ls);
for(i=ls-1;i>=0;i--)
printf("%d",ans[i]);
if((m[lm-1]-'0')%2 && (n[ln-1]-'0')%2)
printf(".41\n");
else
printf(".00\n");
}
return 0;
}
发表于 2017-05-29 15:41:05
回复(0)
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
int main()
{
char m[100],n[100];
int ***[100],cp[100];
int i,j,k,tem;
while(cin>>m>>n)
{
for(i=0;i<100;i++) ***[i]=0;
for(i=strlen(m)-1;i>=0;i--)
{
for(j=0;j<100;j++) cp[j]=0;k=0;
for(j=strlen(n)-1;j>=0;j--)
{
cp[strlen(n)+strlen(m)-2-i-j]=((m[i]-'0')*(n[j]-'0')+k)%10;
k=((m[i]-'0')*(n[j]-'0')+k)/10;
}
cp[strlen(n)+strlen(m)-2-i-j]=k;k=0;
for(j=0;j<100;j++)
{
tem=***[j];
***[j]=(tem+cp[j]+k)%10;
k=(tem+cp[j]+k)/10;
}
}
for(i=99;i>=0;i--) if(***[i]) break;
for(;i>=0;i--) printf("%d",***[i]);
if(***[0]%2==0) cout<<".00"<<endl;
else cout<<".41"<<endl;
}
return 0;
}
发表于 2015-09-06 17:30:44
回复(0)
问题信息
难度：
16条回答
29收藏
10632浏览
通过挑战的用户
-
2023-03-14 19:20:16
-
2023-02-24 12:36:40
-
2023-02-20 17:57:17 -
2022-10-06 09:55:31
-
2022-07-04 15:10:57
相关试题
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
while True: try: m, n = raw_input().split(' ') m = int(m) n = int(n) except: break if m%2 == 0 or n%2 == 0: print str(m*n)+'.00' else: print str(m*n)+'.41'