A20938.正方形

提高+/省选-

通过率:0%

时间限制:1.00s

内存限制:128MB

题目描述

nn 个大小不一的正方形,现将它们依次以 4545 度斜放入第一象限,每个正方形都要与 xx 轴有一个交点,且不能与之前放入的正方形重叠。在此前提下,正方形与 xx 轴交点的坐标应尽可能小。问这样放置后,从上往下看,至少能部分被看见的正方形有哪些?

输入格式

每个测试点包含多组测试数据。每个测试数据的第一行是一个整数 nn,第二行是 nn 个正整数,表示每个正方形的边长。输入以一行单独的 00 结束。

输出格式

对于每个测试数据输出一行,增序输出至少可看到部分的正方形的编号,用空格隔开。

输入输出样例

  • 输入#1

    4 
    3 5 1 4 
    3 
    2 1 2 
    0 

    输出#1

    1 2 4 
    1 3

说明/提示

数据范围及约定

  • 对于 50%50\% 的数据,n10n \le 10
  • 对于 100%100\% 的数据,n50n \le 50 正方形的大小不超过 3030
首页