南阳OJ-34-韩信点兵

[TOC]

南阳OJ-No.34

时间限制3000ms,内存限制65535KB,**难度1**

描述

相传韩信才智过人,从不直接清点自己军队的人数,只要让士兵先后以三人一排、五人一排、七人一排地变换队形,而他每次只掠一眼队伍的排尾就知道总人数了。输入3个非负整数a,b,c ,表示每种队形排尾的人数(a<3,b<5,c<7),输出总人数的最小值(或报告无解)。已知总人数不小于10,不超过100 。

输入

输入3个非负整数a,b,c ,表示每种队形排尾的人数(a<3,b<5,c<7)。例如,输入:2 4 5

输出

输出总人数的最小值(或报告无解,即输出No answer)。实例,输出:89

样例输入

2 1 6

样例输出

41


背景小故事

韩信点兵的成语来源淮安民间传说:刘邦曾经问他:你觉得我可以带兵多少?韩信:最多十万。刘邦不解的问:那你呢?韩信自豪地说:越多越好,多多益善嘛!刘邦半开玩笑半认真的说:那我不是打不过你?韩信说:不,主公是驾驭将军的人才,不是驾驭士兵的,而将士们是专门训练士兵的。
淮安民间传说着一则故事——“韩信点兵”,其次有成语“韩信点兵,多多益善”。韩信带1500名兵士打仗,战死四五百人,站3人一排,多出2人;站5人一排,多出4人;站7人一排,多出6人。韩信马上说出人数:1049。


思路

思路一:

最终的所求数num一定是被3整除后余x,被5整除后余y,被7整除后余z,且10<=num<=100。所以便利条件寻找即可。

思路二:

条件归并:找到X,Y,Z三个数组,分别存放除以3余x的数,除以5余x的数,除以3余y的数。
定义新方法,输入两个数组,返回两数组中第一个相同的数。
先对X,Y进行方法运算得到m,构建数组W除以m余(35=15)
对W,Z进行方法运算得到n,则最终结果=n+x
y*z。

凡是用3个一数剩下的余数,将它用70去乘(因为70是5与7的倍数,而又是以3去除余1的数);5个一数剩下的余数,将它用21去乘(因为21是3与7的倍数,又是以5去除余1的数);7个一数剩下的余数,将它用15去乘(因为15是3与5的倍数,又是以7去除余1的数),将这些数加起来,若超过105,就减掉105,如果剩下来的数目还是比105大,就再减去105,直到得数比105小为止。


JAVA

思路一

时间20,内存61

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
import java.util.Scanner;

public class Main {
public static Scanner cin = new Scanner(System.in);
public static int x, y, z, num;

public static void main(String[] args) throws Exception {
x = cin.nextInt();
y = cin.nextInt();
z = cin.nextInt();

for (int i=10; i<=100; i++) {
if ((i-x)%3==0) {
if ((i-y)%5==0) {
if ((i-z)%7==0) {
System.out.println(i);
break;
}
}
}
num = i;
}

if(num == 100) {
System.out.println("No answer");
}
}
}

C++

思路一

时间0,内存240

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include <iostream>
using namespace std;

int main()
{
int x, y, z, num;

cin >> x >> y >> z;

for (int i=10; i<=100; i++) {
if ((i-x)%3==0) {
if ((i-y)%5==0) {
if ((i-z)%7==0) {
cout << i;
break;
}
}
}
num = i;
}

if(num == 100) {
cout << "No answer";
}
}

思路二

时间4,内存240

1
2
3
4
5
6
7
8
9
10
11
12
13
#include<iostream>
using namespace std;

int main()
{
int a,b,c;
cin >> a >> b >> c;
int n=(a*70+b*21+c*15)%105;
if(n>100||n<10)
cout << "No answer" << endl;
else
cout << n << endl;
}
文章作者: HibisciDai
文章链接: http://hibiscidai.com/2017/02/16/2017-02-16-南阳OJ-No.34-韩信点兵-1/
版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 HibisciDai