游客 Signup | Login
中文 | En

2294 - Cantor表

  

<span style="font-family:宋体;">现代数学的著名证明之一是</span><span>Georg Cantor</span><span style="font-family:宋体;">证明了有理数是可枚举的。他是用下面这一张表来证明这一命题的：</span> 


<table cellspacing="0" cellpadding="0" width="222" align="left" height="135">
	<tbody>
		<tr>
			<td height="135" valign="top" align="left">
				<p class="MsoNormal">
					<span>1/1<span>&nbsp; </span>1/2 <span>&nbsp;</span>1/3 <span>&nbsp;</span>1/4 <span>&nbsp;</span>1/5 </span><span style="font-family:宋体;">…</span> 
				</p>
				<p class="MsoNormal">
					<span>2/1 <span>&nbsp;</span>2/2 <span>&nbsp;</span>2/3 <span>&nbsp;</span>2/4 <span>&nbsp;</span></span><span style="font-family:宋体;">…</span> 
				</p>
				<p class="MsoNormal">
					<span>3/1 <span>&nbsp;</span>3/2 <span>&nbsp;</span>3/3 <span>&nbsp;</span></span><span style="font-family:宋体;">…</span> 
				</p>
				<p class="MsoNormal">
					<span>4/1 <span>&nbsp;</span>4/2 <span>&nbsp;</span></span><span style="font-family:宋体;">…</span> 
				</p>
				<p class="MsoNormal">
					<span>5/1 <span>&nbsp;</span></span><span style="font-family:宋体;">…</span> 
				</p>
				<p class="MsoNormal">
					<span style="font-family:宋体;">…</span> 
				</p>
			</td>
		</tr>
	</tbody>
</table>


<span> 
<table cellspacing="0" cellpadding="0" width="100%">
	<tbody>
		<tr>
			<td>
				<div class="shape">
					<p class="MsoNormal">
						<span>1/1<span>&nbsp; </span>1/2 <span>&nbsp;</span>1/3 <span>&nbsp;</span>1/4 <span>&nbsp;</span>1/5 </span><span style="font-family:宋体;">…</span> 
					</p>
					<p class="MsoNormal">
						<span>2/1 <span>&nbsp;</span>2/2 <span>&nbsp;</span>2/3 <span>&nbsp;</span>2/4 <span>&nbsp;</span></span><span style="font-family:宋体;">…</span> 
					</p>
					<p class="MsoNormal">
						<span>3/1 <span>&nbsp;</span>3/2 <span>&nbsp;</span>3/3 <span>&nbsp;</span></span><span style="font-family:宋体;">…</span> 
					</p>
					<p class="MsoNormal">
						<span>4/1 <span>&nbsp;</span>4/2 <span>&nbsp;</span></span><span style="font-family:宋体;">…</span> 
					</p>
					<p class="MsoNormal">
						<span>5/1 <span>&nbsp;</span></span><span style="font-family:宋体;">…</span> 
					</p>
					<p class="MsoNormal">
						<span style="font-family:宋体;">…</span> 
					</p>
					<p class="MsoNormal">
						<span></span>
					</p>
				</div>
			</td>
		</tr>
	</tbody>
</table>


<span></span>


<span></span>


<span></span>


<span></span>


<span></span>


<span></span>


<span></span>



<span><span>&nbsp;&nbsp;&nbsp; </span></span><span style="font-family:宋体;">我们以</span><span>Z</span><span style="font-family:宋体;">字形给上表的每一项编号。第一项是</span><span>1/1</span><span style="font-family:宋体;">，然后是</span><span>1/2</span><span style="font-family:宋体;">，</span><span>2/1</span><span style="font-family:宋体;">，</span><span>3/1</span><span style="font-family:宋体;">，</span><span>2/2</span><span style="font-family:宋体;">，…</span> 


<span><span>&nbsp;&nbsp;&nbsp; </span></span><span style="font-family:宋体;">输入：整数</span><span>N</span><span style="font-family:宋体;">（</span><span>1</span><span style="font-family:宋体;">≤</span><span>N</span><span style="font-family:宋体;">≤</span><span>10000000</span><span style="font-family:宋体;">）</span><span><span>&nbsp;&nbsp;&nbsp;&nbsp; </span></span><span style="font-family:宋体;">输出：表中的第</span><span>N</span><span style="font-family:宋体;">项</span> 


<span><span>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; </span></span><span style="font-family:宋体;">样例：</span><span><span>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; </span>INPUT<span>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; </span>OUTPUT</span> 


<span><span>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; </span></span><span style="font-family:宋体;">　　　　　　　</span><span>N=7<span>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; </span>1/4</span>

Input

Output

Examples

Input

7

Output

1/4

Solution C++

#include <cstdlib>
#include <cstdio>
using namespace std;
int cs(int);
int main()
{
	int n;
	scanf("%d",&n);
	int k;
	bool even=false;
	int sum=0;
	for(int i=1;i<=n;i++)
	{
		sum+=i;
		if(sum>=n)
		{
			k=i;
			if(i%2==0)
			{
				even=true;
				n=sum-n;
			}
			else
			{
				n=n-cs(i-1)-1;
			}
			break;
		}
	}
	int a,b;
	if(even)
	{
		a=k-n;
		b=k+1-a;
	}
	else
	{
		a=k-n;
		b=k+1-a;
	}
	printf("%d/%d",a,b);
	//system("pause");
	return 0;
}
int cs(int a)
{
	if(a==1)
	    return 1;
	else
	    return a+cs(a-1);
}
Time Limit 1 second
Memory Limit 128 MB
Discuss Stats
上一题 下一题