Problem F
Equating Equations
Input:standard input
Output:standard output
Time Limit:6seconds
Memory Limit:32 MB
Read equations with up to16terms and+and–operators (not unary) and reorder the terms (but not the operators) so that the equations hold. For example
1 + 2 = 4 - 5 + 6
is not a correct equation but the terms can be rearranged thus so it is:
6 + 2 = 4 - 1 + 5
Input
Standard input consists of several pseudo-equations, one per line. Each pseudo-equation has up to16integer terms and each term is less than100. Adjacent terms are separated by one operator, and spaces always appear surrounding
the terms. There is exactly one = operator in the equation
Output
Your output will consist of one line per input line, with the same operators and the same terms. The order of the operators must be preserved, but the terms can be reordered so the equation holds. Any ordering such that the equation holds is correct. If
there is more than one ordering any one of the orderings will do. If no ordering exists, a line containing
no solution
should be printed. One space should appear on either side of each operator and there should be no other spaces.
Sample Input
1 + 2 = 4 - 5 + 6
1 + 5 = 6 + 7
Sample Output
6 + 2 = 4 - 1 + 5
no solution
(The Decider Contest, Source: Waterloo ACM Programming Contest)
题意:给一个式子,符号位置不能变,数字位置可以变,求转换成正确等式。
思路:由于只有加减,所以左边减号相当于右边加号,右边加号相当于左边减号,如此一来左右两边相等,为sum/ 2,然后去背包求sum / 2的组成方法,然后按加减输出即可。
代码:
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
const int N = 20;
int num[N], numn, opern, Min, sum, jian, jia, jianz, jiaz, dp[N][N * 100], path[N][N * 100][N], pathn[N][N * 100], path2[N], pathn2, vis[105];;
char oper[N], c, str[105];
void init() {
int Num = 0, flag = 0;
numn = opern = Min = sum = jian = jia = jianz = jiaz = 0;
for (int i = 0; i <= strlen(str); i ++) {
if (str[i] == '+' || str[i] == '=' || str[i] == '-') {
if (str[i] == '+') {
jiaz ++;
jia ++;
}
if (str[i] == '-') {
jian ++;
jianz ++;
}
if (str[i] == '=') {
jia = 0;
jian = 0;
}
oper[opern++] = str[i];
}
else if (str[i] >= '0' && str[i] <= '9') {
Num = Num * 10 + (str[i] - '0');
flag = 0;
}
else {
if (flag == 0) {
num[numn++] = Num;
sum += Num;
Num = 0;
flag = 1;
}
}
}
Min = jiaz - jia + jian + 1;
}
void DP() {
memset(dp, 0, sizeof(dp));
memset(pathn, 0, sizeof(pathn));
dp[0][0] = 1;
for (int k = 0; k < numn; k ++) {
for (int i = Min; i >= 1; i --) {
for (int j = sum; j >= num[k]; j --) {
if (dp[i - 1][j - num[k]] == 1) {
dp[i][j] = 1;
for (int l = 0; l < i - 1; l ++)
path[i][j][l] = path[i - 1][j - num[k]][l];
path[i][j][i - 1] = num[k]; pathn[i][j] = i;
}
}
}
}
}
void print() {
pathn2 = 0;
memset(vis, 0, sizeof(vis));
for (int i = 0; i < numn; i ++)
vis[num[i]] ++;
for (int i = 0; i < pathn[Min][sum]; i ++) {
vis[path[Min][sum][i]] --;
}
for (int i = 0; i < numn; i ++) {
if (vis[num[i]]) {
path2[pathn2++] = num[i];
vis[num[i]] --;
}
}
printf("%d", path[Min][sum][0]);
int flag = 0; int s1 = 1, s2 = 0;
for (int i = 0; i < opern; i ++) {
char c = oper[i];
if (flag == 0) {
if (c == '+')
printf(" %c %d", c, path[Min][sum][s1++]);
if (c == '-')
printf(" %c %d", c, path2[s2++]);
if (c == '=') {
flag = 1;
printf(" %c %d", c, path2[s2++]);
}
}
else {
if (c == '+')
printf(" %c %d", c, path2[s2++]);
if (c == '-')
printf(" %c %d", c, path[Min][sum][s1++]);
}
}
printf("\n");
}
int main() {
while (gets(str) != NULL) {
init();
if (sum % 2) printf("no solution\n");
else {
sum /= 2;
DP();
if (dp[Min][sum])
print();
else printf("no solution\n");
}
}
return 0;
}
分享到:
相关推荐
Equating geometrical area to probability Continuous data types The heart of inferential statistics: Central limit theorem Central limit theorem Skewness and kurtosis Skewness Kurtosis Combinations ...
Adams, C, & Fay, J. (1981). No more secrets: Protecting your child from sexual assault. San Luis Obispo, CA: Impact Publisher, 90 pp., ... 39), Darwin (“equating anger with aggression,” p. 37), a
Adams, C, & Fay, J. (1981). No more secrets: Protecting your child from sexual assault. San Luis Obispo, CA: Impact Publisher, 90 pp., ... 39), Darwin (“equating anger with aggression,” p. 37), a
Driver, E., & Droisen, A. (Eds.). (1989). Child sexual abuse: A feminist reader. New York: New York University Press, 202 pp., [dollar... 39), Darwin (“equating anger with aggression,” p. 37), and othe
Matlab领域上传的视频均有对应的完整代码,皆可运行,亲测可用,适合小白; 1、代码压缩包内容 主函数:main.m; 调用函数:其他m文件;无需运行 运行结果效果图; 2、代码运行版本 Matlab 2019b;若运行有误,根据提示修改;若不会,私信博主; 3、运行操作步骤 步骤一:将所有文件放到Matlab的当前文件夹中; 步骤二:双击打开main.m文件; 步骤三:点击运行,等程序运行完得到结果; 4、仿真咨询 如需其他服务,可私信博主或扫描视频QQ名片; 4.1 博客或资源的完整代码提供 4.2 期刊或参考文献复现 4.3 Matlab程序定制 4.4 科研合作
Node.js,简称Node,是一个开源且跨平台的JavaScript运行时环境,它允许在浏览器外运行JavaScript代码。Node.js于2009年由Ryan Dahl创立,旨在创建高性能的Web服务器和网络应用程序。它基于Google Chrome的V8 JavaScript引擎,可以在Windows、Linux、Unix、Mac OS X等操作系统上运行。 Node.js的特点之一是事件驱动和非阻塞I/O模型,这使得它非常适合处理大量并发连接,从而在构建实时应用程序如在线游戏、聊天应用以及实时通讯服务时表现卓越。此外,Node.js使用了模块化的架构,通过npm(Node package manager,Node包管理器),社区成员可以共享和复用代码,极大地促进了Node.js生态系统的发展和扩张。 Node.js不仅用于服务器端开发。随着技术的发展,它也被用于构建工具链、开发桌面应用程序、物联网设备等。Node.js能够处理文件系统、操作数据库、处理网络请求等,因此,开发者可以用JavaScript编写全栈应用程序,这一点大大提高了开发效率和便捷性。 在实践中,许多大型企业和组织已经采用Node.js作为其Web应用程序的开发平台,如Netflix、PayPal和Walmart等。它们利用Node.js提高了应用性能,简化了开发流程,并且能更快地响应市场需求。
Matlab领域上传的视频均有对应的完整代码,皆可运行,亲测可用,适合小白; 1、代码压缩包内容 主函数:main.m; 调用函数:其他m文件;无需运行 运行结果效果图; 2、代码运行版本 Matlab 2019b;若运行有误,根据提示修改;若不会,私信博主; 3、运行操作步骤 步骤一:将所有文件放到Matlab的当前文件夹中; 步骤二:双击打开main.m文件; 步骤三:点击运行,等程序运行完得到结果; 4、仿真咨询 如需其他服务,可私信博主或扫描视频QQ名片; 4.1 博客或资源的完整代码提供 4.2 期刊或参考文献复现 4.3 Matlab程序定制 4.4 科研合作
Matlab领域上传的视频均有对应的完整代码,皆可运行,亲测可用,适合小白; 1、代码压缩包内容 主函数:main.m; 调用函数:其他m文件;无需运行 运行结果效果图; 2、代码运行版本 Matlab 2019b;若运行有误,根据提示修改;若不会,私信博主; 3、运行操作步骤 步骤一:将所有文件放到Matlab的当前文件夹中; 步骤二:双击打开main.m文件; 步骤三:点击运行,等程序运行完得到结果; 4、仿真咨询 如需其他服务,可私信博主或扫描视频QQ名片; 4.1 博客或资源的完整代码提供 4.2 期刊或参考文献复现 4.3 Matlab程序定制 4.4 科研合作
金融支付:浅析如何用定期资产设计活期产品.docx
Excel模板个人简历文艺清新单页06.docx
Matlab领域上传的视频均有对应的完整代码,皆可运行,亲测可用,适合小白; 1、代码压缩包内容 主函数:main.m; 调用函数:其他m文件;无需运行 运行结果效果图; 2、代码运行版本 Matlab 2019b;若运行有误,根据提示修改;若不会,私信博主; 3、运行操作步骤 步骤一:将所有文件放到Matlab的当前文件夹中; 步骤二:双击打开main.m文件; 步骤三:点击运行,等程序运行完得到结果; 4、仿真咨询 如需其他服务,可私信博主或扫描视频QQ名片; 4.1 博客或资源的完整代码提供 4.2 期刊或参考文献复现 4.3 Matlab程序定制 4.4 科研合作
吹瓶转线清线(清场)记录表.xls
支持win10,win11(21H2及以前版本)系统
Modbus Slave version 9.3.2 Build 2156, modbus 协议从机,非常好用,包括32位与64位
Excel模板个人简历稳重大气单页03.docx
11记录控制程序.doc
Matlab领域上传的视频均有对应的完整代码,皆可运行,亲测可用,适合小白; 1、代码压缩包内容 主函数:main.m; 调用函数:其他m文件;无需运行 运行结果效果图; 2、代码运行版本 Matlab 2019b;若运行有误,根据提示修改;若不会,私信博主; 3、运行操作步骤 步骤一:将所有文件放到Matlab的当前文件夹中; 步骤二:双击打开main.m文件; 步骤三:点击运行,等程序运行完得到结果; 4、仿真咨询 如需其他服务,可私信博主或扫描视频QQ名片; 4.1 博客或资源的完整代码提供 4.2 期刊或参考文献复现 4.3 Matlab程序定制 4.4 科研合作
第一步安装.zip
Node.js,简称Node,是一个开源且跨平台的JavaScript运行时环境,它允许在浏览器外运行JavaScript代码。Node.js于2009年由Ryan Dahl创立,旨在创建高性能的Web服务器和网络应用程序。它基于Google Chrome的V8 JavaScript引擎,可以在Windows、Linux、Unix、Mac OS X等操作系统上运行。 Node.js的特点之一是事件驱动和非阻塞I/O模型,这使得它非常适合处理大量并发连接,从而在构建实时应用程序如在线游戏、聊天应用以及实时通讯服务时表现卓越。此外,Node.js使用了模块化的架构,通过npm(Node package manager,Node包管理器),社区成员可以共享和复用代码,极大地促进了Node.js生态系统的发展和扩张。 Node.js不仅用于服务器端开发。随着技术的发展,它也被用于构建工具链、开发桌面应用程序、物联网设备等。Node.js能够处理文件系统、操作数据库、处理网络请求等,因此,开发者可以用JavaScript编写全栈应用程序,这一点大大提高了开发效率和便捷性。 在实践中,许多大型企业和组织已经采用Node.js作为其Web应用程序的开发平台,如Netflix、PayPal和Walmart等。它们利用Node.js提高了应用性能,简化了开发流程,并且能更快地响应市场需求。
Matlab领域上传的视频均有对应的完整代码,皆可运行,亲测可用,适合小白; 1、代码压缩包内容 主函数:main.m; 调用函数:其他m文件;无需运行 运行结果效果图; 2、代码运行版本 Matlab 2019b;若运行有误,根据提示修改;若不会,私信博主; 3、运行操作步骤 步骤一:将所有文件放到Matlab的当前文件夹中; 步骤二:双击打开main.m文件; 步骤三:点击运行,等程序运行完得到结果; 4、仿真咨询 如需其他服务,可私信博主或扫描视频QQ名片; 4.1 博客或资源的完整代码提供 4.2 期刊或参考文献复现 4.3 Matlab程序定制 4.4 科研合作