Orange Boy Can You Solve It Out? Ep.19

比以往更加黑暗的思考题
广西省人大音乐

Idolatrize World

Haniyasushin Keiki loves crafting. She has n kinds of items. The i-th kind of item has name name_i. She also has m recipes. The i-th recipe needs len_i of different kinds of different items as input. The j-th item is ${input_i}jand needs{x_i}_jof them. Then the recipe will produceoutput_iof numbery_i.
Note that the recipe is not bidirectional.
Your task is to give each kind of item a value
v_iSo that for each recipe i,\sum
{j=1}^{len_i}{x_i}j\times v{{input_i}j}=y_i\times v{output_i}$ holds or report it's impossible.

Example

Recipes:
1 log -> 4 plank
2 plank -> 4 stick
3 plank + 2 stick -> 1 pickaxe
Output:
log=8
plank=2
stick=1
pickaxe=8

Example 2

Recipes:
1 log -> 4 plank
4 plank -> 4 log
Output:
Impossible

Constriants

Subtask 1(49%): len_i=y_i=1 always holds
Subtask 2(49%): ${x_i}j=1always holds
Subtask 3(1%):
n,m\leq10For all data:\sum
{j=1}^{len_i}{x_i}_j\leq9,y_i\leq9holds for each i,n\leq10^5,m\leq10^5$

Solution By MonkeyKing

This problem can be solved by solving the equation for v. Then use linear algebra.
And set all v_i to 0 also works.
keiki
广西省人大代表就是她!

版权声明:
作者:XGN
链接:https://blog.hellholestudios.top/archives/254
来源:Hell Hole Studios Blog
文章版权归作者所有,未经允许请勿转载。

THE END
分享
二维码
< <上一篇
下一篇>>