Start: Oct, 02, 2021 08:00:00
专题3 广搜及优化
End: Oct, 23, 2021 12:00:00
Time elapsed:
Time remaining:

倒水 1231

Time Limit:  1 Sec    Memory Limit:   128 MB
Submission:56     AC:15     Score:100


Description

有一个很大的水缸和二个容量分别为XY的水壶,按照以下的规则倒水,问最少经几次倒水后,可得到Z升水。

规则1:水缸向水壶1倒水,将水壶1装满;

规则2:水缸向水壶2倒水,将水壶2装满;

规则3:水壶1向水缸倒水,直到水壶1空;

规则4:水壶2向水缸倒水,直到水壶2空;

规则5:水壶1向水壶2倒水,直到水壶1空了或者水壶2满了;

  规则6:水壶2向水壶1倒水,直到水壶2空了或者水壶1满了;

Input

只有一行数据,包括以空格分隔的三个数字,分别表示水壶1( <= 100) 水壶2的水量( <= 100 )以及期望得到的水量( <=100 )

Output

若经若干次倒水能得到所要求的水量,则输出最少的倒水次数;若无论如何倒水都无法得到规定的水量,则输出No Solution!

Samples

input:
4 3 1
output:
2