Problem A. Part Elf
Small input 8 points |
Solve A-small
|
Large input 12 points |
Solve A-large
|
Problem
Vida says she's part Elf: that at least one of her ancestors was an Elf. But she doesn't know if it was a parent (1 generation ago), a grandparent (2 generations ago), or someone from even more generations ago. Help her out!
Being part Elf works the way you probably expect. People who are Elves, Humans and part-Elves are all created in the same way: two parents get together and have a baby. If one parent is A/B
Elf, and the other parent is C/D
Elf, then their baby will be(A/B + C/D) / 2
Elf. For example, if someone who is 0/1
Elf and someone who is 1/2
Elf have a baby, that baby will be 1/4
Elf.
Vida is certain about one thing: 40 generations ago, she had 240
different ancestors, and each one of them was 1/1
Elf or 0/1
Elf.
Vida says she's P/Q Elf. Tell her what is the minimum number of generations ago that there could have been a 1/1
Elf in her family. If it is not possible for her to be P/Q Elf, tell her that she must be wrong!
Input
The first line of the input gives the number of test cases, T. T lines follow. Each contains a fraction of the form P/Q, where P and Q are integers.
Output
For each test case, output one line containing "Case #x: y", where x is the test case number (starting from 1) and y is the minimum number of generations ago a 1/1 Elf in her family could have been if she is P/Q Elf. If it's impossible that Vida could be P/Q Elf, y should be the string "impossible" (without the quotes).
Limits
1 ≤ T ≤ 100.
Small dataset
1 ≤ P < Q ≤ 1000.
P and Q have no common factors. That means P/Q is a fraction in lowest terms.
Large dataset
1 ≤ P < Q ≤ 1012.
P and Q may have common factors. P/Q is not guaranteed to be a fraction in lowest terms.
Sample
Input |
Output |
5 1/2 3/4 1/4 2/23 123/31488 |
Case #1: 1 Case #2: 1 Case #3: 2 Case #4: impossible Case #5: 8 |
Note that the fifth sample case does not meet the limits for the Small input. Even if you don't solve it correctly, you might still have solved the Small input correctly.
Explanation of sample cases
In the first sample case, Vida could have a 1/1
Elf parent and a 0/1
Elf parent. That means she could have had a 1/1 Elf one generation ago, so the answer is 1.
In the second sample case, Vida could have had a 1/1
Elf parent and a 1/2
Elf parent. That means she could have had a 1/1
Elf one generation ago, so the answer is 1.
In the third sample case, Vida could have had a 0/1
Elf parent and a 1/2
Elf parent. The1/2
Elf parent could have had a 1/1
Elf parent and a 0/1
Elf parent. That means she could have had a 1/1
Elf two generations ago, so the answer is 2.
In the fourth sample case, it's impossible to be exactly 2/23
Elf if your ancestors 40 generations ago were all 0/1
Elf or 1/1
Elf.
Note
Yes, Vida has a lot of ancestors. If that is the part of the problem that seems the most unrealistic to you, please re-read the part about Elves.
时间搞错了,没来得及去做google 的2014 jam,不过没啥,因为做题的速度远跟不上。。。。,人老了,智商也不够,也就只能做个A。开始还把题目意思搞错了。。。要求的是最近的一代。我当时求得是,最少要经过多少代,才能得到P/Q,感觉我理解的更难。
——————————————————————————————————————
#include <stdio.h> #include <iostream> long long gcd(long long P,long long Q){ long long r =Q; do{ r = Q; Q = P%Q; P = r; }while(Q!=0); return r; } bool simple(long long P,long long Q,long long &op,long long &oq) { if(P>Q) return false; long long u = gcd(Q,P); op = P/u; oq = Q/u; return true; } int main(int argc ,char *argv[]) { int N=0; scanf("%d",&N); long long P,Q; long long op,oq; for(int i=0;i<N;i++){ scanf("%I64d/%I64d",&P,&Q); simple(P,Q,op,oq); long long j=1; int count =0; for(;j<oq;j<<=1){count++;} if(j != oq) { printf("Case #%d: impossible\n",i+1); continue; } j=1; int count2=0; while(j<=op) {j<<=1;} long long v = oq/j; while(v!=0){ v >>=1; count2++; } printf("Case #%d: %d\n",i+1,count2); } }
——————————————————————————————————————————
思路:
- 约简单P/Q,得到op,oq;
- 如果oq不满足2的整数次幂,失败,(ps:op一定是奇数)。否则继续
- 计算不小于op的最近2的整数次幂j, j=log[(op)] (上取整),如op=5;oq=16,实际得到的是j=8;
- 继续约简j/oq, 得到 1/x;
- 计算log(x),返回log(x)
如果改成计算,至少要经过多少代,才能得到P/Q.那么上面的需要修改下。
结果为:
代数 = op 中1的个数+ log(oq)-1;
因为,二进制op中,每产生1个1,必须要做一次加法。
记1{x}为二进制x1的个数
如果op = 5,那么1{op}=2,如果op=16;那么需要经过2+4-1=5代才能得到5/16;
1{x}
相关推荐
lede模拟器-openwrt模拟器-malta-mips-be-uClibc.part1.rar,由于文件太大,分成了两个文件上传part1和part2 linux或windows都可以运行,需要安装qemu qemu-system-mips -M malta -hda lede-malta-be-root.ext4 -...
lede模拟器-openwrt模拟器-malta-mips-be-uClibc.part1.rar,由于文件太大,分成了两个文件上传part1和part2 linux或windows都可以运行,需要安装qemu qemu-system-mips -M malta -hda lede-malta-be-root.ext4 -...
xbox360刷机专用文件,用于xbox360刷机用。把本文件和“updflash.bin”文件拷贝到U盘根目录,插入xbox360主机的USB插口里,按光驱键开机,即可“升级”或“恢复”系统。
gcc-linaro-aarch64-none-elf-4.9-2014.07_linux.tar.bz2
hex,bin,elf,axf文件格式的详细区别,解析。很有用
《ELF文件格式分析.pdf》文档,非常不错的elf格式参考文档,参考elf解析过程,能很快掌握elf文件格式
Part 1, "Object Files" describes the ELF object file format for the three main types of object files. Part 2, "Program Loading and Dynamic Linking" describes the object file information and system ...
Altera verilog 编写的.sof 文件以及NIOS 编写的.elf文件,怎么进行和平成.hex文件。再使用altera 编译器生成.JIC 文件进行固化,my.sh里面修改.ELF和.SOF文件的名称,然后通过Altera 。Nios II Command Shell 脚本...
ELF文件格式,英文版,详细介绍ELF文件格式
UNIX类操作系统中普遍采用的目标文件格式ELF(Executable and Linkable Format),目的是研究操作...本文首先介绍ELF文件格式规范,然后结合一个简单的C语言程序,分析编译、链接后生成的可重定位、可执行格式实例。
elf.tga elf.tga elf.tga elf.tga 用于Open Inventor纹理显示
No Elf file associated with target 这是vivado2016.4的bug 解决方案: 1.使用system debug 代替 GDB 2.替换xmdterm.tcl 文件: 下载本xmdterm.tcl 资源,然后到你的SDK的安装目录下替换原来的xmdterm.tcl ...
ODriveFirmware_v3.6-24V.elf
ELF中文手册: 可执行连接格式(Executable and Linking Format)最初是作为应用程序二进制接口(Application Binary Interface(ABI)的一部分被UNIX系统实验室(USL)开发和发布。工具接口标准委员会(TIS)将还在发展的ELF...
chrome_elf.dll, win10遇到文件夹下的chrome_elf.dll拒绝访问,于是找到这个dll,复制到相应路径下, 32为系统:C:\WINNT\System32 64位系统:C:\Windows\SysWOW64 继续安装,问题得到解决 上传了一个chrome_elf.dll...
ELF文件格式分析文档,北京大学信息科学技术学院操作系统实验室教学材料,滕启明编写
detail description about .ELF file format
签名下载ELF检测
elf手册,elf格式的说明手册,英文的.elf Handbook
1. 目标文件(Object file) 3 序言 3 文件格式 3 数据表示 4 ELF Header 5 ELF 鉴别(Identification) 8 节 11 特殊节 18 字符串表String Table 22 符号表Symbol Table 23 符号值Symbol Values 27 重定位Relocation 27...