Can I have a sample input that would pass test 7? thanks

#include <cstdio>
void main (){
    int res= 0, a1, a2;
    double p, q;
    scanf ("%lf%lf", &p, &q);
    do{
        res ++,a1= (int)(p* (double)res)/100, a2= (int)(q* (double)res-(1e-7))/100;
    }while (a1== a2);
    printf ("%d\n", res);
}

..

Edited by author 13.05.2010 13:55

something wrong with the 1st test or tests
Following prog give me ans for all n (1..100)
but at first test it gave me TL

import java.math.BigInteger;
import java.util.Scanner;

public class Timus1407 {
    public static void main(String[] args){
        Scanner input = new Scanner(System.in);
        int n = input.nextInt();
        String s = "2";
        BigInteger two = new BigInteger("2");
        for (int i = 2; i <= n; i++) {
            BigInteger bigInteger = two.pow(i);
            String tmp = "1" + s;
            if(new BigInteger(tmp).mod(bigInteger) == BigInteger.ZERO){
                s = tmp;
            }
            else{
                s = "2" + s;
                if(new BigInteger(s).mod(bigInteger) != BigInteger.ZERO){
                    for(;;){}
                }
            }
        }
        System.out.print(s);
    }
}

My AC solution for test

3
1 3 1

answers

2 1 2 2 3

while better answer is

2 1 2 3 2

Hi ,....
A Greedy Algorithm Gets AC but it is Wrong ...
for example for this Test Case The AC code says No
5 2
1 2
1 3
2 3
4 2
4 2

фейреверк ->  фейерверк

My AC program gives answer "1" to the test:

GTACcAaa
1
1 8

What is test 10?

#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;

const int INF = -(1<<30);

int dp[2][260][4][4],cur,pre;
unsigned int full_path[17][260][4][4];    int full_len[17][260][4][4];

bool can_down[17][4][4];

unsigned int path[17][4][4]; // record the path on each floor use bitset;
int best[17][4][4]; //best[L][i][j] record the largest weighted of the paths from (i,j) whitch has a length of L;
unsigned int sta;    int len, wt;    //length , state and weight;
bool used[4][4];

int N;
int w[17][4][4];
int des_r,des_c;
int dy[4] = {-1, 1, 0, 0}, dx[4] = {0, 0, -1, 1};
char opp_dir[4] = {'S', 'N', 'E', 'W'};
int opp_dy[4] = {1, -1, 0 ,0},    opp_dx[4] = {0, 0, 1, -1};
/*
 *      N(0)
 * W(2)      E(3)
 *      S(1)
 * because L less than 15;  so it can be recorded as a 4 bits string which does'n exceed 4^15;
 */

inline bool isok(int r,int c){
    return r >= 0 && r < 4 && c >= 0 && c < 4;
}
void search(int n, int r, int c){

    wt += w[n][r][c];   used[r][c] = true;
    if(best[len][r][c] < wt ){
        best[len][r][c] = wt;
        path[len][r][c] = sta;
    }
    int i;

    //printf("pre_state=%u\n",sta);
    //printf("len = %d\n",len);

    for(i = 0; i < 4; i++){
        int ty = dy[i] + r, tx = dx[i] + c;
        if(isok(ty,tx) && (!used[ty][tx])){
            sta = (sta<<2) + (unsigned int)i;   len ++;
            search(n,ty,tx);
            sta >>= 2;   len --;
        }
    }

    //printf("after_state = %u\n",sta);
    wt -= w[n][r][c];   used[r][c] = false;

}

void print_path(unsigned int p, int len){
    if(len == 0){
        return;
    }
    printf("%c",opp_dir[p%4]);
    print_path(p>>2,len-1);
    des_r += opp_dy[p%4];    des_c += opp_dx[p%4];
}

int main()
{
    freopen("in.txt","r",stdin);
    while(scanf("%d",&N) != EOF){
        int t,i,j,k;
        for(i = N - 1; i >= 0; i--){
            for(j = 0; j < 4; j++){
                for(k = 0; k < 4; k++){
                    scanf("%d",&w[i][j][k]);
                }
            }

            for(j = 0; j < 4; j++){
                for(k = 0; k < 4; k++){
                    scanf("%d",&t);
                    can_down[i][j][k] = t ? true : false;
                }
            }
        }
        scanf("%d%d",&des_r,&des_c);
        des_r --;   des_c --;

        cur = 0;

        int days;
        for(days = 0; days <= 16; days++){
            if(days == 0){
                fill_n(dp[cur][days][0], 16, 0);
            }else{
                fill_n(dp[cur][days][0], 16, INF);
            }
        }

        fill_n(can_down[0][0], 16, true);
        fill_n(can_down[N][0], 16, false);
        can_down[N][des_r][des_c] = true;

        memset(used, false, sizeof(used));

        for(i = 0; i < N; i++){
            pre = cur;  cur = pre ^ 1;

            for(days = 0; days <= 16 * (i + 1); days++){
                fill_n(dp[cur][days][0], 16, INF);
            }

            for(j = 0; j < 4; j++){
                for(k = 0; k < 4; k++){


                    if(can_down[i][j][k]){
                        for(len = 0; len < 16; len ++){
                            fill_n(best[len][0], 16, INF);
                        }
                        len = 0; sta = 0;   wt = 0;
                        search(i, j, k);
                    }
                    int m, n, pre_days;

                    for(pre_days = i; pre_days <= i*16; pre_days++){
                        if(dp[pre][pre_days][j][k] >=0 ){

                            for(m = 0; m < 4; m++){
                                for(n = 0; n < 4; n++){
                                    if(can_down[i+1][m][n]){

                                        for(int inc_days = 0; inc_days <16; inc_days ++){
                                            days = pre_days + inc_days + 1;
                                            if( best[inc_days][m][n] >= 0 && dp[cur][days][m][n] < dp[pre][pre_days][j][k] + best[inc_days][m][n]){
                                                dp[cur][days][m][n] = dp[pre][pre_days][j][k] + best[inc_days][m][n];
                                                full_path[i][days][m][n] = path[inc_days][m][n];
                                                full_len[i][days][m][n] = inc_days;
                                            }
                                        }
                                    }
                                }
                            }
                        }
                    }
                }
            }

        }

        double res = 0;  int ndays;
        for(days = N; days <= 16*N; days ++){
            double tmp = (dp[cur][days][des_r][des_c]*1.0)/(days*1.0);

            if(tmp > res){
                res = tmp;  ndays = days;
            }
        }

        printf("%.4f\n",res);
        printf("%d\n",ndays-1);

        int flo = N-1;
        if(ndays == 1){
            continue;
        }

        while(true){
            len = full_len[flo][ndays][des_r][des_c]; unsigned int p = full_path[flo][ndays][des_r][des_c];
            //printf("des_r=%d,des_c=%d\n",des_r,des_c);
            print_path(p,len);

            ndays -= len + 1;
            if(ndays <= 1){
                printf("\n");   break;
            }

            printf("D");

            flo --;
        }
    }
    return 0;
}

And now WA#13
        Baker's dozen!

Edited by author 25.04.2006 19:43

Or could you send me your code to investigate?
kobchik83@list.ru

I do not trust that this problem can be solved during contest!
Because it demand big amount of tehnical work such
as grammar analysis, string manipulations and sorting.

What the fucking test is it? I failed on it many times, using every possible precision in calculations!

import java.util.Arrays;
import java.util.Scanner;

public class Timus1403 {

    /**
     * @param args
     */
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        int n = input.nextInt();
        Order[] order = new Order[n];
        int[] num = new int[100001];
        int[] ans = new int[100001];
        boolean[] used = new boolean[100001];
        Arrays.fill(used, false);
        for (int i = 0; i < order.length; i++) {
            int d = input.nextInt();
            int p = input.nextInt();
            order[i] = new Order(i + 1, d, p);
        }
        for (int i = 0; i < num.length; i++) {
            num[i] = i;
        }
        Arrays.sort(order);
        int count = 0;
        for (int i = 0; i < order.length; i++) {
            int j = order[i].deadline;
            if(num[j] > 0 && !used[num[j]]){
                count++;
                int x = num[j];
                ans[num[j]] = order[i].index;
                used[num[j]] = true;
                num[num[j]] = num[j] - 1;
                if(x == j){
                    continue;
                }
                num[order[i].deadline]--;

            }
        }
        System.out.println(count);
        for (int i = 0; i < used.length; i++) {
            if(used[i]){
                System.out.print(ans[i] + " ");
            }
        }


    }

}

class Order implements Comparable<Order>{
    public int index;
    public int deadline;
    public int price;

    public Order(int i, int d, int p){
        index = i;
        deadline = d;
        price = p;
    }

    @Override
    public String toString(){
        String ret = "";
        ret+= this.index + " " + this.deadline + " " + this.price;
        return ret;
    }

    public int compareTo(Order other) {
        return -(this.price - other.price);
    }

}

Edited by author 24.10.2010 08:20

   var
   s : integer;
   ch : char;

begin
   s := 0;
   while not eof do
     begin
       read(ch);
       case ch of
       '1', '5' : inc(s);
       '2', '4', '6', '9' : inc(s, 2);
       '3', '7' : inc(s, 3);
       '8' : inc(s, 4);
       end;
     end;
   writeLn(s);
end.
this ic gave me AC!!

   var
   s : integer;
   ch : char;
   a : array ['0'..'9'] of byte = (0, 1, 2, 3, 2, 1, 2, 3, 4, 2);

begin
   s := 0;
   while not eof do
     begin
       read(ch);
       s := s + a[ch];
     end;
   writeLn(s);
end.
and this WA#1!!!!
i don't know why, who can explain it to me!!
thanks!!

i think it will work out fine.
But just got WA1.
Can you help me ?
thx!






#include <cstdlib>
#include <iostream>

using namespace std;


int shu(int);


int main(int argc, char *argv[])
{
    int a[10],b=0,max=0,d=0;
    while (cin>>a[b])
    {if (a[b]==0) break;
     b++;}
     while (1)
     {if (a[d]==0) break;
      while (a[d]>=0)
      {if (shu(a[d])>max) max=shu(a[d]);
       a[d]--;}
       cout<<max<<endl;
       d++;}

    system("PAUSE");
    return EXIT_SUCCESS;
}

  int shu(int n)
  {int c;
   if (n==0) c=0;
   else if (n==1) c=1;
   else if (n%2==0) c=shu(n/2);
   else c=shu((n-1)/2)+shu((n-1)/2+1);}

Does the algorithm must have the minimal numbers of steps?

At first I got wa on test 12 19 ...
After this test I got ac
6
1 10
1 10
1 6
1 10
1 10
6 3
2
3 1
3 2

Edited by author 20.10.2010 14:21