文档章节

sicily 1050 Numbers & Letters

Ciel
 Ciel
发布于 2013/01/09 20:25
字数 797
阅读 107
收藏 0

Description

In the early 80’s, a popular TV show on Dutch television was ‘Cijfers en Letters’ (Numbers and Letters). This game consisted of two game elements, in which the main goal was to outclass your opponent. Letters is a game in which you are given a number of letters with which you should form the longest Dutch word possible. Since Dutch is a very hard language to learn we will postpone implementation of this game element until after the contest. 
For the second game element ‘Numbers’ 5 different numbers are chosen, together with a target number. The aim is to use some arithmetic on ( some of) the five numbers to form the target number. Each number can be used only once. It might not be possible to form the target number given the input numbers, in that case the largest number smaller than the target number that can be calculated should be given. The only mathematical operations allowed are: +, -, *, /.  All intermediate results should be integers, so division is not always allowed (e.g. (2*2)/4 is OK, but 2*(2/4) is not). 
Examples: 
- If the 5 numbers are 1, 2, 3, 7 and 100 and the target number is 573, the target number can be reached as follows: (((100-1)*2)-7)*3. -If the 5 numbers are 3, 26, 78, 12 and 17, and the target number is 30, the target number can be reached as follows: (78*3)-(12*17). 
- If the 5 numbers are 67, 69, 58, 22, 2, and the target number is 929, the target number cannot be reached, but the largest number smaller than the target number that can be reached is 923 = (22-(67-58))*(69+2). 
Your assignment is to write a program that calculates the best approximation from below of the target number using arithmetic on the 5 given numbers. Note that if it is not possible to reach the exact number, you should give the largest reachable number below the target number.

Input

The first line contains the number of runs, N. The next N lines consist of six numbers separated by a space. The first 5 numbers Mi, 1≤Mi≤100, are the numbers you can use to calculate the target number. The sixth number is the target number T, 0≤T≤1000.

Output

The output consists of N rows, each containing the best approximation of the target number using the 5 given numbers.

Sample Input

3
1 2 3 7 100 573
3 26 78 12 17 30
67 69 58 22 2 929

Sample Output

573
30 
923

分析:

深搜法或回溯法即可,不断地任取两个数做加减乘除得到新的数,又和剩下的数组成新的数据进行新的搜索,反复如此,观察是否有数字满足题目要求。如果满足要求则输出答案,注意除零的判断和乘法的限定。

代码:

// Problem#: 1050
// Submission#: 1878130
// The source code is licensed under Creative Commons Attribution-NonCommercial-ShareAlike 3.0 Unported License
// URI: http://creativecommons.org/licenses/by-nc-sa/3.0/
// All Copyright reserved by Informatic Lab of Sun Yat-sen University
#include <iostream>
#include <cstring>
using namespace std;

int q,m,num;
int buffer[6];
bool visit[6];

void dfs(int k ){
    for( int i=1; i<=5; i++ ){
        if( !visit[i] && buffer[i]<=num && num-buffer[i]<q){
            q = num - buffer[i];
            m = buffer[i];
        }
    }
    for( int i=1 ; i<=5 ; i++ ){
        if( !visit[i] ){
            for( int j=i+1 ; j<=5 ; j++ ){
                if( !visit[j] ){
                    int tmp = buffer[i];
                    buffer[i] = buffer[i] + buffer[j];
                    visit[j] = true;
                    dfs(k-1);
                    visit[j] = false;
                    buffer[i] = tmp;
                    buffer[i] = buffer[i] - buffer[j];
                    visit[j] = true;
                    dfs(k-1);
                    visit[j] = false;
                    buffer[i] = tmp;
                    buffer[i] = buffer[j] - buffer[i];
                    visit[j] = true;
                    dfs(k-1);
                    visit[j] = false;
                    buffer[i] = tmp;
                    buffer[i] = buffer[i] * buffer[j];
                    visit[j] = true;
                    if( k!=2 || (k==2 && tmp>=0 && tmp<=100000) ) dfs(k-1);
                    visit[j] = false;
                    buffer[i] = tmp;
                    if( buffer[j]!=0 && buffer[i]%buffer[j]==0 ){
                        buffer[i] = buffer[i] / buffer[j];
                        visit[j] = true;
                        dfs(k-1);
                        visit[j] = false;
                        buffer[i] = tmp;
                    }
                    if( buffer[i]!=0 && buffer[j]%buffer[i]==0 ){
                        buffer[i] = buffer[j]/buffer[i];
                        visit[j] = true;
                        dfs(k-1);
                        visit[j] = false;
                        buffer[i] = tmp;
                    }
                }
            }
        }
    }
}

int main(){
    int n;
    cin >> n;
    while( n-- ){
        for (int i=1; i<=5; i++)
            cin >> buffer[i];
        cin >> num;
        memset(visit,false,sizeof(visit));
        q = 1000;
        dfs(5);
        cout << m << endl;
    }
    return 0;
}

© 著作权归作者所有

上一篇: sicily 1090 Highways
下一篇: sicily 1317 Sudoku
Ciel
粉丝 3
博文 24
码字总数 18532
作品 0
程序员
私信 提问
使用ReactiveCocoa实现iOS平台响应式编程

使用ReactiveCocoa实现iOS平台响应式编程 ReactiveCocoa和响应式编程 在说ReactiveCocoa之前,先要介绍一下FRP(Functional Reactive Programming,响应式编程),在维基百科中有这样一个例子...

陈小猫同学
2014/07/09
71
0
Unicode 7.0 有什么新特性

Unicode的前两个发布版本(6.2和6.3)非常让人失望,因为加入到标准中的新字符数非常之少(6.2中有1个而6.3中有5个),所以对于那些认为Unicode中的110000个字符还不是太够的人来说,Unicode 7.0...

oschina
2013/10/28
5.4K
6
Oracle 11g R2 ADG 搭建

--============Oracle ADG搭建============== --==========准备阶段========= 1.检查primary为archivelog模式。 select log_mode from v$database; 如果为noarchivelog模式,切换到archivelo......

UltraSQL
2018/07/23
0
0
uva 755 - 487--3279

题目 Businesses like to have memorable telephone numbers. One way to make a telephone number memorable is to have it spell a memorable word or phrase. For example, you can call ......

面码
2014/08/21
101
0
响应式编程框架ReactiveCocoa学习——基本操作符

我在上一篇博客中《响应式编程框架ReactiveCocoa介绍与入门》简单介绍了ReactiveCocoa的介绍和简单使用,主要是翻译了官方文档中的README部分,其实个人认为技术最好的学习方式就是去看官方文...

CHENYUFENG1991
2016/05/22
0
0

没有更多内容

加载失败,请刷新页面

加载更多

【2019年8月版本】OCP 071认证考试最新版本的考试原题-第5题

choose the best answer The CUSTOMERS table has a CUST_LAST_NAME column of data type VARCHAR2. The table has two rows whose COST_LAST_MANE values are Anderson and Ausson. Which q......

oschina_5359
31分钟前
3
0
电脑怎样制作流程图?分享绘制流程图方法

流程图的绘制可以用很多方法来实现,小编经常使用电脑对流程图进行绘制,即简单又便利,相信很多朋友都因为不知道怎样绘制流程图而选择了放弃,今天这篇文章希望可以让大家重拾绘制流程图的信...

干货趣分享
33分钟前
3
0
Elasticsearch 7.x 之文档、索引和 REST API 【基础入门篇】

前几天写过一篇《Elasticsearch 7.x 最详细安装及配置》,今天继续最新版基础入门内容。这一篇简单总结了 Elasticsearch 7.x 之文档、索引和 REST API。 什么是文档 文档Unique ID 文档元数据...

泥瓦匠BYSocket
36分钟前
3
0
TL665x-EasyEVM开发板处理器、flash、RAM

TL665x-EasyEVM是广州创龙基于SOM-TL665x核心板研发的一款TI C66x多核定点/浮点高性能DSP开发板,采用核心板+底板方式,底板尺寸为200mm*106.65mm,采用4*50pin和1*80pin B2B工业级连接器,稳...

Tronlong创龙
41分钟前
3
0
DevExpress Report-XRTable绑定数据

将从跳转前的页面(A)中获取传入的数据(dtOrd、BatchID、ModelID),绑定到Report报表对应的控件 ,代码如下: this.xrtBatchID.Text = sBatchID; this.xrtModel.Text ...

_Somuns
42分钟前
2
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部