codeforces B. Simple Molecules 解题报告

时间:2024-08-05 14:04:26

题目链接:http://codeforces.com/problemset/problem/344/B

题目意思:这句话是解题的关键: The number of bonds of an atom in the molecule must be equal to its valence number。 给定三个原子的化学价,规定化学价数等于该原子与另外两个原子所连接的原子键之和。

又一次把简单问题复杂化了.....(以下注释部分读者可以忽略)

/*

一开始三重循环枚举,绝对超时(10^6 * 10^6 * 10^6),不敢提交!!后来甚至想到这三个原子构成的原子键与总的化学价数成两倍关系(貌似没什么用,也好像不太正确,最后觉得无法实施,没深究下去了)......昨天上课再想,想到把这三个数从小到大排序,然后枚举最小和次小的原子的原子键,这样枚举出的值最大也不会超过最小的那个原子的价数,知道其中两个原子的原子键后,其余两个原子键自然就能计算出来。(例如8  3 11,3和8连接的原子键最大只可能是3)这样做,虽然在一般情况下(不考虑极端的10^6),枚举的范围小了,然而这三个原子的输入顺序在排序的过程中被改变了,用结构体保存原来输入的序号?越来越不可行了......

*/

今天硬着头皮,做好TLE的心理准备,不排序直接枚举(1~10^6)输入的前两个数的原子键数,一旦发现直接输出。其实三个原子键构成这样一个关系:假设输入的是a,b,c,枚举a,b之间的原子键数i(0<= i <= 10^6 )。想到b、c原子键数符合:b - i ;a、c之间的原子键符合:a - i。最后如果符合 (a -  i ) + (b - i ) = c,即找出一组解。

 #include <iostream>
#include <stdio.h>
#include <stdlib.h>
using namespace std; const int maxn = 1e6 + ; int main()
{
int a, b, c, i;
while (scanf("%d%d%d", &a, &b, &c) != EOF)
{
int flag = ;
for (i = ; i <= maxn; i++)
{
if (a + b - * i == c && b-i >= && a-i >= ) // 一定要判断 b-i 和 a-i 的取值,负数的需要排序
{
flag = ; // 找出一组解,直接跳出循环
printf("%d %d %d\n", i, b-i, a-i);
break;
}
}
if (!flag)
printf("Impossible\n");
}
return ;
}